坑 XIX POI(完)

完结撒花！

题解：

fes:首先按照差分约束系统构图，然后发现最后的答案是每个强联通分量的取值个数之和，而每个强联通分量的取值个数就是这个强联通分量里两点间的最长路

#include<cstdio>
int n,m1,m2;
int head[601],end[200001],len[200001],next[200001],tp=0;
int f[601][601];
int dfn[601],low[601],tim=0,dad[601],gs=0,siz[601],d[601],mx[601],mn[601],vis[601],st[601],stp=0;
int q[200001],hh=1,tt=0,iq[601],cnt[601];
int abs(int a){return a<0?-a:a;}
void tarjan(int p)
{
	int i,j,k;
	dfn[p]=low[p]=++tim;
	st[++stp]=p;
	vis[p]=1;
	for(i=head[p];i;i=next[i])
	{
		if(!vis[end[i]])tarjan(end[i]);
		if(vis[end[i]]!=2)
		{
			if(low[end[i]]<low[p])low[p]=low[end[i]];
		}
	}
	if(low[p]==dfn[p])
	{
		++gs;
		while(st[stp+1]!=p)
		{
			dad[st[stp]]=gs;
			vis[st[stp]]=2;
			siz[gs]++;
			stp--;
		}
	}
}
			
int main()
{
	int i,j,k;
	scanf("%d%d%d",&n,&m1,&m2);
	for(i=1;i<=n;i++)
	for(j=1;j<=n;j++)f[i][j]=-(1<<29);
	for(i=1;i<=m1;i++)
	{
		int x,y;
		scanf("%d%d",&x,&y);
		next[++tp]=head[x];head[x]=tp;end[tp]=y;len[tp]=1;
		next[++tp]=head[y];head[y]=tp;end[tp]=x;len[tp]=-1;
		if(f[x][y]<1)f[x][y]=1;
		if(f[y][x]<-1)f[y][x]=-1;
	}
	for(i=1;i<=m2;i++)
	{
		int x,y;
		scanf("%d%d",&x,&y);
		next[++tp]=head[x];head[x]=tp;end[tp]=y;len[tp]=0;
		if(f[x][y]<0)f[x][y]=0;
	}
	for(i=1;i<=n;i++)if(!vis[i])tarjan(i);
	for(i=1;i<=n;i++)f[i][i]=0;
	//for(i=1;i<=n;i++)
	//for(j=1;j<=n;j++)printf("%d%c",f[i][j]," \n"[j==n]);
	//for(i=1;i<=n;i++)printf("i=%d dad[i]=%d d[i]=%d\n",i,dad[i],d[i]);
	for(i=1;i<=n;i++)
	for(j=1;j<=n;j++)if(dad[i]==dad[j])
	for(k=1;k<=n;k++)if(dad[i]==dad[k]&&dad[j]==dad[k])
	if(f[j][i]+f[i][k]>f[j][k])f[j][k]=f[j][i]+f[i][k];
	for(i=1;i<=n;i++)if(f[i][i]>0){puts("NIE");return 0;}
	//for(i=1;i<=n;i++)
	//for(j=1;j<=n;j++)printf("%d%c",f[i][j]," \n"[j==n]);
	//printf("gs=%d\n",gs);
	int s=0;
	//for(i=1;i<=n;i++)printf("i=%d dad[i]=%d d[i]=%d\n",i,dad[i],d[i]);
	for(i=1;i<=n;i++)
	for(j=1;j<=n;j++)if(dad[i]==dad[j])
	{
		if(abs(f[i][j])>mx[dad[i]])mx[dad[i]]=abs(f[i][j]);
	}
	for(i=1;i<=gs;i++)s+=mx[i]+1;
	printf("%d\n",s);
	return 0;
}

lit:可以发现只需要知道第一个串的字母对应第二个串的哪个字母，然后求个逆序对就没了。对应关系就是第一个串的第x个字母y对应第二个串的第x个字母y

#include<cstdio>
#include<vector>
int n;
char s1[1000002],s2[1000002];
int a[1000001];
std::vector<int> v[26];
int bit[1000001];
long long ans=0;
int main()
{
	int i,j,k;
	scanf("%d%s%s",&n,s1+1,s2+1);
	for(i=1;i<=n;i++)v[s1[i]-'A'].push_back(i);
	for(i=n;i>=1;i--)
	{
		a[i]=v[s2[i]-'A'].back();
		v[s2[i]-'A'].pop_back();
	}
	for(i=n;i>=1;i--)
	{
		for(j=a[i];j;j-=j&-j)ans+=bit[j];
		for(j=a[i];j<=n;j+=j&-j)bit[j]++;
	}
	printf("%lld\n",ans);
	return 0;
}

odl:对于每个1..1000000求出把它的倍数变成它要几步，找出里面的最小和次小值，然后对于每个它的倍数用最小值（本来就是步数最小就用次小值）更新答案。

#include<cstdio>
#include<vector>
int n,a[100001];
int b[1000001];
int ans[100001],wans[100001];
int p[1000001],tp=0,isp[1000001];
int gs[1000001];
int mn[33][2];
int mx;
int main()
{
	int i,j,k;
	scanf("%d",&n);
	for(i=1;i<=n;i++)ans[i]=1<<30;
	for(i=1;i<=n;i++)
	{
		scanf("%d",&a[i]);
		if(!b[a[i]])b[a[i]]=i;else
		{
			ans[i]=0;wans[i]=b[a[i]];
			if(!wans[b[a[i]]]){ans[b[a[i]]]=0;wans[b[a[i]]]=i;}
		}
		if(a[i]>mx)mx=a[i];
	}
	//for(i=1;i<=mx;i++)printf("%d ",b[i]);puts("");
	isp[1]=1;
	for(i=2;i<=mx;i++)
	{
		if(!isp[i]){p[++tp]=i;gs[i]=1;}
		for(j=1;j<=tp&&p[j]*i<=mx;j++)
		{
			isp[i*p[j]]=1;gs[i*p[j]]=gs[i]+1;
			if(i%p[j]==0)break;
		}
	}
	//for(i=1;i<=mx;i++)printf("%d ",gs[i]);puts("");
	//for(i=2;i<=1000000;i++)if(gs[i]<0||gs[i]>32)printf("i=%d gs[i]=%d\n",i,gs[i]);
	//puts("ok");
	for(i=1;i<=mx;i++)
	{
		for(j=0;j<=32;j++)mn[j][0]=mn[j][1]=1<<30;
		for(j=1;j*i<=mx;j++)
		{
			if(b[i*j])
			{
				//printf("j=%d gs[j]=%d\n",j,gs[j]);
				if(mn[gs[j]][0]>b[i*j])
				{
					mn[gs[j]][1]=mn[gs[j]][0];
					mn[gs[j]][0]=b[i*j];
				}
				else if(mn[gs[j]][1]>b[i*j])mn[gs[j]][1]=b[i*j];
				//printf("%d %d\n",mn[gs[j]][0],mn[gs[j]][1]);
			}
		}
		//for(j=0;j<=32;j++)printf("%d %d\n",mn[j][0],mn[j][1]);
		//printf("%d\n",i);
		for(j=0;j<=32&&mn[j][0]==(1<<30);j++);k=j;
		if(k>32)continue;
		int kk=k;
		for(j=1;j*i<=mx;j++)if(b[i*j]&&!(ans[b[i*j]]==0&&wans[b[i*j]]))
		{
			if(mn[k][0]!=b[i*j])
			{
				if(gs[j]+k<ans[b[i*j]]||gs[j]+k==ans[b[i*j]]&&mn[k][0]<wans[b[i*j]])
				{
					ans[b[i*j]]=gs[j]+k;wans[b[i*j]]=mn[k][0];
					//if(gs[j]+k==0)printf("j=%d k=%d gs[j]+k=%d\n",j,k,gs[j]+k);
				}
			}
			else
			{
				if(mn[k][1]!=(1<<30))
				{
					if(gs[j]+k<ans[b[i*j]]||gs[j]+k==ans[b[i*j]]&&mn[k][1]<wans[b[i*j]])
					{
						ans[b[i*j]]=gs[j]+k;wans[b[i*j]]=mn[k][1];
						//if(gs[j]+k==0)printf("j=%d k=%d gs[j]+k=%d\n",j,k,gs[j]+k);
					}
				}
				else
				{
					for(kk=k+1;kk<=32&&mn[kk][0]==(1<<30);kk++);
					if(kk>32)continue;
					if(gs[j]+kk<ans[b[i*j]]||gs[j]+kk==ans[b[i*j]]&&mn[kk][0]<wans[b[i*j]])
					{
						ans[b[i*j]]=gs[j]+kk;wans[b[i*j]]=mn[kk][0];
						//if(gs[j]+kk==0)printf("j=%d kk=%d gs[j]+kk=%d\n",j,kk,gs[j]+kk);
					}
				}
			}
		}
		//else if(b[i*j])printf("b[i*j]=%d ans[b[i*j]]=%d wans[b[i*j]]=%d\n",b[i*j],ans[b[i*j]],wans[b[i*j]]);
		//else if(i*j<=6)printf("i*j=%d\n",i*j);
		//printf("%d\n",i);
	}
	for(i=1;i<=n;i++)printf("%d\n",wans[i]);
	return 0;
}

ran:缩点，然后lca，然后分类讨论

#include<cstdio>
int n,k;
int dad[500001],dep[500001];
int head[500001],end[1000001],next[1000001],tp=0;
int dfn[500001],low[500001],st[500001],stp=0,tim=0,vis[500001];
int dad2[500001],gs[500001],gss;
int ddd[500001][33];
int wz[500001];
int abs(int a){return a<0?-a:a;}
int max(int a,int b){return a>b?a:b;}
int min(int a,int b){return a<b?a:b;}
void tarjan(int p)
{
	int i,j;
	dfn[p]=low[p]=++tim;
	st[++stp]=p;vis[p]=1;
	for(i=head[p];i;i=next[i])
	{
		if(!vis[end[i]])tarjan(end[i]);
		if(vis[end[i]]!=2&&low[end[i]]<low[p])low[p]=low[end[i]];
	}
	if(low[p]==dfn[p])
	{
		gss++;
		while(st[stp+1]!=p)
		{
			dad2[st[stp]]=gss;gs[gss]++;vis[st[stp]]=2;stp--;
		}
	}
}
void dfs(int p)
{
	int i,j;
	for(i=head[p];i;i=next[i])if(dad2[end[i]]!=dad2[p])
	{
		dep[end[i]]=dep[p]+1;ddd[end[i]][0]=p;
		dfs(end[i]);
	}
	
}
int main()
{
	int i,j,l;
	//freopen("ran.in","r",stdin);freopen("ran.out","w",stdout);
	scanf("%d%d",&n,&k);
	for(i=1;i<=n;i++)
	{
		scanf("%d",&dad[i]);
		next[++tp]=head[dad[i]];head[dad[i]]=tp;end[tp]=i;
	}
	for(i=1;i<=n;i++)if(!vis[i])tarjan(i);
	//puts("ok1");
	for(i=1;i<=n;i++)if(dad2[dad[i]]==dad2[i]&&!wz[i])
	{
		//printf("i=%d vis[i]=%d dad2[i]=%d gs[dad2[i]]=%d\n",i,vis[i],dad2[i],gs[dad2[i]]);
		wz[i]=1;
		for(j=dad[i],l=2;j!=i;j=dad[j],l++)wz[j]=l;
	}
	//puts("ok2");
	for(i=1;i<=n;i++)if(dad2[dad[i]]==dad2[i])
	{
		ddd[i][0]=i;dep[i]=0;
		dfs(i);
	}
	//puts("ok3");
	for(i=1;i<=25;i++)
	for(j=1;j<=n;j++)ddd[j][i]=ddd[ddd[j][i-1]][i-1];
	for(i=1;i<=k;i++)
	{
		int x,y,ax=0,ay=0;
		scanf("%d%d",&x,&y);
		//printf("ddd[x][25]=%d ddd[y][25]=%d dad2[ddd[x][25]]=%d dad2[ddd[y][25]]=%d\n",ddd[x][25],ddd[y][25],dad2[ddd[x][25]],dad2[ddd[y][25]]);
		if(dad2[ddd[x][25]]!=dad2[ddd[y][25]]){puts("-1 -1");continue;}
		if(dep[x]>dep[y])
		{
			for(j=0,l=1;dep[x]!=dep[y];j++,l<<=1)if((dep[x]-dep[y])&l)
			{
				ax+=l;x=ddd[x][j];
			}
		}
		else if(dep[x]<dep[y])
		{
			for(j=0,l=1;dep[x]!=dep[y];j++,l<<=1)if((dep[y]-dep[x])&l)
			{
				ay+=l;y=ddd[y][j];
			}
		}
		for(j=25;j>=0;j--)if(dad2[ddd[x][j]]!=dad2[ddd[y][j]])
		{
			ax+=(1<<j);ay+=(1<<j);x=ddd[x][j];y=ddd[y][j];
		}
		if(dad2[x]!=dad2[y]){ax++;ay++;x=ddd[x][0];y=ddd[y][0];}
		//printf("x=%d y=%d ax=%d ay=%d\n",x,y,ax,ay);
		if(x==y){printf("%d %d\n",ax,ay);continue;}
		if(wz[y]>wz[x])j=wz[y]-wz[x];else j=gs[dad2[x]]-(wz[x]-wz[y]);
		if(max(ax+j,ay)<max(ax,ay+gs[dad2[x]]-j))printf("%d %d\n",ax+j,ay);
		else if(max(ax+j,ay)>max(ax,ay+gs[dad2[x]]-j))printf("%d %d\n",ax,ay+gs[dad2[x]]-j);
		else if(min(ax+j,ay)<min(ax,ay+gs[dad2[x]]-j))printf("%d %d\n",ax+j,ay);
		else if(min(ax+j,ay)>min(ax,ay+gs[dad2[x]]-j))printf("%d %d\n",ax,ay+gs[dad2[x]]-j);
		else if(ax+j>=ay)printf("%d %d\n",ax+j,ay);else printf("%d %d\n",ax,ay+gs[dad2[x]]-j);
	}
	return 0;
}
	

stu:首先二分答案，然后把下降率太大的挖掉，然后枚举挖到底的点，利用单调性判断可不可行，具体的看代码。。。

#include<cstdio>
#include<cstring>
int n;
long long m;
long long x[1000001],a[1000001],b[1000001],c[1000001],d[1000001],f[1000001],g[1000001];
int chk(int mm)
{
	int i,j,k;
	for(i=1;i<=n;i++){a[i]=x[i]+1ll*mm*(i-1);b[i]=x[i]+1ll*mm*(n-i);c[i]=x[i];d[i]=0;f[i]=0;g[i]=0;}
	for(i=n-1;i>=1;i--)if(a[i]>a[i+1]){long long t=a[i]-a[i+1];a[i]-=t;b[i]-=t;c[i]-=t;d[i]+=t;}
	for(i=2;i<=n;i++)if(b[i]>b[i-1]){long long t=b[i]-b[i-1];a[i]-=t;b[i]-=t;c[i]-=t;d[i]+=t;}
	/*printf("mm=%d\n",mm);
	for(i=1;i<=n;i++)printf("%lld ",d[i]);puts("");
	for(i=1;i<=n;i++)printf("%lld ",a[i]);puts("");
	for(i=1;i<=n;i++)printf("%lld ",b[i]);puts("");
	for(i=1;i<=n;i++)printf("%lld ",c[i]);puts("");*/
	
	for(i=2;i<=n;i++)d[i]+=d[i-1];
	//f[1]=c[1]+d[1];
	long long s=0;
	for(i=1,j=1;i<=n;i++)
	{
		while(j<i&&a[i]-c[i]>=a[j]){s-=a[j];j++;}
		f[i]=c[i]+d[i]+s-(i-j)*(a[i]-c[i]);
		s+=a[i];
	}
	for(i=n,j=n,s=0;i>=1;i--)
	{
		while(j>i&&b[i]-c[i]>=b[j]){s-=b[j];j--;}
		g[i]=c[i]+(d[n]-d[i-1])+s-(j-i)*(b[i]-c[i]);
		s+=b[i];
	}
	/*for(i=1;i<=n;i++)printf("%lld ",f[i]);puts("");
	for(i=1;i<=n;i++)printf("%lld ",g[i]);puts("");*/
	
	for(i=1;i<=n;i++)if(f[i]+g[i]-c[i]<=m)return i;
	return 0;
}
int main()
{
	int i,j,k;
	scanf("%d%lld",&n,&m);
	for(i=1;i<=n;i++)scanf("%lld",&x[i]);
	int ll=-1,rr=1000000000,mm;
	int t;
	while(ll<rr-1)
	{
		mm=ll+rr>>1;
		int tt=chk(mm);
		if(tt){rr=mm;t=tt;}else ll=mm;
	}
	printf("%d %d\n",t,rr);
	return 0;
}

tou:感觉这题好大。。看了题解才写出来。。居然是神奇的贪心，具体就是先把两端都不在1..k上的边给连起来，然后对于剩下的边能连就连。。我不知道为什么这样是对的。。。

#include<cstdio>
int n,m,k;
int head[1000001],end[2000001],next[2000001],tp=0;
int dad[1000001];
int ans,ax[2000001],ay[2000001];
int find(int p){return p==dad[p]?p:dad[p]=find(dad[p]);}
int main()
{
	int i,j;
	scanf("%d%d%d",&n,&m,&k);
	for(i=1;i<=m;i++)
	{
		int x,y;
		scanf("%d%d",&x,&y);
		if(x>y){int t=x;x=y;y=t;}
		next[++tp]=head[x];head[x]=tp;end[tp]=y;
	}
	for(i=1;i<=n;i++)dad[i]=i;
	for(i=k+1;i<=n;i++)
	for(j=head[i];j;j=next[j])if(find(i)!=find(end[j]))dad[dad[end[j]]]=dad[i];
	for(i=1;i<=k;i++)
	for(j=head[i];j;j=next[j])if(find(i)!=find(end[j]))dad[dad[end[j]]]=dad[i];else
	{
		ans++;ax[ans]=i;ay[ans]=end[j];
	}
	printf("%d\n",ans);
	for(i=1;i<=ans;i++)printf("%d %d\n",ax[i],ay[i]);
	return 0;
}

bon:根据题意暴力模拟就好了，只需要注意对于相同的数直接从上一次取到的地方开始继续往下取就可以保证复杂度

#include<cstdio>
int m,b[1000001];
int n,a;
int ok[1000001],hs[1000001],wz[1000001];
int gs;
long long ans[1000001];
int main()
{
	int i,j,k;
	scanf("%d",&m);
	for(i=1;i<=m;i++){scanf("%d",&b[i]);hs[b[i]]=1;}
	ok[0]=1;
	scanf("%d",&n);
	long long s=0;
	for(i=1;i<=n;i++)
	{
		scanf("%d",&a);
		for(j=1;j<=a&&wz[a]<=1000000;j++)
		{
			while(wz[a]<=1000000&&ok[wz[a]])wz[a]+=a;
			if(wz[a]>1000000)break;
			ok[wz[a]]=1;
			if(hs[wz[a]])ans[++gs]=s+j;
		}
		s+=a;
	}
	printf("%d\n",gs);
	for(i=1;i<=gs;i++)printf("%lld\n",ans[i]);
	return 0;
}

sza:把询问和事件从小到大处理，用f[i]表示获得i的价值至少需要多少时间，然后按事件顺序处理并计算事件和询问就好了（看了黈力的题解才做出来。。。果然DP需要加强。。）

#include<cstdio>
#include<algorithm>
int n;
struct wp{int c,a,b;}a[1001];
int p;
struct xw{int m,k,s,yw;}b[1000001];
int f[100001];
int ans[1000001];
int cmp1(wp x,wp y){return x.a<y.a;}
int cmp2(xw x,xw y){return x.m<y.m;}
int main()
{
	int i,j,k;
	scanf("%d",&n);
	for(i=1;i<=n;i++)scanf("%d%d%d",&a[i].c,&a[i].a,&a[i].b);
	scanf("%d",&p);
	for(i=1;i<=p;i++){scanf("%d%d%d",&b[i].m,&b[i].k,&b[i].s);b[i].yw=i;}
	std::sort(a+1,a+n+1,cmp1);
	std::sort(b+1,b+p+1,cmp2);
	f[0]=1<<30;
	for(i=1,j=1;i<=p;i++)
	{
		while(j<=n&&a[j].a<=b[i].m)
		{
			for(k=100000;k>=a[j].c;k--)if(std::min(f[k-a[j].c],a[j].b)>f[k])f[k]=std::min(f[k-a[j].c],a[j].b);
			j++;
		}
		if(f[b[i].k]>b[i].m+b[i].s)ans[b[i].yw]=1;else ans[b[i].yw]=0;
	}
	for(i=1;i<=p;i++)if(ans[i])puts("TAK");else puts("NIE");
	return 0;
}

okr:设询问的串是s[1..n]，枚举每个n的质因数i，如果s[1..n/i]是s的一个循环节，那么s[1..n]的最小循环节就是s[1..n/i]的最小循环节。判循环节可以用hash做到O(1)，枚举质因数可以用线性筛做到O(logn)，就没了（问了黈力才会做。。果然太弱了）

#include<cstdio>
#include<cstring>
#include<cstdlib>
int n,q;
char s[500002];
int isp[500001],p[500001],tp=0,pre[500001];
long long hsh[500001],pp[500001];
inline long long gethsh(int l,int r)
{
	return hsh[r]-hsh[l-1]*pp[r-l+1];
}
int main()
{
	int i,j,k;
	srand(233333);
	scanf("%d%s",&n,s+1);
	isp[1]=1;
	for(i=2;i<=n;i++)
	{
		if(!isp[i]){p[++tp]=i;pre[i]=i;}
		for(j=1;j<=tp&&i*p[j]<=n;j++)
		{
			isp[i*p[j]]=1;pre[i*p[j]]=p[j];
			if(i%p[j]==0)break;
		}
	}
	if(tp>0)j=p[rand()%tp+1];else j=233;
	pp[0]=1;
	for(i=1;i<=n;i++){pp[i]=pp[i-1]*j;hsh[i]=hsh[i-1]*j+s[i]-'a';}
	//for(i=1;i<=n;i++)printf("%lld ",hsh[i]);puts("");
	scanf("%d",&q);
	while(q--)
	{
		int a,b;
		scanf("%d%d",&a,&b);
		int l=b-a+1;
		int ans=l;
		for(j=pre[l],k=l;j>0;k/=j,j=pre[k])
		{
			if(gethsh(a,a+(ans-ans/j)-1)==gethsh(a+ans/j,a+ans-1))ans/=j;
		}
		printf("%d\n",ans);
	}
	return 0;
}

roz:求出离它最近的那个fibonacci数，然后减一减，然后递归着做下去就好了（不要问我为什么是对的。。但是想想应该是挺对的是不是？）

#include<cstdio>
#include<algorithm>
int p,tp;
long long f[100001];
int ans[1000001];
int dfs(long long p)
{
	int i,j,k;
	if(p<=1000000&&ans[p])return ans[p];
	if(p==0)return 0;
	i=std::lower_bound(f+1,f+tp+1,p)-f;
	int a1=dfs(p-f[i-1]),a2=dfs(f[i]-p);
	if(a1>a2)a1=a2;
	if(p<=1000000)ans[p]=a1+1;
	return a1+1;
}
int main()
{
	int i,j;
	scanf("%d",&p);
	f[0]=1;f[1]=1;
	for(i=2;i<=100000&&f[i-1]<=4e17;i++)f[i]=f[i-1]+f[i-2];
	tp=i-1;
	while(p--)
	{
		long long k;
		scanf("%lld",&k);
		printf("%d\n",dfs(k));
	}
	return 0;
}

squ:设答案从小到大是a[1]..a[n]，那么a[1]+a[2]一定是最小的，a[1]+a[3]一定是次小的，然后枚举a[2]+a[3]是第几小的，由此就可以算出a[1]..a[3]，然后算出a[4]..a[n]，判断一下合不合法就好了

#include<cstdio>
#include<algorithm>
#include<cstring>
int n,m;
int a[90001];
int b[90001];
int x[301];
int ags,ans[1001][301];
int find(int p)
{
	int ll=0,rr=m+1,mm;
	while(ll<rr-1)
	{
		mm=ll+rr>>1;
		if(a[mm]<p||a[mm]==p&&!b[mm])ll=mm;else rr=mm;
	}
	if(rr==m+1||a[rr]!=p||!b[rr])return -1;
	return rr;
}
int main()
{
	int i,j,k;
	scanf("%d",&n);m=n*(n-1)/2;
	for(i=1;i<=m;i++)scanf("%d",&a[i]);
	std::sort(a+1,a+m+1);
	for(i=3;i<=m&&i<=n+2;i++)if((i==3||a[i]!=a[i-1])&&(a[1]+a[2]+a[i])%2==0)
	{
		int fl=0;
		for(j=3;j<=m;j++)if(j!=i)b[j]=1;
		int l=1;
		int t=(a[1]+a[2]+a[i])/2;
		x[1]=t-a[i];x[2]=t-a[2];x[3]=t-a[1];
		//printf("i=%d x[1]=%d x[2]=%d x[3]=%d\n",i,x[1],x[2],x[3]);
		if(x[1]<=0)fl=1;
		for(j=4;j<=n&&!fl;j++)
		{
			for(;l<=m&&!b[l];l++);
			x[j]=a[l]-x[1];
			if(x[j]<x[j-1]){fl=1;break;}
			for(k=1;k<j;k++)
			{
				int it=find(x[k]+x[j]);
				if(it==-1){fl=1;break;}
				b[it]=0;
			}
		}
		if(!fl){ags++;for(j=1;j<=n;j++)ans[ags][j]=x[j];}
		memset(b,0,sizeof(b));
	}
	printf("%d\n",ags);
	for(i=1;i<=ags;i++)
	for(j=1;j<=n;j++)printf("%d%c",ans[i][j]," \n"[j==n]);
	return 0;
}

lic:暴力算sg就好了

#include<cstdio>
#include<cstring>
#include"cliclib.h"

int n;
int sg[21][21][30001];
int pow2[32],pow3[32];
int dfs(int p2,int p3,int s)
{
	int i,j,k;
	if(pow2[p2]*pow3[p3]+s>=n)return 0;
	if(sg[p2][p3][s]>=0)return sg[p2][p3][s];
	int b[4]={0};
	b[dfs(0,0,s+pow2[p2]*pow3[p3])]=1;
	b[dfs(p2+1,p3,s)]=1;
	b[dfs(p2,p3+1,s)]=1;
	for(i=0;i<3;i++)if(!b[i])break;
	return sg[p2][p3][s]=i;
}
	
int main()
{
	int i,j,k;
	//scanf("%d",&n);
	n=inicjuj();
	//freopen("lic_db2.out","w",stdout);
	pow2[0]=1;
	for(i=1;i<32;i++)pow2[i]=pow2[i-1]*2;
	pow3[0]=1;
	for(i=1;i<32;i++)pow3[i]=pow3[i-1]*3;
	memset(sg,-1,sizeof(sg));
	dfs(0,0,0);
	/*for(i=0;i<=0;i++)//if(sg.count(i))
	{
		for(j=0;j<=n;j++)printf("%d ",sg[i][i][j]);puts("");
	}*/
	i=0;j=0;k=0;
	while(1)
	{
		if(!dfs(0,0,k+pow2[i]*pow3[j]))
		{
			k+=pow2[i]*pow3[j];i=0;j=0;
			alojzy(1);
		}
		else if(!dfs(i+1,j,k))
		{
			i++;alojzy(2);
		}
		else{j++;alojzy(3);}
		int l=bajtazar();
		if(l==1)
		{
			k+=pow2[i]*pow3[j];i=0;j=0;
		}
		else if(l==2)i++;else j++;
	}
	/*else
	{
		for(j=0;j<=n;j++)printf("-1 ");puts("");
	}*/
	return 0;
}

pen:这题问了黈力才做出来。。就是bfs一遍算出每个点的上界，然后从小到大枚举每个上界，看看以它为上界的数的个数和它以下的还能取的数的个数的关系，如果相等就意味着这些点的取值就是这些数。

#include<cstdio>
int n,d[1000001],a[1000001];
int b[1000001];
int dad[1000001];
int gs[1000001],wz[1000001],vis[1000001];
int ans[1000001];
int q[1000001],hh=1,tt=0;
int head[1000001],end[1000001],next[1000001],tp=0;
int rt;
int find(int p){return p==dad[p]?p:dad[p]=find(dad[p]);}
int main()
{
	int i,j,k;
	scanf("%d",&n);
	for(i=1;i<=n;i++)dad[i]=i;
	for(i=1;i<=n;i++)
	{
		scanf("%d%d",&d[i],&a[i]);
		if(d[i]!=i){next[++tp]=head[d[i]];head[d[i]]=tp;end[tp]=i;}else{rt=i;d[i]=0;}
		if(a[i]){dad[a[i]]=a[i]-1;b[i]=a[i];vis[a[i]]=1;}
	}
	a[0]=n+1;q[++tt]=rt;
	while(hh<=tt)
	{
		if(!a[q[hh]])
		{
			a[q[hh]]=find(a[d[q[hh]]]-1);gs[a[q[hh]]]++;wz[a[q[hh]]]=q[hh];
		}
		for(i=head[q[hh]];i;i=next[i])q[++tt]=end[i];
		hh++;
	}
	int s=0;
	for(i=1,j=0;i<=n;i++)
	{
		if(!vis[i]){s++;j=i;}
		if(gs[i])
		{
			if(s==1)b[wz[i]]=j;
			s-=gs[i];j=0;
		}
	}
	for(i=1;i<=n;i++)printf("%d\n",b[i]);
	return 0;
}
			

wyr:首先差分，转化为单点（双点？）修改，然后exgcd算出一个合法的解。然后我们能发现答案显然是当\(\sum a[i]=0\)时比较小，然后就可以通过对一些点的答案-b，+a，来靠近这个结果。由于最终的答案就是\(\sum_{a[i]>0}a[i]+\sum_{b[i]>0}b[i]\)，所以只需要每次选对这个值贡献最小的点进行调整就好了。

#include<cstdio>
int n;
long long a,b,x,y,g;
long long h[100011];
long long aa[100011],ab[100011];
long long v[100011],tot;
int hp[100011],th=0;
long long exgcd(long long a,long long b,long long &x,long long &y)
{
	if(b==0){x=1;y=0;return a;}
	long long tt=exgcd(b,a%b,x,y);
	long long t=x;x=y;y=t-a/b*y;
	return tt;
}
long long val(int p)
{
	long long ans=0;
	if(aa[p]-b>0)ans+=aa[p]-b;
	if(ab[p]+a>0)ans+=ab[p]+a;
	if(aa[p]>0)ans-=aa[p];if(ab[p]>0)ans-=ab[p];
	return ans;
}
void pushup(int p)
{
	if(p>1&&v[hp[p/2]]>v[hp[p]]){int t=hp[p];hp[p]=hp[p/2];hp[p/2]=t;pushup(p/2);}
}
void pushdown(int p)
{
	int ch=p*2;
	if(ch>th)return;
	if(ch<th&&v[hp[ch+1]]<v[hp[ch]])ch++;
	if(v[hp[ch]]<v[hp[p]]){int t=hp[p];hp[p]=hp[ch];hp[ch]=t;pushdown(ch);}
}
int main()
{
	int i,j,k;
	scanf("%d%lld%lld",&n,&a,&b);
	if(a>b){long long t=a;a=b;b=t;}
	for(i=1;i<=n;i++)scanf("%lld",&h[i]);
	n++;
	for(i=n;i>1;i--)h[i]-=h[i-1];
	g=exgcd(a,b,x,y);
	a/=g;b/=g;
	x=(x+b)%b;
	//printf("g=%lld x=%lld y=%lld\n",g,x,y);
	//puts("ok");
	for(i=1;i<=n;i++)
	{
		if(h[i]%g!=0)break;
		h[i]=-h[i]/g;
		aa[i]=x*h[i]%b;
		aa[i]=(aa[i]+b)%b;
		ab[i]=(h[i]-aa[i]*a)/b;
		tot+=aa[i];
		v[i]=val(i);
		hp[++th]=i;pushup(th);
		//printf("i=%d\n",i);
	}
	if(i<=n){puts("-1");return 0;}
	//for(i=1;i<=n;i++)printf("i=%d h[i]=%lld aa[i]=%lld ab[i]=%lld\n",i,h[i],aa[i],ab[i]);
	tot/=b;
	while(tot--)
	{
		i=hp[1];
		aa[i]-=b;ab[i]+=a;
		v[i]=val(i);
		pushdown(1);
	}
	long long s=0;
	for(i=1;i<=n;i++)
	{
		if(aa[i]>0)s+=aa[i];
		if(ab[i]>0)s+=ab[i];
	}
	printf("%lld\n",s);
	return 0;
}
	

bez:如果一个点的值确定了，那么和它在一个连通块的所有点的值都确定了，所以只要对每个连通块中的一点设个x，就可以解出x的范围，就可以算出答案

#include<cstdio>
#include<cmath>
int n,m;
int head[500001],end[6000001],len[6000001],next[6000001],tp=0;
int dad[500001];
int a[500001];
int xmx[500001],xmn[500001];
long long xsa[500001],xsb[500001];
long long zsa[500001],zsb[500001];
void dfs(int p,int d)
{
	int i,j,k;
	//printf("p=%d d=%d\n",p,d);
	zsa[d]+=xsa[p];zsb[d]+=xsb[p];
	if(xsa[p]>0)
	{
		int t=(int)ceil(-1.0*xsb[p]/xsa[p]);
		if(t>xmn[d])xmn[d]=t;
		t=(a[p]-xsb[p])/xsa[p];
		if(t<xmx[d])xmx[d]=t;
	}
	else if(xsa[p]<0)
	{
		int t=(int)ceil(-1.0*xsb[p]/xsa[p]);
		if(t<xmx[d])xmx[d]=t;
		t=(a[p]-xsb[p])/xsa[p];
		if(t>xmn[d])xmn[d]=t;
	}
	else if(!(xsb[p]>=0&&xsb[p]<=a[p])){xmx[d]=xmn[d]-1;}
	for(i=head[p];i;i=next[i])
	{
		if(!dad[end[i]])
		{
			xsa[end[i]]=-xsa[p];xsb[end[i]]=len[i]-xsb[p];dad[end[i]]=d;
			dfs(end[i],d);
		}
		else
		{
			if(xsa[p]+xsa[end[i]]!=0)
			{
				int t=(int)ceil(1.0*(len[i]-xsb[p]-xsb[end[i]])/(xsa[p]+xsa[end[i]]));
				if(t>xmn[d])xmn[d]=t;
				t=(len[i]-xsb[p]-xsb[end[i]])/(xsa[p]+xsa[end[i]]);
				if(t<xmx[d])xmx[d]=t;
			}
			else if(xsb[p]+xsb[end[i]]!=len[i])xmx[d]=xmn[d]-1;
		}
	}
}
	
int main()
{
	int i,j,k;
	scanf("%d%d",&n,&m);
	long long s=0;
	for(i=1;i<=n;i++){scanf("%d",&a[i]);s+=a[i];}
	for(i=1;i<=m;i++)
	{
		int x,y,z;
		scanf("%d%d%d",&x,&y,&z);
		next[++tp]=head[x];head[x]=tp;end[tp]=y;len[tp]=z;
		next[++tp]=head[y];head[y]=tp;end[tp]=x;len[tp]=z;
	}
	for(i=1;i<=n;i++)if(!dad[i])
	{
		xsa[i]=1;xsb[i]=0;xmx[i]=a[i];xmn[i]=0;dad[i]=i;
		dfs(i,i);
	}
	//for(i=1;i<=n;i++)printf("i=%d xsa[i]=%lld xsb[i]=%lld\n",i,xsa[i],xsb[i]);
	long long amx=0,amn=0;
	int fl=0;
	for(i=1;i<=n;i++)if(dad[i]==i)
	{
		if(xmx[i]<xmn[i]){fl=1;break;}
		if(zsa[i]>=0)
		{
			amx+=xmx[i]*zsa[i]+zsb[i];
			amn+=xmn[i]*zsa[i]+zsb[i];
		}
		else
		{
			amn+=xmx[i]*zsa[i]+zsb[i];
			amx+=xmn[i]*zsa[i]+zsb[i];
		}
	}
	if(fl)puts("NIE");else printf("%lld %lld\n",s-amx,s-amn);
	return 0;
}
		
		

hur:从前往后贪心，能取就取，不能取就尝试把取了的数中最大的换成它

#include<cstdio>
#include<algorithm>
int n,a[250001],b[250001];
int h[250001],tp=0;
void pushup(int p)
{
	if(p==1)return;
	if(b[h[p/2]]<b[h[p]]){int t=h[p/2];h[p/2]=h[p];h[p]=t;pushup(p/2);}
}
void pushdown(int p)
{
	int ch=p*2;
	if(ch>tp)return;
	if(ch<tp&&b[h[ch+1]]>b[h[ch]])ch++;
	if(b[h[p]]<b[h[ch]]){int t=h[p];h[p]=h[ch];h[ch]=t;pushdown(ch);}
}
int main()
{
	int i,j,k;
	scanf("%d",&n);
	for(i=1;i<=n;i++)scanf("%d",&a[i]);
	for(i=1;i<=n;i++)scanf("%d",&b[i]);
	long long s=0;
	for(i=1;i<=n;i++)
	{
		s+=a[i];
		if(s>=b[i])
		{
			s-=b[i];
			h[++tp]=i;
			pushup(tp);
		}
		else
		{
			if(b[h[1]]>b[i])
			{
				s+=b[h[1]]-b[i];
				h[1]=i;
				pushdown(1);
			}
		}
	}
	std::sort(h+1,h+tp+1);
	printf("%d\n",tp);
	for(i=1;i<=tp;i++)printf("%d ",h[i]);puts("");
	return 0;
}

pre:如果s[1..i]==s[n-i+1..n]&&s[i+1..j]==s[n-j+1..n-i]那么j就是一个合法的答案。用f[i]表示满足s[i..j]==s[n-j+1..n-i+1]的最大的(j-i+1)，那么可以证明f[i-1]<=f[i]+2，于是就可以利用hash在线性时间内求出f，然后枚举每一位计算答案就好了。

#include<cstdio>
#include<cstring>
const int mod=998244353;
int n;
char s[1000002];
long long hsh[1000001],pw[1000001];
int f[1000001];
long long gethsh(int b,int e){return (hsh[e]-hsh[b-1]*pw[e-b+1]%mod+mod)%mod;}
int min(int a,int b){return a>b?b:a;}
int main()
{
	int i,j,k;
	scanf("%d%s",&n,s+1);
	pw[0]=1;
	for(i=1;i<=n;i++)
	{
		pw[i]=pw[i-1]*233%mod;
		hsh[i]=(hsh[i-1]*233%mod+s[i]-'a')%mod;
		//printf("pw[%d]=%lld hsh[%d]=%lld\n",i,pw[i],i,hsh[i]);
	}
	i=n/2;
	if(s[i]==s[n-i+1])f[i]=1;else f[i]=0;
	for(i=n/2-1;i>=1;i--)
	{
		for(j=min(f[i+1]+2,n/2-i+1);j>0&&gethsh(i,i+j-1)!=gethsh(n-i+1-j+1,n-i+1);j--);
		f[i]=j;
	}
	int ans=0;
	for(i=n/2;i>=1;i--)if(gethsh(1,i-1)==gethsh(n-i+2,n))
	{
		if(f[i]+i-1>ans)ans=f[i]+i-1;
		//printf("i=%d f[i]=%d\n",i,f[i]);
	}
	printf("%d\n",ans);
	return 0;
}