原来打算切完再发的。结果发现动力不足，先发出来吧。。

由于放网盘一定不会有人点开看，还是直接上代码吧。。

T1 线段树模板题

#include<cstdio>
#include<algorithm>
using namespace std;
int m,x,n,a,b,y;
int m1[200010],cover[200010];
int ask(int l,int r,int L,int R,int cur)
{
	if(L<=l&&R>=r)return m1[cur];int ans=0,mid=(l+r)>>1;
	if(L<=mid)ans=ask(l,mid,L,R,cur<<1);
	if(R>mid)ans=max(ans,ask(mid+1,r,L,R,cur<<1|1));
	return ans+cover[cur];
}
void add(int l,int r,int L,int R,int cur,int x)
{
	if(L<=l&&R>=r){m1[cur]+=x,cover[cur]+=x;return;}
	int mid=(l+r)>>1;if(L<=mid)add(l,mid,L,R,cur<<1,x);
	if(R>mid)add(mid+1,r,L,R,cur<<1|1,x);
	m1[cur]=max(m1[cur<<1],m1[cur<<1|1])+cover[cur];
}
int main()
{
	scanf("%d%d%d",&m,&x,&n);
	while(n--)
	{
		scanf("%d%d%d",&a,&b,&y);b--;
		if(ask(1,m,a,b,1)+y<=x)
			add(1,m,a,b,1,y),puts("T");
		else puts("N");
	}
}

T2 LCA裸题，写了离线tarjan

#include<cstdio>
#define N 60010
#define M 120010
using namespace std;
int n,i,x,y,dad[N],v[M],ne[M],head[N],tot,cs[N],dfn[N],fa[N],heed[N],ans,l,m,sg;
void add(int x,int y){v[++l]=y;ne[l]=head[x];head[x]=l;}
void ad(int x,int y){v[++l]=y;ne[l]=heed[x];heed[x]=l;}
void dfs(int x)
{
	cs[x]=cs[dad[x]]+1;dfn[x]=++tot;
	for(int i=head[x];i;i=ne[i])
		if(v[i]!=dad[x])dad[v[i]]=x,dfs(v[i]);
}
int find(int x){return fa[x]==x?x:fa[x]=find(fa[x]);}
void ddfs(int x)
{
	fa[x]=x;
	for(int i=heed[x];i;i=ne[i])
		ans-=cs[find(v[i])];
	for(int i=head[x];i;i=ne[i])
		if(v[i]!=dad[x])ddfs(v[i]);
	fa[x]=dad[x];
}
int main()
{
	scanf("%d",&n);
	for(i=1;i<n;i++)
	{
		scanf("%d%d",&x,&y);
		add(x,y),add(y,x);
	}dfs(1);scanf("%d",&m);
	for(i=sg=1;i<=m;i++,sg=x)
	{
		scanf("%d",&x);ans+=cs[x];
		if(dfn[x]>dfn[sg])ad(x,sg);else ad(sg,x);
	}ddfs(1);printf("%d\n",(ans<<1)-cs[sg]+1);
}

T4 i,j扫一扫就好了。。

#include<cstdio>
using namespace std;
int n,tot,a[100010],ans,ap,i,j;
int main()
{
	scanf("%d",&n);
	for(i=0;i<n;i++)
		scanf("%d",&a[i]),tot+=a[i];
	for(i=0,tot>>=1;i<n;i++)
	{
		for(;ap+a[j]<=tot;ap+=a[j],j=(j+1)%n);
		if(ap>ans)ans=ap;ap-=a[i];
	}printf("%d\n",ans);
}

T5 大力DP

#include<cstdio>
using namespace std;
int n,m,e,p,b,i,a[101],f[101][1010],y[5010],x[5010],v[1010],j,ln;
int main()
{
	scanf("%d%d%d%d%d",&n,&m,&e,&p,&b);
	for(i=1;i<=n;i++)scanf("%d",&a[i]);
	f[e][a[e]]=1;
	for(i=1;i<=m;i++)
		scanf("%d%d",&x[i],&y[i]);
	for(i=a[e]+1;i<=b;i++)
		for(j=1;j<=m;j++)
		{
			if(a[x[j]]<=i)if(f[x[j]][i-a[y[j]]])f[y[j]][i]=x[j];
			if(a[y[j]]<=i)if(f[y[j]][i-a[x[j]]])f[x[j]][i]=y[j];
		}
	for(i=p;b;b-=a[i],i=f[i][b+a[i]])v[++ln]=i;
	for(i=ln;i>=1;i--)printf("%d ",v[i]);
}

T6 贪心。分成n/2组，小的一半分别与大的一半组合。

#include<cstdio>
#include<algorithm>
using namespace std;
int n,i,x,ans,a[100010];
int main()
{
	scanf("%d",&n);
	for(i=1;i<=n;i++)
		scanf("%d",&a[i]),ans+=a[i];
	sort(a+1,a+n+1);
	for(i=1;i<=n>>1;i++)
		ans+=a[n-i+1]-a[i];
	printf("%d\n",ans);
}

T7 单调栈

#include<cstdio>
#include<algorithm>
using namespace std;
int n,i,j,top,f[2010],q[2010],ans,x,st[2010];
int main()
{
	scanf("%d",&n);
	for(i=1;i<=n;i++)
	{
		for(j=1;j<=n;j++)
		{
			scanf("%d",&x);if(x)f[j]=0;else f[j]++;q[top+1]=0;
			for(;st[top]>f[j]&⊤top--)
				ans=max(ans,(j-q[top])*st[top]);
			st[++top]=f[j];if(!q[top])q[top]=j;
		}for(;top;top--)ans=max(ans,(n-q[top]+1)*st[top]);
	}printf("%d\n",ans);
}

T8 先列出同余方程，然后把形如%pi^ki的项拿出来，CRT一下，然后再验证是否正确。特判CRT之后是0的情况。

#include<cstdio>
#define N 30
using namespace std;
int n,i,p[N],sg,phi[N],f[N],a[N],tot,j,l,x,ans,g[N];
long long powmod(long long x,int y,int z)
{
	long long ans=1;
	for(;y;y>>=1,x=x*x%z)if(y&1)ans=ans*x%z;return ans;
}
int main()
{
	scanf("%d",&n);
	for(i=2;i<=n;i++)
	{
		if(!phi[i])p[++l]=i,phi[i]=i-1;
		for(j=1;j<=l&&p[j]*i<=n;j++)
			if(i%p[j])phi[i*p[j]]=phi[i]*(p[j]-1);
			else{phi[i*p[j]]=phi[i]*p[j];break;}
	}for(i=1;i<=n;i++)scanf("%d",&x),g[x]=i;
	for(i=sg=1;i<=n;i++)
	{
		x=g[i];
		if(x>sg)for(j=sg;j<=x;j++)f[n-i+1]+=!a[j];
		else{
			for(j=sg;j<=n;j++)f[n-i+1]+=!a[j];
			for(j=1;j<=x;j++)f[n-i+1]+=!a[j];
		}f[n-i+1]%=n-i+1;a[x]=1;sg=x;
	}tot=1;
	for(i=1;i<=l;tot*=j,i++)
		for(j=p[i];j*p[i]<=n;j*=p[i]);
	for(i=1;i<=l;i++)
	{
		for(j=p[i];j*p[i]<=n;j*=p[i]);
		ans=(ans+f[j]*powmod(tot/j,phi[j]-1,j)*(tot/j))%tot;
	}for(i=1;i<=n;i++)if(ans%i!=f[i])break;
	if(i>n)printf("%d\n",(ans+tot-1)%tot+1);else puts("NIE");
}

T9 大力DP

#include<cstdio>
using namespace std;
int i,s,j,q[1010],b,max1;
int n,nn,m,x,y,X[5010],Y[5010],Z[5010],f[2010][1010],l,r,v[5010],ne[5010],head[1010];
void add(int x,int y){v[++l]=y;ne[l]=head[x];head[x]=l;}
int main()
{
	scanf("%d%d%d",&n,&nn,&m);
	while(m--)scanf("%d%d",&x,&y),add(x,y);
	scanf("%d",&m);
	for(i=1;i<=m;i++)scanf("%d%d%d",&X[i],&Y[i],&Z[i]);
	scanf("%d%d",&b,&s);f[0][b]=1;q[r=1]=b;
	for(l=0;l<=r;l++)for(j=head[q[l]];j;j=ne[j])
		if(!f[0][v[j]])f[0][v[j]]=1,q[++r]=v[j];
	for(i=1;i<=s;i++)
	{
		for(j=1;j<=m;j++)if(Z[j]<=i)
			if(f[i-Z[j]][X[j]])f[i][Y[j]]=1;
		for(j=1,l=r=0;j<=n;j++)if(f[i][j])q[++r]=j;
		for(;l<=r;l++)for(j=head[q[l]];j;j=ne[j])
			if(!f[i][v[j]])f[i][v[j]]=1,q[++r]=v[j];
	}for(i=1;i<=nn;i++)
		for(j=max1;j<=s;j++)
			if(f[j][i])max1=j;
	printf("%d\n",s-max1);
}

T10 估计标算是高精度+牛顿迭代取对数？高精度只取最前面几项调用系统log过了。。

#include<cstdio>
#include<cmath>
#define p 32767
using namespace std;
int ans,f[101][10010],ln,tot[10010],k,n,m,l,i,j;
double q,s;
void multi(int *a,int b,int *c)
{
	int i;
	for(i=1;i<=ln;i++)
	{
		c[i]+=a[i]*b;
		c[i+1]=c[i]>>15;c[i]&=p;
	}if(c[ln+1])ln++;
}
void add(int *a,int *b)
{
	int i;
	for(i=1;i<=ln;i++)
	{
		b[i]+=a[i];
		b[i+1]+=b[i]>>15;b[i]&=p;
	}if(b[ln+1])ln++;
}
void del(int *a,int *b)
{
	int i;
	for(i=1;i<=ln;i++)
	{
		b[i]-=a[i];
		if(b[i]<0)b[i+1]--,b[i]+=p;
	}for(;!b[ln];ln--);
}
int main()
{
	scanf("%d%d%d%d",&k,&n,&m,&l);
	tot[ln=1]=f[1][1]=k;l--;
	for(i=2;i<=m;i++)
	{
		multi(tot,k-1,f[i]);add(f[i],tot);
		if(i>l)del(f[i-l],tot);
	}for(i=14;i>=0;i--)if(tot[ln]>>i)break;
	ans=i+ln*15-15;s=1;
	for(;i>=0;i--,s/=2)if(tot[ln]>>i&1)q+=s;
	if(ln>1)for(i=14;i>=0;i--,s/=2)if(tot[ln-1]>>i&1)q+=s;
	printf("%d\n",ans*(n/m)+(int)(log2(q)*(n/m)));
}

T11 在-+之间加左括号，+-之间加右括号就好了。

#include<cstdio>
using namespace std;
int n,i;
char s[1000010];
int main()
{
	scanf("%d",&n);
	for(i=1;i<n;i++)
		scanf("%s",s+i);
	for(i=1;i<n;i++)
	{
		putchar('-');
		if(s[i]!=s[i+1])
		{
			if(s[i]=='+')putchar(')');
			else if(i+1<n)putchar('(');
		}
	}
}

T12 有下界最小流

#include<cstdio>
#include<cstring>
#include<algorithm>
#define INF 1e9
#define N 5010
#define M 1000010
using namespace std;
int hash[N],kt[N],w[N],flag,max1,x;
int n,S,T,i,m,gs[N],head[N],ne[M],v[M],fl[M],ans,flow,now,pre[N],l,cs[N];
void add(int x,int y,int z)
{
	v[++l]=y;ne[l]=head[x];head[x]=l;fl[l]=z;
	v[++l]=x;ne[l]=head[y];head[y]=l;fl[l]=0;
}
void sap()
{
	memset(cs,0,sizeof(cs));hash[0]=T;cs[0]=INF;
	for(i=1;i<=T;i++)kt[i]=head[i];now=S;flow=INF;
	while(cs[S]<=T)
	{
		flag=0;w[now]=flow;
		for(i=kt[now];i;i=ne[i])
			if(fl[i]&&cs[now]==cs[v[i]]+1)
			{
				flow=min(flow,fl[i]);kt[now]=i;
				pre[v[i]]=i;flag=1;now=v[i];
				if(now==T)
				{
					ans-=flow;
					for(;now!=S;now=v[pre[now]^1])
					{
						fl[pre[now]]-=flow;
						fl[pre[now]^1]+=flow;
					}flow=w[now];
				}break;
			}if(flag)continue;max1=0;
		for(i=head[now];i;i=ne[i])
			if(cs[v[i]]<cs[v[max1]]&&fl[i])max1=i;
		kt[now]=max1;if(!(--hash[cs[now]]))return;
		cs[now]=cs[v[max1]]+1;if(max1)hash[cs[now]]++;
		if(now!=S)now=v[pre[now]^1];flow=w[now];
	}
} 
int main()
{
	scanf("%d",&n);S=n+1;T=S+1;l=1;
	for(i=1;i<n;i++)
	{
		scanf("%d",&m);gs[i]+=m;
		while(m--)scanf("%d",&x),add(i,x,INF),gs[x]--;
	}for(i=1;i<n;i++)
	{
		if(gs[i]>0)add(i,T,gs[i]),ans+=gs[i];
		else add(S,i,-gs[i]);
	}sap();printf("%d\n",ans);
}

T13 题目脑子有问题。。要求最优解，但是数据给的就不是最优解。。最优解内存被卡，时间被卡求不出来。所以sort了一下卡了个时求比他提供的解优的解就能过了。题目类似双塔问题。

#include<cstdio>
#include<algorithm>
#define N 50010
#define M 2000010
using namespace std;
bool cmp(int x,int y){return x>y;}
int n,b[M],f[2][N],max1[M],pre[M],a[N],s,tot,l,i,j,m1,pr,sum,biu,g[2][N],ln[2];
int main()
{
	scanf("%d",&n);b[1]=0;max1[0]=-1;
	f[1][0]=l=1;max1[1]=0;pre[1]=0;
	for(i=1;i<=n;i++)
		scanf("%d",&a[i]),sum+=a[i];
	sort(a+1,a+n+1,cmp);
	for(i=1;i<=n;i++,s=!s)
	{
		tot+=a[i];sum-=a[i];
		for(j=0;j<=tot&&j<=sum;j++)
		{
			m1=-1;
			if(f[!s][j+a[i]])
			{
				m1=max1[f[!s][j+a[i]]]+a[i];
				pr=f[!s][j+a[i]];
			}if(j>=a[i])
			{
				if(max1[f[!s][j-a[i]]]>m1&&f[!s][j-a[i]])
				{
					m1=max1[f[!s][j-a[i]]];
					pr=f[!s][j-a[i]];
				}
			}else
			{
				if(max1[f[!s][a[i]-j]]+a[i]-j>m1&&f[!s][a[i]-j])
				{
					m1=max1[f[!s][a[i]-j]]+a[i]-j;
					pr=f[!s][a[i]-j];
				}
			}f[s][j]=f[!s][j];
			if(m1>max1[f[s][j]])
			{
				max1[++l]=m1;b[l]=j;
				pre[l]=pr;f[s][j]=l;
			}
		}if(f[s][0]>1&&l>=800000){s^=1;break;}
	}s=!s;biu=0;
	for(i=f[s][0];pre[i];i=pre[i])
	{
		if(max1[i]==max1[pre[i]])g[biu][++ln[biu]]=b[i]-b[pre[i]];else
		{
			if(max1[i]-max1[pre[i]]==b[pre[i]]-b[i])
				g[!biu][++ln[!biu]]=b[pre[i]]-b[i];
			else g[biu][++ln[biu]]=b[i]+b[pre[i]],biu^=1;
		}
	}printf("%d %d\n",ln[0],ln[1]);
	for(i=1;i<=ln[0];i++)printf("%d ",g[0][i]);puts("");
	for(i=1;i<=ln[1];i++)printf("%d ",g[1][i]);puts("");
}

T14 爆搜+剪枝。具体不说了看代码吧。。又短又快。。

#include<cstdio>
using namespace std;
int n,m,l,p[1000010],k,vis[1000010],ans,i,sg[1000010],ne[1000010],j;
void dfs(int x,int y)
{
	int t1=(n+m)/x,t2=(n-1)/x+1;
	for(int i=y;i<=l&&p[i]<=t1/p[i];i++)dfs(x*p[i],i);
	if(t2<p[y])t2=p[y];if(t1>k)t1=k+1;if(t2>k)t2=k+1;
	if(ne[t2]<=sg[t1])ans+=sg[t1]-ne[t2]+1;
}
int main()
{
	scanf("%d%d%d",&n,&m,&k);p[0]=1e9;ne[1]=1;
	for(i=2;i<=k;i++)
	{
		sg[i]=l;ne[i]=l+1;if(!vis[i])p[++l]=i,sg[i]++;
		for(j=1;j<=l&&p[j]*i<=k&&i%p[j-1];j++)vis[p[j]*i]=1;
	}sg[k+1]=l;ne[k+1]=l+1;dfs(1,1);printf("%d\n",ans+(n==1));
}

T15 由于姿势水平不够看了题解。一个有趣的转换。类似构建笛卡尔树的思路。

#include<cstdio>
#define mod 1000000000
using namespace std;
int i,j,n,pre,f[2][5010],ans,flag;
char s[5];
int main()
{
	scanf("%d%s",&n,s);n--;
	if(s[0]=='-')f[0][1]=1;pre=1;
	for(i=1;i<n;i++,pre^=1)
	{
		scanf("%s",s);flag=s[0]=='+';
		for(j=i+1;j>0;j--)
		{
			if((j&1)==flag)f[pre][j]=0;
			else f[pre][j]=(f[!pre][j-1]+f[!pre][j]+f[pre][j+2])%mod;
		}
	}for(i=n;i>0;i--)(ans+=f[!pre][i])%=mod;
	printf("%d\n",ans);
}

T16 dfs之meet in the middle

#include<cstdio>
#include<algorithm>
using namespace std;
struct mjj{int x,y;}f[1100000],g[1100000];
int n,t,s,T,S,sum,a[50],i,j,k;
bool cmpf(mjj x,mjj y){return x.x<y.x;}
bool cmpg(mjj x,mjj y){return x.x>y.x;}
int main()
{
	scanf("%d",&n);t=n>>1;s=n-t;
	T=1<<t;S=1<<s;
	for(i=0;i<n;i++)scanf("%d",&a[i]);
	scanf("%d",&sum);
	for(i=0;i<t;i++)f[1<<i].x=a[i];
	for(i=1;i<T;i++)
	{
		f[i].x=f[i-(i&-i)].x+f[i&-i].x;
		f[i].y=i;
	}for(i=0;i<s;i++)g[1<<i].x=a[i+t];
	for(i=1;i<S;i++)
	{
		g[i].x=g[i-(i&-i)].x+g[i&-i].x;
		g[i].y=i;
	}sort(f,f+T,cmpf);sort(g,g+S,cmpg);
	for(i=j=0;i<T;i++)
	{
		for(;g[j].x+f[i].x>sum&&j<S;j++);
		if(g[j].x+f[i].x==sum)break;
	}for(k=0;k<t;k++)printf("%d",f[i].y>>k&1);
	for(k=0;k<s;k++)printf("%d",g[j].y>>k&1);
}

由于剩下一题不会做。。所以决定快速完结开新坑。。