Codeforces Round 749 (Div.1 + Div.2)

比赛链接：点这里

A. Windblume Ode

题意：取一个集合的最大子集使得sum不为质数。

直接上手猜的结论，最少有n-1个数，然后暴力去判就行

bool is_prime(int x) {
    if (x == 1) return true;
    for (int i = 2; i * i <= x; i++) {
        if (x % i == 0) return false;
    }
    return true;
}
int a[N];
void solve() {
    int T; cin >> T; while (T--) {
        int n; cin >> n;
        int ans = 0;
        for (int i = 1; i <= n; i++) {
            cin >> a[i];
            ans += a[i];
        }
        if (!is_prime(ans)) {
            cout << n << endl;
            for (int i = 1; i <= n; i++) cout << i << ' ';
            cout << endl;
        } else {
            cout << n - 1 << endl;
            int f = 0;
            for (int i = 1; i <= n; i++) {
                if (!is_prime(ans-a[i])) {
                    f = i;
                    break;
                }
            }
            for (int i = 1; i <= n; i++) {
                if (i != f) cout << i << ' ';
            }
            cout << endl;
        }
    }
}

B. Omkar and Heavenly Tree

题意：有一棵树，给m个三元关系{ai,bi,ci}表示节点ai和ci的简单路径中不能存在bi节点，问构造方法

还是比较简单的构造，直接考虑不能位于中间的点个数最多为$m < n$,也就是说肯定会有一个点不受任何限制。我们直接让这个点与所有点相连，变成菊花图即可。

void solve() {
    int T; cin >> T; while (T--) {
        int n, m; cin >> n >> m;
        vector<int> vis(n+1);
        for (int i = 1; i <= m; i++) {
            int a, b, c; cin >> a >> b >> c;
            vis[b] = 1;
        }
        int t = 0;
        for (int i = 1; i <= n; i++) if (!vis[i]) t = i;
        for (int i = 1; i <= n; i++) {
            if (i != t) cout << i << ' ' << t << endl;
        }
    }
}

C. Omkar and Determination

题意: 简化一下题意，其实就是问[l,r]列中的子图构成的迷宫中，是否有‘.’无法从迷宫中逃生。

其实我们只需要关注当前列是否存在一个’.’,且它无法逃生，判断这个很简单，只需要知道它的上面和左边是否存在’X’就行。然后我们记一个前缀和sum[i]表示到第i列为止，一共有多少列存在无法逃生的点，然后取子图时只需要比较前缀和sum[l]和sum[r]是否相等就可以了。

string s[N];
int f[N];
void solve() {
    int n, m; cin >> n >> m;
    for (int i = 0; i < n; i++) cin >> s[i];
    for (int i = 1; i < n; i++) {
        for (int j = 1; j < m; j++) {
            if (s[i][j-1] == 'X' && s[i-1][j] == 'X') {
                f[j] = 1;
            }
        }
    }
    for (int i = 1; i < m; i++) f[i] += f[i-1];
    int q; cin >> q;
    while (q--) {
        int l, r; cin >> l >> r;
        l--, r--;
        if (f[r] == f[l]) cout << "YES" << endl;
        else cout << "NO" << endl;
    }
}

D. Omkar and the Meaning of Life

题意：你需要猜一个序列[1,n]，每次你都可以询问一个序列b，然后得到序列$ci=ai+bi$，返回ci中重复的数字的第一个下标。你最多可以询问2*n次。

首先我们可以用n次询问确定一个a[n]，只需要每次询问$b[n] = n$，$b[i]=i,i∈[1,n-1]$，当得到第一个非0返回值时，说明有一个数$y+i=a[n]+n$且y一定为n，因此$a[n]=i$。
然后我们已知a[n]后，将$b[i]=a[n]$，$b[n]=i$，这样得到返回值k时，$a[k]+a[n]=a[n]+i$，易得$a[k]=i$。

int a[N], b[N], n, k;
void print(char c, int *b) {
    cout << c << ' ';
    for (int i = 1; i <= n; i++) cout << b[i] << ' ';
    cout << endl;
    cout.flush();
}
void solve() {
    cin >> n;
    for (int i = 1; i <= n-1; i++) {
        b[n] = n;
        for (int j = 1; j <= n - 1; j++) b[j] = i;
        print('?', b);
        cin >> k;
        if (k) {
            a[n] = i;
            break;
        }
    }
    if (!a[n]) a[n] = n;
    for (int i = 1; i <= n; i++) {
        if (i == a[n]) continue;
        for (int j = 1; j <= n-1; j++) b[j] = a[n];
        b[n] = i;
        print('?', b);
        cin >> k;
        a[k] = i;
    }
    print('!', a);
}

E. Moment of Bloom

题意：一个简单图，每次你可以将ai到bi路径上所有边+1，最后询问所有边权是否为偶数。如果是，输出路径，如果不是，输出最小操作使得全部变为偶数。

可以证明的一点是，如果所有边权为偶数，那么选择的所有点次数也一定是偶数。首先看No的情况，如果存在某个点被选择的次数为奇数，那么肯定是No，操作次数是cnt(奇数点个数)/2。

如果全部点都是偶数，那么先随便取一个生成树，然后暴力去跳父亲节点遍历就可以了。

vector<int> g[N];
int cnt[N], fa[N], fat[N], dep[N];
vector<pii> qry;
int find(int x) {return x == fa[x] ? x : fa[x] = find(fa[x]);}
void dfs(int x, int far) {
    dep[x] = dep[far] + 1;
    for (auto v : g[x]) {
        if (v == far) continue;
        fat[v] = x;
        dfs(v, x);
    }
}
void solve() {
    int n, m; cin >> n >> m;
    for (int i = 1; i <= n; i++) fa[i] = i;
    for (int i = 1; i <= m; i++) {
        int u, v; cin >> u >> v;
        if (find(u) != find(v)) {
            fa[find(u)] = find(v);
            g[u].push_back(v);
            g[v].push_back(u);
        }
    }
    dfs(1, 0);
    int num = 0;
    int q; cin >> q;
    for (int i = 1; i <= q; i++) {
        int l, r; cin >> l >> r;
        cnt[l]++, cnt[r]++;
        qry.push_back({l, r});
    }
    for (int i = 1; i <= n; i++) if (cnt[i] % 2) num++;
    if (num) {
        cout << "NO" << endl;
        cout << num / 2 << endl;
    } else {
        cout << "YES" << endl;
        for (auto it : qry) {
            int l = it.fi, r = it.se;
            vector<int> ans1, ans2;
            while (l != r) {
                if (dep[l] >= dep[r]) {
                    ans1.push_back(l);
                    l = fat[l];
                } else {
                    ans2.push_back(r);
                    r = fat[r];
                }
            }
            ans1.push_back(l);
            reverse(ans2.begin(), ans2.end());
            cout << ans1.size() + ans2.size() << endl;
            for (auto item : ans1) cout << item << ' ';
            for (auto item : ans2) cout << item << ' ';
            cout << endl;
        }
    }
}