「CF1270G」Subset with Zero Sum

发表于

题目链接：https://codeforces.com/contest/1270/problem/G。

本场难度：$\rm G<H<D<E<F$（会写$\rm G,H$但是不会$\rm E,F$的垃圾选手发出感叹）这就是你掉分的借口

把题目给的限制条件变一下就是：$1\leqslant i-a_i\leqslant n$。

令$b_i=i-a_i$，只需要找到一些$b_i$满足$\sum b_i=\sum i$即可。

把每个$b_i$看做指针，那么就形成了一个置换，随便找一个环输出即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
#include<bits/stdc++.h>
using namespace std;
 
void read(int &x) {
    x=0;int f=1;char ch=getchar();
    for(;!isdigit(ch);ch=getchar()) if(ch=='-') f=-f;
    for(;isdigit(ch);ch=getchar()) x=x*10+ch-'0';x*=f;
}
 
void print(int x) {
    if(x<0) putchar('-'),x=-x;
    if(!x) return ;print(x/10),putchar(x%10+48);
}
void write(int x) {if(!x) putchar('0');else print(x);putchar('\n');}
 
#define lf double
#define ll long long 
 
#define pii pair<int,int >
#define vec vector<int >
 
#define pb push_back
#define mp make_pair
#define fr first
#define sc second
 
#define data asd09123jdf02i3h
 
#define FOR(i,l,r) for(int i=l,i##_r=r;i<=i##_r;i++)
 
const int maxn = 1e6+10;
const int inf = 1e9;
const lf eps = 1e-8;
const int mod = 1e9+7;
 
int n,a[maxn],vis[maxn];
 
void solve() {
    read(n);
    for(int i=1;i<=n;i++) read(a[i]),a[i]=i-a[i],vis[i]=0;
    for(int i=1;i<=n;i++) if(a[i]==i) {printf("1\n%d\n",i);return ;}
    int x=1;
    while(!vis[x]) vis[x]=1,x=a[x];
    int v=a[x];vector<int > ans;ans.pb(x);
    while(v!=x) ans.pb(v),v=a[v];
    write(ans.size());
    for(auto x:ans) printf("%d ",x);puts("");
}
 
int main() {
    int t;read(t);while(t--) solve();    
    return 0;
}