Skip to content

11121: 【原1121】二哥吵架

题目

题目描述

author: Huihuang Zheng 原OJ链接:https://acm.sjtu.edu.cn/OnlineJudge-old/problem/1121

Description

二哥这学期和女朋友吵架变多了,女人真不好对付,这不又想出一招来对付二哥了:

石头剪刀布大家都玩过吧?

(没玩过我介绍下,玩过的跳过这段)就是石头赢剪刀,剪刀赢布,布赢石头。

但二哥妹子不跟二哥玩石头剪刀布,她打算出一种新主意:

现在二哥妹子有N种手势,以1-N编号,每个手势都是石头,剪刀,布中的一种,但她不会告诉二哥是哪一种。她会用两种方式描述给二哥听:

第一种: 1, x, y 代表x和y是同一种手势

第二种: 2,x,y 代表x赢y

二哥妹子对二哥用上面两种说法一句接一句说出K句话,当然,这个任性的家伙不会都说真话,当说的话满足下面三个条件任一时,就是假话,否则就是真话!

(1)当前话和之前说的真话冲突,就是假话,如说过2,x,y;现在又说2,y,x

(2)当前的话中x或y比N大,就是假话

(3)当前的话与石头剪刀布的规则矛盾,就是假话,如2,x,x

当不满足以上三个条件时,就认为是真话。二哥的女朋友要求二哥必须说出她讲了几句假话,这样才算了解她的心。

Input Formats

第一行,两个整数 N, K

接下来K行每行三个整数 D, X ,Y, D为1或2,代表上面的两种说法

Output Formats

只有一个整数,二哥妹子说了多少句假话

Sample Input

100 7
1 101 1 
2 1 2
2 2 3 
2 3 3 
1 1 3 
2 3 1 
1 5 5

Sample Output

3

Restrictions

数据范围 1 <= N <= 100000, 0 <= K <= 100000,一切数在int型内可运算。时间限制0.5s

FineArtz's solution

/* 二哥吵架 */
#include <iostream>
using namespace std;

int n, k, ans = 0;
int op, x, y;
int p[100005], r[100005];

int parent(int x){
    if (x != p[x]){
        int t = p[x];
        p[x] = parent(p[x]);
        r[x] = (r[x] + r[t]) % 3;
    }
    return p[x];
}

int main(){
    cin >> n >> k;
    for (int i = 1; i <= n; ++i){
        p[i] = i;
        r[i] = 0;
    }
    while (k--){
        cin >> op >> x >> y;
        if (x > n || y > n){
            ++ans;
            continue;
        }
        if (op == 2 && x == y){
            ++ans;
            continue;
        }
        int px = parent(x), py = parent(y);
        if (px == py){
            if (r[y] != (r[x] + op - 1) % 3)
                ++ans;
        }
        else{
            p[py] = px;
            r[py] = (3 - r[y] + r[x] + op - 1) % 3;
        }
    }
    cout << ans << endl;
}