How to AK ABC256

· · 个人记录

题外话

做出来 ABCD
如果 C 题不犯 sb 错，这场就上 6kyu 了

A

略

B

略

C

填数独，爆搜！
复杂度：O(玄学)，反正是加剪枝过了

D

差分，O(n)
代码： 

#include <bits/stdc++.h>
using namespace std;
namespace Main
{
    typedef long long ll;
    const int maxn=2e5+5;
    int n;
    int L[maxn],R[maxn];
    int cf[maxn];
    void main()
    {
        scanf("%d",&n);
        for(int i=1;i<=n;i++)
        {
            scanf("%d%d",&L[i],&R[i]);
            cf[L[i]-1]--;
            cf[R[i]-1]++;
        }
        for(int i=200000;i>=1;i--)
        {
            cf[i]+=cf[i+1];
        }
        int lst=0;
        int r;
        bool flag=0;
        for(int i=1;i<=200000;i++)
        {
            if(cf[i])
            {
                if(!flag)
                {
                    lst=i;
                    flag=1;
                }
            }
            else
            {
                if(!flag)
                {
                    continue;
                }
                else flag=0;
                r=i;
                printf("%d %d\n",lst,r); 
            }
        }
    }
}
int main()
{
    Main::main();
    return 0;
}

E

将 i 连向 x_i，边权为 c_i
这样就构成了一颗基环树森林。
对于所有树上的点，肯定都能满足要求，先走 i 再走 x_i 就行了。
对于环上的点，例如：

1 \rightarrow 2 \rightarrow 3 \rightarrow 4 \rightarrow 1

这样的，肯定要选一个点先走，那么这个点的上一个点就只能委屈了。
也就是要选取环上边权最小的边加入答案

此题结束 

#include <bits/stdc++.h>
using namespace std;
namespace Main
{
    typedef long long ll;
    const int maxn=2e5+5;
    int n;
    int x[maxn],c[maxn];
    int to[maxn];
    bool ins[maxn],vis[maxn];
    ll ans;
    void cir_ans(int u)
    {
        int start=u;
        int imin=0x3f3f3f3f;
        while(1)
        {
            imin=min(imin,c[u]);
            u=to[u];
            if(u==start)break;
        }
        ans+=(ll)imin;
    }
    void dfs(int u)
    {
        if(vis[u])
        {
            if(ins[u])
                cir_ans(u);
            return;
        }
        ins[u]=1;
        vis[u]=1;
        dfs(to[u]);
        ins[u]=0;
    }
    void main()
    {
        scanf("%d",&n);
        for(int i=1;i<=n;i++)
        {
            scanf("%d",&x[i]);
        }
        for(int i=1;i<=n;i++)
        {
            scanf("%d",&c[i]);
        }
        for(int i=1;i<=n;i++)
        {
            to[i]=x[i];
        }
        for(int i=1;i<=n;i++)
        {
            if(!vis[i])
            {
                dfs(i);
            }
        }
        printf("%lld",ans);
    }
}
int main()
{
    Main::main();
    return 0;
}

F

In queue