这一场打得还行，可惜C没有调出来。不过还是暴涨七百多分。摸不透算分机制。
AGC 29 A
给定一个01序列，每一次可以把01变成10，求最大操作次数。
猜结论题（其实证明很显然）。结论是每一个1后面的0的个数之和。
#include<iostream>
#include<cstdio>
#include<cstring>
int n;
char ch[200005];
int sm[200005];
void init(){
std::cin>>(ch+1);
n=std::strlen(ch+1);
for(int i=1;i<=n;++i){
ch[i]=(ch[i]=='B'?1:0);
}
sm[n+1]=0;
for(int i=n;i>=1;--i){
sm[i]=sm[i+1]+(ch[i]^1);
}
long long ans=0;
for(int i=1;i<=n;++i){
if(ch[i]){
ans+=sm[i+1];
}
}
printf("%lld",ans);
}
int main(){
init();
return 0;
}AGC 29 B
给定一个序列，问从中最多能找出多少个数对使得它们的和是二的次幂。
贪心。考虑从大往小遍历，如果一个大的数能够找到一个比它小的数配成二的次幂，那么不选这个大的数肯定不会更优。
用\(map\)优化一下即可。
#include<iostream>
#include<cstdio>
#include<map>
#include<algorithm>
std::map<int,int> mp;
int n,a[200005];
void init(){
scanf("%d",&n);
for(int i=1;i<=n;++i){
scanf("%d",a+i);
mp[a[i]]?(++mp[a[i]]):mp[a[i]]=1;
}
std::map<int,int>::iterator it=mp.end();
--it;
int ans=0,nw;
while(1){
if(it->second==0){
goto loop;
}
nw=it->first;
for(int i=30;i>=1;--i){
while(it->second>=1&&(1<<i)-nw>=0&&mp[(1<<i)-nw]>=1&&(nw!=(1<<(i-1)))){
--mp[(1<<i)-nw];
it->second-=1;
++ans;
}
while(it->second>=2&&nw==(1<<(i-1))){
it->second-=2;
++ans;
}
}
loop:
if(it==mp.begin()){
break;
}
--it;
}
printf("%d\n",ans);
}
int main(){
init();
return 0;
}AGC 29 D
容易知道，每一轮T一定是能走就走。因为如果T不走，那么A就可以通过不走来强迫游戏结束。
并且，如果P经过了一个障碍上方，游戏就结束了。所以A一定会尽可能地让P走到一个障碍上方。
故而，A不往右走，只有两种情况。一，是下方存在一个障碍；二，是右边有障碍挡住。
很显然，如果固定起始点，只有横坐标与纵坐标相同的点才会挡住A。
因此，每一次A被挡住了，就更新起始点，然后向下走即可。
#include<iostream>
#include<cstdio>
#include<algorithm>
struct data{
int x;int y;
inline bool operator<(const data &B){
return x==B.x?y<B.y:x<B.x;
}
inline void init(int X,int Y){
x=X,y=Y;
}
}a[200005];
int n,h,w;
void init(){
scanf("%d%d%d",&h,&w,&n);
int x,y;
for(int i=1;i<=n;++i){
scanf("%d%d",&x,&y);
a[i].init(x,y);
}
std::sort(a+1,a+1+n);
int nw=0;
for(int i=1;i<=n;++i){
if(a[i].x-nw==a[i].y){
++nw;
}
if(a[i].x-nw>a[i].y){
printf("%d\n",a[i].x-1);
return;
}
}
printf("%d\n",h);
}
int main(){
init();
return 0;
}