JZTXT

4.1

发布时间 2023-04-01 23:17:55作者: cxy8

牛客修棋盘

我们通过观察可以知道，走到每个点的奇偶性是确定的

同时我们的合法状态只有两种


如果我们对每个点都修改的话，我们能达到的状态如下：

所以我们每次修改次数最少的话应该是考虑我们每个点都修改的状态，当我们把每个点都修改的话就是互补的一个状态

#include <iostream>
#include <queue>

#define x first
#define y second
using namespace std;
typedef pair<int, int>PII;
const int N = 1010;
int res, n, m;
char g[N][N];
bool st[N][N];


int main()
{
    cin >> n >> m;
    for(int i = 1; i <= n; ++ i)
        for(int j = 1; j <= m; ++ j)
        {
            char ch; cin >> ch;
            int x = ch -'0';
            if((i + j) % 2 == 0 && x == 1)    res ++;
            if((i + j) % 2 && x == 0)    res ++;
        }
    if(res == m * n)    puts("0");
    else    cout << res << endl;
    return 0;
}

推导部分和

这道题的是带边权并查集的应用，比较难想到的是建图

对于每个区间l, r，k, 我们可以由前缀和s[r] - s[l - 1] = k，我们从r连一条l-1的边

WechatIMG819.png

#include <iostream>

using namespace std;
typedef long long LL;
const int N = 1e5 + 10;
//p[N]数组用来做并查集
int p[N], n, m, q;
//s[N]数组是当前点到根结点的权值和，也是前缀和
LL s[N];

//并查集的查询操作（带路径压缩）
int find(int x)
{
    if(x == p[x])   return x;
    else
    {
        int t = find(p[x]);
        s[x] += s[p[x]];
        p[x] = t;
        return t;
    }
}


int main()
{
    // freopen("1.in", "r", stdin);
    cin >> n >> m >> q;
    for(int i = 1; i <= n; ++ i)    p[i] = i;
    for(int i = 0; i < m; ++ i)
    {
        int l ,r;
        LL k; 
        cin >> l >> r >> k;
        int t1 = find(l - 1), t2 = find(r);
        if(t1 != t2)
        {
            p[t2] = t1;
            s[t2] = s[l - 1] - s[r] + k;
        }
    }
    while(q --)
    {
        int l, r;cin >> l >> r;
        int t1 = find(l - 1), t2 = find(r);
        if(t1 != t2)    puts("UNKNOWN");
        else printf("%lld\n", s[r] - s[l - 1]);
        
    }
    return 0;
}