悬关,有注释
  • 板块P10512 序列合并
  • 楼主lch66
  • 当前回复0
  • 已保存回复0
  • 发布时间2024/5/30 21:14
  • 上次更新2024/5/31 09:01:03
查看原帖
悬关,有注释
907675
lch66楼主2024/5/30 21:14
#include<stdio.h>
#include<iostream>
#include<algorithm>
#include<queue>
#include<stack>
#include<math.h>
#include<map>
#include<string.h>
#include<string>
#include<set>
using namespace std;
#define ll long long
int n, m, x, f[200005][35] = { 0 }, cnt[35] = { 0 }, mmax = 0, vis[200005] = { 0 };
int main()
{//从高位开始判断,如果高位的0的个数小于当前的m,那么清除高位为0的数,m减去个数更新
	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	cin >> n >> m;
	for (int i = 1; i <= n; i++)
	{
		cin >> x;
		int t = 0;
		while (x > 0)//首先将所有的数存为二进制
		{
			f[i][t] = x % 2;
			if (x % 2)cnt[t]++;
			t++;
			x /= 2;
		}
		mmax = max(mmax, t);//mmax是最高可能的二进制位数
	}
	for (int i = 0; i < mmax; i++)
	{
		cnt[i] = n - cnt[i];//cnt数组存二进制第i位有多少个0
	}
	int d = mmax - 1;//d从最高位开始
	while (m > 0&&d>=0)
	{
		if (cnt[d] <= m)//如果d位0的个数小于等于m,那么将这些二进制第d位为0的数全部清除
		{
			m -= cnt[d];
			for (int i = 1; i <= n; i++)
			{
				if (!vis[i] && !f[i][d])//vis数组判断是否已经被清除,满足条件时清除
				{
					vis[i] = 1;
					for (int j = 0; j < mmax; j++)
					{
						if (!f[i][j])//清除时把该数二进制数位为0的贡献也清除掉
						{
							cnt[j]--;
						}
					}
				}
			}
		}
		d--;//d减一
	}
	int u = 1, ans = 0;
	for (int i = 0; i < mmax; i++)//最后判断
	{
		int flag = 1;
		for (int j = 1; j <= n; j++)
		{
			if (!vis[j] && !f[j][i])//没被清掉,且第i位为0,那么最后的合并就没有2^i
			{
				flag = 0;
				break;
			}
		}
		if (flag)
		{
			ans += u;
		}
		u *= 2;
	}
	cout << ans;
}
2024/5/30 21:14
加载中...