1 条题解
-
1
先化简不等式:
记 ,连边 到 。则这个图中任意一个环都是一个合法的子集。
因为对于环 S,环上点和可以表示为 $\sum_{i\in S}i=\sum_{i\in S} to_i =\sum_{i\in S} i-a_i \rightarrow \sum a_i=0$
tips:代码语言为 GNU G++17 9.2.0 (64 bit, msys 2)
#include<bits/stdc++.h> const int Maxn=1e6+10; using namespace std; int t,n,m,a[Maxn],to[Maxn]; bool vis[Maxn]; vector<int>ans; int main(){ scanf("%d",&t); while(t--){ ans.clear(); scanf("%d",&n); for(int i=1;i<=n;i++){ scanf("%d",&a[i]); to[i]=i-a[i],vis[i]=0; } int x=1; while(!vis[x]){ vis[x]=1,x=to[x]; } ans.push_back(x),x=to[x]; while(x!=ans[0]){ ans.push_back(x),x=to[x]; } printf("%d\n",ans.size()); for(int j=0;j<ans.size();j++){ printf("%d ",ans[j]); } printf("\n"); } return 0; }
- 1
信息
- ID
- 2456
- 时间
- 2000ms
- 内存
- 256MiB
- 难度
- 10
- 标签
- 递交数
- 3
- 已通过
- 1
- 上传者