数列分治
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
