博客主页:PH_modest的博客主页
当前专栏:每日一题
其他专栏:
每日反刍
* C++跬步积累
* C语言跬步积累
座右铭:广积粮,缓称王!
一.题目描述
题目大意:
塞浦路斯的天气非常炎热。因此,Theofanis 将此视为创建一家冰淇淋公司的契机。
他把冰淇淋锁在大储藏室里,防止其他冰淇淋生产商进入。然而,他忘记了密码。幸运的是,这把锁对健忘的人有特殊的功能!
要打开这把锁,你需要找到一个由 n n n 个元素组成的数组 a a a :
- KaTeX parse error: Expected 'EOF', got '&' at position 11: 0 \le a_i &̲lt; 2^{30} 和
- M i , j = a i ∣ a j M_{i,j} = a_i | a_j Mi,j=ai∣aj 对于所有 i ≠ j i \neq j i=j ,其中 ∣ | ∣ 表示 bitwise OR 运算。
这个锁有一个 bug,有时它会给出没有任何解的表格。在这种情况下,冰激凌将永远保持冰冻状态。
你能找到一个数组来打开锁吗?
题目链接:
B. StORage room(Codeforces Round 912 (Div. 2))
二.思路分析
- 首先需要知道 | 操作符的特点:只有两个数对应位上都是0时,结果的对应才是0,否则是1
- 所以我们可以假设xi为0x7fffffff(每一位上都是1),然后用这个数与结果进行&操作,操作结束之后,就会把肯定是0的位上的1变成0(觉得难理解的可以试着用样例模拟一下)
三.代码展示
//https://codeforces.com/contest/1903/problem/B
//两个数|,如果结果的某一位为0,那么这两个数对应的位也为0
//
#include<iostream>
#include<algorithm>
#include<string>
#include<deque>
#include<map>
#include<queue>
#include<vector>
#include<cstring>
#define int long long
using namespace std;
int s[2000][2000];
int v[200020];
void solve()
{
memset(v,0x7fffffff,sizeof(v));
int n;
cin>>n;
for(int i=0;i<n;i++)
{
for(int j=0;j<n;j++)
{
cin>>s[i][j];
}
}
for(int i=0;i<n;i++)
{
for(int j=0;j<i;j++)
{
v[i]&=s[i][j];
}
for(int j=i+1;j<n;j++)
{
v[i]&=s[i][j];
}
}
int flag=1;
for(int i=0;i<n;i++)
{
for(int j=0;j<n;j++)
{
if(i!=j&&(v[i]|v[j])!=s[i][j])
{
flag=0;
break;
}
}
if(flag==0)
{
break;
}
}
if(flag==0)
{
cout<<"NO"<<"\n";
}
else if(n==1)
{
cout<<"Yes"<<"\n";
cout<<"1"<<"\n";
}
else
{
cout<<"Yes"<<"\n";
for(int i=0;i<n;i++)
{
cout<<v[i]<<" ";
}
cout<<"\n";
}
}
signed main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int t;
cin>>t;
while(t--)
{
solve();
}
return 0;
}
最后:
每日一题系列旨在养成刷题的习惯,所以对代码的解释并不会特别详细,但足够引导大家写出来,选的题目都不会特别难,但也不是特别简单,比较考验大家的基础和应用能力,我希望能够将这个系列一直写下去,也希望大家能够和我一起坚持每天写代码。
之后每个星期都会不定期更新codeforces和atcoder上的题目,想要学习算法的友友们千万别错过了,有什么疑问欢迎大家在评论区留言或者私信博主!
在这里送大家一句话:广积粮,缓称王!
文章评论