一眼题，不解释。。

#include<cstdio>
int n,m,k,ans=0;
int fa[1000001];
struct re{
	int u,v;
} a[2000001];
re b[2000001];
int getfa(int x){return fa[x]==x? x:fa[x]=getfa(fa[x]);}
int main(){
	//freopen("tou1a.in","r",stdin);
	scanf("%d%d%d",&n,&m,&k);
	for (int i=1;i<=n;i++) fa[i]=i;
	for (int i=1;i<=m;i++){
		scanf("%d%d",&a[i].u,&a[i].v);
		if (a[i].u<=k||a[i].v<=k) continue;
		int fx=getfa(a[i].u);
		int fy=getfa(a[i].v);
		if (fx!=fy){
			fa[fx]=fy;
		}
	}
	for (int i=1;i<=m;i++){
		if (a[i].u>k&&a[i].v>k) continue;
		int fx=getfa(a[i].u);
		int fy=getfa(a[i].v);
		if (fx==fy){
			ans++;
			b[ans].u=a[i].u;
			b[ans].v=a[i].v;
		}
		else fa[fx]=fy;
	}
	printf("%d\n",ans);
	for (int i=1;i<=ans;i++) printf("%d %d\n",b[i].u,b[i].v);
}

二分答案+单调队列。。main过了，bzoj无限tle。。。

#include<cstdio>
#include<algorithm>
using namespace std;
typedef long long ll;
int q[1000011];
int n,maxi=0;
int ansx,ansk;
ll m;
int a[1000011];
ll sum[1000011];
ll c[1000011],f[1000011],fr[1000011],fl[1000011],g[1000011];
inline ll min(ll a,ll b){return a<b? a:b;}
inline bool check(int xx){
	ll x=xx;
    int h=0,t=1;
    c[1]=a[1];
    q[t]=1;
    f[1]=0;
    sum[1]=a[1];
    for (int i=2;i<=n;i++){
        sum[i]=sum[i-1]+a[i];
        c[i]=min(c[i-1]+x,a[i]);
        while (h<t&&c[q[t]]+x*q[t]>=c[i]+x*i) t--;
        int j=q[t];
        //printf("i=%d j=%d\n",i,j);
        if (h==t){ f[i]=sum[i]-(c[i]+c[i]+(i-1)*x)*i/2;}
        else { f[i]=sum[i]-sum[j]-(c[i]+c[i]+(i-j-1)*x)*(i-j)/2+f[j];}
        q[++t]=i;
    }
    //for (int i=1;i<=n;i++) printf("f[%d]=%I64d ",i,f[i]);
    //printf("\n");
    //for (int i=1;i<=n;i++) printf("c[%d]=%I64d\n",i,c[i]);
    h=0;  t=1;  q[1]=1; fl[1]=a[1];
    for (int i=2;i<=n;i++){
        while (h+1<t&&c[q[h+2]]+q[h+2]*x<=i*x) h++;
        int j=q[h+1];
        if (c[q[h+1]]+q[h+1]*x>i*x){fl[i]=sum[i]-(i-1)*x*i/2;}
        else {fl[i]=sum[i]-sum[j]-(i-j-1)*x*(i-j)/2+f[j];}
        while (h<t&&c[q[t]]+q[t]*x>=c[i]+i*x) t--;
        q[++t]=i;
    }
    //for (int i=1;i<=n;i++) printf("fl[%d]=%I64d ",i,fl[i]);
    //printf("\n");
    h=0; t=1; c[n]=a[n];  q[t]=n;  g[n]=0;
    sum[n]=a[n];
    for (int i=n-1;i>=1;i--){
        sum[i]=sum[i+1]+a[i];
        c[i]=min(c[i+1]+x,a[i]);
        while (h<t&&c[q[t]]-x*q[t]>=c[i]-x*i) t--;
        int j=q[t];
        if (h==t){ g[i]=sum[i]-(c[i]+c[i]+(n-i)*x)*(n-i+1)/2;}
        else { g[i]=sum[i]-sum[j]-(c[i]+c[i]+(j-i-1)*x)*(j-i)/2+g[j];}
        q[++t]=i;
    }
    //for (int i=1;i<=n;i++) printf("g[%d]=%I64d ",i,g[i]);
    //printf("\n");
    h=0;  t=1;  q[1]=n; fr[n]=a[n];
    ll ans=fr[n]+fl[n]-a[n];
    for (int i=n-1;i>=1;i--){
        while (h+1<t&&c[q[h+2]]-q[h+2]*x<=-i*x) h++;
        int j=q[h+1];
        if (c[q[h+1]]-q[h+1]*x>-i*x){fr[i]=sum[i]-(n-i)*x*(n-i+1)/2;}
        else {fr[i]=sum[i]-sum[j]-(j-i-1)*x*(j-i)/2+g[j];}
        while (h<t&&c[q[t]]-q[t]*x>=c[i]-i*x) t--;
        q[++t]=i;
        ans=min(ans,fl[i]+fr[i]-a[i]);
    }
    //printf("ans=%I64d\n",ans);
    if (ans>m) return false;
    if (x<ansx){
        ansx=x;
        for (int i=1;i<=n;i++){
            if (fr[i]+fl[i]-a[i]<=m){
                ansk=i;
                break;
            }
        }
    }
    return true;
}
inline void half(int l,int r){
    while (l!=r){
        int mm=(l+r)/2;
        //printf("%I64d\n",mm);
        if (check(mm)) r=mm;
        else l=mm+1;
    }
}
int main(){
	//freopen("stu.in","r",stdin);
	//freopen("stu.out","w",stdout);
    scanf("%d%lld",&n,&m);
    ansx=1000000000;  ansk=1000000000;
    for (int i=1;i<=n;i++){
		scanf("%d",&a[i]);
		maxi=max(maxi,a[i]);
	}
	//printf("%d\n",maxi);
	if (maxi>20000000) maxi=20000000;
	half(0,maxi+1);
	if (ansx==1000000000) half(20000001,100000000);
    printf("%d %d\n",ansk,ansx);
    //printf("%d\n",check(1076));
}

基圈上的外向树求lca。。。先预处理所有的环长，以及外向树内的lca，对每个询问，在一棵树上就直接求，在一个环上就先到根，再判断从哪个方向走，如果不在一个环上输出-1 -1。。。

另：lca不知哪写错了，求大神查错。。。

#include<cstdio>
#include<cmath>
#include<cstring>
int can[500001];
int ansx=0,ansy=0,n,p=0,ss=0,m,sum=0;
int d[500001],pos[500001],fa[500001];
int f[500001][20],root[500001];
int dis[500001],kind[500001],head[500001],next[1000001];
struct re{
	int u,v;
} a[1000001];
inline int max(int a,int b){return a>b? a:b;}
inline int min(int a,int b){return a<b? a:b;}
void getlca(int x,int y){
	ansx=0;  ansy=0;
	if (x==y) return;
	//printf("fu\n");
	if (dis[x]>dis[y]){
		int xx=dis[x]-dis[y];
		ansx=xx;
		int k=int(log2(n));
		while (k>=0){
			if (xx>=(1<<k)){
				x=f[x][k];
				xx-=(1<<k);
			}
			k--;
		}
	}else{
		int xx=dis[y]-dis[x];
		ansy=xx;
		//printf("%d\n",xx);
		int k=int(log2(n));
		while (k>=0){
			if (xx>=(1<<k)){
				y=f[y][k];
				xx-=1<<k;
			}
			k--;
		}
	}
	//printf("f2\n");
	if (x==y) return;
	//printf("ansx=%d ansy=%d\n",ansx,ansy);
	//printf("x\n");
	int k=int(log2(n)); 
	while (k>=0){
		//printf("%d %d %d %d %d\n",k,ansx,ansy,f[x][k],f[y][k]);
		if (f[x][k]!=f[y][k]&&f[x][k]!=0&&f[y][k]!=0){
			ansx+=1<<k;  ansy+=1<<k;
			x=f[x][k];  y=f[y][k];
		}
		k--;
	}
	ansx++;  ansy++;
}
void get(int x,int y){
	if (root[x]==root[y]){
		//printf("e\n");
		getlca(x,y);
		return;
	}
	if (kind[root[x]]!=kind[root[y]]) return;
	ansx=dis[x];  ansy=dis[y];
	x=root[x];  y=root[y];
	int t=kind[x];
	int len=d[t];
	int lx=pos[y]-pos[x];
	if (lx<0) lx+=len;
	int rx=pos[x]-pos[y];
	if (rx<0) rx+=len;
	//printf("len=%d px=%d py=%d\n",len,pos[x],pos[y]);
	//printf("ax=%d ay=%d tx=%d ty=%d\n",ansx,ansy,lx,rx);
	if (max(lx+ansx,ansy)<max(ansx,rx+ansy)){
		//printf("a1\n");
		ansx+=lx;
		return;
	}
	if (max(lx+ansx,ansy)>max(ansx,rx+ansy)){
		//printf("a2\n");
		ansy+=rx;
		return;
	}
	//printf("f1 %d %d\n",ansx,rx+ansy);
	//printf("f2 %d %d\n",ansx+lx,ansy);
	if (min(lx+ansx,ansy)<min(ansx,rx+ansy)){
		//printf("b1\n");
		ansx+=lx;
		return;
	}
	if (min(lx+ansx,ansy)>min(ansx,rx+ansy)){
		//printf("b2\n");
		ansy+=rx;
		return;
	}
	//printf("s\n");
	ansx+=lx;
}
void done(int i){
	root[i]=i;
	kind[i]=++ss;
	d[ss]++;
	pos[i]=++p;
	int j=fa[i];
	while (j!=i){
		//printf("j=%d %d\n",j,i);
		root[j]=j;
		kind[j]=ss;
		d[ss]++;
		pos[j]=++p;
		j=fa[j];
	}
}
void dfs(int i,int x){
	can[i]=x;
	int k=fa[i];
	if (can[k]==x){
		done(k);
		return;
	}
	if (can[k]) return;
	can[k]=x;
	dfs(k,x);
}
void dfs2(int i){
	can[i]=1;
	//printf("ii=%d\n",i);
	int x=int(log2(n));
	f[i][0]=fa[i];
	for (int j=1;j<=x;j++){
		f[i][j]=f[f[i][j-1]][j-1];
	}
	for (int j=head[i];j;j=next[j]){
		int k=a[j].v;
		if (root[k]||can[k]) continue;
		root[k]=root[i];
		dis[k]=dis[i]+1;
		dfs2(k);
	}
}
void build(int u,int v){
	a[++sum].u=u;
	a[sum].v=v;
	next[sum]=head[u];
	head[u]=sum;
}
int main(){
	//freopen("ran3c.in","r",stdin);
	//freopen("ran.out","w",stdout);
	scanf("%d%d",&n,&m);
	int x,y;
	for (int i=1;i<=n;i++){
		scanf("%d",&x);
		build(x,i);  build(i,x);
		fa[i]=x;
	}
	for (int i=1;i<=n;i++){
		if (!can[i]) dfs(i,i);
		//printf("%d\n",can[i]);
	}
	//printf("d\n");
	memset(can,0,sizeof(can));
	for (int i=1;i<=n;i++){
		if (root[i]) dfs2(i);
	}
	//for (int i=1;i<=n;i++) printf("i=%d root=%d dis=%d pos=%d kind=%d\n",i,root[i],dis[i],pos[i],kind[i]);
	for (int i=1;i<=m;i++){
		scanf("%d%d",&x,&y);
		ansx=-1;  ansy=-1;
		get(x,y);
		printf("%d %d\n",ansx,ansy);
	}
}

强连通分量+最长路

#include<cstdio>
#include<cstring>
const int maxi=100000000;
int ft[610][610];
bool f[100001],can[100001];
int head[100001],next[200001],d[100001];
int dfn[100001],low[100001],sta[100001],g[100001];
int top=0,s=0,sum=0,ss=0,n,m1,m2,ans=0;
struct re{
    int u,v,w;
} a[200001];
inline int min(int a,int b){return a<b? a:b;}
inline int max(int a,int b){return a>b? a:b;}
inline int abs(int x){return x>=0? x:-x;}
void done(int i){
    ++s;
    while (sta[top]!=i){
        g[sta[top]]=s;
        can[sta[top]]=false;
        top--;
    }
    g[i]=s;
    can[i]=false;
    top--;
}
void dfs(int i){
    dfn[i]=low[i]=++ss;
    sta[++top]=i;
    f[i]=false;
    for (int j=head[i];j;j=next[j]){
        int k=a[j].v;
        if (can[k]){
            if (f[k]) dfs(k);
            low[i]=min(low[i],min(low[k],dfn[k]));
        }
    }
    if (low[i]==dfn[i]) done(i);
}
void build(int u,int v,int w){
    a[++sum].u=u;
    a[sum].v=v;
    a[sum].w=w;
    next[sum]=head[u];
    head[u]=sum;
}
int main(){
    //freopen("fes11a.in","r",stdin);
    scanf("%d%d%d",&n,&m1,&m2);
    int u,v;
    for (int i=1;i<=m1;i++){
        scanf("%d%d",&u,&v);
        build(v,u,1);
        build(u,v,-1);
    }
    for (int i=1;i<=m2;i++){
        scanf("%d%d",&u,&v);
        build(v,u,0);
    }
    memset(f,true,sizeof(f));
    memset(can,true,sizeof(can));
    for (int i=1;i<=n;i++){
        if (f[i])dfs(i);
    }
    //for (int i=1;i<=n;i++) printf("g[%d]=%d\n",i,g[i]);
    for (int i=1;i<=n;i++){
        for (int j=1;j<=n;j++){
            ft[i][j]=-maxi;
        }
    }
    //printf("%d\n",ft[1][1]);
    for (int i=1;i<=n;i++) ft[i][i]=0;
    for (int i=1;i<=sum;i++){
        if (g[a[i].u]==g[a[i].v]){
            ft[a[i].u][a[i].v]=max(ft[a[i].u][a[i].v],a[i].w);
        }
    }
    /*for (int i=1;i<=n;i++){
        for (int j=1;j<=n;j++){
            printf("f[%d][%d]=%d ",i,j,ft[i][j]);
        }
        printf("\n");
    }*/
    for (int k=1;k<=n;k++){
        for (int i=1;i<=n;i++){
            for (int j=1;j<=n;j++){
                //if (i==j) printf("i=%d j=%d k=%d f2=%d f3=%d\n",i,j,k,ft[i][k],ft[k][j]);
                ft[i][j]=max(ft[i][j],ft[i][k]+ft[k][j]);
            }
        }
    }
    /*for (int i=1;i<=n;i++){
        for (int j=1;j<=n;j++){
            printf("f[%d][%d]=%d ",i,j,ft[i][j]);
        }
        printf("\n");
    }*/
    for (int i=1;i<=n;i++){
        if (ft[i][i]>0){
            printf("NIE\n");
            return 0;
        }
    }
    for (int i=1;i<=n;i++){
        for (int j=1;j<=n;j++){
            if (g[i]==g[j]) d[g[i]]=max(d[g[i]],abs(ft[i][j]));
        }
    }
    for (int i=1;i<=s;i++){
        ans+=d[i]+1;
    }
    printf("%d\n",ans);
}

暴力水过。。就是d(a,b)=c[a]+c[b]-c[gcd(a,b)];c[i]表示i的质因子数。然后对每个a[i]暴力枚举gcd(),求一个b使c[a]+c[b]-2*c[gcd()]最小。。这个可以预处理后O(1)解决。。

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxi=1000000000;
int n,m=0,tot=0;
bool ss[1000051];
int prime[1000051];
int f[1000051],g[1000051];
int a[1000051],c[1000051];
int main(){
    scanf("%d",&n);
    for (int i=1;i<=n;i++){
        scanf("%d",&a[i]);
        m=max(m,a[i]);
    }
    memset(ss,true,sizeof(ss));
    for (int i=2;i<=m;i++){
        if  (ss[i]){
            prime[++tot]=i;
            c[i]=1;
        }
        for (int j=1;j<=tot&&prime[j]*i<=m;j++){
            int k=i*prime[j];
            ss[k]=false;
            c[k]=c[i]+1;
            if (i%prime[j]==0) break;
        }
    }
    //for (int i=1;i<=tot;i++) printf("prime[%d]=%d\n",i,prime[i]);
    //for (int i=1;i<=m;i++) printf("c[%d]=%d\n",i,c[i]);
    c[0]=maxi;
    for (int i=1;i<=n;i++){
        for (int j=1;j*j<=a[i];j++){
            if (a[i]%j!=0) continue;
            int k=a[i]/j;
            //printf("i=%d j=%d k=%d\n",i,j,k);
            if (c[a[i]]<c[a[f[j]]]){g[j]=f[j]; f[j]=i;}
            else if (c[a[i]]<c[a[g[j]]]) g[j]=i;
            //printf("g=%d f=%d\n",g[j],f[j]);
            if (j==k) continue;
            if (c[a[i]]<c[a[f[k]]]){g[k]=f[k]; f[k]=i;}
            else if (c[a[i]]<c[a[g[k]]]) g[k]=i;
        }
        //if (i%10000==0) printf("i=%d\n",i);
    }
    //for (int i=1;i<=m;i++) printf("i=%d f=%d g=%d\n",i,f[i],g[i]);
    for (int i=1;i<=n;i++){
        int h=maxi,d=0;
        for (int j=1;j*j<=a[i];j++){
            if (a[i]%j!=0) continue;
            int k=a[i]/j,x;
            if (f[j]==i) x=g[j];
            else x=f[j];
            //printf("i=%d x=%d j=%d k=%d h=%d\n",i,x,j,k,h[i]);
            if (h>c[a[i]]+c[a[x]]-2*c[j]||(h==c[a[i]]+c[a[x]]-2*c[j]&&x<d)){
                h=c[a[i]]+c[a[x]]-2*c[j];
                d=x;
            }
            if (j==k) continue;
            if (f[k]==i) x=g[k];
            else x=f[k];
            if (h>c[a[i]]+c[a[x]]-2*c[k]||(h==c[a[i]]+c[a[x]]-2*c[k]&&x<d)){
                h=c[a[i]]+c[a[x]]-2*c[k];
                d=x;
            }
        }
        //if (i%10000==0) printf("%d\n",i);
        printf("%d\n",d);
    }
}

树状数组维护序列，使{a[i]-i}不增，且{a[i]}递增。。。

#include<cstdio>
#include<algorithm>
using namespace std;
const int maxi=~0u>>1;
int n,ans(0);
int f[200001],t[1000001];
struct re{
    int n,h;
}a[200001];
int lowbit(int x){return x&(-x);}
bool cmp(re a,re b){return a.n==b.n? a.h<b.h:a.n>b.n;}
void change(int x,int c){
    while (x<=n){
        t[x]=max(t[x],c);
        //printf("x=%d t[x]=%d\n",x,t[x]);
        x+=lowbit(x);
    }
}
int ques(int x){
    int ans=0;
    while (x){
        ans=max(ans,t[x]);
        //printf("%d t[x]=%d\n",x,t[x]);
        x-=lowbit(x);
    }
    //printf("ans=%d\n",ans);
    return ans;
}
int main(){
    scanf("%d",&n);
    for (int i=1;i<=n;i++){
        scanf("%d",&a[i].h);
        a[i].n=a[i].h-i;
        //printf("a[%d]=%d\n",i,a[i].n);
    }
    sort(a+1,a+n+1,cmp);
    for (int i=1;i<=n;i++){
        //printf("i=%d n=%d h=%d\n",i,a[i].n,a[i].h);
        if (a[i].n>0) continue;
        int x;
        if (a[i].h-1>0){
            //printf("%d\n",a[i].h);
            x=ques(a[i].h-1);
        }else x=0;
        //printf("x=%d\n",x);
        f[i]=x+1;
        //printf("f=%d\n",f[i]);
        ans=max(ans,f[i]);
        //printf("f[%d]=%d\n",i,f[i]);
        change(a[i].h,f[i]);
    }
    printf("%d\n",ans);
}

裸扫一遍。。记下状态。注意一段中没有一个字母就不能算他为出现最少的字母= =！

#include<cstdio>
int n,ans=0;
char st[1000002];
int f[41][41],g[41][41];
int max(int a,int b){return a>b? a:b;}
int main(){
    scanf("%d",&n);
    scanf("%s",st);
    for (int i=0;i<n;i++){
        int y=st[i]-'a';
        for (int j=0;j<26;j++){
            f[j][y]++;
            f[y][j]--;
            if (!g[y][j]) g[y][j]=1;
            if (g[y][j]==2){g[y][j]=1;f[y][j]++;}
            if (f[y][j]<=-1){f[y][j]=-1;g[y][j]=2;}
            if (g[y][j]) ans=max(ans,f[y][j]);
            if (g[j][y]) ans=max(ans,f[j][y]);
            //printf("f[%c][%c]=%d f[%c][%c]=%d ",j+'a',y+'a',f[j][y],y+'a',j+'a',f[y][j]);
        }
        //printf("\n");
    }
    printf("%d\n",ans);
}

2793: [Poi2012]Vouchers：暴力加小优化，据说是O(mlogm)的。

2091: [Poi2010]The Minima Game：之前做的USACO10的taking turns。。。一样的题额。。

#include<cstdio>
#include<cstring>
typedef long long ll;
int m,n;
ll x,maxi=0,tot=0,sum=0;
ll d[1000001];
ll ans[1000001];
bool c[1000001],f[1000001];
ll max(ll a,ll b){return a>b? a:b;}
int main(){
    scanf("%d",&m);
    memset(f,true,sizeof(f));
    for (int i=1;i<=m;i++){
        scanf("%lld",&x);
        c[x]=true;
        maxi=max(maxi,x);
    }
    scanf("%d",&n);
    for (int i=1;i<=maxi;i++){
        d[i]=i;
    }
    for (int i=1;i<=n;i++){
        scanf("%lld",&x);
        int s=x;
        long long y=d[x];
        while (s){
            if (y>maxi) break;
            if (f[y]){
                tot++;
                d[x]=y;
                f[y]=false;
                //printf("y=%d\n",y);
                if (c[y]) ans[++sum]=tot;
                s--;
            }
            y+=x;
        }
        //printf("s=%d tot=%d\n",s,tot);
        tot+=s;
    }
    printf("%lld\n",sum);
    for (int i=1;i<=sum;i++){
        printf("%lld\n",ans[i]);
    }
}

水题一道不解释，前缀和暴力裸过。。就是不知为什么，poi原数据我总有一个跑不对= =。详见程序

也不算什么难题。。求出所有的置换，再在每个置换中讨论，ans=min(用置换中最小值换所有元素的代价；有全局最小值换置换中最小元素，用全局最小元素换所有元素，再将最小元素换回来),详见代码。。