1 solutions

  • 1
    @ 2021-10-30 9:19:55

    题意

    已知 nn 个数,求一个非空子集使得其和为零。

    题解

    发现 inaii1i-n\le a_i\le i-1

    所以 ai=ij(1jn)a_i=i-j(1\le j\le n)

    那么可以构造成ai+aj=ij+jk=ika_i+a_j=i-j+j-k=i-k,关系形成一张图。

    只要找一条链就合法了。

    每个点一个出边,是个基环数,直接跑环就可以了。

    #include<bits/stdc++.h>
    using namespace std;
    typedef long long ll;
    const int N=1e6+5;
    int _,n,a[N],vis[N];
    int main() {
        scanf("%d",&_);
        while(_--){
            scanf("%d",&n);
            for(int i=1;i<=n;i++){
                int x;
                scanf("%d",&x);
                a[i]=i-x;
            }
            for(int i=1;i<=n;i++)vis[i]=0;
            int now=1;
            for(;!vis[now];now=a[now])vis[now]=1;
            int t=now;
            vector<int> ans;
            ans.clear();
            for(;a[now]!=t;now=a[now])ans.push_back(now);
            ans.push_back(now);
            printf("%d\n",ans.size());
            for(int i:ans)printf("%d ",i);
            puts("");
        }
        return 0;
    }
    
    • 1

    Information

    ID
    1429
    Time
    2000ms
    Memory
    256MiB
    Difficulty
    10
    Tags
    # Submissions
    9
    Accepted
    3
    Uploaded By