CF1270G Subset with Zero Sum

首先一定要从每个数的范围 \(i - n \le a_i \le i - 1\) 入手，最开始是这样一个想法，不难发现对于每个 \(i\) 都能选 \(n\) 个数，并且能选的右端点在 \(i - 1\)，那么我们可以吧每个 \(i\) 前移一位，实际上就是 \(0 \sim n - 1\) 这些位置上选没选数，而如果这个位置上没选那么就一定选在了前面，实际上这样还是非常不好做，于是我考虑只选择了一个负数的情况，发现还是不能发现一种简便的方法来找出这个集合，因此我们需要换一种方式思考。

既然分析性质行不通，我们可以考虑直接构造出答案。像这种找到一个集合满足一些条件的题目，我们可以将其转化为图论问题，例如求一个连通块的权值和为特定值或者找到一个环使得环上权值和为特定值，转化方式就需要巧妙的连边了。因为 \(a_i\) 涉及到负数不方便连边，于是我们可以对于每个 \(a_i\) 增添一个增量 \(k\)，即将 \(a_i \rightarrow b_i = a_i + k_i\) 那么原问题就转化为寻找一个集合使得 \(\sum b_i = \sum k_i\)。我的想法是对于每个 \(i\) 我们连边 \(i \rightarrow a_i + k_i\) 可以发现这中间有 \(n\) 条边，因为是有向边我们找联通块不方便，因此可以考虑找环。于是我们接下来的目的就是寻找一个合适的 \(k_i\) 使得连出来环上的边满足上述条件，然后我就不会做了，下面的做法只能无限 \(\rm stO\) 出题人。首先我们需要注意到这样一件事，如果刚好 \(n\) 个点，\(n\) 条边那么图中一定会存在一个环，于是我们就可以让 \(1 \le a_i + k_i \le n\) 那么这样就一定会出现环了，与此同时我们需要注意到一个如果要满足 \(\sum b_i = \sum k_i\) 那么不难发现环上的权值和要是编号和，事实上根据之前的连边如果能出现环那么环上的权值和一定是编号和，因为我们是每个编号 \(i\) 向外连一条边。再观察一下数据范围 \(i - n \le a_i \le i - 1\)，两边不正好出现了 \(1, n\) 吗？先把两边减去 \(i\) 可得 \(-n \le a_i - i \le -1\) 再反个号 \(1 \le i - a_i \le n\) 不就是我们想要的东西吗？于是对于每个 \(i\) 我们连边 \(i \rightarrow i - a_i\) 再在图上找一个环即可。注意多组数据不能直接 \(\rm memset\)。

#include<bits/stdc++.h>

using namespace std;

#define N 1000000 + 5

#define rep(i, l, r) for(int i = l; i <= r; ++i)

bool book[N];

int T, n, x, top, cnt, a[N], fa[N], st[N], ans[N];

int read(){

    char c; int x = 0, f = 1;

    c = getchar();

    while(c > '9' || c < '0'){ if(c == '-') f = -1; c = getchar();}

    while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();

    return x * f;

}

int main(){

    T = read();

    while(T--){

        n = read();

        rep(i, 1, n) a[i] = read(), fa[i] = i - a[i];

        x = 1, cnt = top = 0;

        while(!book[x]) book[x] = true, st[++top] = x, x = fa[x];

        while(st[top] != x) book[st[top]] = false, ans[++cnt] = st[top--];

        ans[++cnt] = st[top];

        while(top) book[st[top--]] = false;

        printf("%d\n", cnt);

        rep(i, 1, cnt) printf("%d ", ans[i]); puts("");

    }

    return 0;

}

巴特西

CF1270G Subset with Zero Sum

最新文章

热门文章