昨晚深夜修仙上紫记，虽然不错还是很有遗憾的。
A. Maxim and Biology
看完就会做的题，然而手速跟不上
#include<cstdio> #include<iostream> #include<cstring> #include<cstdlib> #include<algorithm> #include<cmath> using namespace std; typedef long long LL; const int _=1e2; const int maxn=510; char ss[110]; int a[110]; int getdis(int x,int y) { if(x>y)swap(x,y); return min(y-x,x+26-y); } int main() { int n,m; scanf("%d%s",&n,ss+1); for(int i=1;i<=n;i++)a[i]=ss[i]-'A'+1; int mn=(1<<30); for(int i=1;i<=n-3;i++) { mn=min(mn,getdis(a[i],1)+getdis(a[i+1],3)+getdis(a[i+2],20)+getdis(a[i+3],7)); } printf("%d ",mn); return 0; }
B. Dima and a Bad XOR
其实先开的是B，但是O(nm*1024)相当不靠谱不是很敢写。。。后来写得还是磕磕绊绊总之相当不爽。就是那种要抢时间这个题又烦的一批的感觉
#include<cstdio> #include<iostream> #include<cstring> #include<cstdlib> #include<algorithm> #include<cmath> using namespace std; typedef long long LL; const int _=1e2; const int maxn=510; int a[maxn][maxn]; bool f[maxn][1024];int d[maxn][1024],fr[maxn][1024]; int as[maxn]; int main() { int n,m,mx=0; scanf("%d%d",&n,&m); f[0][0]=true; for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) scanf("%d",&a[i][j]),mx=max(mx,a[i][j]); while(mx!=(mx&-mx))mx-=(mx&-mx); mx<<=1; if(mx==0)mx=2; for(int i=0;i<n;i++) for(int zt=0;zt<mx;zt++) if(f[i][zt]) { for(int j=1;j<=m;j++) f[i+1][zt^a[i+1][j]]=true,d[i+1][zt^a[i+1][j]]=j,fr[i+1][zt^a[i+1][j]]=zt; } for(int zt=1;zt<mx;zt++) if(f[n][zt]) { puts("TAK"); for(int i=n;i>=1;i--) { as[i]=d[i][zt],zt=fr[i][zt]; } for(int i=1;i<=n;i++)printf("%d ",as[i]); puts("");return 0; } puts("NIE"); return 0; }
C. Problem for Nazar
和B一起让我自闭了半个多小时，看错一发题意。其实就是按题意模拟，然后写到45min才过真是！@#￥%……&，也是疯狂调试没什么底的，还好样例比较强。
#include<cstdio> #include<iostream> #include<cstring> #include<cstdlib> #include<algorithm> #include<cmath> using namespace std; typedef long long LL; const LL mod=1e9+7; inline LL ad(LL x,LL y){return (x>=mod-y)?(x-mod+y):x+y;} inline LL re(LL x,LL y){return (x<y)?(x-y+mod):x-y;} LL solve(LL n) { if(n==0)return 0; int op=1; LL i,step=0,ost=1,est=2,ret=0; for(i=1;i<=n;i<<=1) { if(step+i>=n)break; if(op==1) { LL ed=ost+2*(i-1); ret=ad(ret,(ost+ed)%mod*(i%mod)%mod*(mod/2+1)%mod); ost=ed+2; } else { LL ed=est+2*(i-1); ret=ad(ret,(est+ed)%mod*(i%mod)%mod*(mod/2+1)%mod); est=ed+2; } op^=1; step+=i; } if(op==1) { LL ed=ost+2*(n-step-1);if(ed%2==0)ed--; ret=ad(ret,(ost+ed)%mod*((n-step)%mod)%mod*(mod/2+1)%mod); } else { LL ed=est+2*(n-step-1);if(ed%2==1)ed--; ret=ad(ret,(est+ed)%mod*((n-step)%mod)%mod*(mod/2+1)%mod); } return ret; } int main() { LL l,r; scanf("%lld%lld",&l,&r); printf("%lld ",re(solve(r),solve(l-1))); return 0; }
D. Stas and the Queue at the Buffet
sb微扰。我觉得比A还sb。
#include<cstdio> #include<iostream> #include<cstring> #include<cstdlib> #include<algorithm> #include<cmath> using namespace std; typedef long long LL; const int _=1e2; const int maxn=1e5+_; struct node{int a,b;}p[maxn]; bool cmp(node n1,node n2){return n1.a-n1.b>n2.a-n2.b;} int main() { int n; scanf("%d",&n); for(int i=1;i<=n;i++) scanf("%d%d",&p[i].a,&p[i].b); sort(p+1,p+n+1,cmp); LL ans=0; for(int i=1;i<=n;i++) { ans+=(LL)(i-1)*p[i].a+(LL)(n-i)*p[i].b; } printf("%lld ",ans); return 0; }
E. Number of Components
这个E岂不是搞笑的？？明明O(n)还放1e5
考虑已经得到前i-1个点的贡献，现在加入i这个点，假如a[i]不在[l,r]里面或a[i],a[i-1]都在[l,r]里面它没有贡献，否则就会产生贡献。
第二天rose_king又给出了一个更直观的做法：因为联通块数=总点数-被删的边数，答案就是=总点数-被删的边数-不在[l,r]的点数
#include<cstdio> #include<iostream> #include<cstring> #include<cstdlib> #include<algorithm> #include<cmath> using namespace std; typedef long long LL; const int _=1e2; const int maxn=1e5+_; int a[maxn]; int main() { int n; scanf("%d",&n); for(int i=1;i<=n;i++)scanf("%d",&a[i]); LL ans=(LL)(a[1]-1)*(n-a[1])+n; int L,R; for(int i=2;i<=n;i++) { if(a[i]==a[i-1])continue; if(a[i]>a[i-1]) { L=a[i]-1-a[i-1],R=n-a[i]; } else if(a[i]<a[i-1]) { L=a[i]-1,R=a[i-1]-1-a[i]; } ans+=(LL)L*R+L+R+1; } printf("%lld ",ans); return 0; }
F. Sonya and Informatics
这个F也是我有问题，看错了一发题意浪费了半个小时，然后脑子不清醒写了个假的，其实只要设f[i]表示在正确位置的1的个数为i然后明显矩乘优化就完事了
咕了
这几场手速都是极大的劣势
天天又看错题
还很慢热，写完模拟才有点做题的感觉
总之就是菜鸡一个
不过没fail题算是有点安慰吧