POI2008
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);
}
评论 (0)
