AGC029

这一场打得还行，可惜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;
}