首页 > 其他分享 >Codeforces Round 912 (Div. 2)

Codeforces Round 912 (Div. 2)

时间:2023-12-01 13:22:06浏览次数:33  
标签:std int Codeforces cin 011 ans Div include 912

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";
            }
        }
    }

标签:std,int,Codeforces,cin,011,ans,Div,include,912
From: https://www.cnblogs.com/kdlyh/p/17869486.html

相关文章

  • RuCode 2020 Division A+B. I ✖ [PR #5] 和平共处
    前言认认真真学习了一下这道题相关的做法以及有关的二分图网络流理论,感觉自己又刷新了一些东西的理解。所以说我们就从普通的二分图匹配开始吧!二分图匹配众所周知,二分图最大匹配可以用网络流Dinic算法做到\(O(m\sqrtn)\)的复杂度。在某些特定的图下,我们有一种“贪心流”......
  • [Codeforces] CF1591C Minimize Distance
    CF1591CMinimizeDistance题目一条线上有\(n\)(\(1\len\le2\cdot10^5\))个仓库,第\(i\)个仓库的位置是\(x_i\)(\(1\lei\len\))。你有\(n\)箱货物,要分别运到这\(n\)个仓库里。你的初始位置在点\(0\),一次可以携带\(k\)(\(1\lek\len\))箱货物。在送完携带......
  • [Codeforces] CF1603A Di-visible Confusion
    CF1603ADi-visibleConfusion题目给一个长度为\(n\)的序列\(a_1,a_2,\dots,a_n\),对于每个位置\(i\),如果\(a_i\%\left(i+1\right)\not=0\),就可以将\(a_i\)删掉。删掉之后,后面的数都会往前面移动一位。问能否将序列删成空。数据范围\(1\let\le10^4,1\len\le10^5,1\le......
  • [AGC052C] Nondivisible Prefix Sums 题解
    题目链接点击打开链接题目解法好题!一个序列是不合法的,必定满足某些结论,我们不妨猜测一下首先如果和为\(P\)的倍数,必定不合法然后手玩几个可以发现,最极限的情况是\(P-1\)个\(1\;+\;\)\(b_i\;+\;\)\(P-b_i\)如果在这个情况下再加一个\(1\),就爆了其中\(1\)可以替......
  • Codeforces Round 883 (Div. 3)
    CodeforcesRound883(Div.3)A.RudolphandCuttheRope题意:有一颗糖果在连在绳子上,求剪短多少根绳子,他能落地思路:只要绳子长度比钉子高度大就不用减#include<bits/stdc++.h>usingnamespacestd;voidsolve(){intn,res=0;cin>>n;while(n--)......
  • Codeforces Round 911 (Div. 2)
    CodeforcesRound911(Div.2)基本情况A题秒了。B题条件没想明白,也不造点数据就无脑交,导致罚了不少时。B.LauraandOperations我先推出了,对于一个数,当另外两个数的个数之和为偶数时解可行,且这个数本身要能跟后面数替换。比如11223333就可以操作122333(1......
  • Codeforces Round 910 (Div. 2)
    https://codeforces.com/contest/1898C题可以造一个大小为4的环,然后再造一个来回,这样就解决了%4=0,%4=2的情况,而奇数的情况显然无解。#include<cstdio>#include<algorithm>#include<cstring>#include<cmath>#include<map>#include<vector>#include<set>#includ......
  • Codeforces Round 829 (Div. 1)A1. Make Nonzero Sum (easy version)(思维找规律)
    先考虑无解的情况:当n为奇数时无解相邻的两个元素一定可以变成0\[a[i]!=a[i+1]时,分成[i,i],和[i+1,i+1]\]\[a[i]=a[i+1]时,分成[i,i+1]\]这两种情况对答案的贡献都是0,当n为奇数时我们总会有一个没办法凑成0.#include<bits/stdc++.h>#definelsp<<1#......
  • Educational Codeforces Round 158 (Rated for Div. 2)
    A.LineTripThereisaroad,whichcanberepresentedasanumberline.Youarelocatedinthepoint\(0\)ofthenumberline,andyouwanttotravelfromthepoint\(0\)tothepoint\(x\),andbacktothepoint\(0\).Youtravelbycar,whichs......
  • CodeTON Round 7 (Div. 1 + Div. 2, Rated, Prizes!)
    看到B官方题解写了一堆,而如果能注意到一些性质,几行就写完了题意:给一个A,B构成的字符串,可以将“AB”翻转成"BA",问最多可以进行多少次翻转?实际上在手动模拟以后发现,由于题目限制了每个位置只能翻转一次,所以情况简单了不少。只要还没过最后一个B,那么最后一个B之前的所有A就会被反......