POI2008

orz hhw posted @ 2017年11月22日 22:52 in 做题记录 with tags 解题报告 POI , 1258 阅读

T1 砖块 虽然是一道傻逼题,但是看别人代码都这么长,我也就傻逼地写了个平衡树,很久没写权值平衡树的我竟然1A了,爽~看来平衡树还真是不容易写错啊

#include<cstdio>
#include<algorithm>
#define N 100100
#define inf 1e9
using namespace std;typedef long long LL;
int n,k,i,rt,x,y,tot,u,a[N],sz[N],fa[N],c[N][2],val[N];LL ans,sum[N];
void ps(int k){int l=c[k][0],r=c[k][1];sum[k]=(LL)val[k]+sum[l]+sum[r];sz[k]=sz[l]+sz[r]+1;}
void R(int x){
    int y=fa[x],k=(c[y][0]==x);
    c[y][!k]=c[x][k];fa[c[x][k]]=y;
    fa[x]=fa[y];c[fa[y]][c[fa[y]][1]==y]=x;
    c[x][k]=y;fa[y]=x;ps(y);
}
void sy(int x,int g){for(;(y=fa[x])!=g;R(x))if(fa[y]!=g)R((x==c[y][0])==(y==c[fa[y]][0])?y:x);ps(x);if(!g)rt=x;}
void nn(int &x,int la,int va){x=++tot;fa[x]=la;val[x]=sum[x]=va;sz[x]=1;c[x][0]=c[x][1]=0;}
void ins(int va){
	for(x=rt;c[x][va>val[x]];x=c[x][va>val[x]]);
	nn(c[x][va>val[x]],x,va);sy(c[x][va>val[x]],0);
}
void del(int va){
	for(x=rt;val[x]!=va;x=c[x][va>val[x]]);
	sy(x,0);for(u=c[rt][1];c[u][0];u=c[u][0]);
	sy(u,rt);c[u][0]=c[rt][0];fa[c[rt][0]]=u;fa[u]=0;rt=u;
}
LL find(int k){
	for(x=rt;sz[c[x][0]]!=k;)if(k<=sz[c[x][0]])x=c[x][0];else k-=sz[c[x][0]]+1,x=c[x][1];
	sy(x,0);return sum[c[x][1]]+(LL)val[x]*(sz[c[x][0]]-1)-sum[c[x][0]]-(LL)val[x]*(sz[c[x][1]]-1)-2ll*inf;
}
int main(){
	for(scanf("%d%d",&n,&k),i=1;i<=n;i++)scanf("%d",&a[i]);
	for(ins(inf),ins(-inf),ans=1e17,i=1;i<=n;i++){
		ins(a[i]);if(i>k)del(a[i-k]);
		if(i>=k)ans=min(ans,find((k+1)/2));
	}printf("%lld",ans);
}

T2 海报 首先宽度可以忽略,要想省下矩形,肯定要有相同高度的,可以用一个单调栈维护一个单调下降的高度,每次把要加的高度加入队尾,如果和队尾不同则ans++

#include<cstdio>
int n,x,t,ans,q[250010];
int main(){
	for(scanf("%d",&n);n--;){
		scanf("%d%d",&x,&x);
		for(;x<q[t];t--);
		if(x>q[t])ans++,q[++t]=x;
	}printf("%d",ans);
}

T4 CLO 网络流加了个读入优化还是没卡过去QAQ

只好写了个并查集,大概就是一个联通块如果有$\geq n$条边就是有解的,两个联通块合并时如果任意一个联通块有解则合并的联通块有解,这样就可以在$O(n)$的时间内出解了。。不过话说回来这题n才100000,为什么网络流跑不过去呢?

#include<cstdio>
#include<cstring>
#define N 333333
#define M 1666666
int n,m,s,t,tot,i,u,flow,now,tmp,x,y,ans,fir[N],cur[N],pre[N],d[N],num[N],la[M],va[M],ne[M];bool v[N];char ch;
void read(int &x){
    for(ch=getchar();ch<'0'||ch>'9';ch=getchar());
    for(x=0;ch>='0'&&ch<='9';ch=getchar())x=x*10+ch-'0';
}
void ins(int x,int y){
    la[++tot]=y;ne[tot]=fir[x];fir[x]=tot;va[tot]=1;
    la[++tot]=x;ne[tot]=fir[y];fir[y]=tot;va[tot]=0;
}
bool dfs(int x){
    v[x]=1;if(x==t)return 1;
    for(int i=fir[x];i;i=ne[i])
        if(va[i]&&!v[la[i]]){
            pre[la[i]]=i;
            if(dfs(la[i]))return 1;
        }
    return 0;
}
int main(){
	for(read(n),read(m),s=n+m+1,t=s+1,tot=i=1;i<=n;i++)ins(s,i);
	for(i=1;i<=m;i++)read(x),read(y),ins(x,i+n),ins(y,i+n),ins(i+n,t);
	for(;dfs(s);ans++){
        for(i=t;i!=s;i=la[pre[i]^1])va[pre[i]]^=1,va[pre[i]^1]^=1;
        memset(v,0,sizeof(v));
    }
	puts(ans==n?"TAK":"NIE");
}
#include<cstdio>
#define N 100100
int n,m,i,x,y,p,q,fa[N];bool ok[N];
int gf(int x){return fa[x]==x?x:fa[x]=gf(fa[x]);}
int main(){
	for(scanf("%d%d",&n,&m),i=1;i<=n;i++)fa[i]=i;
	for(;m--;){
		scanf("%d%d",&x,&y),p=gf(x),q=gf(y);
		if(p==q)ok[p]=1;else fa[p]=q,ok[q]|=ok[p];
	}
	for(i=1;i<=n;i++)if(!ok[gf(i)])return puts("NIE"),0;
	puts("TAK");
}

T5 激光发射器 直接输出n/2就行啦

#include<cstdio>
int main(){int n;scanf("%d",&n);printf("%d",n/2);}

T6 账本BBB 首先可以$O(n)$预处理出从每个点开始转一圈会出现的最小前缀和,并求出最少要变得步数,然后枚举每个点作为起点,如果要把减变加就在前面加,对答案有相应贡献,把加变减在后面减,对答案无影响,如果此时最小前缀和仍小于$0$,就还要变$2*(\frac{1+x}{2})$次,于是$O(n)$就可以出解

#include<cstdio>
#include<cmath>
#include<algorithm>
#include<cstring>
#define N 2002000
using namespace std;typedef long long LL;
int n,p,q,x,y,i,h,t,wil,Q[N],b[N],sum[N];char s[N];LL ans,cost;
int main(){
	for(scanf("%d%d%d%d%d%s",&n,&p,&q,&x,&y,s+1),i=n<<1;i>n;i--)sum[i]=sum[i+1]+(s[i-n]=='-'?-1:1);
	for(i=n;i;i--)sum[i]=sum[i+1]+(s[i]=='-'?-1:1);
	for(h=1,t=0,i=n<<1;i;i--){
		for(;h<=t&&sum[Q[t]]<sum[i];t--);
		for(Q[++t]=i;Q[h]-i>n&&h<=t;h++);
		if(i<=n)b[i]=sum[i]-sum[Q[h]];
	}
	wil=(q-p-sum[n+1])>>1;
	for(ans=1e17,i=1;i<=n;i++){
		cost=(LL)(n-i+1)%n*y+(LL)abs(wil)*x;
		b[i]+=p+max(wil,0)*2;
		if(b[i]<0)cost+=(LL)(1-b[i]>>1)*x*2;
		ans=min(ans,cost);
	}
	printf("%lld",ans);
}

T7 BLO 今天刚学了双联通分量,就做到这道题。只要把割点找出然后求出每个割点的贡献即可,每个割点的贡献为割点割的块大小的和平方-平方和+割点割的块大小*剩余的大小

#include<cstdio>
#include<algorithm>
#define N 101000
#define M 1001000
using namespace std;typedef long long LL;
int n,m,x,y,i,tot,tm,sz[N],fir[N],dfn[N],low[N],la[M],ne[M];LL ans[N];
void ins(int x,int y){la[++tot]=y;ne[tot]=fir[x];fir[x]=tot;}
void dfs(int x){
	dfn[x]=low[x]=++tm;sz[x]=1;int i,y,now=0;
	for(i=fir[x];i;i=ne[i]){
		if(dfn[y=la[i]])low[x]=min(low[x],dfn[y]);else{
			dfs(y);sz[x]+=sz[y];
			low[x]=min(low[x],low[y]);
			if(dfn[x]<=low[y])ans[x]+=(LL)now*sz[y],now+=sz[y];
		}
	}
	ans[x]+=(LL)now*(n-now-1);
}
int main(){
	for(scanf("%d%d",&n,&m);m--;)scanf("%d%d",&x,&y),ins(x,y),ins(y,x);
	for(dfs(1),i=1;i<=n;i++)printf("%lld\n",(ans[i]+n-1)*2);
}

T8 枪战 首先考虑最小死亡人数,首先入度为0的不会死,然后入度为0的点把其出点打死,此时入度为0的点不会死,用一个队列不断处理就能得到树上的答案,对于一个环,最后存活的人数是$\frac{cnt+1}{2}$;考虑最大死亡人数,如果一个联通块只有一个人那么必须死,如果是一个环只有一个活,如果是一棵树只有入度为0的人活

#include<cstdio>
#include<cstring>
#define N 1001000
int n,i,h,t,x,ans1,ans2,cnt,top,sz,tot,w,st[N],du[N],to[N],q[N],fir[N],la[N<<1],ne[N<<1];bool ff,v[N],dead[N];
void ins(int x,int y){la[++tot]=y;ne[tot]=fir[x];fir[x]=tot;}
int main(){
	for(scanf("%d",&n),i=1;i<=n;i++)scanf("%d",&to[i]),du[to[i]]++;
	for(i=1;i<=n;i++)if(!du[i])q[++t]=i;
	while(h!=t){
		v[x=q[++h]]=1;
		if(!dead[to[x]]){
			v[to[x]]=dead[to[x]]=1;
			ans1++;
			if(!--du[to[to[x]]])q[++t]=to[to[x]];
		}
	}
	for(i=1;i<=n;i++)if(!v[i]){
		for(cnt=0,x=i;!v[x];x=to[x])v[x]=1,cnt++;
		ans1+=cnt+1>>1;
	}
	printf("%d ",ans1);
	memset(v,0,sizeof(v));memset(du,0,sizeof(du));
	for(i=1;i<=n;i++)du[to[i]]++,ins(i,to[i]),ins(to[i],i);
	for(i=1;i<=n;i++)if(!v[i]){
		for(top=h=0,ff=1,v[q[t=1]=x=i]=1;h!=t;){
			x=q[++h];st[++top]=x;
			for(w=fir[x];w;w=ne[w])if(!v[la[w]])v[la[w]]=1,q[++t]=la[w];
		}
		if(top==1)ans2++;else{
			for(cnt=0,sz=top;top;cnt+=du[st[top--]]==0);
			if(!cnt)ans2+=sz-1;else ans2+=sz-cnt;
		}
	}
	printf("%d",ans2);
}

T9 Poc 首先把字符串哈希,然后离散化,对于相同哈希值的字符串建立平衡树,平衡树支持插入、删除和全部更新最大值,要注意特判$x1==x2$的情况

#include<cstdio>
#include<map>
#include<algorithm>
#define S 1000000009
#define N 200100
using namespace std;typedef unsigned long long LL;map<LL,int>mp;
int n,m,p,i,j,x,Q,x1,y1,x2,y2,ans,tot,y,v,rt[N],sz[N],lz[N],ms[N],fa[N],c[N][2];
LL pw[110],hs[1010],h1,h2;char s[1010][110];
#define O c[x][0]
#define P c[x][1]
void down(int x){
	if(lz[x]){
		if(O)lz[O]=max(lz[O],lz[x]),ms[O]=max(ms[O],lz[x]);
		if(P)lz[P]=max(lz[P],lz[x]),ms[P]=max(ms[P],lz[x]);
		lz[x]=0;
	}
}
void up(int &k,int s){lz[k]=max(lz[k],s);ms[k]=max(ms[k],s);}
void R(int x){
    int y=fa[x],k=(c[y][0]==x);down(y);down(x);
	c[y][!k]=c[x][k];fa[c[x][k]]=y;
    fa[x]=fa[y];if(fa[y])c[fa[y]][c[fa[y]][1]==y]=x;
    c[x][k]=y;fa[y]=x;
}
void sy(int x,int g,int &rt){for(down(x);(y=fa[x])!=g;R(x))if(fa[y]!=g)R((x==c[y][0])==(y==c[fa[y]][0])?y:x);if(!g)rt=x;}
void ins(int &RT,int p,int sz){for(x=RT;P;x=P);sy(x,0,RT);c[x][1]=p;fa[p]=x;up(RT,sz);}
void del(int &RT,int x){
     sy(x,0,RT);for(p=O;c[p][1];p=c[p][1]);
     if(p){
	 	sy(p,x,RT);RT=p;
     	if(P)fa[P]=RT;
     	fa[RT]=0,c[RT][1]=P;
     }else RT=P,fa[P]=0;
     O=P=0; 
}
int main(){
	for(scanf("%d%d%d",&n,&m,&Q),pw[m]=1,i=m-1;i;i--)pw[i]=pw[i+1]*S;
	for(i=1;i<=n;i++){
		for(scanf("%s",s[i]+1),j=1;j<=m;j++)hs[i]=hs[i]*S+s[i][j];
		v=mp[hs[i]];if(v)ins(rt[v],i,++sz[v]);else v=mp[hs[i]]=++tot,sz[v]=1,rt[v]=i,up(rt[v],1);
	}
	for(;Q--;){
		scanf("%d%d%d%d",&x1,&y1,&x2,&y2);
		if(x1==x2){
			v=mp[hs[x1]];del(rt[v],x1);if(!--sz[v])mp[hs[x1]]=rt[v]=0;
			hs[x1]=hs[x1]+pw[y1]*(s[x2][y2]-s[x1][y1])+pw[y2]*(s[x1][y1]-s[x2][y2]);
			v=mp[hs[x1]];if(v)ins(rt[v],x1,++sz[v]);else v=mp[hs[x1]]=++tot,sz[v]=1,rt[v]=x1,up(rt[v],1);
			swap(s[x1][y1],s[x2][y2]);continue;
		}
		h1=hs[x1]+pw[y1]*(s[x2][y2]-s[x1][y1]);h2=hs[x2]+pw[y2]*(s[x1][y1]-s[x2][y2]);
        v=mp[hs[x1]];del(rt[v],x1);if(!--sz[v])mp[hs[x1]]=rt[v]=0;
        v=mp[hs[x2]];del(rt[v],x2);if(!--sz[v])mp[hs[x2]]=rt[v]=0;
        v=mp[h1];if(v)ins(rt[v],x1,++sz[v]);else v=mp[h1]=++tot,sz[v]=1,rt[v]=x1,up(rt[v],1);
		v=mp[h2];if(v)ins(rt[v],x2,++sz[v]);else v=mp[h2]=++tot,sz[v]=1,rt[v]=x2,up(rt[v],1);
		hs[x1]=h1;hs[x2]=h2;swap(s[x1][y1],s[x2][y2]);
	}
	for(i=1;i<=n;i++)v=mp[hs[i]],sy(i,0,rt[v]),printf("%d\n",ms[i]);
}

T10 Uci 考虑矩形肯定是不断变小的,于是可以用$f[l][r][u][d][0~3]$表示矩形的范围和当前所在的边,不过暴力转移的复杂度是$n^5$的,不过发现转移可以前缀和优化一下,就变成$n^4$的了,再加个滚动数组就A了

#include<cstdio>
#include<cstring>
#include<algorithm>
#define N 110
using namespace std;
int n,m,M,x,y,i,j,l,r,u,d,le,ri,up,dw,x1,x2,y1,y2,p,tot,ans,f,v[N][N],v1[N][N],v2[N][N],g[2][N][N][N][4];char s[N];
int add(int &x,int z){x=(x+z)%M;}
int main(){
	for(scanf("%d%d%d%d%d",&n,&m,&M,&y,&x),i=1;i<=n;i++)
		for(scanf("%s",s+1),j=1;j<=m;j++)v[i][j]=s[j]=='*';
	if(v[x][y])return puts("0"),0;v[x][y]=2;
	for(i=1;i<=n+1;i++)for(j=1;j<=m+1;j++)v1[i][j]=v1[i][j-1]+v[i][j],v2[i][j]=v2[i-1][j]+v[i][j];
	le=y-1;ri=m+1-y;up=x;dw=n+1-x;tot=le+ri+up+dw;g[tot&1][ri][up][dw][0]=1;
	for(i=tot;i>=0;i--)
		for(f=i&1,r=min(ri,i);r>=0;r--)
			for(u=min(up,i-r);u>=0;u--)
				for(d=min(dw,i-r-u);d>=0;d--){
					l=i-r-u-d;
					if(l>le)break;
					x1=x-u;x2=x+d;y1=y-l;y2=y+r;
					for(j=0;j<4;j++)if(p=g[f][r][u][d][j]){
						if(j==0){//向上走
							if(u)add(g[f^1][r][u-1][d][0],p);
							if(u&&v2[x2-1][y1]-v2[x1][y1]==0)add(g[f^1][r][u-1][d][1],p);
							if(v[x1+1][y1]==2&&v2[x2][y1]-v2[x1+1][y1]==0)add(ans,p);
						}else if(j==1){//向右走
							if(r)add(g[f^1][r-1][u][d][1],p);
							if(r&&v1[x1][y2-1]-v1[x1][y1]==0)add(g[f^1][r-1][u][d][2],p);
							if(v[x1][y2-1]==2&&v1[x1][y2-2]-v1[x1][y1]==0)add(ans,p);
						}else if(j==2){//向下走
							if(d)add(g[f^1][r][u][d-1][2],p);
							if(d&&v2[x2-1][y2]-v2[x1][y2]==0)add(g[f^1][r][u][d-1][3],p);
							if(v[x2-1][y2]==2&&v2[x2-2][y2]-v2[x1][y2]==0)add(ans,p);
						}else{//向左走
							if(l)add(g[f^1][r][u][d][3],p);
							if(l&&v1[x2][y2-1]-v1[x2][y1]==0)add(g[f^1][r][u][d][0],p);
							if(v[x2][y1+1]==2&&v1[x2][y2]-v1[x2][y1+1]==0)add(ans,p);
						}
						g[f][r][u][d][j]=0;
					}
				}
	printf("%d",ans);
}

T11 KUP 考虑去掉$\geq k$的点,剩下的点都是$<k$的,把$>k*2$的点挖掉,弄出每一块合法的区间,如果一块区间是$\geq k$且$\leq k*2$的则一定合法,每次把上面一行或下面一行较小的删去,就能得到答案

#include<cstdio>
#include<algorithm>
#define N 2010
typedef long long LL;
LL sum[N][N];
int k,n,i,j,top,st[N],l[N],r[N],h[N],a[N][N];
LL gsum(int x1,int y1,int x2,int y2){return sum[x2][y2]-sum[x1-1][y2]-sum[x2][y1-1]+sum[x1-1][y1-1];  }
void print(int x1,int y1,int x2,int y2){
	for(;gsum(x1,y1,x2,y2)>k*2;)if(x1==x2)y2--;else if(gsum(x1+1,y1,x2,y2)>=k)x1++;else x2--;
	printf("%d %d %d %d",y1,x1,y2,x2);exit(0);
}
void get(int x){
	int i;for(top=0,i=1;i<=n+1;st[++top]=i++)for(;top&&h[st[top]]>h[i];)r[st[top--]]=i-1;
	for(top=0,i=n;~i;st[++top]=i--)for(;top&&h[st[top]]>h[i];)l[st[top--]]=i+1;
	for(i=1;i<=n;i++)if(h[i])if(gsum(x-h[i]+1,l[i],x,r[i])>=k)print(x-h[i]+1,l[i],x,r[i]);
}
int main(){
	for(scanf("%d%d",&k,&n),i=1;i<=n;i++)for(j=1;j<=n;j++){
		scanf("%d",&a[i][j]);
		if(a[i][j]>=k&&a[i][j]<=k*2)return printf("%d %d %d %d",j,i,j,i),0;
		sum[i][j]=sum[i][j-1]+sum[i-1][j]-sum[i-1][j-1]+a[i][j];
	} 
	for(i=1;i<=n;get(i),i++)for(j=1;j<=n;j++)h[j]=a[i][j]>k*2?0:h[j]+1;
	puts("NIE");
}

T12 Lam 这种傻逼题懒得写高精,反正POI上前几个点能过就行了

#include<cstdio>
typedef long long LL;
int i,n,a[100100];
struct P{LL x,y;}now,p,ans[100100];
LL gcd(LL a,LL b){return !b?a:gcd(b,a%b);}
LL get(P &a){
	LL u=gcd(a.x,a.y);
	a.x/=u;a.y/=u;
}
int main(){
	for(scanf("%d",&n),i=1;i<=n;i++)scanf("%d",&a[i]);
	for(p.x=p.y=1,i=n;i;i--){
		now=p;now.y*=a[i];get(now);ans[i]=now;
		p.x=p.x*a[i]-p.x;p.y*=a[i];get(p);
	}
	for(i=1;i<=n;i++)printf("%lld/%lld\n",ans[i].x,ans[i].y);
}

T13 Per(未完成) 一道超级神题,数学水平太低,看论文都看不懂QAQ

#include<cstdio>
#include<algorithm>
#define fo(i,u,d) for (int i=u;i<=d;i++)
#define maxn 300010
using namespace std;
int n,m,ans,all=0,now,maxm=0,p,sum,maxe;
int prime[50][4];
int v[maxn],d[maxn],num[maxn][3],f[19][maxn];
long long mul;
void mult(int x){now+=num[x][2];mul=mul*num[x][0]%p;}
void div(int x){now-=num[x][2];mul=mul*num[x][1]%p;}
void chg(int x,int ty){
	 int t=v[x];
 	 if (t==0)return;maxe=max(maxe,num[t][2]);
	 for(int i=x;i<=maxm;i+=i&-i)f[num[t][2]][i]=(f[num[t][2]][i]+num[t][0]*ty+p)%p;
}
int cal(int t,int x){
	int s=0;
	for(int i=x;i;i-=i&-i)s=(s+f[t][i])%p;
	return s;
}
void exgcd(int a,int b,long long &x,long long &y){if(b==0)x=1,y=0;else{exgcd(b,a%b,x,y);long long xx=x;x=y;y=xx-a/b*y;}}
int calc(int a,int m){
	long long x,y;
	exgcd(a,m,x,y);
	return (x%m+m)%m;
}
int count(int pp,int e){
	int pe[30];
	pe[0]=1;fo(i,1,e)pe[i]=pe[i-1]*pp;
	maxe=0;
	fo(i,1,n){
		num[i][0]=i;num[i][2]=0;
		while(num[i][0]%pp==0){
			num[i][0]/=pp;
			num[i][2]++;
		}
		maxe=max(maxe,num[i][2]);
		num[i][1]=calc(num[i][0],p);
	}
	mul=sum=1,now=0;
	fo(i,1,n){
		if (i<n)mult(i);
		div(++v[d[i]]);
	}
	fo(i,1,maxm)chg(i,1);
	fo(i,1,n-1){
		fo(j,max(-now,0),min(maxe,e-now-1))
			sum=(sum+mul*cal(j,d[i]-1)%p*pe[j+now])%p;
		div(n-i);
		mult(v[d[i]]);
		chg(d[i],-1);
		v[d[i]]--;
		chg(d[i],1);
	}
	fo(i,1,maxm)chg(i,-1);
	v[d[n]]--;
	return sum;
}
void solve(){
	 int t=m;
	 for(int i=2;i*i<=m;i++)
	 	if (t%i==0){
	 		prime[++all][0]=i;
	 		prime[all][1]=1;
	 		prime[all][2]=0;
	 		while(t%i==0){
	 			t/=i;
	 			prime[all][1]*=i;
	 			prime[all][2]++;
	 		}
	 	}
 	 if (t>1){
 	 	prime[++all][0]=t;
 	 	prime[all][1]=t;
 	 	prime[all][2]=1;
 	 }
 	 fo(i,1,all){
 	 	p=prime[i][1];
 	 	long long tt=count(prime[i][0],prime[i][2]);
 	 	ans=(ans+tt*calc(m/p,p)%m*(m/p))%m;
 	 }
}
int main(){
	scanf("%d%d",&n,&m);
	fo(i,1,n)scanf("%d",d+i),maxm=max(d[i],maxm);
	solve();
	printf("%d\n",ans);
}

T14 POD Subdivision of Kingdom 这题直接暴力要T,要在暴力基础下加一些小优化就能过啦

#include<cstdio>
int n,m,i,x,y,ans,u,T,du[27],a[27];
int calc(int x){for(T=0;x;x>>=1)T+=(x&1);return T;}
void dfs(int x,int left,int now,int sel){
	if(!left){if(now<ans)ans=now,u=sel;return;}
	dfs(x+1,left-1,now+du[x]-2*calc(sel&a[x]),sel|(1<<(x-1)));
	if(n-x>=left)dfs(x+1,left,now,sel);
}
int main(){
	for(scanf("%d%d",&n,&m),ans=2e9;m--;)scanf("%d%d",&x,&y),du[x]++,du[y]++,a[x]|=(1<<(y-1)),a[y]|=(1<<(x-1));
	dfs(2,(n>>1)-1,du[1],1);for(i=1;i<=n;i++)if((1<<(i-1))&u)printf("%d ",i);
}

T15 Sta 傻逼树形DP一道

#include<cstdio>
#define N 1001000
typedef long long LL;LL go[N],ans;
int i,x,y,tot,n,u,fir[N],fa[N],sz[N],la[N<<1],ne[N<<1];
void ins(int x,int y){la[++tot]=y;ne[tot]=fir[x];fir[x]=tot;}
void dfs(int x){
	int i,y;sz[x]=1;
	for(i=fir[x];i;i=ne[i])if(fa[x]!=(y=la[i])){
		fa[y]=x;dfs(y);
		sz[x]+=sz[y];go[x]+=go[y]+(LL)sz[x];
	}
}
void dfs2(int x){
	if(x!=1)go[x]=go[fa[x]]+(LL)n-(LL)sz[x]*2;if(go[x]>ans||go[x]==ans&&x<u)ans=go[x],u=x;
	for(int i=fir[x];i;i=ne[i])if(fa[x]!=la[i])dfs2(la[i]);
}
int main(){
	for(scanf("%d",&n),i=1;i<n;i++)scanf("%d%d",&x,&y),ins(x,y),ins(y,x);
	dfs(1);dfs2(1);printf("%d",u);
}

T16 Tro 暴力枚是$n^3$的,考虑选取一个点$a$,然后剩下的点的面积为$\sum ((a,x)×(a,y))$,而我们知道×是$x1y2-x2y1$,而$x1$、$y1$固定,只要按$a$的极角排序,然后求出$\sum y2$,$\sum x2$,利用×积,就可以快速出解,复杂度$O(n^2lgn)$

#include<cstdio>
#include<algorithm>
#define N 3030
using namespace std;long long ans,sx,sy;
int n,i,j,tot;struct P{int x,y;}e[N],p[N];
bool cmp(P a,P b){return a.y<b.y||a.y==b.y&&a.x<b.x;}
bool Cmp(P a,P b){return a.x*b.y>a.y*b.x;}
int main(){
	for(scanf("%d",&n),i=1;i<=n;i++)scanf("%d%d",&e[i].x,&e[i].y);sort(e+1,e+n+1,cmp);
	for(i=1;i<=n-2;i++){
		for(sx=sy=0,tot=0,j=i+1;j<=n;j++)p[++tot]=P{e[j].x-e[i].x,e[j].y-e[i].y};
		sort(p+1,p+tot+1,Cmp);
		for(j=1;j<=tot;j++){
			ans+=sx*p[j].y-sy*p[j].x;
			sx+=p[j].x;sy+=p[j].y;
		}
	}printf("%lld.%d",ans/2,ans&1?5:0);
}