CF1107

丢人场。
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;
}

发表评论

您的电子邮箱地址不会被公开。