CF1111

我一直以为这一天是除夕来着，不过也不算错就是了。
一场超级变态的比赛。具体来说就是：

We are sincerely apologize for the weak pretest of problem B.

——出题人

实际造成的效果就很感人了_(:з」∠)_，三分之一的选手被Hack，结束之后剩下的三分之二中的三分之二又FST了。

总之，我在只有两题的情况下涨分了…

---

CF1111A
热身题，暴力上个比较就行了。
（其实我没看数据范围，但复杂度大概是对的。）

---

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#include<vector>
using namespace std;

const char yuan[]={'a','e','i','o','u'};
bool bo1[200005],bo2[200005];
char ch1[200005],ch2[200005];
int n1,n2;
void init(){
	std::cin>>ch1+1;
	std::cin>>ch2+1;
	n1=strlen(ch1+1),n2=strlen(ch2+1);
	if(n1!=n2){
		puts("No");
		return;
	}
	for(int i=1;i<=n1;++i){
		for(int j=0;j<5;++j){
			if(ch1[i]==yuan[j]){
				bo1[i]=1;
			}
			if(ch2[i]==yuan[j]){
				bo2[i]=1;
			}
		}
	}
	for(int i=1;i<=n1;++i){
		if(bo1[i]!=bo2[i]){
			puts("No");
			return;
		}
	}
	puts("Yes");
	return;
}
int main(){
	init();
	return 0;
}

---

CF1111C
发现两个结论：
如果一个要塞下面有英雄，除非英雄全部聚集在某半边，否则一定是剖开来处理更优。
如果一个要塞下面是空的，一定是不剖开处理更优。
这两个结论都可以有用题目给出的式子来轻易地证明。
所以我们现在要考虑的就是如果一个要塞下面有英雄并且英雄全部聚集在某半边的情况。
考虑分治。
但是最后有一个问题：如何快速地统计一个区间之内的英雄数量？
虽然数据范围很大，但是排个序然后大力二分统计即可。
善用upperbound。

---

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#include<vector>
using namespace std;
/*

*/ 
long long n,k,A,B;
long long ans=0;
long long a[100005];
//所有[L,R]之间的英雄个数。
//显然upperbound(L-1)并且upperbound(R),相减即可。 
inline long long calc(int L,int R){
	return (std::upper_bound(a+1,a+1+k,R)-std::upper_bound(a+1,a+1+k,L-1)); 
}
inline long long dfs(int L,int R){
	if(L==R){
		int X=calc(L,R);
		return X?B*X:A;
	}
	if(!calc(L,R)){
		return A;
	}
	int MID=(L+R)>>1;
	if(!calc(L,MID)||!calc(MID+1,R)){
		return std::min(B*(R-L+1)*calc(L,R),dfs(L,MID)+dfs(MID+1,R));
	}else{
		return dfs(L,MID)+dfs(MID+1,R);
	}
}
void init(){
	scanf("%I64d%I64d%I64d%I64d",&n,&k,&A,&B);
	for(int i=1;i<=k;++i){
		scanf("%I64d",a+i);
	}
	std::sort(a+1,a+1+k);
	printf("%I64d",dfs(1,1<<n));
}
int main(){
	init();
	return 0;
}