转载请注明出处：http://www.cnblogs.com/Delostik/p/3553114.html
持续更新中
例行吐槽：趴桌子上睡着了
【A. Genetic Engineering】
http://codeforces.com/contest/391/problem/A
问最少插入几个字符，使得字符串不存在连续偶数个相同字母。不说什么
1 #include <iostream> 2 #include <string> 3 using namespace std; 4 5 string s; 6 int cnt; 7 8 int main(){ 9 cin>>s; 10 s+=‘ ‘; 11 int n=s.size(),i,j; 12 for(i=0;i<n;){ 13 for(j=i;j<n;j++) 14 if(s[j]!=s[i]){ 15 if((j-i)%2==0) cnt++; 16 break; 17 } 18 i=j; 19 } 20 cout<<cnt<<endl; 21 }
【B. Word Folding】
http://codeforces.com/contest/391/problem/B
将字符串蛇形折叠，其中一列字母相同，问最多折叠几层。
若S[i]=S[j]且ij之间隔了偶数个（包括0）字母的时候，可以找到一个折叠点将S[i]和S[j]折叠并对齐。相同的那一列从上到下的下标一定是奇偶交替的。
1 #include <iostream> 2 #include <vector> 3 #include <cstring> 4 using namespace std; 5 typedef pair<int,int> PII; 6 template<class T>inline void gmax(T &a,T b){if(a<b)a=b;} 7 8 string s; 9 int ans; 10 vector<int> v; 11 bool vis[1010]; 12 13 int main(){ 14 cin>>s; 15 int n=s.size(); 16 for(int k=‘A‘;k<=‘Z‘;k++){ 17 v.clear(); 18 for(int i=0;i<n;i++) 19 if(s[i]==k) v.push_back(i); 20 memset(vis,false,sizeof(vis)); 21 for(int i=0;i<v.size();i++) 22 if(!vis[i]){ 23 int cnt=1; 24 for(int j=i+1;j<v.size();j++) 25 if((v[j]%2)+(v[j-1]%2)==1) vis[j]=true,cnt++; 26 gmax(ans,cnt); 27 } 28 } 29 cout<<ans<<endl; 30 }
【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排序后）。
1 #include <iostream> 2 #include <algorithm> 3 #include <vector> 4 #include <queue> 5 #define p first 6 #define e second 7 #define inf ~0uLL>>1 8 using namespace std; 9 typedef pair<int,int> PII; 10 template<class T>inline void gmin(T &a,T b){if(a>b)a=b;} 11 12 int n,m; 13 long long ans=inf; 14 PII a[200010]; 15 16 int main(){ 17 cin>>n>>m; 18 m--; 19 for(int i=0;i<n;i++) 20 cin>>a[i].p>>a[i].e; 21 sort(a,a+n,greater<PII>()); 22 for(int k=0;k<3;k++){ 23 int top=0; 24 long long tmp=0; 25 priority_queue< int,vector<int>,less<int> > b; 26 priority_queue< int,vector<int>,greater<int> > c; 27 int des=a[m].p+k; 28 for(int i=0;i<n;i++){ 29 if(a[i].p+1==des || a[i].p==des) b.push(a[i].e); 30 else{ 31 if(a[i].p>des) top++; 32 c.push(a[i].e); 33 } 34 } 35 if(top>m) continue; 36 while(!b.empty()){ 37 if(top<m){ 38 top++; 39 c.push(b.top()); 40 }else{ 41 des--; 42 tmp+=b.top(); 43 } 44 b.pop(); 45 } 46 while(des>0 && !c.empty()){ 47 tmp+=c.top(); 48 c.pop(); 49 des--; 50 } 51 if(des<=0) gmin(ans,tmp); 52 } 53 cout<<((ans==inf)?-1:ans)<<endl; 54 }
【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，然后判断是否存在交点就可以了。扫描线。
1 #include <iostream> 2 #include <algorithm> 3 #include <set> 4 using namespace std; 5 6 struct LINE{int x,y,l;}a[50010],b[50010],c[50010],p[100010]; 7 int n,m; 8 set<int> M; 9 10 bool cmp(LINE a,LINE b){ 11 return a.x<b.x || a.x==b.x && a.l>b.l; 12 } 13 14 bool check(int mid){ 15 int tot1=0,tot2=0; 16 M.clear(); 17 for(int i=0;i<n;i++) 18 if(a[i].l>=2*mid){ 19 c[tot1].x=a[i].x; 20 c[tot1].y=a[i].y+mid; 21 c[tot1++].l=a[i].l-2*mid; 22 } 23 for(int i=0;i<m;i++) 24 if(b[i].l>=2*mid){ 25 p[tot2].x=b[i].x+mid; 26 p[tot2].y=b[i].y; 27 p[tot2++].l=1; 28 p[tot2].x=b[i].x+b[i].l-mid+1; 29 p[tot2].y=b[i].y; 30 p[tot2++].l=0; 31 } 32 sort(c,c+tot1,cmp); 33 sort(p,p+tot2,cmp); 34 int j=0; 35 for(int i=0;i<tot1;i++){ 36 for(;j<tot2 && p[j].x<=c[i].x;j++) 37 if(p[j].l) M.insert(p[j].y); 38 else M.erase(p[j].y); 39 set<int>::iterator tmp=M.lower_bound(c[i].y); 40 if(tmp!=M.end() && (*tmp)<=c[i].y+c[i].l) return 1; 41 } 42 return 0; 43 } 44 45 int main(){ 46 cin>>n>>m; 47 for(int i=0;i<n;i++) 48 cin>>a[i].x>>a[i].y>>a[i].l; 49 for(int i=0;i<m;i++) 50 cin>>b[i].x>>b[i].y>>b[i].l; 51 int low=1,high=100000000; 52 while(low<=high){ 53 int mid=(low+high)>>1; 54 if(check(mid)) low=mid+1; 55 else high=mid-1; 56 } 57 cout<<low-1<<endl; 58 }
【E】 Loading...
【Codeforces Rockethon 2014】Solutions
原文：http://www.cnblogs.com/Delostik/p/3553114.html
