Codeforces 1093CD(二分图染色 + 乘法原理)

发表于 | 分类于 | | + s

Codeforces 1093C
题意：给出数列$b_i​$, 已知一个序列$\forall i, a_i+a_{n-i+1}=b_i​$且$a_i \leq a_{i+1}​$，请构造出一个合法$a_i$数列，保证至少有一组解。
解：这个保证至少有一组解提示我们要最优化构造。
最优就是前面尽可能小，后面尽可能大。
所以我们让$a[0]=0, a[n+1]=INF$，然后根据升序约束求出$a[1, n/2]$的值, $a[n/2+1,n]$则为$b[i]-a[i]$

Codeforces 1093D
题意：给出$n$点$m$无向边图，请给每个点赋点权$1,2,3$，使得$\forall (u,v) \in E，w_u+w_v$为奇数。求方案数模$998244353$
解：对于一条边和要是奇数，那么点权一奇以偶。那么对图二分图染色，不同颜色的点分类赋奇数还是偶数，注意图不连通。最开始我把所有点一起算了贡献，直接爆炸。要分开乘法原理算。

知识点：
1093C:

#include<cstdio> 
#include<cstring>
#include<algorithm>
#include<iostream>
#include<vector>
#include<queue>
#include<cmath>
#define ms(i, j) memset(i, j, sizeof i)
#define LL long long
#define db double
#define fir first
#define sec second
#define mp make_pair
using namespace std;

namespace flyinthesky {

    LL n, a[200000 + 5], b[200000 + 5];

    void clean() {
    }
    int solve() {
        clean();
        cin >> n;
        for (int i = 1; i <= n / 2; ++i) scanf("%lld", &b[i]);
        a[n + 1] = 1e18;
        a[n + 1] += 100;
        for (int i = 1; i <= n / 2; ++i) {
            a[i] = max(a[i - 1], b[i] - a[n - i + 2]);
            a[n - i + 1] = b[i] - a[i];
        }
        for (int i = 1; i <= n; ++i) printf("%lld ", a[i]);
        return 0;
    }
}
int main() {
    flyinthesky::solve();
    return 0;
}

1093D:

#include<cstdio> 
#include<cstring>
#include<algorithm>
#include<iostream>
#include<vector>
#include<queue>
#include<cmath>
#define ms(i, j) memset(i, j, sizeof i)
#define LL long long
#define db double
#define fir first
#define sec second
#define mp make_pair
using namespace std;

namespace flyinthesky {

    const int MAXN = 300000 + 5, MO = 998244353;

    vector<int > G[MAXN];
    int fl, n, m, en, vis[MAXN], col[MAXN], js[3];
    LL whw[MAXN];

    void dfs(int u) {
        if (fl == 1) return ;
        vis[u] = 1;
        for (int i = 0; i < (int)G[u].size(); ++i) {
            int v = G[u][i];
            if (col[v] == col[u]) {
                fl = 1; break ;
            }
            if (!vis[v]) {
                col[v] = (col[u] == 1 ? 2 : 1);
                ++js[col[v]];
                dfs(v);
            }
        }
    }

    void clean() {
        fl = en = 0;
        for (int i = 0; i <= n; ++i) G[i].clear(), vis[i] = col[i] = 0;
    }
    int solve() {
        scanf("%d%d", &n, &m);
        clean();
        for (int u, v, i = 1; i <= m; ++i) {
            scanf("%d%d", &u, &v);
            G[u].push_back(v), G[v].push_back(u);
        }
        LL ans = 1;
        for (int u = 1; u <= n; ++u) {
            if (!vis[u]) {
                ms(js, 0);
                js[1] = 1, col[u] = 1, dfs(u);
                if (fl == 1) return printf("0\n"), 0;
                ans = (ans * ((whw[js[1]] + whw[js[2]]) % MO) % MO) % MO;
            }
        }
        printf("%lld\n", ans);
        return 0;
    }
}
int main() {
    flyinthesky::whw[0] = 1;
    for (int i = 1; i <= 300001; ++i) flyinthesky::whw[i] = (flyinthesky::whw[i - 1] * 2) % flyinthesky::MO;
    int t; scanf("%d", &t);
    while (t--) flyinthesky::solve();
    return 0;
}
------ 本文结束 ------