1 条题解

  • 1
    @ 2022-12-17 9:25:04

    先化简不等式:inaii11iaini-n\le a_i≤i-1 \rightarrow 1 \le i-a_i\le n

    toi=iaito_i=i-a_i,连边 iitoito_i。则这个图中任意一个环都是一个合法的子集。

    因为对于环 S,环上点和可以表示为 $\sum_{i\in S}i=\sum_{i\in S} to_i =\sum_{i\in S} i-a_i \rightarrow \sum a_i=0$

    codecode

    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
    上传者