POI2011
T1 Tree Rotations 写了个暴力归并然后T了，我只能想到Splay啊，可别人代码都这么短。。
还是乖乖地写了下Splay,代码也不长，不过是在搞不懂最短的不到1K是怎么做到的，写Splay这道题就比较直观了，只要暴力把小的合到大的上面然后统计答案就可以了
#include<cstdio>
#include<cstdio>
#include<algorithm>
#define N 222222
using namespace std;
typedef long long LL;
int n,x,top,a[N],b[N];LL ans;
void get(){
int i,j,k,l,r,mid;LL now=0;
scanf("%d",&x);
if(!x){
l=top+1;get();mid=top;get();r=top;
for(k=l,j=mid+1,i=l;i<=mid;b[k++]=a[i],i++)
for(;j<=r&&a[j]<a[i];b[k++]=a[j++])now+=(LL)(mid-i+1);
for(;j<=r;b[k++]=a[j++]);
for(k=l;k<=r;k++)a[k]=b[k];
ans+=min(now,(LL)(mid-l+1)*(LL)(r-mid)-now);
}else a[++top]=x;
}
int main(){
scanf("%d",&n);get();
printf("%lld",ans);
}
#include<cstdio>
#include<algorithm>
#define N 2222222
using namespace std;
typedef long long LL;
int n,x,y,tot,top,fa[N],sz[N],q[N],c[N][2],val[N];LL ans,now;
void ps(int x){sz[x]=sz[c[x][0]]+sz[c[x][1]]+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 &rt){for(;y=fa[x];R(x))if(fa[y])R((x==c[y][0])==(y==c[fa[y]][0])?y:x);ps(x);rt=x;}
void Nw(int &x,int la,int key){x=++tot;fa[x]=la;val[x]=key;sz[x]=1;}
void ins(int key,int &rt){
int x=rt;for(;c[x][key<val[x]];x=c[x][key<val[x]]);
Nw(c[x][key<val[x]],x,key);sy(c[x][key<val[x]],rt);now+=sz[c[rt][0]];
}
void tr(int x){if(!x)return;q[++top]=val[x];tr(c[x][0]);tr(c[x][1]);}
int get(){
scanf("%d",&x);
if(!x){
int l=get(),r=get();LL sum=(LL)sz[l]*(LL)sz[r];if(sz[l]<sz[r])swap(l,r);now=0;top=0;
tr(r);sort(q+1,q+top+1);for(int i=1;i<=top;i++)ins(q[i],l);ans+=min(now,sum-now);return l;
}else{val[++tot]=x;sz[tot]=1;return tot;}
}
int main(){scanf("%d",&n);get();printf("%lld",ans);}
T2 Difference 每次维护出$cnt[i]-cnt[j]-(cnt[i2]-cnt[j2])$，可以维护出$cnt[i]-cnt[j]$的最小值，就可以快速转移了
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int n,i,j,c,ans,f[27][27],g[27][27];char s[1001000];
int main(){
scanf("%d%s",&n,s+1);
for(i=1;i<=n;i++){
c=s[i]-'a';
for(j=0;j<26;j++){
f[c][j]++;f[j][c]--;
if(!g[j][c])g[j][c]=1;
if(g[j][c]==2){g[j][c]--;f[j][c]++;}
if(f[j][c]<=-1){f[j][c]=-1;g[j][c]=2;}
if(g[j][c])ans=max(ans,f[j][c]);
if(g[c][j])ans=max(ans,f[c][j]);
}
}
printf("%d",ans);
}
T3 Shift 先把$1~n-2$暴力调整到相应位置，如果符合则直接输出，否则如果是奇数不合法，偶数把$n$不断往前跳得到正确答案，WA了好久，后来发现步数>n要取模，而且模为0还要删去。。
#include<cstdio>
#define N 2222
int n,i,u,x,y,t,tp,pt,a[N*N],b[N*N];
int abs(int x){return x>0?x:-x;}
void add(int x){x*b[tp]>0?b[tp]+=x:b[++tp]=x;}
void c1(){u=(u-1+n)%n;add(1);}
void c2(){
x=(u+1)%n;y=(u+2)%n;t=a[u];
a[u]=a[y];a[y]=a[x];a[x]=t;
add(-1);
}
void c3(){u=(u+1)%n;add(n-1);}
int main(){
for(scanf("%d",&n);i<n;i++)scanf("%d",&a[i]);
for(i=2;i<n-1;i++){
for(;a[u]!=i;c1());
for(;a[(u-1+n)%n]!=i-1;){
c1();
if(a[(u-1+n)%n]!=i-1)c1(),c2();else c2(),c2();
}
}
for(;a[u]!=1;c1());
if(a[(u+n-1)%n]!=n){
if(n&1)return puts("NIE DA SIE"),0;
for(c1();a[(u+1)%n]!=n;)c2(),c2(),c3(),c3();
for(;a[u]!=1;)c1();
}
for(i=1;i<=tp;i++)if(abs(b[i])%n!=0)a[++pt]=abs(b[i])%n,b[pt]=b[i]>0?1:0;
for(printf("%d\n",pt),i=1;i<=pt;i++)printf("%d",a[i]),printf("%c ",b[i]?'a':'b');
}
T4 Conspiracy 先2-SAT构造一组方案，然后要调整的话肯定最多只能调整一对，可以求出每个调整影响到的人，如果>1则不合法，如果没有影响到人则把答案加上，影响到则把两个人一起改的答案加上，不过要注意一个块只有1个人的时候要特判
#include<cstdio>
#define N 5050
int n,m,i,j,t,x,ans,c0,c1,g[N][N],q[N<<1],a[N],b[N];bool v[N<<1];
int dfs(int x){
if(v[x>n?x-n:x+n])return 0;
if(v[x])return 1;v[q[++t]=x]=1;
if(x>n){for(int i=1;i<=n;i++)if(i!=x-n&&g[x-n][i])if(!dfs(i))return 0;}
else for(int i=1;i<=n;i++)if(i!=x&&!g[x][i])if(!dfs(i+n))return 0;
return 1;
}
int main(){
for(scanf("%d",&n),i=1;i<=n;i++)for(scanf("%d",&m);m--;g[i][x]=1)scanf("%d",&x);
for(i=1;i<=n;i++)if(!v[i]&&!v[i+n])
if(t=0,!dfs(i)){
for(;t;v[q[t--]]=0);
if(!dfs(i+n))return puts("0"),0;
}
for(i=1;i<=n;i++)if(v[i])c0++;else c1++;
for(i=1;i<=n;i++)if(v[i])for(j=1;j<=n;j++)if(!v[j]&&g[i][j])if(!a[i])a[i]=j;else a[i]=-1;
for(i=1;i<=n;i++)if(!v[i])for(j=1;j<=n;j++)if(v[j]&&!g[i][j])if(!b[i])b[i]=j;else b[i]=-1;
for(i=1;i<=n;i++)if(v[i])ans+=!a[i]&&c0>1;else ans+=!b[i]&&c1>1;
for(i=1;i<=n;i++)if(v[i])for(j=1;j<=n;j++)if(!v[j]&&(!a[i]||a[i]==j)&&(!b[j]||b[j]==i))ans++;
printf("%d",ans+(c0&&c1));
}
T5 Lightning Conductor 一开始化出了式子$max(a[j]+\sqrt{abs(i-j)})-a[i]$，但感觉无从下手，试了下斜率优化发现不可行，又回去想了一天多，还是没想出来，只好去看题解。这原来是一道不用斜率优化的1D1D单调性优化，和NOI2009的诗人小G差不多。。单调性DP优化几乎都忘光了。。差不多就是对于区间$[l,r]$都用值$p$来更新答案。。
对于这道题$\sqrt{x}-\sqrt{x-1}$单调递减，如果$k<j<i$且对于$i$而言$j$比$k$优，$k$就是无用的。。
维护很多个区间三元组${p,l,r}$,对于每个插入的$i$，他能管得区间一定是$[x,n]$
如果对于$n$，当前$i$比队尾更优，就把队尾弹出，最后的队尾$(p,l,r)$满足在$l$上$p$比$i$优，在$r$上$i$比$p$优，可以二分查找这个分界点$x$
然后将队尾变成$(p,l,x-1)$,然后将$(i,x+1,n)$加入，这样就完成了单调性DP优化，这也差不多是单调性DP的基本步骤。。斜率优化如果想不出不妨想想单调性优化。。
#include<cstdio>
#include<cmath>
#include<algorithm>
#define N 500500
using namespace std;
double f[N],g[N];
int n,i,l,r,mid,a[N];
struct data{int p,l,r;}q[N];
double cal(int j,int i){return a[j]+sqrt(abs(i-j))-a[i];}
void dp(double *f){
for(int h=1,t=0,i=1;i<=n;i++){
q[h].l++;if(h<=t&&q[h].l>q[h].r)h++;
if(h>t||cal(i,n)>cal(q[t].p,n)){
for(;h<=t&&cal(i,q[t].l)>cal(q[t].p,q[t].l);t--);
if(h>t)q[++t]=(data){i,i,n};else{
l=q[t].l;r=q[t].r;
while(l<r){
mid=l+r>>1;
if(cal(q[t].p,mid)>cal(i,mid))l=mid+1;else r=mid;
}
q[t].r=l-1;q[++t]=(data){i,l,n};
}
}
f[i]=cal(q[h].p,i);
}
}
int main(){
scanf("%d",&n);for(i=1;i<=n;i++)scanf("%d",&a[i]);
dp(f);reverse(a+1,a+n+1);dp(g);
for(i=1;i<=n;i++)printf("%d\n",(int)ceil(max(f[i],g[n-i+1])));
}
T6 Lollipop 首先所有前缀和都是可行的，然后对于每个数找到他右边最多有几个2，然后对每个2进行如下判定，如果1位置后面的2数量比i后面的2少，就向右移动$ex[1]$位，否则就向右移$ex[i]$位，但如果超过$n$就是不合法的
#include<cstdio>
#define N 2001000
int n,m,i,sum,x,l[N],r[N],ex[N];char s[N];
int main(){
scanf("%d%d%s",&n,&m,s+1);
for(i=n;i;i--)s[i]=='W'?ex[i]=0:ex[i]=ex[i+1]+1;
for(i=1;i<=n;i++){
sum+=s[i]=='W'?1:2;
l[sum]=1;r[sum]=i;
if(s[i]=='T'){
if(ex[1]<ex[i])l[sum-1]=ex[1]+2,r[sum-1]=i+ex[1];else
if(i+ex[i]!=n+1)l[sum-1]=ex[i]+1,r[sum-1]=i+ex[i];
}
}
while(m--){
scanf("%d",&x);
if(x>sum||!l[x])puts("NIE");else printf("%d %d\n",l[x],r[x]);
}
}
T7 Temperature 一开始写个贪心WA了，后来发现贪心有点不对，要改成单调队列，维护单调上升的l[]值来得到答案
#include<cstdio>
#define N 1111111
int n,i,ans=1,h=1,t,la=1,now,l[N],r[N],q[N];char ch;
int main(){
scanf("%d",&n);
for(i=1;i<=n;i++){
scanf("%d%d",&l[i],&r[i]);
for(;l[q[t]]<=l[i]&&h<=t;t--);
q[++t]=i;now=la;
for(;l[q[h]]>r[i];)now=q[h++]+1;
ans=ans>i-now+1?ans:i-now+1;la=now;
}
printf("%d",ans);
}
T8 Strongbox 很神的题，弄出所有gcd去重后判断。。
#include<cstdio>
#include<algorithm>
using namespace std;
typedef long long LL;
LL m,ans,a[251000];int n,i,tot;
LL gcd(LL a,LL b){return !b?a:gcd(b,a%b);}
void check(LL x){
for(int i=1;i<=tot;i++)if(a[i]%x==0)return;
ans=min(ans,x);
}
int main(){
scanf("%lld%d",&m,&n);ans=m;
for(i=1;i<=n;i++)scanf("%lld",&a[i]),a[i]=gcd(a[i],m);
sort(a+1,a+n);for(i=1;i<n;i++)if(a[i]!=a[i+1])a[++tot]=a[i];
for(i=1;(LL)i*i<=a[n];i++)if(a[n]%i==0){
check(i);check(a[n]/i);
}
printf("%lld",m/ans);
}
T9 Garbage 就是有一些需要改变的边，每次可以改变一个环的状态，求可行解
如果需要改的边的点的度数为奇数则无解，因为每次改变的是一个环
首先如果两个环相交，则多出来的是不必要的，所以每个环一定不相交，可以每次找出一个环然后删掉
于是可以对每个点暴力扩展找环，加一个对走边条件的小优化，时间复杂度就是$O(n+m)$的了
#include<cstdio>
#define M 2001000
int n,m,x,y,p,q,i,t,tot,cnt,scc,fir[M],st[M],pos[M],du[M],a[M],ne[M],la[M];bool is[M],v[M];
void ins(int x,int y){la[++tot]=y;ne[tot]=fir[x];fir[x]=tot;du[x]++;}
int main(){
for(scanf("%d%d",&n,&m),tot=1;m--;){scanf("%d%d%d%d",&x,&y,&p,&q);if(p^q)ins(x,y),ins(y,x);}
for(i=1;i<=n;i++)if(du[i]&1)return puts("NIE"),0;
for(x=1;x<=n;x++)for(st[t=1]=y=x;y;y=q){
for(is[y]=1,q=0,i=fir[y];i;i=ne[i])if(!v[i]){
v[i]=v[i^1]=1;fir[y]=ne[i];
if(is[p=la[i]]){
for(a[++cnt]=q=p;st[t]!=p;is[st[t--]]=0)a[++cnt]=st[t];
pos[++scc]=cnt;
}else q=st[++t]=p;
break;
}
if(!q&&t)q=st[t--];
}
for(printf("%d\n",scc),x=1;x<=scc;printf("%d\n",a[pos[x-1]+1]),x++)for(printf("%d ",pos[x]-pos[x-1]),i=pos[x-1]+1;i<=pos[x];i++)printf("%d ",a[i]);
}
T10 Plot 可以二分每个覆盖圆半径的最大值然后进行判断，进行判断的时候当然不能在没有随机的情况下直接暴力判，要先倍增找到一个合适的范围，然后二分查找这个范围中该半径控制的范围，这样时间复杂度是$O(nlog^2n)$？虽然我觉得是$O(nlg^3n)$，而如果不倍增复杂度是$n^2lgn$的。。反正这题有5分钟的时限，去爆爆OJ的感觉挺好的
#include<cstdio>
#include<cmath>
#include<cstdlib>
#include<algorithm>
#define eps 1e-9
#define N 100010
using namespace std;
int n,m,i,cnt,ans[N][2];
double l,r,mid,R;
struct P{double x,y;}a[N],b[N],O;
double dis(P x,P y){return sqrt((x.x-y.x)*(x.x-y.x)+(x.y-y.y)*(x.y-y.y));}
P get(P a,P b,P c){
double a1=b.x-a.x,b1=b.y-a.y,c1=(a1*a1+b1*b1)/2,a2=c.x-a.x,b2=c.y-a.y,c2=(a2*a2+b2*b2)/2,d=a1*b2-a2*b1;
return (P){a.x+(c1*b2-c2*b1)/d,a.y+(a1*c2-a2*c1)/d};
}
void cal(int l,int r){
int i,j,k,n=0;
for(i=l;i<=r;i++)a[++n]=b[i];
for(i=2;i<=n;i++)swap(a[1+(rand()%n)],a[i]);
for(O=a[1],R=0,i=2;i<=n;i++)if(R+eps<dis(O,a[i]))
for(O=a[i],R=0,j=1;j<i;j++)if(R+eps<dis(O,a[j]))
for(O=(P){(a[i].x+a[j].x)/2,(a[i].y+a[j].y)/2},R=dis(O,a[i]),k=1;k<j;k++)
if(R+eps<dis(O,a[k]))O=get(a[i],a[j],a[k]),R=dis(O,a[k]);
}
bool ok(double x){
int i,j,l,r,mid,t,sum=0;
for(i=1;i<=n;i=t+1){
for(j=1;i+(1<<j)-1<=n;j++){
cal(i,i+(1<<j)-1);
if(R>x+eps)break;
}
t=i,l=i+(1<<(j-1))-1;r=i+(1<<j)-1;if(r>n)r=n;
while(l<=r){
cal(i,mid=(l+r)>>1);
if(R<x+eps)l=(t=mid)+1;else r=mid-1;
}
if(++sum>m)return 0;
ans[++cnt][0]=i;ans[cnt][1]=t;
}
return 1;
}
int main(){
scanf("%d%d",&n,&m);for(i=1;i<=n;i++)scanf("%lf%lf",&b[i].x,&b[i].y);
cal(1,n);r=R;
if(m>1)for(;r-l>eps;cnt=0)if(ok(mid=(l+r)/2))r=mid;else l=mid;
ok(r);printf("%.8lf\n%d\n",r,cnt);
for(i=1;i<=cnt;i++)cal(ans[i][0],ans[i][1]),printf("%.8lf %.8lf\n",O.x,O.y);
}
T11 Dynamite 先二分爆破的时间，然后贪心，对于每个点，有三种情况，一种是子树中有选择的点还有对上面的贡献，一种是子树中还有未覆盖到的关键点，还有一种是既没有贡献点也没有关键点，贪心进行三种情况的转移，如果能利用贡献尽量利用贡献，不能了再选该点为关键点
#include<cstdio>
#include<algorithm>
#define N 300030
using namespace std;
int n,m,x,y,tot,cnt,ans,l,r,mid,i,a[N],fir[N],ne[N<<1],la[N<<1],f[N],st[N];
void ins(int x,int y){la[++tot]=y;ne[tot]=fir[x];fir[x]=tot;}
void dfs(int x,int fa,int lim){
int i,y,n1=-1,n2=a[x]-1;
for(i=fir[x];i;i=ne[i]){
y=la[i];
if(y!=fa){
dfs(y,x,lim);
if(st[y]==0)n1=max(n1,f[y]-1);else
if(st[y]==1)n2=max(n2,f[y]+1);
}
}
if(n1<n2)if(n2==lim)cnt++,f[x]=lim,st[x]=0;else f[x]=n2,st[x]=1;
else if(n1!=-1)f[x]=n1,st[x]=0;else f[x]=0,st[x]=2;
}
bool ok(int x){cnt=0;dfs(1,0,x);if(st[1]==1)cnt++;return cnt<=m;}
int main(){
scanf("%d%d",&n,&m);for(i=1;i<=n;i++)scanf("%d",&a[i]);
for(i=1;i<n;i++)scanf("%d%d",&x,&y),ins(x,y),ins(y,x);
for(l=0,r=n;l<=r;){
mid=l+r>>1;
if(ok(mid))ans=mid,r=mid-1;else l=mid+1;
}
printf("%d",ans);
}
T12 Inspection 坚挺了15S WA了，本地数据都过的，真是搞不懂。。大概就是求出每个点到其他点的距离和-到最远点的距离，但是最大子树$*2=n$时要特判一下，只能从最大子树中找最大直径。。原来是$n=1$的情况没有忒判
#include<cstdio>
#include<algorithm>
#define N 1001000
using namespace std;
typedef long long LL;LL go[N],ans,now;bool flag;
int n,i,tot,x,y,up[N],ma[N],fa[N],to[N],ne[N<<1],la[N<<1],fir[N],size[N];
void ins(int x,int y){la[++tot]=y;ne[tot]=fir[x];fir[x]=tot;}
void dfs(int x){
size[x]=1;to[x]=0;
for(int i=fir[x];i;i=ne[i]){
int y=la[i];
if(fa[x]!=y){
fa[y]=x;
dfs(y);
to[x]=max(to[y]+1,to[x]);
if(size[y]>ma[x])ma[x]=size[y];
size[x]+=size[y];
go[x]+=go[y]+(LL)size[y];
}
}
if(n-size[x]>ma[x])ma[x]=n-size[x];
}
void dfs2(int x){
if(x!=1)go[x]=go[fa[x]]+(LL)n-(LL)size[x]*2;
int mx1=-1,mx2=-1,now;
for(int i=fir[x];i;i=ne[i]){
int y=la[i];
if(fa[x]!=y){
if(to[y]>mx1)mx2=mx1,mx1=to[y];
else if(to[y]>mx2)mx2=to[y];
}
}
for(int i=fir[x];i;i=ne[i]){
int y=la[i];
if(fa[x]!=y){
if(to[y]==mx1)now=mx2;else now=mx1;
up[y]=max(up[x]+1,max(1,now+2));
dfs2(y);
}
}
}
int main(){
scanf("%d",&n);if(n==1)return puts("0"),0;
for(i=1;i<n;i++)scanf("%d%d",&x,&y),ins(x,y),ins(y,x);
dfs(1);dfs2(1);
for(x=1;x<=n;x++)if(ma[x]*2<=n){
flag=0;now=1e18;
for(i=fir[x];i;i=ne[i]){
int y=la[i];
if(fa[x]==y){
now=min(now,go[x]*2-(LL)up[x]);
if(size[x]*2==n){
flag=1;
printf("%lld\n",go[x]*2-(LL)up[x]);
break;
}
}else{
now=min(now,go[x]*2-(LL)to[y]-1);
if(size[y]*2==n){
flag=1;
printf("%lld\n",go[x]*2-(LL)to[y]-1);
break;
}
}
}
if(!flag)printf("%lld\n",now);
}else puts("-1");
}
T13 Meteors 很容易想到二分时间，但是如果二分时间后对每个国家暴力判显然是不可行的，于是需要CDQ分治
以时间为单位分治，每次把mid时间内完成收集的国家放到一边，剩下的放到另一边，用链表存储每个国家的信息，就可以在$O(mlgmlgk)$之内出解
#include<cstdio>
#define inf 1e9
#define N 333333
typedef long long LL;
int n,m,i,x,k,tot,la[N],ne[N],fir[N],e[N],id[N],L[N],R[N],a[N],ans[N],q1[N],q2[N];
LL sum,cur[N],now[N],c[N];
void add(int x,int z){for(;x<=m;x+=x&-x)c[x]+=z;}
LL que(int x){for(sum=0;x;x-=x&-x)sum+=c[x];return sum;}
void get(int x,int y,int z){add(x,z);add(y+1,-z);}
void solve(int l,int r,int h,int t){
if(l==r){for(int i=h;i<=t;i++)ans[id[i]]=l;return;}
int i,j,w,mid=(l+r)>>1,ln=0,rn=0;
for(i=l;i<=mid;i++)if(L[i]<=R[i])get(L[i],R[i],a[i]);else get(L[i],m,a[i]),get(1,R[i],a[i]);
for(i=h;i<=t;i++){
cur[w=id[i]]=0;
for(j=fir[w];j;j=ne[j]){
cur[w]+=que(la[j]);
if(cur[w]+now[w]>e[w])break;
}
if(cur[w]+now[w]>=e[w])q1[++ln]=w;else q2[++rn]=w,now[w]+=cur[w];
}
for(i=l;i<=mid;i++)if(L[i]<=R[i])get(L[i],R[i],-a[i]);else get(L[i],m,-a[i]),get(1,R[i],-a[i]);
for(i=1;i<=ln;i++)id[h+i-1]=q1[i];
for(i=1;i<=rn;i++)id[h+i+ln-1]=q2[i];
solve(l,mid,h,h+ln-1);solve(mid+1,r,h+ln,t);
}
int main(){
scanf("%d%d",&n,&m);
for(i=1;i<=m;i++)scanf("%d",&x),la[++tot]=i,ne[tot]=fir[x],fir[x]=tot;
for(i=1;i<=n;i++)scanf("%d",&e[i]),id[i]=i;
scanf("%d",&k);
for(i=1;i<=k;i++)scanf("%d%d%d",&L[i],&R[i],&a[i]);
k++;L[i]=1;R[i]=m;a[i]=inf;
solve(1,k,1,n);
for(i=1;i<=n;i++)ans[i]==k?puts("NIE"):printf("%d\n",ans[i]);
}
T14 黄主力做了%%%
T15 Sticks 写了个贪心2100MS被鏼死,把贪心改一下，只要从大到小选就A啦哈哈，虽然跑得超慢，但主要原因是写了个set+堆，想不通为什么这道题没有1K以内的。。
#include<cstdio>
#include<set>
#include<algorithm>
using namespace std;
set<int>st[52];
int n,i,x,p,rt,sz,a,b,c,val[52],ch[52][2];
int merge(int x,int y){
if(!x||!y)return x+y;
if(val[x]<val[y])swap(x,y);
ch[x][1]=merge(ch[x][1],y);
swap(ch[x][0],ch[x][1]);
return x;
}
int main(){
scanf("%d",&n);
for(i=1;i<=n;i++){
scanf("%d",&x);
while(x--){
scanf("%d",&p);
st[i].insert(p);
}
val[i]=*--st[i].end();
rt=merge(rt,i);sz++;
}
while(sz>=3){
a=rt;rt=merge(ch[rt][0],ch[rt][1]);ch[a][0]=ch[a][1]=0;
b=rt;rt=merge(ch[rt][0],ch[rt][1]);ch[b][0]=ch[b][1]=0;
c=rt;rt=merge(ch[rt][0],ch[rt][1]);ch[c][0]=ch[c][1]=0;
if(val[b]+val[c]>val[a])return printf("%d %d %d %d %d %d",a,val[a],b,val[b],c,val[c]),0;
rt=merge(rt,c);rt=merge(rt,b);
st[a].erase(val[a]);
if(st[a].size())val[a]=*--st[a].end(),rt=merge(rt,a);else sz--;
}
puts("NIE");
}
T16 Party 乱写个按度数排序贪心选点的贪心，竟然1A了哈哈。。看了下正解，应该是对不合法点对进行去除就可以了
#include<cstdio>
#include<algorithm>
#define N 3030
#define M 9000200
using namespace std;
int n,m,i,j,x,y,tot,h,fir[N],du[N],a[N],q[N],v[N],ne[M],la[M];
bool flag;bool cmp(int x,int y){return du[x]>du[y];}
void ins(int x,int y){la[++tot]=y;ne[tot]=fir[x];fir[x]=tot;du[x]++;}
int main(){
scanf("%d%d",&n,&m);for(i=1;i<=n;i++)a[i]=i;
for(i=1;i<=m;i++)scanf("%d%d",&x,&y),ins(x,y),ins(y,x);
sort(a+1,a+n+1,cmp);q[1]=a[1];h=1;
for(i=2;i<=n;i++){
if(h>=(n/3))break;
for(j=fir[a[i]];j;j=ne[j])v[la[j]]=i;
flag=1;
for(j=1;j<=h;j++)if(v[q[j]]!=i){flag=0;break;}
if(flag)q[++h]=a[i];
}
for(i=1;i<=h;i++)printf("%d ",a[i]);
}
T17 Programming Contest 写了个费用流动态加边，但正好T了。。本地的数据都能过。。难道歪果仁都会ZKW费用流吗。。难道我vector作死？
#include<cstdio>
#include<cstring>
#include<vector>
#include<algorithm>
#define inf 1e9
#define N 222222
#define M 2222222
using namespace std;
int n,m,i,he,ta,s,t,R,T,k,x,y,sz,ns,ans,flow,sum,tot,p,to[N],o[510],fir[N],dis[N],pre[N],q[M],la[M],ne[M],cos[M],va[M];
bool v[N];vector<int>a[510];vector<int>::iterator it;char ch;
void read(int &x){
for(ch=getchar();ch<'0'||ch>'9';ch=getchar());
for(x=0;ch>='0';ch=getchar())x=x*10+ch-'0';
}
void ins(int x,int y,int fl,int co){
la[tot]=y;ne[tot]=fir[x];cos[tot]=co;va[tot]=fl;fir[x]=tot++;
la[tot]=x;ne[tot]=fir[y];cos[tot]=-co;va[tot]=0;fir[y]=tot++;
}
bool spfa(){
memset(v,0,sizeof(v));
for(i=1;i<=ns;i++)dis[i]=inf;
he=0;ta=1;dis[s]=0;v[s]=1;q[1]=s;
while(he!=ta)
for(i=fir[x=q[he=he%ns+1]],v[x]=0;i;i=ne[i])
if(dis[x]+cos[i]<dis[y=la[i]]&&va[i]){
dis[y]=dis[x]+cos[pre[y]=i];
if(!v[y])v[q[ta=ta%ns+1]=y]=1;
}
if(dis[t]==inf)return 0;return 1;
}
void end(){
sum=inf;
for(i=t;i!=s;i=la[pre[i]^1])if(va[pre[i]]<sum)sum=va[pre[i]];
for(i=t;i!=s;i=la[pre[i]^1]){
va[p=pre[i]]-=sum;
va[p^1]+=sum;
ans+=sum*cos[p];
}
p=to[la[pre[t]^1]];o[p]++;to[++ns]=p;
if(o[p]<=sz){
ins(ns,t,1,o[p]);
for(it=a[p].begin();it!=a[p].end();it++)ins(*it,ns,1,0);
}
flow+=sum;
}
int main(){
read(n);read(m);read(R);read(T);read(k);sz=T/R;s=m+1;ns=t=s+1;tot=2;
for(i=1;i<=m;i++)ins(s,i,1,0);
for(i=1;i<=n;i++)to[++ns]=i,o[i]=1,ins(ns,t,1,1);
for(i=1;i<=k;i++)read(x),read(y),a[x].push_back(y),ins(y,x+m+2,1,0);
for(;spfa();end());
printf("%d %d",flow,ans*R);
}
评论 (0)
