NAN.NAN.NAN DAY 4

Posted on By 张, 高畅 NAN.NAN.NAN DAY 4无评论

你家网络怎么这么卡。

日常膜拜360小广告，因为它比我发挥稳定的多。

[T1]

真·STL大法好。

配上 C++11 开始支持的 auto 类型，整个代码非常清爽。

感谢出题人没有要求求排名，否则只能手写了

时间复杂度 O(n \log n)

#include<bits/stdc++.h>
using namespace std;
const int N=5e5+5;
int n;
set<int>S;
int main()
{
    freopen("set.in","r",stdin);
    freopen("set.out","w",stdout);
    scanf("%d",&n);
    while(n--)
    {
        int op,x;
        scanf("%d%d",&op,&x);
        if(op==1)S.insert(x);
        else if(op==2)
        {
            if(S.count(x))S.erase(x);
        }
        else if(op==3)puts(S.count(x)?"yes":"no");
        else if(op==4)
        {
            auto it=S.lower_bound(x);
            printf("%d\n",(it==S.end())?-1:*it);
        }
        else if(op==5)
        {
            auto it=S.upper_bound(x);
            printf("%d\n",(it==S.end())?-1:*it);
        }
        else if(op==6)
        {
            auto it=S.lower_bound(x);
            if(it!=S.end()&&*it==x)printf("%d\n",x);
            else printf("%d\n",(it==S.begin()&&*it>x)?-1:*(--it));
        }
        else if(op==7)
        {
            auto it=S.lower_bound(x);
            printf("%d\n",(it==S.begin()&&*it>=x)?-1:*(--it));
        }
    }
    return 0;
}

[T2]

神秘贪心/猜结论题。

显然我们要一个人一直出牌直到出到只剩一张。

然后找他逆时针最近且牌数大于 1 的，重复以上过程。

时间复杂度 O(n)，注意需要开启 __int128

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5;
typedef __int128 LN;
int n,a[N];
LN res;
void print(LN x)
{
    if(x>9)print(x/10);
    putchar(x%10+48);
}
int main()
{
    freopen("poker.in","r",stdin);
    freopen("poker.out","w",stdout);
    scanf("%d",&n);
    for(int i=1;i<=n;i++)scanf("%d",&a[i]);
    if(a[1]==1)
    {
        puts("1");
        return 0;
    }
    if(a[1]>1)res+=(LN)(a[1]-1);
    int flag=1;
    for(int i=n;i>1;i--)
    {
        if(a[i]>1)
        {
            if(flag==1)res--;
            res+=(LN)(a[i]-1);
            flag=i;
        }
    }
    print(res*(LN)n+(LN)flag);
    return 0;
}

[T3]

似乎是 原？

但是忘了。

首先有一个结论，一直操作一个点使得全图变成同一个颜色是最优的，此时需要的步数是显然的，只需要一遍 BFS 求离这个点最大距离即为操作此点的答案。

时间复杂度 O(n^2+nm) ，大概是 O(n^3) 量级的。

#include<bits/stdc++.h>
using namespace std;
#define x first
#define y second
const int N=505,M=125005;
typedef pair<int,int> PII;
int n,m,color[N],res=1e9,par[N],ce[N][N];
PII E[M];
vector<int>G[N];
int find(int x)
{
    if(par[x]==x)return x;
    else return par[x]=find(par[x]);
}
int d[N],st[N]; 
int bfs(int S)
{
    queue<int>q;
    memset(d,0x3f,sizeof d);
    memset(st,0,sizeof st);
    d[S]=0;
    q.push(S);
    int res=0;
    while(q.size())
    {
        int u=q.front();
        q.pop();
        if(st[u])continue;
        st[u]=1;
        res=max(res,d[u]);
        for(auto j:G[u])
        {
            if(d[j]>d[u]+1)
            {
                d[j]=d[u]+1;
                q.push(j);
            }
        }
    }
    return res;
}
int main()
{
    freopen("tutu.in","r",stdin);
    freopen("tutu.out","w",stdout);
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&color[i]);
        par[i]=i;
    }
    for(int i=1;i<=m;i++)
    {
        int a,b;
        scanf("%d%d",&a,&b);
        E[i]={a,b};
        if(color[a]==color[b])
        {
            a=find(a),b=find(b);
            if(a<b)swap(a,b);
            if(a!=b)par[a]=b;
        }
    }
    for(int i=1;i<=m;i++)
    {
        int a=E[i].x,b=E[i].y;
        if(color[a]!=color[b])
        {
            a=find(a),b=find(b);
            if(!ce[a][b]&&!ce[b][a])
            {
                G[a].push_back(b);
                G[b].push_back(a);
                ce[a][b]=ce[b][a]=1;
            }
        }
    }
    for(int i=1;i<=n;i++)
    {
        if(par[i]==i)res=min(res,bfs(i));
    }
    printf("%d",res);
    return 0;
}

[T4]

判定为 不会写DP导致的。

首先考虑 m=n-1 的情况，即这个图形成了一棵树。

此时可以直接上树形DP，设 f_{i,0/1} 代表以 i 为根的子树中，不选或选择 i 这个点所能获得的最大收益。

有转移方程式：
$f{u,0}=\sum{j \in son(u)} \max(f{j,0},f{j,1})f{u,1}=\sum{j \in son(u)} f_{j,0}$

跳过 m=n 的情况，直接考虑正解。

将每个环进行缩点（是的我这一步就不会），重新定义DP状态，其中 f_{i,0/1} 代表以第 i 个环离根最近的那一个点选不选。

至于这个状态怎么算，就直接在环上断掉一条边跑区间DP。

注意细节与常数，期望复杂度 O(n+m)

#include<bits/stdc++.h>
using namespace std;
const int N=5e5+5,M=2200005;
typedef long long LL;
const LL INF=1e15;
typedef pair<int,int>PII;
#define x first
#define y second
int n,m;
int h[N],hs[N],e[M],ne[M],idx;
PII E[M];
LL w[N],f[N][2],g[N][2],NOT[N],YES[N];
void add(int h[],int a,int b){e[idx]=b,ne[idx]=h[a],h[a]=idx++;}
int stk[N],top,id[N],cnt,in_stk[N],st[N];
vector<int>cir[N];
void dfs(int u,int father)
{
    stk[++top]=u;
    st[u]=in_stk[u]=1;
    for(int i=h[u];~i;i=ne[i])
    {
        int j=e[i];
        if(j==father)continue;
        if(in_stk[j])
        {
            cir[++cnt].push_back(j);
            id[j]=cnt; 
            for(int k=top;stk[k]!=j;k--)
            {
                cir[cnt].push_back(stk[k]);
                id[stk[k]]=cnt;
            }
        }
        if(!st[j])dfs(j,u);
    }
    in_stk[u]=0; 
    top--;
}
void DP(int u,int father)
{
    /*
    DP DP ON LINK
    */
    //for(auto i:cir[u])printf("%d ",i);
    //puts("");
    for(int i=hs[u];~i;i=ne[i])
    {
        int j=e[i];
        if(j==father)continue;
        DP(j,u);
    }
    if(cir[u].size()==1)
    {
        f[u][0]=0;
        f[u][1]=w[cir[u].back()];
        for(int i=h[cir[u].back()];~i;i=ne[i])
        {
            f[u][0]+=max(f[id[e[i]]][0],f[id[e[i]]][1]);
            f[u][1]+=f[id[e[i]]][0];
        }
    }
    else
    {
        int S=cir[u].size();
        for(int i=0;i<S;i++)
        {
            int cur=cir[u][i];
            NOT[i]=YES[i]=0;
            for(int j=h[cur];~j;j=ne[j])
            {
                YES[i]+=f[id[e[j]]][0];
                NOT[i]+=max(f[id[e[j]]][0],f[id[e[j]]][1]);
            }
        }
        g[0][0]=NOT[0];//g[0][1]=YES[0]+w[cir[u][0]];
        g[0][1]=-INF;
        for(int i=1;i<S;i++)
        {
            int cur=cir[u][i];
            g[i][0]=g[i][1]=0;
            g[i][0]=max(g[i-1][0],g[i-1][1])+NOT[i];
            g[i][1]=g[i-1][0]+YES[i]+w[cur];
        }
        f[u][0]=max(g[S-1][0],g[S-1][1]);
        g[0][0]=-INF;//g[0][0]=NOT[0];
        g[0][1]=YES[0]+w[cir[u][0]];
        for(int i=1;i<S;i++)
        {
            int cur=cir[u][i];
            g[i][0]=g[i][1]=0;
            g[i][0]=max(g[i-1][0],g[i-1][1])+NOT[i];
            g[i][1]=g[i-1][0]+YES[i]+w[cur];
        }
        f[u][1]=g[S-1][0];

    }
    //printf("==%d %lld %lld\n",u,f[u][0],f[u][1]);
}
int main()
{
    freopen("bamboo.in","r",stdin);
    freopen("bamboo.out","w",stdout);
    memset(h,-1,sizeof h);
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)scanf("%lld",&w[i]);
    for(int i=1,a,b;i<=m;i++)
    {
        scanf("%d%d",&a,&b);
        E[i]={a,b};
        add(h,a,b);
        add(h,b,a);
    }
    dfs(1,-1);
    for(int i=1;i<=n;i++)
    {
        if(!id[i])cir[id[i]=++cnt].push_back(i);
    }
    memset(h,-1,sizeof h);
    memset(hs,-1,sizeof hs);
    idx=0;
    for(int i=1;i<=m;i++)
    {
        int a=E[i].x,b=E[i].y;
        if(id[a]!=id[b])
        {
            add(h,a,b);
            add(h,b,a);
            add(hs,id[a],id[b]);
            add(hs,id[b],id[a]);
        }
    }
    DP(id[1],-1);
    printf("%lld\n",max(f[id[1]][0],f[id[1]][1]));
    return 0;
}
训练日志

发表回复