解题过程
中午吃饭比较晚，到机房lfw开始发各队的账号密码，byf开始读D题,shl电脑卡的要死,启动中...然后听到谁说A题过了好多，然后shl让blf读A题，A题blf一下就A了。然后lfw读完M题（shl的电脑终于打开了，然后输入密码，密码错误。。。自闭），说AC 自动机板题，然后找板子，，，突然发现自己读错题目。后来不知道怎么A的。shl copy了一遍密码终于登上账号。然后lfw一个人用单调栈和前缀和st表A掉了I题；byf 秒了H题；
shl和byf读j题，读完吧题意告诉lfw,lfw说水题，然后树链剖分加线段树离线就过了。同时byf在想K题，然后推出式子，利用前缀和就过了(听说好多对TLE了，应该没用前缀和维护)；然后还有一个多小时，，，shl和byf看D题,lfw看C题，然后shl和byf没啥想法，lfw调C调了一万年，最后也没过。。。这场每一题都是一下就过了，罚时较少。(这场shl全场OB,没碰键盘，状态极差...)
C题要注意一下，java 的BigInteger运算比c++用数组模拟高精度快，lfw被卡住了，c++要几分钟预处理，java几乎1s出来,所以最后用java，但是看错题没看到要字典序最小，没时间改
第二天改好了，最后java也超时。。。要矩阵乘法预处理出28个数。。。
题解
先放代码，题解后面更新。
A. PERFECT NUMBER PROBLEM
#include<bits/stdc++.h> using namespace std; int main() { printf("6\n"); printf("28\n"); printf("496\n"); printf("8128\n"); printf("33550336\n"); return 0; }
B. Greedy HOUHO
Unsolved.
C. Angry FFF Party
Unsolved.
D. Match Stick Game
Unsolved.
E. Card Game
Unsolved.
F. Information Transmitting
Unsolved.
G. tsy's number
Unsolved.
H. Coloring Game
#include<bits/stdc++.h> #define int long long using namespace std; const int mod=1e9+7; int quick_pow(int a,int b) { int ans=1; while(b) { if(b&1) ans=ans*a%mod; a=a*a%mod; b>>=1; } return ans; } int32_t main() { int n; scanf("%lld",&n); if(n==1) {printf("1\n");return 0;} printf("%lld\n",2*2*quick_pow(3,n-2)%mod); return 0; }
I. Max answer
#include<bits/stdc++.h> #define maxl 500010 using namespace std; int n,top,lg; long long ans=0; long long s[maxl]; long long a[maxl],sum[maxl],dol[maxl],dor[maxl]; long long mini[20][maxl],mx[20][maxl]; map <long long,int> mp; map <long long,int> :: iterator it; inline void prework() { scanf("%d",&n); for(int i=1;i<=n;i++) scanf("%lld",&a[i]),sum[i]=sum[i-1]+a[i]; top=0;int l=0,r=0; while(l<=n && r<=n) { while(a[l]<=0 && l<=n) l++; if(a[l]>0) { r=l; while(a[r+1]>0) r++; top=0;s[0]=l-1; for(int i=l;i<=r;i++) { while(top>0 && a[i]<a[s[top]]) { dor[s[top]]=i; top--; } s[++top]=i;dol[i]=s[top-1]; } while(top>0) dor[s[top]]=r+1,top--; for(int i=l;i<=r;i++) ans=max(ans,(sum[dor[i]-1]-sum[dol[i]])*a[i]); } else r=l; l=r+1; } } inline void mainwork() { int lg=log2(n),t; for(int i=0;i<=n;i++) mx[0][i]=mini[0][i]=sum[i]; for(int i=1;i<=lg;i++) for(int j=0;j<=n;j++) { mx[i][j]=max(mx[i-1][j],mx[i-1][j+(1<<(i-1))]); mini[i][j]=min(mini[i-1][j],mini[i-1][j+(1<<(i-1))]); } long long mxx,mii; for(int i=1;i<=n;i++) if(a[i]<0) { t=log2(i-0+1); mxx=max(mx[t][0],mx[t][i-(1<<t)+1]); t=log2(n-i+1); mii=min(mini[t][i],mini[t][n-(1<<t)+1]); ans=max((mii-mxx)*a[i],ans); } } inline void print() { printf("%lld",ans); } int main() { prework(); mainwork(); print(); return 0; }
J. Distance on the tree
#include<bits/stdc++.h> #define maxl 200010 #define inf 2000000001 using namespace std; int n,nn,q,cnt=0,nodecnt=0,num=0; int a[maxl],dep[maxl],tot[maxl],son[maxl],top[maxl],fa[maxl],ehead[maxl]; int idx[maxl],dy[maxl],ans[maxl]; struct ed { int to,nxt; }e[maxl<<1]; struct node { int l,r,sum; }tree[maxl<<2]; struct qu { int u,v,w,id; }que[maxl],edg[maxl<<1]; char ch[maxl]; inline void adde(int u,int v) { e[++cnt].to=v;e[cnt].nxt=ehead[u];ehead[u]=cnt; } void dfs1(int u,int f) { int v; dep[u]=dep[f]+1;fa[u]=f;tot[u]=1; for(int i=ehead[u];i;i=e[i].nxt) { v=e[i].to; if(v==f) continue; dfs1(v,u); tot[u]+=tot[v]; if(tot[v]>tot[son[u]]) son[u]=v; } } void dfs2(int u,int topf) { int v; idx[u]=++nodecnt;dy[nodecnt]=u; top[u]=topf; if(!son[u]) return; dfs2(son[u],topf); for(int i=ehead[u];i;i=e[i].nxt) { v=e[i].to; if(idx[v]) continue; dfs2(v,v); } } void build(int k,int l,int r) { tree[k].l=l;tree[k].r=r; if(l==r) { tree[k].sum=0; return; } int mid=(l+r)>>1; build(k<<1,l,mid); build(k<<1|1,mid+1,r); tree[k].sum=tree[k<<1].sum+tree[k<<1|1].sum; } inline bool cmp(const qu &x,const qu &y) { return x.w<y.w; } inline void prework() { scanf("%d%d",&n,&q); int u,v,w;num=n; nn=n; for(int i=1;i<=n-1;i++) { scanf("%d%d%d",&u,&v,&w); num++;edg[i]=qu{u,v,w,num}; adde(u,num);adde(num,v); adde(v,num);adde(num,u); } for(int i=1;i<=q;i++) { scanf("%d%d%d",&que[i].u,&que[i].v,&que[i].w); que[i].id=i;; } sort(edg+1,edg+1+n-1,cmp); sort(que+1,que+1+q,cmp); n=num; dfs1(1,0); dfs2(1,1); build(1,1,n); } void add(int k,int l) { if(tree[k].l==tree[k].r) { tree[k].sum++; return; } int mid=(tree[k].l+tree[k].r)>>1; if(l<=mid) add(k<<1,l); else add(k<<1|1,l); tree[k].sum=tree[k<<1].sum+tree[k<<1|1].sum; } int getsum(int k,int l,int r) { if(tree[k].l==l && tree[k].r==r) return tree[k].sum; int mid=(tree[k].l+tree[k].r)>>1; if(l>mid) return getsum(k<<1|1,l,r); else if(r<=mid) return getsum(k<<1,l,r); else return getsum(k<<1,l,mid)+getsum(k<<1|1,mid+1,r); } inline int gettreesum(int x,int y) { int ans=0; while(top[x]!=top[y]) { if(dep[top[x]]<dep[top[y]]) swap(x,y); ans+=getsum(1,idx[top[x]],idx[x]); x=fa[top[x]]; } if(dep[x]>dep[y]) swap(x,y); ans+=getsum(1,idx[x],idx[y]); return ans; //printf("%d\n",ans); } inline void mainwork() { //int x,y; /*scanf("%d",&q); for(int i=1;i<=q;i++) { scanf("%s",ch); scanf("%d%d",&x,&y); if(ch[0]=='C') { a[x]=y; add(1,idx[x]); } else if(ch[1]=='S') gettreesum(x,y); else gettreemax(x,y); }*/ int edind=0; for(int i=1;i<=q;i++) { while(edind<nn-1 && edg[edind+1].w<=que[i].w) ++edind,add(1,idx[edg[edind].id]); ans[que[i].id]=gettreesum(que[i].u,que[i].v); } } inline void print() { for(int i=1;i<=q;i++) printf("%d\n",ans[i]); } int main() { prework(); mainwork(); print(); return 0; }
K. MORE XOR
#include<bits/stdc++.h> using namespace std; const int size=1e5+5; #define int long long int sum[4][size]; int arr[size]; int32_t main() { int t; scanf("%lld",&t); int n; while(t--) { scanf("%lld",&n); memset(sum,0,sizeof(sum)); for(int i=1;i<=n;i++) { scanf("%lld",&arr[i]); } for(int i=1;i<=n;i++) { for(int j=0;j<=3;j++) { sum[j][i]=sum[j][i-1]; } sum[i%4][i]=sum[i%4][i]^arr[i]; } int q; scanf("%lld",&q); int l,r; while(q--) { scanf("%lld%lld",&l,&r); int len=r-l+1; if(len%4==0) printf("0\n"); else if(len%4==1) { int b=l%4; printf("%lld\n",sum[b][l-1]^sum[b][r]); } else if(len%4==2) { int b=l%4,c=(l+1)%4; printf("%lld\n",sum[b][l-1]^sum[b][r]^sum[c][l-1]^sum[c][r]); } else if(len%4==3) { int c=(l+1)%4; printf("%lld\n",sum[c][l-1]^sum[c][r]); } } } return 0; }
L. qiqi'tree
Unsolved.
M. Subsequence
#include<bits/stdc++.h> #define maxl 100010 int slen,tlen,n; int nxt[maxl][27]; int nxtind[27]; char s[maxl],t[maxl]; inline void prework() { scanf("%s",s+1); slen=strlen(s+1); for(int i=0;i<26;i++) nxtind[i]=maxl-1; for(int i=slen;i>=1;i--) { for(int j=0;j<26;j++) nxt[i][j]=nxtind[j]; nxtind[s[i]-'a']=i; } for(int j=0;j<26;j++) nxt[0][j]=nxtind[j]; } inline bool check() { tlen=strlen(t+1); int u=0; for(int i=1;i<=tlen;i++) { u=nxt[u][t[i]-'a']; if(u==0 || u>slen) return false; } return true; } inline void mainwork() { scanf("%d",&n); for(int i=1;i<=n;i++) { scanf("%s",t+1); if(check()) puts("YES"); else puts("NO"); } } int main() { prework(); mainwork(); return 0; }
shl聚菜。%lfw.%byf.