快速开坑治疗颓废（看上去这届有不少码农题又可以锻炼代码能力了~）

T1 单调队列，模拟

#include<cstdio>
using namespace std;
int n,m,a[300010],q[300010],s,t,x,top,i;
int main()
{
	scanf("%d%d",&n,&m);
	for(i=1;i<=n;i++)scanf("%d",&a[i]);
	for(i=n;i>=1;i--)
	{
		for(;top&&a[i]<a[q[top]];top--);
		q[++top]=i;
	}s=n+1;t=1;
	while(m--)
	{
		scanf("%d",&x);
		for(;x>a[q[t]]&&t<=top;s=q[t++]);s--;
		if(s==q[t]&&t<=top)t++;
	}if(s>=0)printf("%d\n",s);else puts("0");
}

T2 注意题目给的性质。预处理next数组，然后再处理出每个点最小的next，然后就没了

#include<cstdio>
using namespace std;
int n,ne[1000010],sg[1000010],i,t;
char s[1000010];
long long ans;
int main()
{
	scanf("%d%s",&n,s+1);ne[0]=-1;
	for(i=1;i<=n;i++)
	{
		for(t=ne[i-1];t>=0&&s[t+1]!=s[i];t=ne[t]);
		ne[i]=t+1;if(!sg[ne[i]])sg[i]=ne[i];else sg[i]=sg[ne[i]];
		if(sg[i])ans+=i-sg[i];
	}printf("%lld\n",ans);
}

T3 丧心病狂卡内存。。奇奇怪怪的东西都是在卡内存。。

#include<cstdio>
#include<cstring>
#define N 1000010
using namespace std;
char usa[N],use[N],vis[N],ch;
int v[N],ne[N],head[N],t;
int flag,x,y,l,time,n,m,i,q[N],gs[N],r,j,stack[N],top;
void read(int &x)
{
	for(ch=getchar();ch<'0';ch=getchar());
	for(x=0;ch>='0';ch=getchar())x=x*10+ch-'0';
}
void add(int x,int y){v[++l]=y;ne[l]=head[x];head[x]=l;gs[y]++;}
void change()
{
	memset(stack,0,sizeof(stack));
	memset(gs,0,sizeof(gs));
	for(i=1;i<=n;i++)
		for(j=head[i];j;j=t)
		{
			t=ne[j];ne[j]=stack[v[j]];
			stack[v[j]]=j;gs[i]++;v[j]=i;
		}
	for(i=1;i<=n;i++)head[i]=stack[i];
}
void tarjan(int x)
{
	if(!usa[x]){vis[x]=2;return;}
	int now=++time;q[x]=time;
	vis[x]=1;stack[++top]=x;
	for(int i=head[x];i;i=ne[i])
	{
		if(!vis[v[i]])tarjan(v[i]);
		if(vis[v[i]]<2)
		{
			if(q[v[i]]<=now)use[x]=1;
			if(q[v[i]]<q[x])q[x]=q[v[i]];
		}
	}if(now==q[x])
		for(;stack[top+1]!=x;top--)
			vis[stack[top]]=2;
}
void play()
{
	for(i=1;i<n;i++)if(use[i]&&usa[i])q[++r]=i;
	int ans=0,tot=0;if(r)ans=36501;change();
	for(l=1;l<=r;l++)
		for(i=head[q[l]];i;i=ne[i])
			if(!use[v[i]])use[v[i]]=1,q[++r]=v[i];
	change();
	for(i=1;i<=n;i++)if(use[i])
	{
		gs[i]=36501;
		for(j=head[i];j;j=ne[j])if(!use[v[j]])gs[v[j]]--;
	}for(i=1;i<=n;i++)if(!gs[i]&&usa[i])q[++r]=i;
	for(i=l;i<=r;i++)
		for(j=head[q[i]];j;j=ne[j])
		{
			gs[v[j]]--;
			if(!gs[v[j]]&&usa[v[j]])q[++r]=v[j];
		}gs[n]=1;
	for(i=r;i>=l;i--)
	{
		for(j=head[q[i]];j;j=ne[j])if(usa[v[j]])
			gs[q[i]]+=gs[v[j]];
		if(gs[q[i]]>36500)gs[q[i]]=36501;
		if(gs[q[i]]>ans)ans=gs[q[i]];
	}if(ans<=36500)printf("%d\n",ans);else puts("zawsze");
	for(i=1;i<n;i++)if(gs[i]==ans)++tot;printf("%d\n",tot);
	for(i=1;i<n;i++)if(gs[i]==ans)printf("%d ",i);
}
int main()
{
	read(n);read(m);n++;
	for(i=1;i<=m;i++)read(x),read(y),add(y,x);
	for(usa[q[l=r=1]=n]=1;l<=r;l++)
		for(j=head[q[l]];j;j=ne[j])
			if(!usa[v[j]])usa[v[j]]=1,q[++r]=v[j];
	change();l=r=0;
	for(i=1;i<=n;i++)if(!vis[i])tarjan(i);play();
}

T4 二维的吧。。写KD-tree T了，多半是姿势问题，后来写了个树套树渣渣版。。

#include<cstdio>
#include<algorithm>
using namespace std;
int D,S,n,d,s,x,y,w,ans;
int sum[2][2100][2100],cov[2][2100][2100];
int find1(int l,int r,int L,int R,int cur1,int cur,int t)
{
	if(L<=l&&R>=r)return sum[t][cur1][cur];
	int mid=(l+r)>>1,ans=cov[t][cur1][cur];
	if(L<=mid)ans=max(ans,find1(l,mid,L,R,cur1,cur<<1,t));
	if(R>mid)ans=max(ans,find1(mid+1,r,L,R,cur1,cur<<1|1,t));
	return ans;
}
int find(int l,int r,int L,int R,int a,int b,int cur)
{
	if(L<=l&&R>=r)return find1(1,S,a,b,cur,1,0);
	int mid=(l+r)>>1,ans=find1(1,S,a,b,cur,1,1);
	if(L<=mid)ans=max(ans,find(l,mid,L,R,a,b,cur<<1));
	if(R>mid)ans=max(ans,find(mid+1,r,L,R,a,b,cur<<1|1));
	return ans;
}
void add1(int l,int r,int L,int R,int cur1,int cur,int t,int w)
{
	if(w>sum[t][cur1][cur])sum[t][cur1][cur]=w;
	if(L<=l&&R>=r)
	{
		if(w>cov[t][cur1][cur])cov[t][cur1][cur]=w;
		return;
	}int mid=(l+r)>>1;
	if(L<=mid)add1(l,mid,L,R,cur1,cur<<1,t,w);
	if(R>mid)add1(mid+1,r,L,R,cur1,cur<<1|1,t,w);
}
void add(int l,int r,int L,int R,int a,int b,int cur,int w)
{
	add1(1,S,a,b,cur,1,0,w);
	if(L<=l&&R>=r){add1(1,S,a,b,cur,1,1,w);return;}
	int mid=(l+r)>>1;
	if(L<=mid)add(l,mid,L,R,a,b,cur<<1,w);
	if(R>mid)add(mid+1,r,L,R,a,b,cur<<1|1,w);
}
int main()
{
	scanf("%d%d%d",&D,&S,&n);
	while(n--)
	{
		scanf("%d%d%d%d%d",&d,&s,&w,&x,&y);
		w+=find(1,D,x+1,x+d,y+1,y+s,1);
		if(w>ans)ans=w;
		add(1,D,x+1,x+d,y+1,y+s,1,w);
	}printf("%d\n",ans);
}

T5 首先把每个点的最小距离处理出来，然后并查集就好了。。处理最小距离看上去好小是v图，但是时间不够？？然后写了个乱搞。。

#include<cstdio>
#include<cstring>
#include<algorithm>
#define get(a,b) (a<<10|b)
#define gx(a) ((a)>>10)
#define gy(a) ((a)&1023)
#define gxz(a,b) (gx(a)-gx(b))
#define gyz(a,b) (gy(a)-gy(b))
#define len(a,b) (gxz(a,b)*gxz(a,b)+gyz(a,b)*gyz(a,b))
#define X 1024
#define N 1100000
#define M 6100000
using namespace std;
int n,m,x,y,S,T,u,lab[N],q[M],ux,uy,xx,yy,zz,l,r,use[N],qq[N],t;
int dis[N],i,j,s,R,ne[N],head[N<<1],maxn,dad[N],flag;
char ch;
int find(int x){return dad[x]==x?x:dad[x]=find(dad[x]);}
void read(int &x)
{
	for(ch=getchar();ch<'0';ch=getchar());
	for(x=0;ch>='0';ch=getchar())x=x*10+ch-'0';
}
void gb(int x,int y)
{
	use[x]=0;
	if(gx(x)>1)
	{
		u=x-X;t=len(u,y);
		if(dis[u]>t)
		{
			lab[u]=y;dis[u]=t;
			if(!use[u])use[u]=1,q[++r]=u;
		}
	}if(gx(x)<n)
	{
		u=x+X;t=len(u,y);
		if(dis[u]>t)
		{
			lab[u]=y;dis[u]=t;
			if(!use[u])use[u]=1,q[++r]=u;
		}
	}if(gy(x)>1)
	{
		u=x-1;t=len(u,y);
		if(dis[u]>t)
		{
			lab[u]=y;dis[u]=t;
			if(!use[u])use[u]=1,q[++r]=u;
		}
	}if(gy(x)<m)
	{
		u=x+1;t=len(u,y);
		if(dis[u]>t)
		{
			lab[u]=y;dis[u]=t;
			if(!use[u])use[u]=1,q[++r]=u;
		}
	}
}
void biu(int x,int y)
{
	if(gx(x)>1)if(use[u=x-X]!=y)
	{
		t=len(u,y);
		s=max(abs(gxz(u,y)),abs(gyz(u,y)));
		if(dis[u]>t)lab[u]=y,dis[u]=t;
		if(dis[u]>t-s)qq[++r]=u;use[u]=y;
	}if(gx(x)<n)if(use[u=x+X]!=y)
	{
		t=len(u,y);
		s=max(abs(gxz(u,y)),abs(gyz(u,y)));
		if(dis[u]>t)lab[u]=y,dis[u]=t;
		if(dis[u]>t-s)qq[++r]=u;use[u]=y;
	}if(gy(x)>1)if(use[u=x-1]!=y)
	{
		t=len(u,y);
		s=max(abs(gxz(u,y)),abs(gyz(u,y)));
		if(dis[u]>t)lab[u]=y,dis[u]=t;
		if(dis[u]>t-s)qq[++r]=u;use[u]=y;
	}if(gy(x)<m)if(use[u=x+1]!=y)
	{
		t=len(u,y);
		s=max(abs(gxz(u,y)),abs(gyz(u,y)));
		if(dis[u]>t)lab[u]=y,dis[u]=t;
		if(dis[u]>t-s)qq[++r]=u;use[u]=y;
	}
}
int main()
{
	memset(dis,63,sizeof(dis));
	read(n);read(m);read(x);read(y);S=get(x,y);
	read(x);read(y);read(s);T=get(x,y);
	while(s--)
	{
		read(x);read(y);u=get(x,y);
		dis[u]=0;lab[u]=u;q[++r]=u;
	}R=r;
	for(l=1;l<=r;l++)gb(q[l],lab[q[l]]);
	memset(use,0,sizeof(use));
	for(i=1;i<=R;i++)
	{
		use[q[i]]=q[i];
		for(qq[l=r=1]=q[i];l<=r;l++)
			biu(qq[l],q[i]);
	}
	for(i=1;i<=n;i++)
		for(j=1;j<=m;j++)
		{
			u=get(i,j);s=dis[u];
			ne[u]=head[s];head[s]=u;
			if(s>maxn)maxn=s;
		}flag=1;
	for(i=maxn;i>=0&&flag;i--)
		for(j=head[i];j&&flag;j=ne[j])
		{
			dad[j]=j;
			if(gx(j)>1)if(dad[j-X])dad[find(j-X)]=j;
			if(gx(j)<n)if(dad[j+X])dad[find(j+X)]=j;
			if(gy(j)>1)if(dad[j-1])dad[find(j-1)]=j;
			if(gy(j)<m)if(dad[j+1])dad[find(j+1)]=j;
			if(dad[S]&&find(S)==find(T))flag=0;
		}
	printf("%d\n",i+1);
}

T6 先把坐标转换一下，然后求加权中位数，然后再转回来。如果转回来不是整数要判一下怎么扭最优

#include<cstdio>
#include<algorithm>
using namespace std;
int n,i,x[100010],y[100010],z[100010],j,f[100010],g[100010],X,Y;
long long tot,t1,t2;
bool cmp1(int a,int b){return x[a]<x[b];}
bool cmp2(int a,int b){return y[a]<y[b];}
int main()
{
	scanf("%d",&n);
	for(i=1;i<=n;i++)
	{
		scanf("%d%d%d",&X,&Y,&z[i]);
		x[i]=X-Y;y[i]=X+Y;tot+=z[i];f[i]=g[i]=i;
	}sort(f+1,f+n+1,cmp1);sort(g+1,g+n+1,cmp2);
	for(i=1,t1=0;i<=n&&(t1<<1)<tot;i++)t1+=z[f[i]];
	for(j=1,t2=0;j<=n&&(t2<<1)<tot;j++)t2+=z[g[j]];
	X=x[f[i-1]];Y=y[g[j-1]];
	if((X+Y)&1)
	{
		if((t1<<1)<tot+z[f[i-1]])
		{
			if((t2<<1)<tot+z[g[j-1]])t1<t2?X++:Y++;
			else t1+t2<tot+z[g[j-1]]?X++:Y--;
		}else
		{
			if((t2<<1)<tot+z[g[j-1]])t1+t2<tot+z[f[i-1]]?Y++:X--;
			else t1-z[f[i-1]]<t2-z[g[j-1]]?Y--:X--;
		}
	}printf("%d %d\n",(X+Y)>>1,(Y-X)>>1);
} 

T7 KM。费用流会T2333

#include<cstdio>
#include<cstring>
#include<algorithm>
#define INF 1e9
using namespace std;
long long v[210][210],fx[210],fy[210],sl[210],ans;
int n,m,a,b,c,i,j,visy[210],visx[210],dad[210];
bool dfs(int x)
{
	visx[x]=1;
	for(int i=1;i<=n;i++)
		if(!visy[i])
		{
			if(v[x][i]==fx[x]+fy[i])
			{
				visy[i]=1;
				if(!dad[i]||dfs(dad[i]))
				{
					dad[i]=x;
					return 1;
				}
			}else sl[i]=min(sl[i],fx[x]+fy[i]-v[x][i]);
		}return 0;
}
void KM()
{
	for(i=1;i<=n;i++)
		for(j=1;j<=n;j++)
			if(v[i][j]>fx[i])fx[i]=v[i][j];
	for(i=1;i<=n;i++)
	{
		memset(sl,63,sizeof(sl));
		for(;;)
		{
			memset(visx,0,sizeof(visx));
			memset(visy,0,sizeof(visy));
			if(dfs(i))break;int d=1e9;
			for(j=1;j<=n;j++)
				if(sl[j]<d&&!visy[j])d=sl[j];
			for(j=1;j<=n;j++)
				if(visx[j])fx[j]-=d;
			for(j=1;j<=n;j++)
				if(visy[j])fy[j]+=d;
				else sl[j]-=d;
		}
	}for(i=1;i<=n;i++)
		ans+=v[dad[i]][i];
}
int main()
{
	scanf("%d",&n);
	for(i=1;i<=n;i++)
	{
		scanf("%d%d%d%d",&m,&a,&b,&c);
		for(j=a;j<=b;j++)
			v[i][j]=INF-abs(j-m)*c;
	}KM();ans=INF*n-ans;
	if(ans>=INF)puts("NIE");else printf("%lld\n",ans);
}

T8 贪心。考虑一个由2k条触手组成的块一定能分成k条不同的链。然后要最大化这东西。把一条直径拎出来然后贪心选择2k-1条最长的从叶子上来的路径就好了。

#include<cstdio>
#include<algorithm>
#define N 2000010
using namespace std;
int v[N],ne[N],head[N],use[N],rt,j,ans;
int n,k,i,x,y,f[N],a[N],q[N],l,r,b[N],dad[N];
bool cmp(int x,int y){return a[x]>a[y];}
void add(int x,int y){v[++l]=y;ne[l]=head[x];head[x]=l;}
int main()
{
	scanf("%d%d",&n,&k);
	for(i=1;i<n;i++)
	{
		scanf("%d%d",&x,&y);
		add(x,y);add(y,x);
	}use[1]=1;
	for(q[l=r=1]=1;l<=r;l++)
		for(i=head[q[l]];i;i=ne[i])
			if(!use[v[i]])q[++r]=v[i],use[v[i]]=1;
	rt=q[r];k=(k<<1)-1;
	for(q[l=r=1]=rt;l<=r;l++)
		for(i=head[q[l]];i;i=ne[i])
			if(v[i]!=dad[q[l]])dad[v[i]]=q[l],q[++r]=v[i];
	for(i=n;i>=1;i--)
	{
		for(j=head[q[i]];j;j=ne[j])
			if(v[j]!=dad[q[i]]&&a[v[j]]>a[q[i]])
				a[q[i]]=a[v[j]],b[q[i]]=v[j];
		a[q[i]]++;f[i]=i;
	}sort(f+1,f+n+1,cmp);
	for(i=1;i<=n&&k>0;i++)if(a[f[i]])
	{
		ans+=a[f[i]];k--;
		for(j=f[i];j;j=b[j])a[j]=0;
	}printf("%d\n",ans);
}

T9 大力DP

#include<cstdio>
#include<algorithm>
#define N 610
#define M 10010
using namespace std;
int n,x[N],y[N],m,k,i,j,X,Y,f[N][N],tot,g[N][N],ans;
struct mjj{int x,y,z;}a[M];
bool cmp(mjj x,mjj y){return x.x*y.y<x.y*y.x;}
int main()
{
	scanf("%d",&n);
	for(i=1;i<=n;i++)
		scanf("%d%d",&x[i],&y[i]);
	scanf("%d",&m);
	for(i=1;i<=m;i++)
		scanf("%d%d%d",&a[i].x,&a[i].y,&a[i].z);
	for(i=1;i<=n;i++)
	{
		for(j=1;j<=m;j++)
			a[j].x-=x[i],a[j].y-=y[i];
		sort(a+1,a+m+1,cmp);k=1;tot=0;
		for(j=i+1;j<=n;j++)
		{
			X=x[j]-x[i];Y=y[j]-y[i];
			for(;a[k].x*Y<a[k].y*X&&k<=m;k++)tot+=a[k].z;f[i][j]=tot;
			for(;a[k].x*Y==a[k].y*X&&k<=m;k++)tot+=a[k].z;g[i][j]=tot;
		}for(j=1;j<=m;j++)
			a[j].x+=x[i],a[j].y+=y[i];
	}ans=1e-9;
	for(i=1;i<=n;i++)
		for(j=i+1;j<=n;j++)
			for(k=j+1;k<=n;k++)
				ans=max(ans,g[i][k]-f[i][j]-f[j][k]);
	printf("%d\n",ans);
}

T10 把必经路读进来，然后把边和边之间的关系确定，然后把连续的边缩成一条，然后跑欧拉回路。。

#include<vector>
#include<cstdio>
#include<algorithm>
#define N 50010
#define M 200010
using namespace std;
int n,m,b[M],c[M],i,j,st[N],en[N],ne[M],sg[M],t,k,x,Sg,biu;
int gs[N],ds[N],v[M],l,head[N],ss[M],na[M],kt,tot,vis[N];
struct mjj{int x,y;}a[M];
bool cmp(mjj x,mjj y){return x.x==y.x?x.y<y.y:x.x<y.x;}
void add(int x,int y,int z)
{
	gs[x]++;ds[y]++;
	v[++l]=y;na[l]=head[x];
	head[x]=l;ss[l]=z;
}
void dfs(int x)
{
	vector<int>vs;int t,i,s,j,b1=x;
	for(;head[x];)
	{
		vs.push_back(head[x]);t=v[head[x]];
		head[x]=na[head[x]];x=t;
	}if(head[b1])dfs(b1);
	for(i=0;i<vs.size();i++)
	{
		t=vs[i];s=v[vs[i]];
		for(j=ss[t];j;j=ne[j])
			printf("%d\n",a[j].y);
		if(head[s])dfs(s);
	}
}
int find(int x)
{
	int ans=0;vis[x]=1;
	for(int i=head[x];i;i=na[i])
		ans+=vis[v[i]]?1:find(v[i])+1;
	return ans;
}
int main()
{
	scanf("%d%d",&n,&m);
	for(i=1;i<=m;i++)scanf("%d%d",&a[i].x,&a[i].y);
	sort(a+1,a+m+1,cmp);
	for(i=1;i<=m;i++)b[i]=a[i].y;
	for(i=j=1;i<=n;i++)
	{
		st[i]=j;
		for(;a[j].x==i;j++);en[i]=j-1;
	}scanf("%d",&t);
	while(t--)
	{
		scanf("%d%d",&k,&Sg);k--;
		for(i=1;i<=k;i++)
		{
			scanf("%d",&x);
			c[i]=lower_bound(b+st[Sg],b+en[Sg]+1,x)-b;
			if(a[c[i]].y!=x||a[c[i]].x!=Sg)break;Sg=x;
		}if(i<=k)break;
		for(i=1;i<k;i++)
		{
			if(ne[c[i]]&&ne[c[i]]!=c[i+1])break;
			ne[c[i]]=c[i+1];
		}if(i<k)break;
		for(i=2;i<=k;i++)
		{
			if(sg[c[i]]&&sg[c[i]]!=c[i-1])break;
			sg[c[i]]=c[i-1];
		}if(i<=k)break;
	}if(t>=0){puts("NIE");return 0;}
	for(i=1;i<=m;i++)if(!sg[i])
	{
		for(j=i;ne[j];j=ne[j])biu++;
		add(a[i].x,a[j].y,i);biu++;
	}for(i=kt=1;i<=n;i++)if(gs[i]>ds[i])break;
	if(i<=n||find(kt)<l||biu<m){puts("NIE");return 0;}
	puts("TAK");printf("%d\n",kt);dfs(kt);
}

T11 大力DP。。

#include<cstdio>
using namespace std;
int l,r,ans;
int k,m,n,i,j,f[2010][2010],g[2010][2010],ok[2010][2010],x;
int main()
{
	scanf("%d%d%d",&k,&m,&n);
	for(i=1;i<=n;i++)
		for(j=1;j<=m;j++)
		{
			scanf("%d",&x);
			f[i][j]=f[i-1][j]+x;
			g[i][j]=g[i][j-1]+x;
		}ok[0][n]=3;
	for(i=1;i<=n;i++)
	{
		l=1;r=m;
		for(j=n;j>=i;j--)
		{
			for(;f[j][l]-f[i-1][l]<=k&&l<=r;l++);
			for(;f[j][r]-f[i-1][r]<=k&&l<=r;r--);
			ok[i][j]=(g[i][r]-g[i][l-1]<=k)<<1|(g[j][r]-g[j][l-1]<=k);
			if(!((ok[i-1][j]>>1)|(ok[i][j+1]&1)))ok[i][j]=0;
			if(ok[i][j]&&l>r&&j-i>ans)ans=j-i;
		}
	}ok[0][n]=0;ok[0][m]=3;
	for(i=1;i<=m;i++)
	{
		l=1;r=n;
		for(j=m;j>=i;j--)
		{
			for(;g[l][j]-g[l][i-1]<=k&&l<=r;l++);
			for(;g[r][j]-g[r][i-1]<=k&&l<=r;r--);
			ok[i][j]=(f[r][i]-f[l-1][i]<=k)<<1|(f[r][j]-f[l-1][j]<=k);
			if(!((ok[i-1][j]>>1)|(ok[i][j+1]&1)))ok[i][j]=0;
			if(ok[i][j]&&l>r&&j-i>ans)ans=j-i;
		}
	}printf("%d\n",n+m-ans-1);
}

T13 大力DP，前缀最大值优化一下。。

#include<cstdio>
#include<cstring>
#include<algorithm>
#define N 2010
using namespace std;
int n,m,g[N][N],f[N][N],h[N][N],a[N],i,ans,j,k;
int main()
{
	memset(g,63,sizeof(g));memset(h,63,sizeof(h));
	memset(f,63,sizeof(f));ans=2e9;
	scanf("%d%d",&m,&n);m++;g[0][0]=0;
	for(i=1;i<=n;i++)
	{
		scanf("%d",&a[i]);a[i]+=a[i-1]+1;
		for(j=k=i-1;j>=0&&a[i]-a[j]<=m;j--)
		{
			for(;a[i]-a[j]>=a[j]-a[k]&&k>=0;k--);
			f[i][j]=g[j][k+1]+a[i]-a[j];if(!j)f[i][j]=0;
			if(k>=0)f[i][j]=min(f[i][j],h[j][k]+a[j]-a[i]);
			g[i][j]=min(g[i][j+1],f[i][j]-a[i]+a[j]);
		}j++;if(!j)h[i][j]=f[i][j]+a[i]-a[j],j++;
		for(;j<=i;j++)h[i][j]=min(h[i][j-1],f[i][j]+a[i]-a[j]);
	}for(i=0;i<=n;i++)if(f[n][i]<ans)ans=f[n][i];printf("%d\n",ans);
}

T14 考虑数位dp，如果dp到某一位，某个数那位是1，但却选了0，那么剩下的数位就可以任意选，所以一定有解。

#include<cstdio>
using namespace std;
typedef unsigned long long ull;
ull ans,s,t,a[60];
int i,n;
void dfs(int x)
{
	ull s=0,t[3],t1,t2,tt;
	t[0]=1;t[1]=t[2]=0;
	for(i=1;i<=n;i++)
	{
		t1=t[1];t2=t[2];
		tt=(a[i]&((1<<x)-1))+1;
		if(a[i]>>x&1)
		{
			s^=a[i]>>x&1;
			t[1]=t[0]+t2*(1<<x)+t1*tt;
			t[2]=t1*(1<<x)+t2*tt;
		}else t[1]=t1*tt,t[2]=t2*tt;
		t[0]=t[0]*tt;
	}if(!s)
	{
		ans+=t[2];
		if(x)dfs(x-1);else ans++;
	}else ans+=t[1];
}
int main()
{
	scanf("%d",&n);
	for(i=1;i<=n;i++)scanf("%llu",&a[i]);
	dfs(31);printf("%llu\n",ans-1);
}

T15 状压DP。注意滚动数组否则mle

#include<cstdio>
#define mod 1000000
using namespace std;
int n0,n1,n2,n3,f[2][39][39][39][16],ans,i,j,k,l;
int get(int x,int y,int z,int t,int X,int Y)
{
	if(x+y+z+t<=1)return 1;
	ans=f[x&1][y][z][t][(3^X)<<2|Y];
	if((X>>1)!=(Y>>1))ans+=f[x&1][y][z][t][(X^1)<<2|Y];
	if((X&1)!=(Y&1))ans+=f[x&1][y][z][t][(2^X)<<2|Y];
	if((X^3)==Y)ans+=f[x&1][y][z][t][X<<2|Y];
	return ans%mod;
}
int main()
{
	scanf("%d%d%d%d",&n0,&n1,&n2,&n3);
	for(i=0;i<=n0;i++)
	{
		for(j=0;j<=n1;j++)
			for(k=0;k<=n2;k++)
				for(l=0;l<=n3;l++)
				{
					if(i>1)f[i&1][j][k][l][0]=get(i-1,j,k,l,0,0);
					if(i&&j)f[i&1][j][k][l][1]=get(i,j-1,k,l,1,0);
					if(i&&k)f[i&1][j][k][l][2]=get(i,j,k-1,l,2,0);
					if(i&&l)f[i&1][j][k][l][3]=get(i,j,k,l-1,3,0);
					if(j&&i)f[i&1][j][k][l][4]=get(i-1,j,k,l,0,1);
					if(j>1)f[i&1][j][k][l][5]=get(i,j-1,k,l,1,1);
					if(j&&k)f[i&1][j][k][l][6]=get(i,j,k-1,l,2,1);
					if(j&&l)f[i&1][j][k][l][7]=get(i,j,k,l-1,3,1);
					if(k&&i)f[i&1][j][k][l][8]=get(i-1,j,k,l,0,2);
					if(k&&j)f[i&1][j][k][l][9]=get(i,j-1,k,l,1,2);
					if(k>1)f[i&1][j][k][l][10]=get(i,j,k-1,l,2,2);
					if(k&&l)f[i&1][j][k][l][11]=get(i,j,k,l-1,3,2);
					if(l&&i)f[i&1][j][k][l][12]=get(i-1,j,k,l,0,3);
					if(l&&j)f[i&1][j][k][l][13]=get(i,j-1,k,l,1,3);
					if(l&&k)f[i&1][j][k][l][14]=get(i,j,k-1,l,2,3);
					if(l>1)f[i&1][j][k][l][15]=get(i,j,k,l-1,3,3);
				}
	}ans=0;if(n0+n1+n2+n3==1)ans++;
	for(i=0;i<16;i++)ans+=f[n0&1][n1][n2][n3][i];
	printf("%d\n",ans%mod);
}

T16 建trie树跑一炮。。由于其恶意卡内存，就以时间换空间了。。

#include<cstdio>
#define N 2000010
using namespace std;
int n,ne[N],head[N],lab[N],num[N],vis[N],cur,t,i,ln,j,k,T,ss[N],nex[N];
char s[N];
long long ans;
int main()
{
	scanf("%d",&n);nex[0]=-1;
	for(i=1;i<=n;i++)
	{
		scanf("%d%s",&ln,s+1);
		for(j=1;j<=ln;j++)
		{
			for(t=nex[j-1];s[t+1]!=s[j]&&t>=0;t=nex[t]);
			nex[j]=t+1;vis[j]=0;
		}for(j=ln;j;j=nex[j])vis[j]=1;vis[0]=1;
		for(j=1,cur=0;j<=ln;j++)
		{
			for(k=head[cur];k&&lab[k]!=s[j];k=ne[k]);
			if(k)cur=k;else ne[++T]=head[cur],head[cur]=T,cur=T;
			lab[cur]=s[j];if(vis[ln-j])ans+=num[cur],ss[cur]++;
		}num[cur]++;ans+=(ss[cur]-num[cur]);
	}printf("%lld\n",(ans<<1)+n);
}

T17 乱搞，首先度数>=（n-k）都得删，然后删掉之后可以保证所有点的度数sigma必须小于k*(k-1)，于是最多有k*(k-1)个点非0，拿出来，每次选择度数最大的点，判断是否选。如果选的话删掉他，否则删掉所有和他相连的点。时间复杂度2^k*k*k。。还有注意去重边。。

#include<cstdio>
#define M 7000010
#define N 1000010
using namespace std;
int an[N],q[N],i,x,y,s,tot,ne[M],sg[M],use[N];
int l,ans,ln,n,k,m,gs[N],v[M],vis[N],la[N],K,j;
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';
}
void add(int x,int y)
{
	v[++l]=y;sg[ne[x]]=l;ne[l]=ne[x];ne[x]=l;gs[x]++;sg[l]=x;
	v[++l]=x;sg[ne[y]]=l;ne[l]=ne[y];ne[y]=l;gs[y]++;sg[l]=y;
}
void del(int l)
{
	ne[sg[l]]=ne[l];
	if(ne[l])sg[ne[l]]=sg[l];
}
void biu(int x,int y)
{
	if(y>0)vis[x]=-1;else vis[x]=0;
	for(int i=ne[x];i;i=ne[i])gs[v[i]]+=y;
}
void dfs(int x)
{
	if(x<=ans)return;int max1=0,i,s;
	for(i=1;i<=ln;i++)
		if((gs[q[i]]&vis[q[i]])>gs[max1])max1=q[i];
	if(!max1)
	{
		ans=x;
		for(i=1;i<=ln;i++)
			if(!vis[q[i]])an[k-(x++)]=q[i];
		return;
	}biu(max1,-1);dfs(x-1);biu(max1,1);
	if(gs[max1]<=x)
	{
		s=gs[max1];
		for(i=ne[max1];i;i=ne[i])
			if(vis[v[i]])biu(v[i],-1),la[v[i]]=x;
		dfs(x-s);
		for(i=ne[max1];i;i=ne[i])
			if(la[v[i]]==x)biu(v[i],1),la[v[i]]=0;
	}
}
int main()
{
	read(n);read(k);read(m);
	K=k;k=n-k;ans=-1;l=n;
	for(i=1;i<=m;i++)
		read(x),read(y),add(x,y);
	for(i=1;i<=n;i++)
	{
		vis[i]=-1;
		for(j=ne[i];j;j=ne[j])if(!use[v[j]])
			use[v[j]]=1;else del(j),gs[i]--;
		for(j=ne[i];j;j=ne[j])use[v[j]]=0;
	}
	for(;k;k--)
	{
		for(s=1;s<=n;s++)
			if((vis[s]&gs[s])>k)break;
		if(s>n)break;biu(s,-1);
	}for(i=1;i<=n&&tot<=k*(k-1);i++)
	if(vis[i]&gs[i])
	{
		if(gs[s]>k)break;
		q[++ln]=i;tot+=gs[s];
	}if(i<=n||tot>k*(k-1)){puts("NIE");return 0;}
	dfs(k);if(ans<0){puts("NIE");return 0;}
	printf("%d\n",K+ans);
	for(i=1;i+ans<=k;i++)vis[an[i]]=0;
	for(i=1;i<=n;i++)if(vis[i])printf("%d ",i);puts("");
}