8月Day1

高士渠 LV 5 · 2026-8-3 20:49:00

主题：dp和异或

A.Qualification Rounds

https://qycode64.com/course/6a478a5569fcccaa3fd46c88/exam/6a6f9924205105c2c1af9983/problem/CF868C

题意：有n个问题，从中选任意个，使得每个队伍知道的问题数量是总题数的一半，输出可不可行。

思路：每道题对k支队伍的知识状态可以压缩成一个k位二进制数（k≤4，最多16种状态），只需检查是否存在非空状态组合使得每支队伍知道的题目数<=总数的一半，且可以证明只需考虑大小不超过2的子集

#include<bits/stdc++.h>
using namespace std;
int v[20],a[20][5];
int main(){
	freopen("rtmrts.in", "r", stdin);
	freopen("rtmrts.out", "w", stdout);
	int n,k;
	cin>>n>>k;
	for(int i=1;i<=n;i++){
		int s=0;
		for(int j=0;j<k;j++){
			int x;
			cin>>x;
			if(x)s=s*2+1;
			else s=s*2;
		}
		v[s]=1;
	}
	vector<int>b;
	for(int i=0;i<(1<<k);i++){
		if(v[i])b.push_back(i);
	}
	int m=b.size();
	for(int mask=1;mask<(1<<m);mask++){
		int c[5]={0};
		int tot=0;
		for(int i=0;i<m;i++){
			if(mask&(1<<i)){
				tot++;
				int tmp=b[i];
				for(int j=k-1;j>=0;j--){
					if(tmp%2)c[j]++;
					tmp/=2;
				}
			}
		}
		int ok=1;
		for(int j=0;j<k;j++){
			if(c[j]*2>tot){
				ok=0;
				break;
			}
		}
		if(ok){
			cout<<"YES\n";
			return 0;
		}
	}
	cout<<"NO\n";
	return 0;
}

B.Dima and a Bad XOR

https://qycode64.com/record/6a700036205105c2c1afa166?courseId=6a478a5569fcccaa3fd46c88

题意：给定一个n×m的矩阵，每行选一个数，使得这n个数的异或和>0。如果存在，输出 "TAK" 和每行选的列号；否则输出 "NIE"。

思路：初始化dp[0][0]=1，逐行转移，枚举当前行的每一列，最后检查 dp[n][i] 是否有i>0，如果有，回溯输出方案，否则输出 "NIE"

#include<bits/stdc++.h>
using namespace std;
int a[505][505],dp[505][1030],pre[505][1030],ans[505];
int main(){
	freopen("badxor.in","r",stdin);
	freopen("badxor.out","w",stdout);
	int n,m;
	cin>>n>>m;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			cin>>a[i][j];
		}
	}
	dp[0][0]=1;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			for(int k=0;k<1024;k++){
				if(dp[i-1][k]){
					int nxt=k^a[i][j];
					dp[i][nxt]=1;
					pre[i][nxt]=j;
				}
			}
		}
	}
	for(int i=1;i<1024;i++){
		if(dp[n][i]){
			cout<<"TAK\n";
			int cur=i;
			for(int j=n;j>=1;j--){
				ans[j]=pre[j][cur];
				cur^=a[j][ans[j]];
			}
			for(int j=1;j<=n;j++)cout<<ans[j]<<" ";
			cout<<"\n";
			return 0;
		}
	}
	cout<<"NIE\n";
	return 0;
}

C.Boboniu and Bit Operations

https://qycode64.com/course/6a478a5569fcccaa3fd46c88/exam/6a6f9924205105c2c1af9983/problem/CF1395C

题意：给定两个数组a和b，长度n和m（n,m<=200），每个数<512（2^9）。对每个a[i]，你需要选一个b[j]，令 c[i]=a[i]&b[j]（按位与）。不同i可选同一个j。求最小的c[1]|c[2]|...|c[n]。

思路：对于候选答案x，判断是否可行：对每个a[i]，是否存在某个b[j]，使得(a[i]&b[j])|x==x，这等价于：a[i]&b[j]是x的子集（即不会产生 x 以外的二进制位）如果所有a[i]都满足，则x可行。从小到大枚举x，第一个可行的就是答案。

#include<bits/stdc++.h>
using namespace std;
int a[210],b[210];
int main(){
	freopen("bit.in","r",stdin);
	freopen("bit.out","w",stdout);
	int n,m;
	cin>>n>>m;
	for(int i=1;i<=n;i++)cin>>a[i];
	for(int i=1;i<=m;i++)cin>>b[i];
	int ans=1000;
	for(int x=0;x<512;x++){
		int ok=1;
		for(int i=1;i<=n&&ok;i++){
			int flag=0;
			for(int j=1;j<=m;j++){
				if(((a[i]&b[j]) | x) == x){
					flag=1;
					break;
				}
			}
			if(!flag)ok=0;
		}
		if(ok){
			ans=x;
			break;
		}
	}
	cout<<ans<<"\n";
	return 0;
}

D.Factorials and Powers of Two

https://qycode64.com/course/6a478a5569fcccaa3fd46c88/exam/6a6f9924205105c2c1af9983/problem/CF1646C?lang=zh

题意：强大数=2的幂或阶乘。给定 n（≤ 1e12），求最少用多少个互不相同的强大数之和表示n。如果不可能，输出-1。

思路：枚举阶乘数的所有子集，剩余部分用二进制（2的幂）表示，注意去重冲突，取最小个数

#include<bits/stdc++.h>
using namespace std;
vector<long long>f;
int main(){
	freopen("factorials.in","r",stdin);
	freopen("factorials.out","w",stdout);
	int t;
	cin>>t;
	long long x=1;
	for(long long i=1;i<=15;i++){
		x=x*i;
		if(i>=3)f.push_back(x);
	}
	while(t--){
		long long n;
		cin>>n;
		long long ans=__builtin_popcountll((unsigned long long)n);
		int m=f.size();
		for(int mask=0;mask<(1<<m);mask++){
			long long sum=0,cnt=0,a=0;
			for(int i=0;i<m;i++){
				if(mask&(1<<i)){
					sum+=f[i];
					cnt++;
					long long tmp=f[i];
					if((tmp&(tmp-1))==0){
						int bit=0;
						long long p=1;
						while(p<tmp){
							p<<=1;
							bit++;
						}
						a|=(p);
					}
				}
			}
			if(sum>n)continue;
			long long rem=n-sum,bits=0,ok=1;
			long long p=1;
			for(int i=0;i<=60;i++){
				if(rem&p){
					if(a&p){
						ok=0;
						break;
					}
					bits++;
				}
				p<<=1;
			}
			if(ok)ans=min(ans,cnt+bits);
		}
		cout<<ans<<"\n";
	}
	return 0;
}

E.Party Lemonade

https://qycode64.com/course/6a478a5569fcccaa3fd46c88/exam/6a6f9924205105c2c1af9983/problem/CF913C

题意：有n种瓶子，第 i 种容量为2^(i-1)升，价格为ci卢布，每种无限供应。求至少买L升的最少花费。

思路：预处理价格使大瓶不贵于两个小瓶，小瓶不贵于大瓶，然后从大到小贪心买，同时考虑多买一个当前容量瓶子的情况取最小值。

#include<bits/stdc++.h>
using namespace std;
long long a[100],ans=4e18;
int main(){
	freopen("party.in","r",stdin);
	freopen("party.out","w",stdout);
	int n,l;
	cin>>n>>l;
	for(int i=1;i<=n;i++)cin>>a[i];
	for(int i=2;i<=n;i++)a[i]=min(a[i],a[i-1]*2);
	for(int i=n-1;i>=1;i--)a[i]=min(a[i],a[i+1]);
	long long sum=0;
	for(int i=n;i>=1;i--){
		int zx=l/(1LL<<(i-1));
		sum+=1LL*zx*a[i];
		l-=zx*(1LL<<(i-1));
		long long tmp=sum;
		if(l>0)tmp+=a[i];
		if(tmp<ans)ans=tmp;
	}
	cout<<ans<<"\n";
	return 0;
}

F.XOR, Expression and Two Binary Numbers

https://qycode64.com/course/6a478a5569fcccaa3fd46c88/exam/6a6f9924205105c2c1af9983/problem/CF2234D

题意：有一个长度为 2^k+1的序列，每个元素是n位二进制数。已知首尾两个数，按规则用异或填充中间位置。求所有位置的popcount*(n-popcount)的和

思路：填充过程中，每个位置只可能是三种值：A，B，C(A&B)，分别统计出现次数，用popcount计算贡献后求和。

#include<bits/stdc++.h>
using namespace std;
int main(){
	freopen("binary.in","r",stdin);
	freopen("binary.out","w",stdout);
	int t;
	cin>>t;
	while(t--){
		int n,k;
		string s,z;
		cin>>n>>k>>s>>z;
		long long oneA=0,oneB=0,oneC=0;
		for(int i=0;i<n;i++){
			if(s[i]=='1')oneA++;
			if(z[i]=='1')oneB++;
			if(s[i]!=z[i])oneC++;
		}
		long long end=1,mid=1;
		for(int i=2;i<=k;i++){
			long long nend=end+mid;
			long long nmid=2*end-1;
			end=nend;
			mid=nmid;
		}
		if(k==1){
			end=1;mid=1;
		}
		long long ans=0;
		ans+=end*oneA*(n-oneA);
		ans+=end*oneB*(n-oneB);
		ans+=mid*oneC*(n-oneC);
		cout<<ans<<"\n";
	}
	return 0;
}

已修改 4 次查看举报

8月Day1

主题：dp和异或

A.Qualification Rounds

B.Dima and a Bad XOR

C.Boboniu and Bit Operations

D.Factorials and Powers of Two

E.Party Lemonade

F.XOR, Expression and Two Binary Numbers

0 条评论

目前还没有评论...

8月Day1

主题：dp和异或

A.Qualification Rounds

B.Dima and a Bad XOR

C.Boboniu and Bit Operations

D.Factorials and Powers of Two

E.Party Lemonade

F.XOR, Expression and Two Binary Numbers

0 条评论

目前还没有评论...

还没有账户？

登录