熬夜氪肝打(CF)，好不容易搞出来三道题，TMD又(FST)了
(
m{QAQ})，还是第二道题，死因：数组开小。我什么时候能认真一些啊……
第三道题因为错了太多+做得完，和第二题一个分
不过我竟然涨了4个rating（可能是我太菜了，已经不屑于扣我的( t{rating})了）
A.Cashier
还是水，不过比上次好些
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
int read(){
int k=0,f=1; char c=getchar();
for(;c<'0'||c>'9';c=getchar())
if(c=='-') f=-1;
for(;c>='0'&&c<='9';c=getchar())
k=k*10+c-48;
return k*f;
}
int ans=0;
int main(){
int n=read(),l=read(),a=read();
int x1=0;
for(int i=1;i<=n;i++){
int x=read(),y=read();
ans+=(x-x1)/a;
x1=x+y;
}
ans+=(l-x1)/a;
cout<<ans;
return 0;
}
B.Forgery
这题我一开始毫无思路，所以先刚的(C)题再回来做的，然后就数组开小了……
我们枚举每一个周围全是(#)的元素，然后将它中间的点的坐标入栈。
枚举完毕后，我们新建一张空白图，将坐标依次出栈，在空白图上将它周围的点全变成(#),然后与原图比较
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int read(){
int k=0,f=1; char c=getchar();
for(;c<'0'||c>'9';c=getchar())
if(c=='-') f=-1;
for(;c>='0'&&c<='9';c=getchar())
k=k*10+c-48;
return k*f;
}
bool mapp[1010][1010],wmap[1010][1010];
//check枚举每个元素
bool check(int x,int y){
if(mapp[x+1][y]&&mapp[x+2][y]&&mapp[x][y+1]&&mapp[x][y+2]
&&mapp[x+1][y+2]&&mapp[x+2][y+2]&&mapp[x+2][y+1])
return 1;
else return 0;
}
int wx[1000010],wy[1000010],top;//就是这个地方，数组开小了1000倍……
int fx[9]={0,1,0,-1,0,1,-1,1,-1},
fy[9]={0,0,1,0,-1,-1,1,1,-1};
int main(){
int n=read(),m=read();
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++){
char c; cin>>c;
if(c=='#') mapp[i][j]=1;
}
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++){
if(mapp[i][j]){
if(check(i,j)) wx[++top]=i+1,wy[top]=j+1;
}
}
//填新图
while(top){
int x=wx[top],y=wy[top]; --top;
for(int i=1;i<=8;i++) wmap[x+fx[i]][y+fy[i]]=1;
}
//比较
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
if(mapp[i][j]!=wmap[i][j]){
cout<<"NO"; exit(0);
}
cout<<"YES";
return 0;
}
C.Sequence Transformation
能自己做出(mathbb{C})题来，还是很开心的。
因为题中要求字典序最大，但开始几次无论我们删哪个数，它们的(gcd)肯定都是(1),所以我们只要让数列的(gcd)尽量早的不为(1)就好了，所以我们可以先将奇数删去，这样可以最早的输出一个大于(1)的数——(2)。
以此类推，我们再留下(4)的倍数、留下(8)的倍数……一直到最接近并小于(n)的(2)的整数次幂。
之后比较麻烦的是最后一位数的判定。如果(n)能被(ans[n-1])整除，那为了字典序最大，我们要最后再把(n)删去。如果(n)不能被(ans[n-1])整除，为了字典序最大，我们要提前删去(n)，来保证最早输出(2)的幂
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
long long read(){
long long k=0,f=1; char c=getchar();
for(;c<'0'||c>'9';c=getchar())
if(c=='-') f=-1;
for(;c>='0'&&c<='9';c=getchar())
k=k*10+c-48;
return k*f;
}
long long ans[1000010],hhh=1,pos;
int main(){
long long n=read(); long long cnt=n;
if(n==1){
cout<<"1"; return 0;
}
while(cnt){
long long tot=cnt/2; if(cnt%2) tot++;
for(long long i=1;i<=tot;i++) ans[++pos]=hhh;
cnt-=tot; hhh<<=1;
}
if(!(n%(ans[n-1]))) ans[n]=n;
else ans[n]=(ans[n-1]*(n/ans[n-1]));
for(long long i=1;i<=n;i++) cout<<ans[i]<<" ";
return 0;
}