Eliminate the Conflict
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 1838 Accepted Submission(s): 789
Problem Description
Conflicts are everywhere in the world, from the young to the elderly, from families to countries. Conflicts cause quarrels, fights or even wars. How wonderful the world will be if all conflicts can be eliminated.
Edward contributes his lifetime to invent a 'Conflict Resolution Terminal' and he has finally succeeded. This magic item has the ability to eliminate all the conflicts. It works like this:
If any two people have conflict, they should simply put their hands into the 'Conflict Resolution Terminal' (which is simply a plastic tube). Then they play 'Rock, Paper and Scissors' in it. After they have decided what they will play, the tube should be opened and no one will have the chance to change. Finally, the winner have the right to rule and the loser should obey it. Conflict Eliminated!
But the game is not that fair, because people may be following some patterns when they play, and if the pattern is founded by others, the others will win definitely.
Alice and Bob always have conflicts with each other so they use the 'Conflict Resolution Terminal' a lot. Sadly for Bob, Alice found his pattern and can predict how Bob plays precisely. She is very kind that doesn't want to take advantage of that. So she tells Bob about it and they come up with a new way of eliminate the conflict:
They will play the 'Rock, Paper and Scissors' for N round. Bob will set up some restricts on Alice.
But the restrict can only be in the form of "you must play the same (or different) on the ith and jth rounds". If Alice loses in any round or break any of the rules she loses, otherwise she wins.
Will Alice have a chance to win?
Edward contributes his lifetime to invent a 'Conflict Resolution Terminal' and he has finally succeeded. This magic item has the ability to eliminate all the conflicts. It works like this:
If any two people have conflict, they should simply put their hands into the 'Conflict Resolution Terminal' (which is simply a plastic tube). Then they play 'Rock, Paper and Scissors' in it. After they have decided what they will play, the tube should be opened and no one will have the chance to change. Finally, the winner have the right to rule and the loser should obey it. Conflict Eliminated!
But the game is not that fair, because people may be following some patterns when they play, and if the pattern is founded by others, the others will win definitely.
Alice and Bob always have conflicts with each other so they use the 'Conflict Resolution Terminal' a lot. Sadly for Bob, Alice found his pattern and can predict how Bob plays precisely. She is very kind that doesn't want to take advantage of that. So she tells Bob about it and they come up with a new way of eliminate the conflict:
They will play the 'Rock, Paper and Scissors' for N round. Bob will set up some restricts on Alice.
But the restrict can only be in the form of "you must play the same (or different) on the ith and jth rounds". If Alice loses in any round or break any of the rules she loses, otherwise she wins.
Will Alice have a chance to win?
Input
The first line contains an integer T(1 <= T <= 50), indicating the number of test cases.
Each test case contains several lines.
The first line contains two integers N,M(1 <= N <= 10000, 1 <= M <= 10000), representing how many round they will play and how many restricts are there for Alice.
The next line contains N integers B1,B2, ...,BN, where Bi represents what item Bob will play in the ith round. 1 represents Rock, 2 represents Paper, 3 represents Scissors.
The following M lines each contains three integers A,B,K(1 <= A,B <= N,K = 0 or 1) represent a restrict for Alice. If K equals 0, Alice must play the same on Ath and Bth round. If K equals 1, she must play different items on Ath and Bthround.
Each test case contains several lines.
The first line contains two integers N,M(1 <= N <= 10000, 1 <= M <= 10000), representing how many round they will play and how many restricts are there for Alice.
The next line contains N integers B1,B2, ...,BN, where Bi represents what item Bob will play in the ith round. 1 represents Rock, 2 represents Paper, 3 represents Scissors.
The following M lines each contains three integers A,B,K(1 <= A,B <= N,K = 0 or 1) represent a restrict for Alice. If K equals 0, Alice must play the same on Ath and Bth round. If K equals 1, she must play different items on Ath and Bthround.
Output
For each test case in the input, print one line: "Case #X: Y", where X is the test case number (starting with 1) and Y is "yes" or "no" represents whether Alice has a chance to win.
Sample Input
2
3 3
1 1 1
1 2 1
1 3 1
2 3 1
5 5
1 2 3 2 1
1 2 1
1 3 1
1 4 1
1 5 1
2 3 0
Sample Output
Case #1: no
Case #2: yes
Hint
'Rock, Paper and Scissors' is a game which played by two person. They should play Rock, Paper or Scissors by their hands at the same time. Rock defeats scissors, scissors defeats paper and paper defeats rock. If two people play the same item, the game is tied..
Source
题意:
给出 T 组样例,后给出 n,m,代表有 n round 剪刀石头布游戏,除了不输掉任意 1 round之外,还要满足 m 个条件。每个条件给出 a,b,k。如果 k == 0,代表要求 a 和 b 要一样,k == 1 的话则要求 a 和 b 不一样。输出能不能赢。
思路:
2 - sat。预处理出每一局能出的两个数是,令其一个为真一个为假。当 k == 1 的时候,两个数相等的时候则要求建边。当 k == 0 的时候,两个数不相等的时候需要建边。最后走一遍 2 - sat 则可得出答案。
AC:
#include <cstdio> #include <cstring> #include <algorithm> #include <vector> #include <stack> using namespace std; const int MAX = 10005 * 2; int n, m; int res[MAX][2]; vector<int> v[MAX]; int dfs_clock, scc_cnt; int pre[MAX], low[MAX], cmp[MAX]; stack<int> s; void init () { for (int i = 0; i < MAX; ++i) v[i].clear(); } void dfs(int u) { pre[u] = low[u] = ++dfs_clock; s.push(u); for (int i = 0; i < v[u].size(); ++i) { if (!pre[ v[u][i] ]) { dfs( v[u][i] ); low[u] = min(low[u], low[ v[u][i] ]); } else if (!cmp[ v[u][i] ]) { low[u] = min(low[u], pre[ v[u][i] ]); } } if (low[u] == pre[u]) { ++scc_cnt; for (;;) { int x = s.top(); s.pop(); cmp[x] = scc_cnt; if (x == u) break; } } } void scc() { dfs_clock = scc_cnt = 0; memset(pre, 0, sizeof(pre)); memset(cmp, 0, sizeof(cmp)); for (int u = 1; u <= 2 * n; ++u) { if (!pre[u]) dfs(u); } } int main() { int t; scanf("%d", &t); for (int tt = 1; tt <= t; ++tt) { init(); scanf("%d%d", &n, &m); for (int i = 1; i <= n; ++i) { int ans; scanf("%d", &ans); if (ans == 1) { res[i][0] = 1, res[i][1] = 2; } else if (ans == 2) { res[i][0] = 2, res[i][1] = 3; } else { res[i][0] = 3, res[i][1] = 1; } } while (m--) { int a, b, k; scanf("%d%d%d", &a, &b, &k); if (k) { if (res[a][0] == res[b][0]) { v[a].push_back(b + n); v[b].push_back(a + n); } if (res[a][0] == res[b][1]) { v[a].push_back(b); v[b + n].push_back(a + n); } if (res[a][1] == res[b][0]) { v[a + n].push_back(b + n); v[b].push_back(a); } if (res[a][1] == res[b][1]) { v[a + n].push_back(b); v[b + n].push_back(a); } } else { if (res[a][0] != res[b][0]) { v[a].push_back(b + n); v[b].push_back(a + n); } if (res[a][0] != res[b][1]) { v[a].push_back(b); v[b + n].push_back(a + n); } if (res[a][1] != res[b][0]) { v[a + n].push_back(b + n); v[b].push_back(a); } if (res[a][1] != res[b][1]) { v[a + n].push_back(b); v[b + n].push_back(a); } } } scc(); printf("Case #%d: ", tt); int temp = 0; for (int i = 1; i <= n; ++i) { if (cmp[i] == cmp[n + i]) { printf("no\n"); temp = 1; break; } } if (!temp) printf("yes\n"); } return 0; }
相关推荐
A new algorithm to eliminate the ambiguity of GPS
In addition to the default Bochs method using the CTRL key and the middle mouse button there are now the choices: - CTRL+F10 (like DOSBox) - CTRL+ALT (like QEMU) - F12 (replaces win32 'legacyF12'...
division multiplexing (OFDM) can eliminate intra-cell interference since data are carried on the orthogonal subcarries; however, it can not mitigate inter-cell interference (ICI) which affects the ...
Architectural challenges using microservices with service integration and API management are presented and you learn how to eliminate the use of centralized integration products such as the enterprise...
by the offset voltage of the three-phase output current cycle Fourier transform is found only compensation 1, 5, 7 harmonic components to eliminate the dead time effect. simulation and experimental ...
In addition to explaining the motivation for following good physical as well as logical design practices, Lakos provides you with a catalog of specific techniques designed to eliminate cyclic, ...
Utilizing TOR should essentially eliminate the mitigating effects of ipchains, mod_antiloris, and mod_noloris. --socksversion Setting the --socksversion flag tells HTTPLoris to connect through a ...
Built-in low-EMI features, including a clock spectrum spreader, help designers eliminate the kind of emissions-related problems that frequently derail tight development schedules.
- minimum phase filters to eliminate pre-echo - smooth frequency response - import/export functionality - mono and stereo mode Current version 0.3.7, released on 2012-02-05 Works with foobar2000 v...
资源分类:Python库 所属语言:Python 资源全名:eliminate-newlines-1.2.tar.gz 资源来源:官方 安装方法:https://lanzao.blog.csdn.net/article/details/101784059
Architectural challenges using microservices with service integration and API management are presented and you learn how to eliminate the use of centralized integration products such as the enterprise...
the two-dimensional (2-D) direction of arrival angles (DOAs). Also the proposed algorithm can be applied to the situation when the incident sources are mixed either with uncorrelated or fully ...
amplifier parameter modifier with control switches is designed to eliminate the effects of time-varying parameters on the imbalance vibration compensation precision. The adaptive imbalance vibration ...
control method attempts to create 2 objects of the same name. This once again returns AE_ALREADY_EXISTS. When this exception occurs, it invokes the mechanism that will dynamically serialize the ...
Architectural challenges using microservices with service integration and API management are presented and you learn how to eliminate the use of centralized integration products such as the enterprise...
MicroPython and controllers that support it eliminate the need for programming in a C-like language, making the creation of IoT applications and devices easier and more accessible than ever. ...
We show how to use “complementary priors” to eliminate the explainingaway effects thatmake inference difficult in densely connected belief nets that have many hidden layers. Using complementary ...
NULL 博文链接:https://caohong286.iteye.com/blog/1275437
语言:English 格雷戈里有助于改善您的写作习惯。 告诉格雷戈里您想停止使用的单词。 每次使用它们时,您都会收到一条柔和的通知。 适用于所有网站,包括Gmail,Facebook,Twitter,Wordpress。...一些启发链接:...
It reveals the next phase in a hopeful economic and social revolution that is already under way—and in the worldwide effort to eliminate poverty by unleashing the productive energy of every human ...