首页 > 代码库 > Codeforces 164 E Compatible Numbers
Codeforces 164 E Compatible Numbers
题目链接~~>
做题感悟:确实是好题,做拉的比赛的时候想了很久,想到枚举变幻某一位的 0 为 1 ,但是每个数都这样枚举岂不超时的节奏,当时没想到其实从大到小枚举一次就 ok 了。
解题思路:
本题要求两个数 a & b = 0 , 如果 a = 10010 , b 至少(指在 a 中的为 1 的位必须为 0 )是 01101 ,还可以是 00101 ,00001 ,00000。就相当于你去买东西一样,先提出你的要求(必须满足),至于其他方面都无所谓。这样我们可以枚举 b 中的 1 ,让其变为 0 ,那么,怎样枚举呢 ? 一个一个的枚举是不可以的,肯定超时,我们可以统一枚举一下,就跟状态压缩更新状态一样,相当于递推,用动态规划的思想去优化它,每个数最多只变化 0 的个数,然后再用变化了的数去变化。
代码:
#include<iostream> #include<sstream> #include<map> #include<cmath> #include<fstream> #include<queue> #include<vector> #include<sstream> #include<cstring> #include<cstdio> #include<stack> #include<bitset> #include<ctime> #include<string> #include<cctype> #include<iomanip> #include<algorithm> using namespace std ; #define INT __int64 #define L(x) (x * 2) #define R(x) (x * 2 + 1) const int INF = 0x3f3f3f3f ; const double esp = 0.0000000001 ; const double PI = acos(-1.0) ; const INT mod = 1e9 + 7 ; const int MY = 15 ; const int MX = (1<<22) + 5 ; int n ; int dp[MX] ,g[MX] ; int main() { //freopen("input.txt" ,"r" ,stdin) ; while(~scanf("%d" ,&n)) { int S = (1<<22) - 1 ; memset(dp ,0 ,sizeof(dp)) ; for(int i = 0 ;i < n ; ++i) { scanf("%d" ,&g[i]) ; dp[g[i]^S] = g[i] ; // g[I] 需要的另一半 } for(int i = S ; i >= 0 ; --i) // 枚举各种状态 { if(!dp[i]) // 如果没有存值 { for(int j = 0 ;j < 22 ; ++j) // 给其添加 1 让其变成有值 if(dp[i|(1<<j)]) dp[i] = dp[i|(1<<j)] ; } } for(int i = 0 ;i < n ; ++i) { if(i) cout<<" " ; if(dp[g[i]]) cout<<dp[g[i]] ; else cout<<"-1" ; } cout<<endl ; } return 0 ; }
Codeforces 164 E Compatible Numbers
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。