AT3600
不难，但是偏模拟。
#include<bits/stdc++.h>
#define reg register int
#define INF (1<<30)
#define t() cout<<"iakioi\n";
using namespace std;
int read(){
int res=0,fs=1; char c=getchar();
while(!(c>='0' && c<='9')){ if(c=='-')fs=-1; c=getchar(); }
while(c>='0' && c<='9')res=res*10+c-'0',c=getchar();
return res*fs;
}
void print(int x){
if(x<0) { putchar('-'); x=-x;}
if(x>9) print(x/10);
putchar(x%10+'0');
}
int n,cnt,m,a[5010],tmp;
string s,t;
string mx="zzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzz";
bool iakioi(int st,int ed){
for(int i=st,j=0;i<ed,j<t.size();i++,j++){
if(s[i]!='?'&&s[i]!=t[j]) return false;
}
return true;
}
int main() {
ios::sync_with_stdio(false);
cin>>s>>t;
if(s.size()<t.size()){
cout<<"UNRESTORABLE\n";
return 0;
}
for(int i=0;i<s.size();i++){
if(iakioi(i,i+t.size()-1)){
string ans=" ";
// t();
// cout<<i<<endl;
int st=i,ed=i+t.size()-1;
for(int w=st,j=0;w<=ed,j<t.size();w++,j++){
// if(s[i]!='?'&&s[i]!=t[i]) return false;
ans[w]=t[j];
}
// cout<<ans<<endl;
for(int j=0;j<st;j++) if(s[j]=='?') ans[j]='a';
else ans[j]=s[j];
for(int j=ed+1;j<s.size();j++) if(s[j]=='?') ans[j]='a';
else ans[j]=s[j];
while(ans[ans.size()-1]==' ') ans.erase(ans.size()-1,1);
mx=min(mx,ans);
}
}
if(mx=="zzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzz") cout<<"UNRESTORABLE\n";
else cout<<mx<<endl;
return 0;
}
AT3529 [ABC073B] Theater
巨水。
#include<bits/stdc++.h>
#define reg register int
#define INF (1<<30)
using namespace std;
int read(){
int res=0,fs=1; char c=getchar();
while(!(c>='0' && c<='9')){ if(c=='-')fs=-1; c=getchar(); }
while(c>='0' && c<='9')res=res*10+c-'0',c=getchar();
return res*fs;
}
void print(int x){
if(x<0) { putchar('-'); x=-x;}
if(x>9) print(x/10);
putchar(x%10+'0');
}
int x,y,n,cnt,m,a[5010],ans,tmp;
int main() {
ios::sync_with_stdio(false);
cin>>n;
for(int i=1;i<=n;i++) {
cin>>x>>y;
ans+=y-x+1;
}
cout<<ans<<endl;
return 0;
}
AT3853 [ABC085C] Otoshidama
暴力枚举三个面值的张数，注意可能等于，貌似要枚举多一点（大概到10000）
#include<bits/stdc++.h>
#define reg register int
#define INF (1<<30)
using namespace std;
int read(){
int res=0,fs=1; char c=getchar();
while(!(c>='0' && c<='9')){ if(c=='-')fs=-1; c=getchar(); }
while(c>='0' && c<='9')res=res*10+c-'0',c=getchar();
return res*fs;
}
void print(int x){
if(x<0) { putchar('-'); x=-x;}
if(x>9) print(x/10);
putchar(x%10+'0');
}
int n,cnt,m,a[5010],ans,tmp;
int main() {
ios::sync_with_stdio(false);
cin>>n>>ans;
for(int i=0;i<=10000;i++){
for(int j=0;j<=10000;j++){
int k=n-i-j;
if(i+j+k==n&&i*10000+j*5000+k*1000==ans&&k>=0){
cout<<i <<' '<<j<<' '<<k;
cout<<endl;
return 0;
}
}
}
cout<<"-1 -1 -1\n";
return 0;
}
AT2653
zz题。
#include<bits/stdc++.h>
#define reg register int
#define INF (1<<30)
using namespace std;
int read(){
int res=0,fs=1; char c=getchar();
while(!(c>='0' && c<='9')){ if(c=='-')fs=-1; c=getchar(); }
while(c>='0' && c<='9')res=res*10+c-'0',c=getchar();
return res*fs;
}
void print(int x){
if(x<0) { putchar('-'); x=-x;}
if(x>9) print(x/10);
putchar(x%10+'0');
}
int n,cnt,m,a[5010],ans,tmp;
int main() {
ios::sync_with_stdio(false);
cin>>n>>m;
for(int i=1;i<=n;i++) cin>>a[i];
sort(a+1,a+n+1);
for(int i=n;i>=n-m+1;i--) ans+=a[i];
cout<<ans<<endl;
return 0;
}
AT2018 [ABC043B] バイナリハックイージー / Unhappy Hacking (ABC Edit)
字符串模拟题，注意
如果字符串是空的，什么都不会发生。
不判断会
别问我怎么知道的
#include<bits/stdc++.h>
#define reg register int
#define INF (1<<30)
using namespace std;
int read(){
int res=0,fs=1; char c=getchar();
while(!(c>='0' && c<='9')){ if(c=='-')fs=-1; c=getchar(); }
while(c>='0' && c<='9')res=res*10+c-'0',c=getchar();
return res*fs;
}
void print(int x){
if(x<0) { putchar('-'); x=-x;}
if(x>9) print(x/10);
putchar(x%10+'0');
}
int n,cnt,m,a[5010],ans,tmp;
string s;
int main() {
ios::sync_with_stdio(false);
char c;
while(cin>>c){
if(c=='0') s+='0';
if(c=='1') s+='1';
if(c=='B'&&!s.empty()) s.erase(s.size()-1,1);
}
cout<<s<<endl;
return 0;
}
AT360 雨上がり
dp。
#include<bits/stdc++.h>
#define reg register int
#define INF (1<<30)
using namespace std;
int read(){
int res=0,fs=1; char c=getchar();
while(!(c>='0' && c<='9')){ if(c=='-')fs=-1; c=getchar(); }
while(c>='0' && c<='9')res=res*10+c-'0',c=getchar();
return res*fs;
}
void print(int x){
if(x<0) { putchar('-'); x=-x;}
if(x>9) print(x/10);
putchar(x%10+'0');
}
int n,cnt,m,a[5010],ans,tmp,f[114514];
string s;
int main() {
ios::sync_with_stdio(false);
cin>>n;
cin>>s;
f[1]=s[0]=='X',f[2]=s[1]=='X',f[3]=s[2]=='X';//如果是水池，又增加了一个路过的（
for(int i=4;i<=n;i++){
if(s[i-1]=='X') f[i]=1+min(f[i-1],min(f[i-2],f[i-3]));
else f[i]=min(f[i-1],min(f[i-2],f[i-3]));
}
cout<<f[n];
return 0;
}
AT3880 [ABC087B] Coins
baoli题。
#include<bits/stdc++.h>
#define reg register int
#define INF (1<<30)
using namespace std;
int read(){
int res=0,fs=1; char c=getchar();
while(!(c>='0' && c<='9')){ if(c=='-')fs=-1; c=getchar(); }
while(c>='0' && c<='9')res=res*10+c-'0',c=getchar();
return res*fs;
}
void print(int x){
if(x<0) { putchar('-'); x=-x;}
if(x>9) print(x/10);
putchar(x%10+'0');
}
int a,b,c,x,cnt;
int main() {
ios::sync_with_stdio(false);
cin>>a>>b>>c>>x;
for(int A=0;A<=a;A++){
for(int B=0;B<=b;B++){
for(int C=0;C<=c;C++){
int ans=A*500+B*100+C*50;
if(ans==x) cnt++;
}
}
}
cout<<cnt<<endl;
return 0;
}
AT2659 [ABC068B] Break Number
神仙做法就很艹
#include<bits/stdc++.h>
double n;
int main() {
std::cin>>n;
std::cout<<(1<<(int)(log2(n)));
}
AT1979 [AGC001A] BBQ Easy
排序题。
#include<bits/stdc++.h>
using namespace std;
int n,cnt,m,a[5010],ans,tmp;
int main() {
ios::sync_with_stdio(false);
cin>>n;
n*=2;
for(int i=1;i<=n;i++) cin>>a[i];
sort(a+1,a+n+1);
for(int i=1;i<=n;i+=2){
ans+=min(a[i],a[i+1]);
}
cout<<ans;
return 0;
}
AT4787 [ABC129C] Typical Stairs
sb dp。
/*
边界：
f[0]=1,f[1]=1;
递推式：
f[i]=(f[i-1]+f[i-2])%MOD;
特殊情况：
如果此条路被破坏，解的总数为0
解：
f[n]
*/
#include<bits/stdc++.h>
#define MOD 1000000007
using namespace std;
int n,cnt,m,a[114514],ans,tmp;
int f[1919810];
/*
a[i]的值如果为1，表示此条路被破坏，走不通
否则，可以走通
*/
int main() {
cin>>n>>m;
while(m--) cin>>tmp,a[tmp]=1;//标记，tmp这条路被破坏
if(!a[0]) f[0]=1;//注意判断第0条路是否被破坏
if(!a[1]) f[1]=1;
for(int i=2;i<=n;i++)
if(!a[i]) //!a[i]也就是a[i]==0，判断是否被破坏
f[i]=(f[i-1]+f[i-2])%MOD;
cout<<f[n]<<endl;//解就是f[n]
return 0;
}
AT3725 [ARC087A] Good Sequence
就是没达到的部分全部剪掉，超过的部分剪掉超过的 （混乱orz
#include<bits/stdc++.h>
#define reg register int
#define INF (1<<30)
using namespace std;
int read(){
int res=0,fs=1; char c=getchar();
while(!(c>='0' && c<='9')){ if(c=='-')fs=-1; c=getchar(); }
while(c>='0' && c<='9')res=res*10+c-'0',c=getchar();
return res*fs;
}
void print(int x){
if(x<0) { putchar('-'); x=-x;}
if(x>9) print(x/10);
putchar(x%10+'0');
}
int n,cnt,m,a[114514],ans,tmp;
map<int,int>t,vis;
int main() {
ios::sync_with_stdio(false);
cin>>n;
for(int i=1;i<=n;i++) cin>>a[i],t[a[i]]++;
for(int i=1;i<=n;i++){
if(t[a[i]]>=a[i]) ans+=t[a[i]]-a[i],t[a[i]]=a[i];
else if(t[a[i]]<a[i]) ans+=t[a[i]],t[a[i]]=0;
}
cout<<ans<<endl;
return 0;
}
AT1124 電卓ゲーム
把每种情况暴力一遍