2024-04-05

magic

首先 \(n\) 肯定得是 \(R+B\) 的倍数

当 \(\tt R\) 和 \(\tt B\) 的数量除上输入的 \(R\) 和 \(B\) 的比值相同时有解

题解里面有特别神奇的归纳法证明

构造方法就是维护一个栈 栈顶的 \(R+B\) 个符合条件就存到答案里面

但是我在考场上就是想不出来咋做，别人都咋会的，不懂

是我写代码的习惯不好么为甚么别人不特判 0 挂 10 分我不特判就一分没有啊我真服

#include<iostream>
#include<cstring>
#include<algorithm>
#include<vector>

using namespace std;

const int N=1e5+10;

int n;
int R,B;
int rd,bl;

char s[N];

int ctt[N],top,stk[N];

vector<int> ans[N];
int num;

bool judge() {
	if(R==0&&B==0) return false;
	if(n%(R+B)!=0) return false;
	if((R==0&&rd!=0)||(B==0&&bl!=0)) return false;
	if(R==0||B==0) return true;
	if((rd%R!=0)||(bl%B!=0)) return false;
	if(rd/R!=bl/B) return false;
	return true;
}

int main() {
	freopen("magic.in","r",stdin);
	freopen("magic.out","w",stdout); 
	scanf("%d%d%d",&n,&R,&B);
	for(int i=1;i<=n;i++) {
		cin>>s[i];
		if(s[i]=='R') rd++;
		else bl++; 
	}
	if(!judge()) {
		puts("NO");
		return 0;
	}
	for(int i=1;i<=n;i++) {
		stk[++top]=i;
		ctt[top]=ctt[top-1];
		if(s[i]=='R') ctt[top]++;
		if(top>=R+B) {
			if(ctt[top]-ctt[top-B-R]==R) {
				num++;
				int tar=top-R-B;
				while(top>tar) {
					ans[num].push_back(stk[top]);
					top--;
				}
			}
		}
	}
	puts("YES");
	printf("%d\n",num);
	for(int i=num;i;i--) {
		for(int j=0;j<ans[i].size();j++) printf("%d ",ans[i][j]);
		puts("");
	}
	
	return 0;
}

key

模拟赛第二题

只需考虑重要度之和小于 \(m\) 的极大的子集，因为如果极大的子集都不能打开房门，那么重要度之和更小的集合由于钥匙更少，更不可能打开房门

存在一种方案使得答案就是这样的集合的个数
这种方案是：

所以答案就是满足这样的要求的集合的数量

• 和小于 \(m\)
• 加上不在这个集合内的最小的数之后大于等于 \(m\)

#include<iostream>
#include<cstring>
#include<algorithm>

using namespace std;

typedef long long ll;

const ll Inf=1e18;
const int N=25;

int n;
ll m,a[N],sm,mn;

int main() {
	freopen("key.in","r",stdin);
	freopen("key.out","w",stdout); 
	scanf("%d%lld",&n,&m);
	for(int i=1;i<=n;i++) scanf("%lld",&a[i]),sm+=a[i];
	if(sm<m) {
		puts("1");
		return 0;
	}
	int ans=0;
	for(int S=0;S<(1<<n)-1;S++) {
		sm=0,mn=Inf;
		for(int i=1;i<=n;i++) {
			if((S>>(i-1))&1) sm+=a[i];
			else mn=min(mn,a[i]);
		}
		if(sm<m&&sm+mn>=m) ans++;
	}
	printf("%d\n",ans);
	
	return 0;
}