转载请注明出处：http://www.cnblogs.com/Delostik/p/3553114.html
目前已有【A B C D E】
例行吐槽：趴桌子上睡着了
【A. Genetic Engineering】
http://codeforces.com/contest/391/problem/A
问最少插入几个字符，使得字符串不存在连续偶数个相同字母。不说什么
#include <iostream>
#include <string>
using namespace std; string s;
int cnt; int main(){
cin>>s;
s+=' ';
int n=s.size(),i,j;
for(i=;i<n;){
for(j=i;j<n;j++)
if(s[j]!=s[i]){
if((j-i)%==) cnt++;
break;
}
i=j;
}
cout<<cnt<<endl;
}
【B. Word Folding】
http://codeforces.com/contest/391/problem/B
将字符串蛇形折叠，其中一列字母相同，问最多折叠几层。
若S[i]=S[j]且ij之间隔了偶数个（包括0）字母的时候，可以找到一个折叠点将S[i]和S[j]折叠并对齐。相同的那一列从上到下的下标一定是奇偶交替的。
#include <iostream>
#include <vector>
#include <cstring>
using namespace std;
typedef pair<int,int> PII;
template<class T>inline void gmax(T &a,T b){if(a<b)a=b;} string s;
int ans;
vector<int> v;
bool vis[]; int main(){
cin>>s;
int n=s.size();
for(int k='A';k<='Z';k++){
v.clear();
for(int i=;i<n;i++)
if(s[i]==k) v.push_back(i);
memset(vis,false,sizeof(vis));
for(int i=;i<v.size();i++)
if(!vis[i]){
int cnt=;
for(int j=i+;j<v.size();j++)
if((v[j]%)+(v[j-]%)==) vis[j]=true,cnt++;
gmax(ans,cnt);
}
}
cout<<ans<<endl;
}
【C3. The Tournament】
http://codeforces.com/contest/391/problem/C3
与n个选手进行比赛，赢了自己得一分，输了对方得一分，n个选手有已经得到的分数p[i]和赢得比赛需要花费的代价e[i]，问至少花费多少代价可以排名前k，并列的参考胜负场关系。
转化为判定性问题。若最终得分为x，则p[i]>x的选手一定排名比我靠前；p[i]=x的选手如果赢了我那么分数变成p[i]+1排名比我靠前，如果输给我则按胜负关系比我靠后；p[i]=x-1的选手如果赢了我分数变成p[i]排名比我靠前。
所以我们需要纠结的仅仅是p[i]=x和p[i]=x-1的这两种人，选择其中的一部分人打败他们，使得自己的名次在前k即可。x的取值也很显然只有p[k]，p[k]+1,p[k]+2这三种（p排序后）。
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#define p first
#define e second
#define inf ~0uLL>>1
using namespace std;
typedef pair<int,int> PII;
template<class T>inline void gmin(T &a,T b){if(a>b)a=b;} int n,m;
long long ans=inf;
PII a[]; int main(){
cin>>n>>m;
m--;
for(int i=;i<n;i++)
cin>>a[i].p>>a[i].e;
sort(a,a+n,greater<PII>());
for(int k=;k<;k++){
int top=;
long long tmp=;
priority_queue< int,vector<int>,less<int> > b;
priority_queue< int,vector<int>,greater<int> > c;
int des=a[m].p+k;
for(int i=;i<n;i++){
if(a[i].p+==des || a[i].p==des) b.push(a[i].e);
else{
if(a[i].p>des) top++;
c.push(a[i].e);
}
}
if(top>m) continue;
while(!b.empty()){
if(top<m){
top++;
c.push(b.top());
}else{
des--;
tmp+=b.top();
}
b.pop();
}
while(des> && !c.empty()){
tmp+=c.top();
c.pop();
des--;
}
if(des<=) gmin(ans,tmp);
}
cout<<((ans==inf)?-:ans)<<endl;
}
【D2. Supercollider】
http://codeforces.com/contest/391/problem/D2
有若干水平和垂直线段，问最大的一个+号的大小是多少。
暴力复杂度n^2。
仍然是转化问判定性问题。二分答案之后，只需要判定大小为mid的+是否存在即可。
若两条垂直线段(x1,y1)(x1,y2) (x2,y3)(x3,y3)可以组成一个大小为mid的+，那么中心点一定存在于线段 (x1,y1+mid)(x1,y2-mid) (x2+mid,y3)(x3-mid,y3)之中。也就是说把所有线段的两段都截去长度mid，然后判断是否存在交点就可以了。扫描线。
#include <iostream>
#include <algorithm>
#include <set>
using namespace std; struct LINE{int x,y,l;}a[],b[],c[],p[];
int n,m;
set<int> M; bool cmp(LINE a,LINE b){
return a.x<b.x || a.x==b.x && a.l>b.l;
} bool check(int mid){
int tot1=,tot2=;
M.clear();
for(int i=;i<n;i++)
if(a[i].l>=*mid){
c[tot1].x=a[i].x;
c[tot1].y=a[i].y+mid;
c[tot1++].l=a[i].l-*mid;
}
for(int i=;i<m;i++)
if(b[i].l>=*mid){
p[tot2].x=b[i].x+mid;
p[tot2].y=b[i].y;
p[tot2++].l=;
p[tot2].x=b[i].x+b[i].l-mid+;
p[tot2].y=b[i].y;
p[tot2++].l=;
}
sort(c,c+tot1,cmp);
sort(p,p+tot2,cmp);
int j=;
for(int i=;i<tot1;i++){
for(;j<tot2 && p[j].x<=c[i].x;j++)
if(p[j].l) M.insert(p[j].y);
else M.erase(p[j].y);
set<int>::iterator tmp=M.lower_bound(c[i].y);
if(tmp!=M.end() && (*tmp)<=c[i].y+c[i].l) return ;
}
return ;
} int main(){
cin>>n>>m;
for(int i=;i<n;i++)
cin>>a[i].x>>a[i].y>>a[i].l;
for(int i=;i<m;i++)
cin>>b[i].x>>b[i].y>>b[i].l;
int low=,high=;
while(low<=high){
int mid=(low+high)>>;
if(check(mid)) low=mid+;
else high=mid-;
}
cout<<low-<<endl;
}
【E2. Three Trees】
http://codeforces.ru/contest/391/problem/E2
给定三棵树，添加两条边将三棵树连起来，使得新树的所有路径和最大。
计算方法如下
Distances between {xi} and {yi}
Distances between {yi} and {zi}
Distances between pairs of vertices that were connected before we inserted the additional edges
Distances between {xi} and {zi}
The first component is equal to sum(d(X, xi) + d(Y1, yi) + , xi = ..n1, yi = ..n2). Note that the summands are independent, so it can be broken into sum(d(X, xi), xi = ..n1) * n2 + sum(d(Y1, yi), yi = ..n2) * n1 + n1 * n2.
Similarly, the second component is equal to sum(d(Z, zi), zi = ..n3) * n2 + sum(d(Y2, yi), yi = ..n2) * n3 + n2 * n2.
The third component is simply a sum of pairwise distances in each of the trees and is a constant.
The fourth component is equal to sum(d(X, xi) + d(Y1, Y2) + d(Z, zi) + , xi = ..n1, zi = ..n3) = sum(d(X, xi), xi = ..n1) * n3 + sum(d(Z, zi), zi = ..n3) + d(Y1, Y2) * n1 * n3 + * n1 * n3.
前三部分都是可以被独立计算的，关键在于第四部分。可以在三棵树中分别找到一个连接点（一定是到达该点路径和最大的点），枚举三棵树的顺序（左中右），枚举中间那棵树的另一个连接点，这部分的复杂度是O(n)的。
每棵树自己的路径用dfs做dp。
#include <iostream>
#define mm 200010
#define mn 100010
using namespace std;
template<class T>inline void gmax(T &a,T b){if(a<b)a=b;} long long ans,n[]; struct TREE{ long long dist[mn],node[mn],pos,n,SUM,f[mn],sum[mn],maxd; struct EDGE{
int pnt;
EDGE *pre;
EDGE(){}
EDGE(int _pnt,EDGE *_pre):pnt(_pnt),pre(_pre){}
}Edge[mm],*SP,*edge[mn]; void addedge(int a,int b){
edge[a]=new(++SP)EDGE(b,edge[a]);
edge[b]=new(++SP)EDGE(a,edge[b]);
} void build(int nn){
int a,b;
SP=Edge;
n=nn;
for(int i=;i<n;i++){
cin>>a>>b;
addedge(a,b);
}
}
//dfs0用于计算连接点到其他各点的距离
void dfs0(int cur,int fa){
dist[cur]=dist[fa]+;
for(EDGE *j=edge[cur];j;j=j->pre)
if(j->pnt!=fa){
dfs0(j->pnt,cur);
}
}
//dfs1 dfs2用于dp
void dfs1(int cur,int fa){
node[cur]=;
sum[cur]=;
for(EDGE *j=edge[cur];j;j=j->pre)
if(j->pnt!=fa){
dfs1(j->pnt,cur);
node[cur]+=node[j->pnt];
sum[cur]+=sum[j->pnt]+node[j->pnt];
}
} void dfs2(int cur,int fa,long long val){
f[cur]=sum[cur]+val;
for(EDGE *j=edge[cur];j;j=j->pre)
if(j->pnt!=fa)
dfs2(j->pnt,cur,val+sum[cur]-sum[j->pnt]-node[j->pnt]+n-node[j->pnt]);
} void solve(){
dfs1(,);
dfs2(,,);
for(int i=;i<=n;i++){
SUM+=f[i];
if(f[i]>maxd){
maxd=f[i];
pos=i;
}
}
dist[]=-;
dfs0(pos,);
}
}T[]; long long calc(TREE &TL,TREE &TM,TREE &TR){
long long res,ans=;
int i=TM.pos;
for(int j=;j<=TM.n;j++){
//三棵树各自内部的
res=(TL.SUM+TM.SUM+TR.SUM)/;
//TL连向右边两棵
res+=TL.maxd*(TM.n+TR.n)+TM.n*TR.n;
//TR连向左边两棵
res+=TR.maxd*(TL.n+TM.n)+TM.n*TL.n;
//TL和TR
res+=(TM.dist[j]+)*TL.n*TR.n+TL.n*TM.f[i]+TR.n*TM.f[j];
gmax(ans,res);
}
return ans;
} int main(){
cin>>n[]>>n[]>>n[];
for(int i=;i<;i++){
T[i].build(n[i]);
T[i].solve();
}
for(int i=;i<;i++)
for(int j=;j<;j++)
if(i!=j) gmax(ans,calc(T[i],T[j],T[-i-j]));
cout<<ans<<endl;
}