526互联

Codeforces Round 912 (Div. 2)

发布时间 2023-12-01 13:23:03作者: 加固文明幻景

Codeforces Round 912 (Div. 2)

基本概述

最难受的一集。

A 题秒了。

B 题幸苦推了两个小时，最后也通过了pretest了，结果赛后被 HACK。

C 题知道是DP，但觉得不好推状态转移方程，所以全心全意去做 B 题了。

爆掉 \(150\) 分

B. StORage room

我的思路

其实就几乎是答案。

之前几乎没怎么碰过位运算的题目，一开始先搞清楚按位或运算，然后我把样例输入和输出都用二进制搞出来。

对于样例一：

1 2 3 4
1 000 011 011 101
2 011 000 011 111
3 011 011 000 111
4 101 111 111 000
1 2 3 4
001 011 010 101

经过一大堆推导，我得出几个结论：

  • 因按位或只能增加 \(1\) 的个数，不能增加 \(0\) 的个数，所以 \(0\) 比 \(1\) 重要，所以要尽可能地保留 \(0\)。
  • 与第 \(i\) 个答案相关的所有格子刚好是样例的第 \(i\) 行或者第 \(i\) 列。

至少对于样例来说，这个想法没问题，但我一开始没看到解不唯一，还卡了好一会。

然后得出做法：

  • 对于第 \(i\) 个答案，将第 \(i\) 行所有数按位与，结果就是答案。

  • 卡了一会，也想出了怎么验证解正确性，因为数据不大，直接带入验证就可以。

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <bitset>
#include <cstring>

const int N = 1e3 + 10;

int map[N][N];
int ans[N];

int main()
{
	std::ios::sync_with_stdio(false);
	std::cin.tie(nullptr);
	std::cout.tie(nullptr);
	int t, n;
	std::cin >> t;
	while (t--)
	{
		memset(ans, 0, sizeof(ans));
		int cnt = 0, zsum = 0;
		std::cin >> n;
		for (int i = 1; i <= n; i++)
			for (int j = 1; j <= n; j++)
			{
				std::cin >> map[i][j];
			}
		for (int i = 1; i <= n; i++)
		{
			for (int j = 1; j <= n; j++)
			{
				if (j == i)
				{
					continue;
				}
				if (!ans[i])
				{
					ans[i] = map[i][j];
				}
				else
				{
					ans[i] = (ans[i] & map[i][j]);
				}
			}
		}
		bool ok = true;
		for (int i = 1; i <= n; i++)
		{
			for (int j = 1; j <= n; j++)
			{
				if (i == j)
					continue;
				if (map[i][j] != (ans[i] | ans[j]))
				{
					ok = false;
					break;
				}
			}
		}
		if (ok)
		{
			std::cout << "YES\n";
			for (int i = 1; i <= n; i++)
			{
				std::cout << ans[i] << " ";
			}
			std::cout << std::endl;
		}
		else
		{
			std::cout << "NO\n";
		}
	}
	return 0;
}

然而被赛后的数据点干碎了。靠

3
0 0 1
0 0 1
1 1 0

这玩意，我的程序输出的是

NO

然后产生的答案是

1 1 1

然而按照我的思路来说，应该要得出正确答案才对。

毕竟 \(0 \&1 = 0, 0\&1 =0, 1\&1 = 1\)。

而正确答案也确实是这个。

然后我检查了一下代码，真是靠了。

if (!ans[i])
{
	ans[i] = map[i][j];
}

这个 if 我的本意是用来判断除了 \(i = j\) 的第一个数，然后因为是第一个数，\(ans\)之前还没有存，所以不能直接按位与，而是先存进去。

但是对于这个数据，根本不能用这样一个 if 判断！

因为当出现连续的两个 \(0\) 的时候，第三个 \(1\) 本该参与之后的按位与运算了，但无奈 \(ans_i\) 此时等于 \(0\)，所以这个 if 执行了！！！导致第三个 \(1\) 直接赋值给了 \(ans\)。

修改就很简单了，把 \(ans\) 的初始值搞成一个不可能出现的数就行，我改成了 \(-1\)。

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <bitset>
#include <cstring>

const int N = 1e3 + 10;

int map[N][N];
int ans[N];

int main()
{
	std::ios::sync_with_stdio(false);
	std::cin.tie(nullptr);
	std::cout.tie(nullptr);
	int t, n;
	std::cin >> t;
	while (t--)
	{
		memset(ans, -1, sizeof(ans));
		int cnt = 0, zsum = 0;
		std::cin >> n;
		for (int i = 1; i <= n; i++)
			for (int j = 1; j <= n; j++)
			{
				std::cin >> map[i][j];
			}
		for (int i = 1; i <= n; i++)
		{
			for (int j = 1; j <= n; j++)
			{
				if (j == i)
				{
					continue;
				}
				if (ans[i] != -1)
				{
					ans[i] = map[i][j];
				}
				else
				{
					ans[i] = (ans[i] & map[i][j]);
				}
			}
		}
		bool ok = true;
		for (int i = 1; i <= n; i++)
		{
			for (int j = 1; j <= n; j++)
			{
				if (i == j)
					continue;
				if (map[i][j] != (ans[i] | ans[j]))
				{
					ok = false;
					break;
				}
			}
		}
		if (ok)
		{
			std::cout << "YES\n";
			for (int i = 1; i <= n; i++)
			{
                ans[i] = (ans[i] == -1) ? 0 : ans[i];
				std::cout << ans[i] << " ";
			}
			std::cout << std::endl;
		}
		else
		{
			std::cout << "NO\n";
		}
	}
	return 0;
}

真的是，魔鬼就在细节中啊。

标答思路

Solution:

Initially, we set all \(a_i = 2^{30} - 1\) (all bits on).

You can through every \(i\),\(j\) such that \(i \neq j\) and do \(a_i \&= M_{i,j}\) and \(a_j \&= M_{i,j}\).

Then we check if \(M_{i,j} = a_i \& a_j\) for all pairs. If this holds you found the array else the answer is NO.

Proof:

Initially, all elements have all their bits set on and we remove only the bits that affect our answer. If \(M_{i,j}\) doesn't have a specific bit then definitely neither \(a_i\) nor \(a_j\) should have it. If \(M_{i,j}\) has a specific bit on then we don't have to remove anything (in the end we want at least one of \(a_i\) and \(a_j\) to have the bit on).

#include <bits/stdc++.h>
using namespace std;
int main(){
        ios_base::sync_with_stdio(0);
        cin.tie(0);
        int t;
        cin>>t;
        while(t--){
            int n;
            cin>>n;
            int m[n][n];
            int arr[n];
            for(int i = 0;i < n;i++){
                arr[i] = (1<<30) - 1;
            }
            for(int i = 0;i < n;i++){
                for(int j = 0;j < n;j++){
                    cin>>m[i][j];
                    if(i != j){
                        arr[i] &= m[i][j];
                        arr[j] &= m[i][j];
                    }
                }
            }
            bool ok = true;
            for(int i = 0;i < n;i++){
                for(int j = 0;j < n;j++){
                    if(i != j && (arr[i] | arr[j]) != m[i][j]){
                        ok = false;
                    }
                }
            }
            if(!ok){
                cout<<"NO\n";
            }
            else{
                cout<<"YES\n";
                for(int i = 0;i < n;i++){
                    cout<<arr[i]<<" ";
                }
                cout<<"\n";
            }
        }
    }