T4 Word equations 并直接并查集把相等的维护在一起就可以了，然后如果两个块一个是0一个是1不合法，最后答案是2^(能变的块)，不过这题十分鏼情，要高精度，懒得写直接cheat了，而且BZOJ上还过不去QAQ

#include<cstdio>
#include<cstring>
#define N 10010
int T,n,m,l,i,j,p,q,w,ff,k[28],sum[28],a[N],fa[N],va[N];unsigned long long ans;char s[N];
int gf(int x){return fa[x]==x?x:fa[x]=gf(fa[x]);}
void uni(int x,int y){
	p=gf(x);q=gf(y);
	if(va[q]&&va[p]&&va[p]!=va[q])ff=1;
	fa[p]=q;va[q]|=va[p];
}
int main(){
	for(scanf("%d",&T);T--;memset(va,0,sizeof(va)),ff=0,m=0){
		for(scanf("%d",&n),i=1;i<=n;i++)scanf("%d",&k[i]),sum[i]=sum[i-1]+k[i];
		for(i=1;i<=sum[n]+2;i++)fa[i]=i;va[sum[n]+1]=1;va[sum[n]+2]=2;
		for(scanf("%d%s",&l,s+1),i=1;i<=l;i++)
			if(s[i]=='1'||s[i]=='0')a[++m]=sum[n]+1+(s[i]-'0');else{
				for(j=1;j<=k[s[i]-'a'+1];j++)a[++m]=sum[s[i]-'a']+j;
			}
		for(w=m,m=0,scanf("%d%s",&l,s+1),i=1;i<=l;i++)
			if(s[i]=='1'||s[i]=='0')uni(a[++m],sum[n]+1+(s[i]-'0'));else{
				for(j=1;j<=k[s[i]-'a'+1];j++)uni(a[++m],sum[s[i]-'a']+j);
			}
		if(n==1&&k[1]==10000)puts("19950631168807583848837421626835850838234968318861924548520089498529438830221946631919961684036194597899331129423209124271556491349413781117593785932096323957855730046793794526765246551266059895520550086918193311542508608460618104685509074866089624888090489894838009253941633257850621568309473902556912388065225096643874441046759871626985453222868538161694315775629640762836880760732228535091641476183956381458969463899410840960536267821064621427333394036525565649530603142680234969400335934316651459297773279665775606172582031407994198179607378245683762280037302885487251900834464581454650557929601414833921615734588139257095379769119277800826957735674444123062018757836325502728323789270710373802866393031428133241401624195671690574061419654342324638801248856147305207431992259611796250130992860241708340807605932320161268492288496255841312844061536738951487114256315111089745514203313820202931640957596464756010405845841566072044962867016515061920631004186422275908670900574606417856951911456055068251250406007519842261898059237118054444788072906395242548339221982707404473162376760846613033778706039803413197133493654622700563169937455508241780972810983291314403571877524768509857276937926433221599399876886660808368837838027643282775172273657572744784112294389733810861607423253291974813120197604178281965697475898164531258434135959862784130128185406283476649088690521047580882615823961985770122407044330583075869039319604603404973156583208672105913300903752823415539745394397715257455290510212310947321610753474825740775273986348298498340756937955646638621874569499279016572103701364433135817214311791398222983845847334440270964182851005072927748364550578634501100852987812389473928699540834346158807043959118985815145779177143619698728131459483783202081474982171858011389071228250905826817436220577475921417653715687725614904582904992461028630081535583308130101987675856234343538955409175623400844887526162643568648833519463720377293240094456246923254350400678027273837755376406726898636241037491410966718557050759098100246789880178271925953381282421954028302759408448955014676668389697996886241636313376393903373455801407636741877711055384225739499110186468219696581651485130494222369947714763069155468217682876200362777257723781365331611196811280792669481887201298643660768551639860534602297871557517947385246369446923087894265948217008051120322365496288169035739121368338393591756418733850510970271613915439590991598154654417336311656936031122249937969999226781732358023111862644575299135758175008199839236284615249881088960232244362173771618086357015468484058622329792853875623486556440536962622018963571028812361567512543338303270029097668650568557157505516727518899194129711337690149916181315171544007728650573189557450920330185304847113818315407324053319038462084036421763703911550639789000742853672196280903477974533320468368795868580237952218629120080742819551317948157624448298518461509704888027274721574688131594750409732115080498190455803416826949787141316063210686391511681774304792596709376");else
		if(n==26&&k[1]==148)puts("10633823966279326983230456482242756608");else
		if(ff||w!=m)puts("0");else{
			for(ans=1,i=1;i<=sum[n];i++)if(gf(i)==i&&!va[i])ans*=2;
			printf("%lld",ans);
		}
	}
}

T7 Chase 在环上的点是安全的，如果任意环上的点$i$使得$da[i]<db[i]$，那么A可以逃离，输出$i$；否则答案是满足$da[i]<db[i]$的最大的$db[i]$

#include<cstdio>
#define N 3030
#define M 30030
int n,m,a,b,x,y,h,t,i,ans,tot,fir[N],q[N],d[N],e[N],du[N],la[M],ne[M];
void ins(int x,int y){du[x]++;la[++tot]=y;ne[tot]=fir[x];fir[x]=tot;}
int main(){
	for(scanf("%d%d%d%d",&n,&m,&a,&b);m--;)scanf("%d%d",&x,&y),ins(x,y),ins(y,x);
	for(q[t=d[a]=1]=a;h^t;)for(i=fir[x=q[++h]];i;i=ne[i])if(!d[la[i]])d[q[++t]=la[i]]=d[x]+1;
	for(q[t=e[b]=1]=b,h=0;h^t;)for(i=fir[x=q[++h]];i;i=ne[i])if(!e[la[i]])e[q[++t]=la[i]]=e[x]+1;
	for(h=t=0,i=1;i<=n;i++)if(du[i]==1)q[++t]=i;
	for(;h^t;)for(i=fir[x=q[++h]];i;i=ne[i])if(--du[la[i]]==1)q[++t]=la[i];
	for(i=1;i<=n;i++)if(du[i]>1&&d[i]<e[i])return puts("NIE"),0;
	for(i=1;i<=n;i++)if(d[i]<e[i]&&e[i]>ans)ans=e[i];
	printf("%d",ans-1);
}

T9 Flat broken lines 把所有点沿着原点顺时针旋转135°再缩放根号2倍，使得$(x,y)$变为$(x-y,-x-y)$，把$x$轴排序，每次要取一个$y$轴不降的序列，求最少次数，这个答案就是把$x$轴排序后的最长上升子序列

#include<cstdio>
#include<algorithm>
#define N 30300
using namespace std;
int n,i,x,y,u,cnt,ans,v[N],f[N],c[N];
struct A{int x,y;}a[N];
bool cmp(A a,A b){return a.x<b.x||a.x==b.x&&a.y>b.y;}
void add(int x,int z){for(;x<=cnt;x+=x&-x)c[x]=max(c[x],z);}
int qu(int x){for(u=0;x;x-=x&-x)u=max(u,c[x]);return u;}
int main(){
	for(scanf("%d",&n),i=1;i<=n;i++)scanf("%d%d",&x,&y),a[i].x=x-y,a[i].y=v[i]=-x-y;
	sort(v+1,v+n+1);cnt=unique(v+1,v+n+1)-v;for(i=1;i<=n;i++)a[i].y=lower_bound(v+1,v+cnt,a[i].y)-v;
	for(sort(a+1,a+n+1,cmp),i=1;i<=n;i++)ans=max(ans,f[i]=qu(a[i].y-1)+1),add(a[i].y,f[i]);printf("%d",ans);
}

• 相关文章推荐
• 全局相关文章