分治

数列分治

POJ 1854: Evil Straw Warts Live
题解链接 http://www.hankcs.com/program/algorithm/poj-1854-evil-straw-warts-live.html
代码如下

/*

*/
#define method_1
#ifdef method_1
/*
题解链接 http://www.hankcs.com/program/algorithm/poj-1854-evil-straw-warts-live.html 
*/
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<set>
#include<map>
#include<queue>
#include<stack>
#include<vector>
#include<cstring>
#include<cstdlib>
#include<iomanip>
#include<ctime>
#include<string>
#define D(x) cout<<#x<<" = "<<x<<"  "
#define E cout<<endl
using namespace std;
typedef long long ll;
typedef pair<int,int>pii;
const int maxn=8000+5;
const int maxnum=26+5;
const int INF=0x3f3f3f3f;
char s[maxn];
int T,n,ans,cnt[maxnum];
void init(){
    ans=0;
    memset(cnt,0,sizeof(cnt));
}
bool check(){
    for(int i=0;i<=n-1;i++) cnt[s[i]-'a']++;
    int res=0;
    for(int i=0;i<=maxnum-5;i++) if(cnt[i]&1) res++;
    return res<=1; 
}
void solve(){
    int l=0,r=n-1;
    while(l<r){
        if(s[l]==s[r]) l++,r--;
        else{
            int posl=INF,posr=-INF;
            for(int i=l+1;i<r;i++) if(s[i]==s[r]){
                posl=i;break;
            }
            for(int i=r-1;i>l;i--) if(s[i]==s[l]){
                posr=i;break;
            }
            if(posl-l<r-posr){
                ans+=posl-l;
                for(int i=posl;i>=l+1;i--) swap(s[i],s[i-1]);
            }
            else{
                ans+=r-posr;
                for(int i=posr;i<r;i++) swap(s[i],s[i+1]);
            }
        }
    }
}
int main() {
//  ios::sync_with_stdio(false);
    //freopen("Evil Straw Warts Live.in","r",stdin);
    scanf("%d",&T);
    while(T--){
        init();
        scanf("%s",s);
        n=strlen(s);
        if(!check()){
            printf("Impossible\n");
            continue;
        }
        solve();
        printf("%d\n",ans);
    }
    return 0;
}
#endif
#ifdef method_2
/*

*/

#endif
#ifdef method_3
/*

*/

#endif

平面分治

树分治

POJ 2114: Boatherds
简单的点分治，维护一下dis时顺便记录一下所处的子树编号即可，可以避开繁复的容斥过程。
头疼的是，我在求树的重心时，把max_part=max(max_part,s[y]);写成了max_part=max(max_part,s[x]);结果WA了半天。
代码如下

/*

*/
#define method_1
#ifdef method_1
/*
简单的点分治，维护一下dis时顺便记录一下所处的子树编号即可，可以避开繁复的容斥过程。
头疼的是，我在求树的重心时，把max_part=max(max_part,s[y]);写成了max_part=max(max_part,s[x]);结果WA了半天。 
*/
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<set>
#include<map>
#include<queue>
#include<stack>
#include<vector>
#include<cstring>
#include<cstdlib>
#include<iomanip>
#include<ctime>
#include<string>
#define D(x) cout<<#x<<" = "<<x<<"  "
#define E cout<<endl
using namespace std;
typedef long long ll;
typedef pair<int,int>pii;
const int maxn=10000+5;
const int maxm=100+5;
const int INF=0x3f3f3f3f;
int n,X; //判断是否存在两点距离为X 
bool flag;
int head[maxn],tot;
struct node{
    int from,to,c;
}edge[maxn<<1];
void add(int from,int to,int c){
    edge[++tot].from=head[from],head[from]=tot,edge[tot].to=to,edge[tot].c=c;
}
void init(){
    memset(head,0,sizeof(head));
    tot=1;
}
struct node1{
    int d,b;//distance到目前分治中心的距离 belong所在的子树 
    bool operator<(const node1& h)const{return d<h.d;}
}dis[maxn];
int vis[maxn],cnt;
void getdis(int x,int len,int b){
    vis[x]=1;
    dis[++cnt].d=len,dis[cnt].b=b;
    for(int i=head[x];i;i=edge[i].from){
        int y=edge[i].to,c=edge[i].c;
        if(vis[y]) continue;
        getdis(y,len+c,b);
    }
    vis[x]=0;
}
int s[maxn],mins,root;
void getroot(int S,int x){
    s[x]=1,vis[x]=1;
    int max_part=0;
    for(int i=head[x];i;i=edge[i].from){
        int y=edge[i].to;
        if(vis[y]) continue;
        getroot(S,y);
        s[x]+=s[y];
        max_part=max(max_part,s[y]);
    }
    max_part=max(max_part,S-s[x]);
    if(mins>max_part){
        mins=max_part;
        root=x;
    }
    vis[x]=0;
}
void solve(int S,int x){
    if(flag) return;
    mins=S;
    getroot(S,x);
    vis[root]=1;
    cnt=0;
    dis[++cnt].d=0,dis[cnt].b=root;
    for(int i=head[root];i;i=edge[i].from){
        int y=edge[i].to,c=edge[i].c;
        if(vis[y]) continue;
        getdis(y,c,y);
    }
    sort(dis+1,dis+cnt+1);
    /*
    D(root);E;
    for(int i=1;i<=cnt;i++){
        D(dis[i].b);D(dis[i].d);E;
    }
    */
    int l=1,r=cnt;
    while(l<=r){
        while(l<r&&dis[l].d+dis[r].d>X) r--;
        while(l<r&&dis[l].d+dis[r].d==X){
            if(dis[l].b!=dis[r].b) flag=true;
            r--;
        }
        l++;
    }
    int now=root;
    for(int i=head[now];i;i=edge[i].from){
        int y=edge[i].to,c=edge[i].c;
        if(vis[y]) continue;
        solve(s[y],y);
    }
}
int main() {
//  ios::sync_with_stdio(false);
    //freopen("Boatherds.in","r",stdin);
    while(scanf("%d",&n)&&n){
        init();
        for(int i=1;i<=n;i++){
            int to,c;
            while(scanf("%d",&to)&&to) scanf("%d",&c),add(i,to,c),add(to,i,c);
        }
        while(scanf("%d",&X)&&X){
            flag=false;
            memset(vis,0,sizeof(vis));
            solve(n,1);
            if(flag) printf("AYE\n");
            else printf("NAY\n");
        }
        printf(".\n");
    }
    return 0;
}
#endif