第49场周赛 B&C

B

贪心或者dp，加上一个偶数不改变奇偶性，因此如果一个偶数大于0，那么一定要加上这个数。

#include <bits/stdc++.h>
#define endl '\n'
#define all(x) (x).begin(), (x).end()
using namespace std;
using PII = pair<int, int>;
using ll = long long;
constexpr ll mod = 998244353;
constexpr int N = 2e5 + 10;
int f[N][3];
signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n; cin >> n;
    f[0][1] = -2e9;
    for (int i = 1; i<= n;i++) {
        int x; cin >> x;
        if ((x % 2 + 2) % 2 == 1) {
            f[i][1] = max(f[i - 1][1], f[i - 1][0] + x);
            f[i][0] = max(f[i - 1][0], f[i - 1][1] + x);
        } else {
            f[i][1] = max(f[i - 1][1], f[i - 1][1] + x);
            f[i][0] = max(f[i - 1][0], f[i - 1][0] + x);
        }

    }
    cout << f[n][1] <<endl;
    return 0;
}

C

如果存在$1$个连通块不是二分图，一定没有方案满足要求。
如果各个连通块都是二分图，答案就是$\prod ({2^{c1} + 2^{c2}})$, $c1、c2$分别为二分图黑白染色，黑色点和白色点的数量.

#include <bits/stdc++.h>
#define endl '\n'
#define all(x) (x).begin(), (x).end()
using namespace std;
using PII = pair<int, int>;
using ll = long long;
constexpr ll mod = 998244353;
constexpr int N = 3e5 + 10;
vector<int> g[N];
int col[N], c1, c2;
ll power(ll a, int k) {
    ll res = 1;
    while (k) {
        if (k & 1) res = res* a % mod;
        k >>= 1;
        a = a * a % mod;
    }
    return res;
}
int dfs(int x, int c) {
    col[x] = c;
    if (col[x] == 1) c1 ++;
    else c2 ++;
    for (auto &y : g[x]) {
        if (col[y] && col[y] != 3 - c) return 0;
        if (!col[y] && !dfs(y, 3 - c)) return 0;
    }
    return 1;
}
signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int t; cin >> t;
    while (t -- ) {
        ll ans = 1;
        int n, m; cin >> n >> m;
        for (int i = 1; i <= n;i++) g[i].clear(), col[i] = 0;
        for (int i = 0; i< m;i++) {
            int u, v; cin >> u >> v;
            g[u].push_back(v);
            g[v].push_back(u);
        }
        for (int i = 1; i <= n;i++) {
            if (!col[i]) {
                c1 = c2 = 0;
                if (!dfs(i, 1)) {
                    ans = 0;
                    break;
                }
                else {
                    ans *= power(2, c1) + power(2, c2);
                    ans %= mod;
                }
            }
        }
        cout << ans << endl;
    }
    return 0;
}