每日归档： 2019年2月4日

丢人场。
C题想了一个单调队列优化DP，然后瞎jb写，最后还是别人提醒了才发现自己傻了。

---

CF1107A
显然分成两段：第一个数和剩下全部的数是最容易想到的，也一定是合法的。
对于只有两个字符的要特殊处理。

---

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

int n;
char ch[305];
 
void init(){
	memset(ch,0,sizeof(ch));
	scanf("%d",&n);
	cin>>ch+1;
	if(n==2&&ch[1]>=ch[2]){
		puts("NO");
		return;
	}
	puts("YES");puts("2");
	printf("%c ",ch[1]);
	for(int i=2;i<=n;++i){
		putchar(ch[i]);
	}
	puts("");
}
int main(){
	int T;
	scanf("%d",&T);
	while(T--){
		init();
	}
	return 0;
}

---

CF1107B
找规律题。没什么好说的。当然要证明也是可以的，感觉用归纳法是可以，时间不够就没有证明了。

---

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

int n;
long long k,x,ans;

void init(){
	scanf("%d",&n);
	for(int i=1;i<=n;++i){
		scanf("%I64d%I64d",&k,&x);
		ans=(k-1)*9+x;
		printf("%I64d\n",ans);
	}
}
int main(){
	init();
	return 0;
}

---

CF1107C
傻逼贪心，我不知道我怎么想成单调队列优化DP的。
具体来说就是用pq尽可能删小的。正确性（可能一点都不）显然。

---

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

priority_queue<int,vector<int>,greater<int> > q;
char ch[200005];
int a[200005];
void init(){
	int n,K;
	scanf("%d%d",&n,&K);
	long long ans=0;
	for(int i=1;i<=n;++i){
		scanf("%d",&a[i]);
		ans+=a[i]; 
	}
	cin>>ch+1;
	int tot=1;
	for(int i=1;i<=n;++i){
		if(ch[i]==ch[i-1]){
			q.push(a[i]);
			++tot;
			while(tot>K&&!q.empty()){
				ans-=q.top();
				q.pop();
				--tot;
			}
		}else{
			tot=1;
			while(!q.empty()){
				q.pop();
			}
			q.push(a[i]);
		}
	}
	printf("%I64d\n",ans);
}
int main(){
	init();
	return 0;
}

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

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;
}