郴州哪里做网站,网站建设公司 青岛,wordpress云主机模板,合肥专业网站制作题目#xff1a; 题意#xff1a;
如果点x和y有连边#xff0c;当且仅当a[x] or a[y] 260 - 1 #xff08;两者是充分必要#xff09; 现在给你边的关系#xff0c;问你每个点的值应该是多少#xff1f;#xff08;给出一种情况即可#xff09;
题解#xff1a;
…题目 题意
如果点x和y有连边当且仅当a[x] or a[y] 260 - 1 两者是充分必要 现在给你边的关系问你每个点的值应该是多少给出一种情况即可
题解
构造题思路非常巧妙 260就是160,减去1也就是从第一位到第59位都是1第六十位是0省略了 首先01染色将点分为黑点和白点让白色的点为个数少一些的 选数量较少的一组是确保数量小于等于 50 现在每个点都要节点编号id和颜色 id为该点的编号 对于白色的点我们让其最高位为0让其第id位也是0其余位置都是1 对于黑色我们让其最高位是1与它相邻的所有点也就是白点的第id位置为1其余为0
我们来分析分析为什么这样构造是对的 因为所有白色的最高位是0所以确保了所有白色之间没有边。 白色的点第id为也是0而与它相邻的黑点第id位是1两者首位也是0和1正好or后就是260 - 1这就是确保了黑色与所哟相邻的白色节点满足条件 因为黑点除了首位只要相邻的白点的第id位是1所有当一个白点与该黑点不相连时黑点给不了白点所需要位置上的1
综上所述就是黑点所多的也就是1的部分是相邻白点所缺的位置 这个构图不禁让人感叹妙啊~~
代码
#includebits/stdc.h
typedef long long ll;
using namespace std;
inline int read(){int s0,w1;char chgetchar();while(ch0||ch9){if(ch-)w-1;chgetchar();}while(ch0ch9) ss*10ch-0,chgetchar();//s(s3)(s1)(ch^48);return s*w;
}
const int maxn400;
ll ans[maxn],id[maxn];
vectorintg[maxn],color[2];
void dfs(int x,int fa,int col)
{color[col].push_back(x);for(auto v:g[x]){if(vfa)continue;dfs(v,x,col^1);}
}
int main()
{//cout((12312312-2)|1);int n;cinn;for(int i1;in;i){int u,v;cinuv;g[u].push_back(v);g[v].push_back(u);}dfs(1,0,1);//染色过程if(color[0].size()color[1].size())swap(color[0],color[1]);//然后白色为少的 for(int i0;icolor[0].size();i)//对于白色 {int vcolor[0][i];ans[v](1ll60)-1-(1ll59)-(1lli);id[v]i;}for(int i0;icolor[1].size();i){int ucolor[1][i];ll tmp(1ll59);//首位是1for(auto v:g[u]){tmp(1llid[v]);//与第v位相连该点编号是id[v] } ans[u]tmp;id[u]i;}for(int i1;in;i)if(i1) printf(%lld,ans[i]);else printf( %lld,ans[i]);
}
