You are given 𝑛 integers 𝑎1,𝑎2,…,𝑎𝑛, such that for each 1≤𝑖≤𝑛 holds 𝑖−𝑛≤𝑎𝑖≤𝑖−1.

Find some nonempty subset of these integers, whose sum is equal to 0. It can be shown that such a subset exists under given constraints. If there are several possible subsets with zero-sum, you can find any of them.

链接🔗

「CodeForces 1270G」Subset with Zero Sum

题解

因为 in<=ai<=ii - n <= a_i <= i-,所以 1<=iai<=n1 <= i - a_i <=n
我们让每个点ii向点iaii -a_i 连一条边
可以发现,图是基环树森林,因为nn个点nn 条边
可以简单验证下,环上点权加起来的值一定为0,因此我们要求的就是环上的点

代码

const ll maxd = 1e6+10;
 
ll a[maxd],vis[maxd];
stack<ll> s;
V ans;
bool dfs(ll x)
{
    if(vis[x])
    {
        while(s.top()!=x && !s.empty())
        {
            ans.pb(s.top());s.pop();
        }
        ans.pb(s.top());
        return true;
    }
    vis[x] = 1;
    s.push(x);
    return dfs(x - a[x]);
}
int main()
{
//    __IN;__OUT;
    ll t;RLL(t);
    while(t--)
    {
        ll n;RLL(n);ans.clear();
        while(!s.empty()) s.pop();
        F(n)
        {
            RLL(a[i+1]);
            vis[i+1] = 0;
        }
        F(n)if(dfs(i+1)) break;
        PLN((ll)ans.size());
        for(auto x : ans) PLP(x);
        PN();
    }
    return 0;
 
}