- 浏览: 376909 次
- 性别:
- 来自: 杭州
文章分类
最新评论
-
wsyzyrxp:
非常感谢 兄弟 帮了我大忙
[opengl]弹簧质点法模拟柔性布料以及椭球碰撞的opengl实现 -
mingdry0304:
[opengl]彩色立方体旋转 -
tyfengyu:
我刚刚更改的代码加上了标准差stdVal,故recoMat应该 ...
[python]用python实现的pca算法 -
tyfengyu:
python的pca代码有2处错误:1.finalData = ...
[python]用python实现的pca算法 -
暴风雪:
McFlurry 写道前排(凑字数)!擦你怎么摸来这里的
诈尸总结
大致题意:
给出下面一段代码
很明显这段代码是用a[n]数组来计算出b[n][n]。
void calculate(int a[N], int b[N][N]) { for (int i = 0; i < N; ++i) { for (int j = 0; j < N; ++j) { if (i == j) b[i][j] = 0; else if (i % 2 == 1 && j % 2 == 1) b[i][j] = a[i] | a[j]; else if (i % 2 == 0 && j % 2 == 0) b[i][j] = a[i] & a[j]; else b[i][j] = a[i] ^ a[j]; } } }
现在给出b[n][n]数组,求是否存在一个合法的a[n]数组,使其能计算出已经给出的b[][];
大致思路:
2-sat的思路很容易想到,就是考虑所有数字的31个位,对所有的位分为两组-----这个位是0,这个位是1,再按照上面的代码建立逻辑关系,再建图2-sat。
#include<iostream> #include<cstdio> #include <algorithm> #include<cstring> using namespace std; const int inf=1<<30; const int nMax=6000; const int mMax=1000010; class edge{ public: int v,nex; };edge e[mMax]; int k,head[nMax];//head[i]是以点i为起点的链表头部 void addedge(int a,int b){//向图中加边的算法,注意加上的是有向边//b为a的后续节点既是a---->b e[k].v=b; e[k].nex=head[a]; head[a]=k;k++; } int dfn[nMax],low[nMax],sta[nMax],top,atype,belon[nMax],dep; //atype 强连通分量的个数 bool insta[nMax]; void Tarjan(int u){ //我的Tarjan模版 int i,j; dfn[u]=low[u]=++dep; sta[++top]=u; insta[u]=1; for(i=head[u];i;i=e[i].nex){ int v=e[i].v; if(!dfn[v]){ Tarjan(v); low[u]=min(low[u],low[v]); } else{ if(insta[v])low[u]=min(low[u],dfn[v]); } } if(dfn[u]==low[u]){ atype++; //强连通分量个数 do{ j=sta[top--]; belon[j]=atype; //第j个点属于第type个连通块 insta[j]=0; }while(u!=j); } } void init(){ k=1; dep=1; top=atype=0; memset(insta,0,sizeof(insta)); //是否在栈中 memset(head,0,sizeof(head)); //静态链表头指针 memset(low,0,sizeof(low)); //Tarjan的low数组 memset(dfn,0,sizeof(dfn)); //Tarjan的dfn数组 memset(belon,0,sizeof(belon)); //记录每个点属于哪一个强连通分量 } int n,m; int mtx[600][600]; bool judge(){ for(int i=0;i<n;i++){ if(belon[i]==belon[i+n]){ return 0; } } return 1; } int main(){ int i,j,m,a1,a2,num; while(scanf("%d",&n)!=EOF) { for(i=0;i<n;i++) { for(j=0;j<n;j++) { scanf("%d",&mtx[i][j]); } } bool flag=1; for(i=0;i<n;i++) { for(j=0;j<n;j++) { if(mtx[i][j]!=mtx[j][i]) { flag=0; break; } if(i==j&&mtx[i][j]!=0) { flag=0; break; } } } if(!flag) { cout<<"NO\n"; continue; } flag=1; int left; for(left=0;left<31;left++) { num=n; init(); for(i=0;i<n;i++) { for(j=0;j<n;j++) { m=mtx[i][j]&(1<<left); if(i==j)continue; else if (i % 2 == 1 && j % 2 == 1) //// | { a1=i; a2=j; if(m!=0) { addedge(a1+num,a2); addedge(a2+num,a1); } else { addedge(a1,a1+num); addedge(a2,a2+num); } } else if (i % 2 == 0 && j % 2 == 0) //////& { a1=i; a2=j; if(m!=0) { addedge(a1+num,a1); addedge(a2+num,a2); } else { addedge(a1,a2+num); addedge(a2,a1+num); } } else ///// ^ { a1=i; a2=j; if(m!=0) { addedge(a1,a2+num); addedge(a2,a1+num); addedge(a1+num,a2); addedge(a2+num,a1); } else { addedge(a1,a2); addedge(a2,a1); addedge(a1+num,a2+num); addedge(a2+num,a1+num); } } } } for(i=0;i<num*2;i++) { if(!dfn[i])Tarjan(i); } n=num; if(!judge()) { flag=0; break; } } if(flag)printf("YES\n"); else printf("NO\n"); } return 0; }
发表评论
-
[kruskal]hdoj 4786
2014-10-29 20:38 662大致题意: 一个无向图中,每条边都是白边或 ... -
[prim]aizuoj:There is No Alternative
2014-10-20 01:02 845题目地址:http://judge.u-aizu.ac.j ... -
[最大流唯一性判断]hdoj 4888
2014-10-18 16:14 1311题意 给出一个矩阵n行每一行数字的和,m列每列数字的 ... -
[双连通分量+队列优化dijkstra]acdream 1415
2014-10-16 04:03 1095题意: 给出一个n个点,m条边无向图(2 ≤ ... -
[2-sat]hdoj 4751
2014-10-10 21:06 764大致题意 给出一个有向图,问这个图是否能分为两个完全图 ... -
[费用流]hdoj 5045
2014-09-28 00:11 828读题的时候漏掉了“题目是按照顺序出现的”,导致网络赛中这道题 ... -
[dfs+bfs]zoj 3811
2014-09-21 09:59 901题意: 在一个无向图中,能否按照一定的顺序访问图 ... -
[二分+最大流]zoj 3691:flower
2013-04-01 21:05 1609大致题意: 在一个三维空间中有n个点,每个点的坐标 ... -
[spfa]hdoj 4460:Friend Chains
2012-11-08 21:15 1593大致题意: 一个无向图n个点,m条边,求任意两个点之 ... -
[二分匹配]zoj 3156:Taxi
2012-10-25 19:28 1067大致题意: 有n个人和m辆车(n<=m)。给出所有 ... -
[Tarjan]uva 4846:Mines
2012-10-19 10:07 1220大致题意: 给出n个地雷,每颗地雷有一个爆炸范围,这 ... -
[二分匹配]zoj 3646:Matrix Transformer
2012-10-10 21:15 973大致题意: 给出一个n*n的矩阵,每个矩阵元素的U或者 ... -
[拆点+网络流]2012 acm/icpc成都网络赛 hdoj 4292:Food
2012-09-16 17:15 2214大致题意: 有F种食物和D种饮料,每种食物或饮料只能 ... -
[网络流]2012 acm/icpc成都网络赛hdoj 4288:Control
2012-09-16 17:03 1298大致题意: 给出一个又n个点,m条边组成的无向图。给出两 ... -
[floyd+Tarjan]zoj 3232:It's not Floyd Algorithm
2012-09-09 09:49 1067大致题意: 给出一个有向图的传递闭包矩阵,求出这个图 ... -
[最大流]zoj 3642:Just Another Information Sharing Problem
2012-08-28 13:26 1094大致题意: 有n个人,每个人知道ai个消息,并且会 ... -
[Tarjan变形]zoj 3630:Information
2012-08-15 16:42 1103大致题意: 给出一个有向图,现在要删去一个点使得剩下的图 ... -
[Tarjan强连通分量]hdoj 3836:Equivalent Sets
2012-07-21 09:40 919大致题意: 就是给出一个有向图,求最少加多少条边可以 ... -
[最大流]zoj 3305:Get Sauce
2012-06-19 10:04 930大致题意: 有n种原材料,每种一件。现在给出m个组合 ... -
[最小费用流]zoj 3308:Move the Knights
2012-06-15 15:45 930大致题意: 一个国际象棋棋盘上有n个马分布在不同的黑 ...
相关推荐
leetcode中国 POJ problems ID Problem C++ 1001 1002 1003 1004 ...ZOJ 1002 8 POJ 1321 9 HDU 1241 (二)树 ID Problem C++ Source 1 LeetCode 100 2 LeetCode 101 3 LeetCode 437 4 LeetCode 235
zoj网站中多个练习的c++解答,文件名即为题目序号。经本人测试可以使用,主要为动态规划方面的问题,希望给初学者提供帮助。
zoj 2247 Magic Trick.md
ZOJ解题报告ZOJ解题报告ZOJ解题报告ZOJ解题报告
ZOJ题解集合-截至2835。共1244个文件,C/C++,有重复
zoj题目简单归类zoj题目简单归类zoj题目简单归类
acm中zoj1002的可运行C++程序
包含了zoj700多道题目的源代码,在做题时可以参考
Interview,ZOJ,POJ 等平台。 欢迎Coders对代码加以指正和提议! 常见问题总结 两整数求平均值 average = min + (max - min) / 2 防止两整数的和越界 整数乘积对比 1.0 * m * m == num 类似乘积对比, 需转为double...
Problem Arrangement zoj 3777
ZOJ题目答案源码
zoj 1140-zju 2433 简单题的部分答案 都是可以正确通过的,简洁易懂
一个非常非常非常非常实用的zoj结题代码
leetcode下载 题库 开刷日期: 2015-06-15号,开始刷 leetcode ...第2个要介绍的是浙江大学的【ZOJ】 http://acm.zju.edu.cn/ 【只有英文,不支持其他语言显示】 1. leetcode: Problems | LeetCode
学习ACM程序设计的朋友一定要看,这是训练必备的POJ ZOJ题目分类及解题思路
ZOJ1805代码
zoj 1003 c语言的,要写这么多描述吗。。
本代码是zoj上AC的1951的代码,把双重循环简化为O(n),不过素数判断的改进还不够
zoj1027解题指南和代码,还不错,是学校培训给的。
浙大ZOJ题目分类,可以让你更方便快速锁定那你想要联系的题目,是自己快速提高·