Codeforces Round 902 (Div. 2, based on COMPFEST 15

\(D. Effects of Anti Pimples\)

对每个数字能到达的所有位置先预处理最大值，那么就代表选择这个数字之后真实的贡献，那么对这样的预处理值，最小值显然只有一种做法，为 \(2^0\) ，第二小的值应该可以与最小值一起选择，所以答案为 \(2^1\) ，以此类推之后，每个值乘上对应的2的幂次之后求和即可。

void solve(){
    int n=read();
    vector<int>a(n+1);
    for(int i=1;i<=n;i++){
        a[i]=read();
    }
    for(int i=1;i<=n;i++){
        for(int j=2*i;j<=n;j+=i){
            a[i]=max(a[i],a[j]);
        }
    }
    sort(a.begin()+1,a.end());
    mint ans=0,p=1;
    for(int i=1;i<=n;i++){
        ans+=p*(mint)a[i];
        p*=2;
    }
    cout<<ans<<'\n';
    //puts(ans>0?"YES":"NO");
    //puts(ans>0?"Yes":"No");
}

\(E. Autosynthesis\)

对每个 \(i\) 向自己的 \(a_i\) 建单向边。首先所有入度为 \(0\) 点都不能删掉，否则没人能指向他。同时，这些点的出点就需要被删去。那么不断这样操作，最后这张图上只剩下一些环。对每个环而言，长度需要为偶数。

void solve(){
    int n=read();
    vector<int>a(n+1),d(n+1);
    for(int i=1;i<=n;i++){
        a[i]=read();
        d[a[i]]++;
    }
    vector<int>col(n+1,-1),vis(n+1,0);
    queue<int>que;
    for(int i=1;i<=n;i++){
        if(d[i]==0){
            que.push(i);
            vis[i]=1;
        }
    }
    while(que.size()){
        int i=que.front();
        que.pop();
        if(col[i]<0){
            col[i]=1;
        }
        if(col[i]==1){
            col[a[i]]=0;
        }
        d[a[i]]--;
        if((!d[a[i]]||col[a[i]]==0)&&!vis[a[i]]){
            vis[a[i]]=1;
            que.push(a[i]);
        }
    }
    for(int i=1,j;i<=n;i++){
        if(d[i]){
            col[i]=1;
            d[i]=0;
            for(j=i;a[j]!=i;j=a[j]){
                col[a[j]]=!col[j];
                d[j]=0;
            }
            d[j]=0;
            if(col[i]==col[j]){
                cout<<-1<<'\n';
                return ;
            }
        }
    }
    int ans=0;
    for(int i=1;i<=n;i++){
        ans+=col[i];
    }
    cout<<ans<<'\n';
    for(int i=1;i<=n;i++){
        if(col[i]){
            cout<<a[i]<<" ";
        }
    }
}