NOI2015网上同步赛滚粗记&题解
在家里有模板有对拍还是没到金牌线，太弱了、、
Day 1
8:30 你妹啊，题呢？
8:40 你妹啊，题呢？
8:50 看T1，我去，这不傻逼题吗？然后发现要离散化，map一下完事，去看T2。
9:10 T2感觉要写1H多，先看了会T3，感觉没啥思路，于是开始做T2。
9:15 T2也傻逼题？NOI怎么这么傻逼，都一眼题吗？
10:10 写完T2，调了一会，马上就过了大数据，爽。
10:20 这是T3做3H的节奏，不对啊。。
n<=500，这不是鼓励交表吗、、
在草稿纸上推了好久，就是推不出来啊、、
11:00 开始写暴搜
11:15 暴搜n>25根本跑不出来、、可我的目标是30啊
11:20 似乎n>15的质数不用判，直接乘3就行啦？
11:30 搜出了n<=30的情况，开始想怎么弄更多的分
12:00 还是想不出来啊、、看来要弃疗了，检查一下前两题啊
12:20 T1写炸了？似乎不读入要超时，似乎用map要超时？
12:30 发现在线判断是不对的，于是改为离线判
12:40 小数据都错？离散化写炸了、、
13:00 总算改好了，应该能过吧。。
13:10 T1、T2差不多了，继续弄T3吧。。
13:30 把T1、T2交了
13:40 T3弃疗，交表
230滚粗，当场AK的一大堆。。
滚粗的程序：
#include<cstdio>
#include<algorithm>
#define N 222222
using namespace std;
int T,n,x,y,z,p,q,i,now,top,father[N],a[N],b[N],c[N],px[N],ux[N];
bool ff;char ch;
void read(int &x){
for(ch=getchar();ch<'0';ch=getchar());
for(x=0;ch>='0';ch=getchar())x=x*10+ch-'0';
}
int find(int x){
if(father[x]==x)return x;
return father[x]=find(father[x]);
}
int go(int x){
int l=1,r=top;
while(l<r){
int mid=(l+r)>>1;
if(x>ux[mid])l=mid+1;else r=mid;
}
return l;
}
int main(){
freopen("prog.in","r",stdin);
freopen("prog.out","w",stdout);
read(T);
while(T--){
now=0;top=0;
read(n);ff=1;
for(i=1;i<=200000;i++)father[i]=i;
for(i=1;i<=n;i++){
read(a[i]);read(b[i]);read(c[i]);
px[i*2-1]=a[i];px[i*2]=b[i];
}
sort(px+1,px+2*n+1);
for(i=1;i<=2*n;i++)if(px[i]!=px[i-1])ux[++top]=px[i];
for(i=1;i<=n;i++)if(c[i]==1){
p=go(a[i]);
q=go(b[i]);
p=find(p);q=find(q);
father[p]=q;
}
for(i=1;i<=n;i++)if(!c[i]){
p=go(a[i]);
q=go(b[i]);
p=find(p);q=find(q);
if(p==q){ff=0;break;}
}
if(ff)puts("YES");else puts("NO");
}
fclose(stdin);fclose(stdout);
return 0;
}
#include<cstdio>
#include<iostream>
#define N 888888
using namespace std;
int n,m,i,x,y,now,l,r,tot,sz,last[N],next[N],first[N],size[N],high[N],father[N],pos[N],belong[N];
char s[99],ch;bool v[N];
struct T{int sum,lazy,key,l,r;}t[N];
void read(int &x){
for(ch=getchar();ch<'0';ch=getchar());
for(x=0;ch>='0';ch=getchar())x=x*10+ch-'0';
}
void ins(int x,int y){last[++tot]=y;next[tot]=first[x];first[x]=tot;}
void dfs(int x){
v[x]=true;size[x]=1;
for(int i=first[x];i;i=next[i]){
int y=last[i];
if(!v[y]){
high[y]=high[x]+1;father[y]=x;
dfs(y);size[x]+=size[y];
}
}
}
void dfs2(int x,int y){
int now=0;
pos[x]=++sz;belong[x]=y;
for(int i=first[x];i;i=next[i])if(high[last[i]]>high[x]&&size[last[i]]>size[now])now=last[i];
if(!now)return;dfs2(now,y);
for(int i=first[x];i;i=next[i])if(high[last[i]]>high[x]&&last[i]!=now)dfs2(last[i],last[i]);
}
void pushdown(int k){
if(t[k].lazy){
t[k<<1].sum=(t[k<<1].r-t[k<<1].l+1)*t[k].key;
t[k<<1|1].sum=(t[k<<1|1].r-t[k<<1|1].l+1)*t[k].key;
t[k<<1].lazy=t[k<<1|1].lazy=1;
t[k<<1].key=t[k<<1|1].key=t[k].key;
t[k].lazy=t[k].key=0;
}
}
void pushup(int k){t[k].sum=t[k<<1].sum+t[k<<1|1].sum;}
void build(int k,int l,int r){
t[k].l=l;t[k].r=r;
int mid=(l+r)>>1;if(l==r){t[k].sum=1;return;}
build(k<<1,l,mid);build(k<<1|1,mid+1,r);
pushup(k);
}
int query(int k,int x,int y){
pushdown(k);
if(x<=t[k].l&&t[k].r<=y)return t[k].sum;
int l=t[k].l,r=t[k].r,mid=(l+r)>>1;
if(x>mid)return query(k<<1|1,x,y);
else if(y<=mid)return query(k<<1,x,y);
else return query(k<<1,x,mid)+query(k<<1|1,mid+1,y);
}
void insert(int k,int x,int y,int key){
pushdown(k);
if(x<=t[k].l&&t[k].r<=y){
t[k].sum=(t[k].r-t[k].l+1)*key;
t[k].lazy=1;
t[k].key=key;
return;
}
int l=t[k].l,r=t[k].r,mid=(l+r)>>1;
if(x>mid)insert(k<<1|1,x,y,key);
else if(y<=mid)insert(k<<1,x,y,key);
else insert(k<<1,x,mid,key),insert(k<<1|1,mid+1,y,key);
pushup(k);
}
int main(){
freopen("manager.in","r",stdin);
freopen("manager.out","w",stdout);
read(n);
for(i=2;i<=n;i++){
read(x);
ins(x+1,i);
}
dfs(1);
dfs2(1,1);
build(1,1,n);
read(m);
while(m--){
scanf("%s",s);read(x);x++;
if(s[0]=='i'){
now=0;
for(;belong[x]!=belong[1];x=father[belong[x]]){
now+=query(1,pos[belong[x]],pos[x]);
insert(1,pos[belong[x]],pos[x],0);
}
now+=query(1,pos[belong[x]],pos[x]);
insert(1,pos[belong[x]],pos[x],0);
printf("%d\n",now);
}else{
l=pos[x];r=pos[x]+size[x]-1;
now=size[x]-query(1,l,r);
insert(1,l,r,1);
printf("%d\n",now);
}
}
fclose(stdin);fclose(stdout);
return 0;
}
#include<cstdio>
long long ans[41]={0,0,3,9,21,63,111,333,693,1521,2577,7731,13491,40473,67833,119241,239481,718443,1340523,4021569,7494849,13356657,22271409,66814227,130266387,268286823,447212583,896472063,1684872063,5054616189,9566769789,28700309367,57402497367,103063130487};
long long n,p;
int main(){
freopen("dinner.in","r",stdin);
freopen("dinner.out","w",stdout);
scanf("%lld%lld",&n,&p);
if(n<=33)printf("%lld\n",ans[n]%p);else if(n==100)puts("3107203");else puts("0");
fclose(stdin);fclose(stdout);
return 0;
}
Day 2
8:30 打开题目，发现竟然没有提答
8:40 好晕啊，每道题都没有看懂、、而且每道题都20个测试点，各种奇奇怪怪的条件，不知道在想什么
8:45 感觉T1也就wi相等能做，才20分，没希望了
8:50 UOJ上说k=2是裸哈夫曼，哈夫曼是什么啊？百度了一下，发现k=2还是挺简单的
9:15 写完了k=2的情况，开始写wi相等的情况
9:25 写完了wi相等的情况，T1有60了，开始看T2
9:40 T2似乎暴力后缀数组有40分？
10:10 写抄完了T2的暴力，看了会T3，感觉不太可做，于是继续想T2
10:25 发现所有ai相等的情况似乎就是求出height[]然后黈力T1就行啦？
11:25 由于对后缀数组十分生疏，调了1H才调好，现在T2应该是60分。
11:30 感觉剩下40分太难拿了，就去看T3了。
11:35 T3连边很简单，然后做一个点权最长路？
12:00 写完点权最长路，发现左右会走来走去
12:05 试试看缩点吧，于是直接把tarjan+缩点模板复过来，然后发现就是APIO某题？
12:10 缩完了点，发现缩点似乎也不对。。
12:15 发现题读错了，缩点似乎对的，可以拿20分。。
12:20 开始构造返回路径
12:40 写完了走哪条路径，但是发现爆炸了，没办法了，看来T3我是没法做了
12:45 发现大数据第一问都错了，T3弃疗。T2问一问胡主力，他并没有写出来，我也没有听懂他的想法
12:50 看看能不能在T2 sa[] rank[] height[]数组中找规律，但没有结果
13:00 UOJ上有个好心人放了个题解，T1似乎K叉哈夫曼也是可以做的？
13:05 发现K叉会出现一点小问题，发现只要把多的补0就可以了。
开始用最快速度码T1，还好有原来代码的基础，不用改动太多
13:15 终于码完了，调了5分钟，调对了
13:20 把T2、T3交了，开始检查T1
13:25 发现T1还没试大数据，试了下发现对了
13:27 放心了，把T1交了
140滚粗，T3直接0分，一点希望都没有。。。
似乎网上同步赛评测机脑子进gin了，部分分都不算，算的话应该有个20分。。而且T2板子拉了个错的，以致于只有40分。。
滚粗的程序：
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#define N 222222
using namespace std;
long long n,m,i,now,ans,root,l,r,y,dis,jian,m0,step,val[N],son[N][2],high[N];
long long merge(long long x,long long y){
if(!x||!y)return x+y;
if(val[x]>val[y]||(val[x]==val[y]&&high[x]>high[y]))swap(x,y);
son[x][1]=merge(son[x][1],y);
swap(son[x][0],son[x][1]);
return x;
}
int main(){
freopen("epic.in","r",stdin);
freopen("epic.out","w",stdout);
scanf("%lld%lld",&n,&m);
m0=(n-1)%(m-1);
for(i=1;i<=n;i++)scanf("%lld",&val[i]),root=merge(root,i);
if(m0)for(i=1;i<=m-1-m0;i++)val[++n]=0,root=merge(root,n);
step=(n-1)/(m-1);y=n;
while(step--){
y++;dis=0;
for(i=1;i<=m;i++){
now++;
ans+=val[root];
val[y]+=val[root];
dis=max(dis,high[root]);
root=merge(son[root][0],son[root][1]);
}
high[y]=dis+1;
now--;
root=merge(root,y);
}
printf("%lld\n%lld",ans,high[root]);
fclose(stdin);fclose(stdout);
return 0;
}
#include<cstdio>
#include<cstring>
#include<algorithm>
#define N 510000
#define inf 2000000000000000000
#define inf2 1000000000
using namespace std;
int wa[N],wb[N],ws[N],wv[N],sa[N],rank[N],height[N],er[21],log2[N],f[N][21],ans1[N],n,t,tot,now,head;
long long a[N],ans2[N],mav,lc[N],rc[N],ans[N],q[N],total;
struct EG{long long key;int lcp;}eg[4010000];
char str[N];
bool cmp2(EG a,EG b){return a.lcp>b.lcp;}
int cmp(int *r,int a,int b,int l){return (r[a]==r[b])&(r[a+l]==r[b+l]);}
int min(int x,int y){if(x<y)return x;return y;}
void DA(char *r,int *sa,int n,int m){
int i,j,p,*x=wa,*y=wb,*t;
for(i=0;i<m;i++)ws[i]=0;
for(i=0;i<n;i++)ws[x[i]=r[i]]++;
for(i=1;i<m;i++)ws[i]+=ws[i-1];
for(i=n-1;i>=0;i--)sa[--ws[x[i]]]=i;
for(j=1,p=1;p<n;j*=2,m=p){
for(p=0,i=n-j;i<n;i++) y[p++]=i;
for(i=0;i<n;i++)if(sa[i]>=j) y[p++]=sa[i]-j;
for(i=0;i<n;i++)wv[i]=x[y[i]];
for(i=0;i<m;i++)ws[i]=0;
for(i=0;i<n;i++)ws[wv[i]]++;
for(i=1;i<m;i++)ws[i]+=ws[i-1];
for(i=n-1;i>=0;i--)sa[--ws[wv[i]]]=y[i];
for(t=x,x=y,y=t,p=1,x[sa[0]]=0,i=1;i<n;i++)
x[sa[i]]=cmp(y,sa[i-1],sa[i],j)?p-1:p++;
}
}
void calheight(char *r,int *sa,int n){
int i,j,k=0;
for(i=1;i<=n;i++)rank[sa[i]]=i;
for(i=0;i<n;height[rank[i++]]=k)
for(k?k--:0,j=sa[rank[i]-1];r[i+k]==r[j+k];k++);
}
void RMQ(){
int i,j;er[0]=1;
for(i=1;i<20;i++)er[i]=er[i-1]*2;
log2[0]=-1;
for(i=1;i<=n;i++)log2[i]=(i&(i-1))?log2[i-1]:log2[i-1]+1;
for(i=1;i<=n;i++)f[i][0]=height[i];
for(j=1;j<20;j++)
for(i=1;i+er[j]-1<=n;i++)
f[i][j]=min(f[i][j-1],f[i+er[j-1]][j-1]);
}
int lcp(int a,int b){
int x=rank[a],y=rank[b];
if(x>y)t=x,x=y,y=t;
x++;int k=log2[y-x+1];
return min(f[x][k],f[y-er[k]+1][k]);
}
int main(){
freopen("savour.in","r",stdin);
freopen("savour.out","w",stdout);
scanf("%d",&n);
scanf("%s",str);
for(int i=0;i<n;i++)scanf("%lld",&a[i]);
str[n]=0;
DA(str,sa,n+1,128);
calheight(str,sa,n);
if(n>8000){
height[0]=-inf2;q[1]=1;head=1;lc[1]+=1;
for(int i=2;i<=n;i++){
while(height[i]<=height[q[head]]&&head)head--;
lc[i]=i-q[head];
q[++head]=i;
}
height[n+1]=-inf2;q[0]=n+1;q[1]=n;head=1;rc[n]=1;
for(int i=n-1;i;i--){
while(height[i]<height[q[head]]&&head)head--;
rc[i]=q[head]-i;
q[++head]=i;
}
for(int i=1;i<=n;i++)ans[height[i]]+=lc[i]*rc[i];
for(int i=n-1;i>=0;i--)ans2[i]=ans2[i+1]+ans[i];
ans2[0]=(n*(n-1))/2;
for(int i=0;i<n;i++)printf("%lld %lld\n",ans2[i],a[1]*a[1]);
}else{
RMQ();
for(int i=0;i<n;i++)
for(int j=i+1;j<n;j++)
eg[++tot].key=a[i]*a[j],eg[tot].lcp=lcp(i,j);
sort(eg+1,eg+tot+1,cmp2);
now=1;mav=-inf;
for(int i=n-1;i>=0;i--){
while(eg[now].lcp==i&&now<=tot){
mav=max(mav,eg[now].key);
now++;
}
ans1[i]=now-1;
if(mav==-inf)ans2[i]=0;else ans2[i]=mav;
}
for(int i=0;i<n;i++)printf("%d %lld\n",ans1[i],ans2[i]);
}
fclose(stdin);fclose(stdout);
return 0;
}
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#define N 66666
#define M 333333
using namespace std;
int n,i,j,s,head,tail,tot,tot2,x,y,time,scnt,top,S,ans,u,step,dis[N],first[N],first2[N],first3[N],next[M],next2[M],next3[M],last[M],last2[M],q[M<<4],dfn[N],low[N],stack[N],belong[N],val[N],pre[N],ste[N];
bool v[N],instack[N],vis[N];
struct EG{int x,y,z;}eg[N];
bool cmp1(EG a,EG b){return a.x<b.x||(a.x==b.x&&a.y<b.y);}
bool cmp2(EG a,EG b){return a.y<b.y||(a.y==b.y&&a.x<b.x);}
bool cmp3(EG a,EG b){return a.x+a.y<b.x+b.y||(a.x+a.y==b.x+b.y&&a.y<b.y);}
bool cmp4(EG a,EG b){return a.y-a.x<b.y-b.x||(a.y-a.x==b.y-b.x&&a.y<b.y);}
void insert(int x,int y){last[++tot]=y;next[tot]=first[x];first[x]=tot;}
void ins(int x,int y){last2[++tot2]=y;next2[tot2]=first2[x];first2[x]=tot2;}
void tarjan(int x){
int now=0;
dfn[x]=low[x]=++time;
stack[++top]=x;
instack[x]=1;
for(int i=first[x];i;i=next[i]){
int y=last[i];
if(!dfn[y]){tarjan(y);if(low[y]<low[x])low[x]=low[y];}
else if(instack[y]&&dfn[y]<low[x])low[x]=dfn[y];
}
if(low[x]==dfn[x]){
scnt++;
while(now!=x){
now=stack[top--];
instack[now]=0;
belong[now]=scnt;
val[scnt]+=1;
}
}
}
void rebuild(){
for(i=1;i<=n;i++)
for(j=first[i];j;j=next[j])
if(belong[i]!=belong[last[j]])ins(belong[i],belong[last[j]]);
}
void spfa(){
int head=0,tail=1;S=n;
q[1]=belong[S];v[belong[S]]=1;dis[belong[S]]=val[belong[S]];
while(head!=tail)
for(i=first2[x=q[++head]],v[x]=0;i;i=next2[i])
if(dis[x]+val[y=last2[i]]>dis[y]){
pre[y]=x;
dis[y]=dis[x]+val[y];
if(!v[y])v[q[++tail]=y]=1;
}
}
int main(){
freopen("farm.in","r",stdin);
freopen("farm.out","w",stdout);
scanf("%d",&n);
for(i=1;i<=n;i++)scanf("%d%d",&eg[i].x,&eg[i].y),eg[i].z=i;
n++;eg[n].x=0;eg[n].y=0;eg[n].z=n;
sort(eg+1,eg+n+1,cmp1);
for(i=2;i<=n;i++)if(eg[i-1].x==eg[i].x)insert(eg[i-1].z,eg[i].z);
sort(eg+1,eg+n+1,cmp2);
for(i=2;i<=n;i++)if(eg[i-1].y==eg[i].y)insert(eg[i-1].z,eg[i].z),insert(eg[i].z,eg[i-1].z);
sort(eg+1,eg+n+1,cmp3);
for(i=2;i<=n;i++)if(eg[i-1].x+eg[i-1].y==eg[i].x+eg[i].y)insert(eg[i-1].z,eg[i].z);
sort(eg+1,eg+n+1,cmp4);
for(i=2;i<=n;i++)if(eg[i-1].x-eg[i-1].y==eg[i].x-eg[i].y)insert(eg[i-1].z,eg[i].z);
for(i=1;i<=n;i++)if(!dfn[i])tarjan(i);
rebuild();
spfa();
for(i=1;i<=n;i++)if(dis[belong[i]]>ans)ans=dis[belong[i]],u=belong[i];
printf("%d\n",ans-1);
for(i=1;i<=n;i++){
next3[i]=first3[belong[i]];
first3[belong[i]]=i;
}
while(dis[u]>1){
for(i=first3[u];i;i=next3[i])ste[++step]=i;
u=pre[u];
}
for(i=step;i;i--)printf("%d ",ste[i]);puts("");
printf("%d\n",n-1);
/*for(i=1;i<=n;i++)printf("%d ",belong[i]);puts("");
for(i=1;i<=n;i++)printf("%d ",pre[i]);puts("");
for(i=1;i<=n;i++)printf("%d ",dis[belong[i]]);puts("");*/
fclose(stdin);fclose(stdout);
return 0;
}
感觉自己实力还是太弱了，很多算法不会，傻逼题要写好久，不会的题骗不到多少分，这样不滚粗才怪呢
后记：
哎Day2T2真的是后缀树裸题，用后缀自动机建出后缀树然后后缀树上随便弄就可以了。。比后缀数组不知道高到哪里去了
Day1T3其实也很简单，做的时候非常脑残，都想到放素数了背包想不出，会背包50肯定有的啊。。。
按照题解的方法来做，感觉非常有道理，代码也很短。。是这次NOI第3短的题。。。
简要题解
Day1：
T1程序自动分析：直接并查集，遇到相等就合并不等就判断，要离散化
T2软件包管理器：可以说是裸的树剖了，有两个操作，安装操作相当于把一条链全改为1，卸载操作相当于把一个子树全改为0，然后树剖裸上就可以了
T3寿司晚宴：先考虑往A和B两边放素数，然后判断，要求每个方案的素数在选的数中至少要分解出至少一个
然后得到g[j|u[i]]=g[j|u[i]]+g[j](u[i]为i分解质因数的二进制表示），直接背包就可以了
然后发现50-100的素数不用管直接乘3就可以了，然后轻松50分。。
但发现小于根号n的素数只有9个，可以对小质数进行压缩，大质数进行DP，设初值dp[x][y]=g[x]*g[y]((x&y)==0)
然后枚举每个大质数的所有整数z,z可以分给A、B或不用，于是
分给A： d[x | z][y][0] = (d[x | z][y][0] + d[x][y][0] + f[x][y]) % mod;
分给B： d[x][y | z][1] = (d[x][y | z][1] + d[x][y][1] + f[x][y]) % mod;
累加：dp[x][y] = (dp[x][y] + d[x][y][0] + d[x][y][1]) % mod;
其中(x&y)==0，x,y均倒序循环，最后Σdp[x][y]((x&y)==0)即为答案
#include<cstdio>
#include<cmath>
#include<cstring>
#define N 555
long long M,n,i,j,k,l,w,tmp,now,ans,sum,p,sq,SZ,u[N],g[N],pr[N],d[N][N][2],dp[N][N];
bool f[N],y[N];
int main(){
scanf("%lld%lld",&n,&M);
for(i=2;i<=n;i++){
if(!f[i])pr[++p]=i;
for(j=1;j<=p&&i*pr[j]<=n;j++){
f[i*pr[j]]=1;
if(i%pr[j]==0)break;
}
}
for(i=1;i<=p;i++)if(pr[i]<=sqrt(n))++sq;SZ=(1<<sq)-1;
for(i=2;i<=n;i++){
for(tmp=i,j=1;j<=sq&&tmp>1;j++)
if(tmp%pr[j]==0){
u[i]|=1<<(j-1);
while(tmp%pr[j]==0)tmp/=pr[j];
}
if(tmp>1)y[i]=1;
}
for(g[0]=1,i=2;i<=n;i++)
if(!y[i])for(j=SZ;j>=0;j--)g[j|u[i]]=(g[j|u[i]]+g[j])%M;
for(i=0;i<=SZ;i++)
for(j=0;j<=SZ;j++)
if((i&j)==0)dp[i][j]=(g[i]*g[j])%M;
for(i=sq+1;i<=p;i++){
memset(d,0,sizeof(d));
for(j=pr[i];j<=n;j+=pr[i])
for(k=SZ;k>=0;k--)
for(l=SZ;l>=0;l--)if((k&l)==0){
d[k|u[j]][l][0]=(d[k|u[j]][l][0]+d[k][l][0]+dp[k][l])%M;
d[k][l|u[j]][1]=(d[k][l|u[j]][1]+d[k][l][1]+dp[k][l])%M;
}
for(j=0;j<=SZ;j++)
for(k=0;k<=SZ;k++)
if((j&k)==0)dp[j][k]=(dp[j][k]+d[j][k][0]+d[j][k][1])%M;
}
for(i=0;i<=SZ;i++)
for(j=0;j<=SZ;j++)
if((i&j)==0)sum=(sum+dp[i][j])%M;
printf("%lld",sum);
}
Day2：
T1荷马史诗：就是K叉哈夫曼，每次把最小的K个选出来求和再放到堆里，如此往复即可，不过K叉时要把多的填为0才能保证正确性
T2品酒大会：后缀数组的做法暂时不会，不过这题是后缀树裸题，先后缀自动机构造出后缀树，然后在后缀树上搞，维护两个最大值和两个最小值，很明显最大值是max(max(ma1[x]*ma2[x],mi1[x]*mi2[x]),max(ma1[x]*mi2[x],ma2[x]*mi1[x])); else if(sz[x]>=3)now=max(max(ma1[x]*ma2[x],mi1[x]*mi2[x]),ma1[x]*mi1[x])，然后统计方案数，注意统计size时由于边是有权值的，要稍微处理一下，不过也非常简单，在每一层单独统计，然后去掉多余的就可以了
#include<cstdio>
#include<algorithm>
#include<cstring>
#define N 600006
#define inf 2e18
using namespace std;
long long n,m,cnt,S,last,tot,now,tmp,p,q,np,nq,c,i,j,y,son[N][26],fa[N],step[N],a[N],to[N],mi1[N],mi2[N],ma1[N],ma2[N],sz[N],la[N],ne[N],fi[N],va[N],ans[N],mav[N],nx[N];
char s[N];bool vis[N];//x,y是连的两个点，z是长度
void insert(long long x,long long y,long long z){la[++tot]=y;ne[tot]=fi[x];va[tot]=z;fi[x]=tot;}
void add(long long x){//后缀自动机
c=s[x]-'a';p=last;step[np=last=++cnt]=step[p]+1;to[np]=i;
for(;p&&!son[p][c];p=fa[p])son[p][c]=np;
if(!p)fa[np]=S;else{
q=son[p][c];
if(step[p]+1==step[q])fa[np]=q;else{
nq=++cnt;step[nq]=step[p]+1;
memcpy(son[nq],son[q],sizeof son[q]);
fa[nq]=fa[q];fa[q]=fa[np]=nq;
for(;p&&son[p][c]==q;p=fa[p])son[p][c]=nq;
}
}
}
void dfs(long long x,long long high){//在后缀树上遍历
if(to[x])ma1[x]=mi1[x]=a[to[x]],sz[x]=1;else ma1[x]=-inf,mi1[x]=inf,sz[x]=0;
ma2[x]=-inf;mi2[x]=inf;
for(long long i=fi[x];i;i=ne[i]){
long long y=la[i];
dfs(y,high+va[i]);
if(ma1[y]>ma1[x]){
ma2[x]=ma1[x];ma1[x]=ma1[y];
if(ma2[y]>ma2[x])ma2[x]=ma2[y];
}else if(ma1[y]>ma2[x])ma2[x]=ma1[y];
if(mi1[y]<mi1[x]){
mi2[x]=mi1[x];mi1[x]=mi1[y];
if(mi2[y]<mi2[x])mi2[x]=mi2[y];
}else if(mi1[y]<mi2[x])mi2[x]=mi1[y];
sz[x]+=sz[y];nx[x]+=nx[y];
}
now=-inf;tmp=(sz[x]*(sz[x]-1))/2;
if(sz[x]>=4)now=max(max(ma1[x]*ma2[x],mi1[x]*mi2[x]),max(ma1[x]*mi2[x],ma2[x]*mi1[x])); else if(sz[x]>=3)now=max(max(ma1[x]*ma2[x],mi1[x]*mi2[x]),ma1[x]*mi1[x]);
else if(sz[x]>=2)now=ma1[x]*ma2[x];
if(now!=inf)ans[high]+=tmp-nx[x],mav[high]=max(mav[high],now);
nx[x]+=tmp-nx[x];
}
int main(){
scanf("%lld",&n);scanf("%s",s+1);
for(S=last=++cnt,i=n;i;i--)add(i);//倒着加入后缀自动机
for(vis[S]=i=1;i<=cnt;i++)//不断回退建立出后缀树
if(to[i]&&!vis[i])for(j=i;!vis[j];vis[j]=1,j=fa[j])insert(fa[j],j,step[j]-step[fa[j]]);
for(i=0;i<=n;i++)mav[i]=-inf;
for(i=1;i<=n;i++)scanf("%lld",&a[i]);
dfs(1,0);
for(i=n-1;i>=0;i--)ans[i]=ans[i]+ans[i+1],mav[i]=max(mav[i],mav[i+1]);
for(i=0;i<n;i++){
if(mav[i]==-inf)mav[i]=0;
printf("%lld %lld\n",ans[i],mav[i]);
}
}
T3小园丁与老司机：实在是太难了，蒟蒻实在不会，40分还是可以接受的，100分就太那啥了。。。
[NOI2015][BZOJ4195]程序自动分析[BZOJ4196]软件包管理器[BZOJ4198]荷马史诗【BZOJ4199】品酒大会【BZOJ4197】寿司晚宴
2015年7月19日 20:03
哈夫曼太难了QwQ
2015年7月19日 20:30
跪Au爷
2015年7月21日 16:53
其实我D2T2是写出来的