天天看点

[UOJ Easy Round #2]简要题解A. 手机的生产C. 谣言的传播

A. 手机的生产

题目链接

http://uoj.ac/problem/113

思路

找规律可以发现,只有$表达式的话,fork()会产生3台手机,fork()$fork()会产生4台手机,fork()$fork()$fork会产生5台手机……依次类推。

那么我们可以用|把若干个连续的$块分割开,每个长度为 x 的$块会产生x−1个结果为0的表达式, 1 个结果为1的表达式,那么我们可以从右边往左边递推,假设共tot个$块,可以得到 f[i]=[i,tot] 段$块产生的手机个数,容易得到DP方程:

f[i]=(num[i]−1)f[i+1]+1,num[i]=第i段连续的$的长度

代码

#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <algorithm>

#define MAXN 410000
#define MOD 998244353

using namespace std;

typedef long long int LL;

LL total=;
int ans[MAXN],n;
char s[MAXN],op[MAXN];

char ch[];
LL stack[MAXN];
int top=;

LL f[MAXN];

int main()
{
    scanf("%d",&n);
    if(n==)
    {
        cout<<<<endl;
        return ;
    }
    for(int j=;j<n;j++)
    {
        scanf("%s",ch);
        if(ch[]=='&')
            op[j]='&';
        else op[j]='|';
    }
    int h=,t=;
    LL tmp=;
    while(h<n&&t<n)
    {
        if(op[t]=='&') tmp++,t++;
        else
        {
            h=t=t+;
            stack[++top]=tmp;
            tmp=;
        }
    }
    stack[++top]=tmp;
    f[top]=stack[top];
    for(int i=top-;i>=;i--)
        f[i]=(f[i+]*(stack[i]-)%MOD+)%MOD;
    printf("%lld\n",f[]);
    return ;
}
           

C. 谣言的传播

题目链接

http://uoj.ac/problem/115

思路

蒟蒻太弱,只会做40分的。。。。

前10分可以通过爆枚序列 b 的全排列得到。

之后30分可以枚举i的谣言终结者 b[i] ,然后求出 i 的影响系数,容易发现这就是一个二分图最小/最大权匹配问题,对于点i而言,将它的入点与所有的 j(j≠i) 的出点连边,边权为 j 作为b[i]的情况下 i <script type="math/tex" id="MathJax-Element-732">i</script>的影响系数,然后做费用流或KM,然后通过残余网络可以找出可行解。

代码

#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <algorithm>

#define INF 0x3f3f3f3f

using namespace std;

int n,a[];

namespace bruteforce
{
    const int MAXN=;
    int b[MAXN],ansmin[MAXN],ansmax[MAXN],minans=INF,maxans=-INF;
    bool used[MAXN];
    int sum=;
    bool vis[MAXN];

    void calc(int S,int x,int fa)
    {
        sum++;
        if(b[S]==x) return;
        if(!vis[a[x]])
        {
            vis[a[x]]=true;
            calc(S,a[x],x);
        }
    }

    void DFS(int pos)
    {
        if(pos>n)
        {
            sum=;
            bool flag=true;
            /*if(b[1]==4&&b[2]==1&&b[3]==5&&b[4]==3&&b[5]==2)
                cout<<1<<endl;*/
            for(int i=;i<=n;i++)
            {
                for(int j=;j<=n;j++) vis[j]=false;
                //sum++;
                vis[i]=true;
                calc(i,i,);
            }
            if(!flag) return;
            if(sum<minans)
            {
                minans=sum;
                for(int i=;i<=n;i++)
                    ansmin[i]=b[i];
            }
            if(sum>maxans)
            {
                maxans=sum;
                for(int i=;i<=n;i++)
                    ansmax[i]=b[i];
            }
            return;
        }
        for(int i=;i<=n;i++)
            if(!used[i]&&i!=pos)
            {
                used[i]=true;
                b[pos]=i;
                DFS(pos+);
                used[i]=false;
            }
    }

    void solve()
    {
        DFS();
        printf("%d\n",minans);
        for(int i=;i<=n;i++)
            printf("%d ",ansmin[i]);
        printf("\n");
        printf("%d\n",maxans);
        for(int i=;i<=n;i++)
            printf("%d ",ansmax[i]);
        printf("\n");
    }
}

namespace KM
{
    const int MAXV=;
    const int MAXE=;

    int S=MAXV-,T=MAXV-;

    struct edge
    {
        int u,v,w,cap,next;
    }edges[MAXE*];

    int head[MAXV],nCount=;

    void AddEdge(int U,int V,int W,int C)
    {
        edges[++nCount].u=U;
        edges[nCount].v=V;
        edges[nCount].w=W;
        edges[nCount].cap=C;
        edges[nCount].next=head[U];
        head[U]=nCount;
    }

    void add(int U,int V,int W,int C)
    {
        AddEdge(U,V,W,C);
        AddEdge(V,U,-W,);
    }

    int q[MAXE*],dist[MAXV],pre[MAXV];
    bool inQueue[MAXV];

    bool SPFA_max()
    {
        memset(pre,-,sizeof(pre));
        memset(dist,-INF,sizeof(dist));
        memset(inQueue,false,sizeof(inQueue));
        int h=,t=;
        q[h]=S;
        dist[S]=;
        inQueue[S]=true;
        while(h<t)
        {
            int u=q[h++];
            inQueue[u]=false;
            for(int p=head[u];p!=-;p=edges[p].next)
            {
                int v=edges[p].v;
                if(dist[u]+edges[p].w>dist[v]&&edges[p].cap)
                {
                    dist[v]=dist[u]+edges[p].w;
                    pre[v]=p;
                    if(!inQueue[v])
                    {
                        inQueue[v]=true;
                        q[t++]=v;
                    }
                }
            }
        }
        return pre[T]!=-;
    }

    int MCMF_max()
    {
        int cost=;
        while(SPFA_max())
        {
            int flow=INF;
            for(int p=pre[T];p!=-;p=pre[edges[p].u])
                flow=min(flow,edges[p].cap);
            for(int p=pre[T];p!=-;p=pre[edges[p].u])
            {
                edges[p].cap-=flow;
                edges[p^].cap+=flow;
            }
            cost+=flow*dist[T];
        }
        return cost;
    }

    bool SPFA_min()
    {
        memset(pre,-,sizeof(pre));
        memset(dist,INF,sizeof(dist));
        memset(inQueue,false,sizeof(inQueue));
        int h=,t=;
        q[h]=S;
        dist[S]=;
        inQueue[S]=true;
        while(h<t)
        {
            int u=q[h++];
            inQueue[u]=false;
            for(int p=head[u];p!=-;p=edges[p].next)
            {
                int v=edges[p].v;
                if(dist[u]+edges[p].w<dist[v]&&edges[p].cap)
                {
                    dist[v]=dist[u]+edges[p].w;
                    pre[v]=p;
                    if(!inQueue[v])
                    {
                        inQueue[v]=true;
                        q[t++]=v;
                    }
                }
            }
        }
        return pre[T]!=-;
    }

    int MCMF_min()
    {
        int cost=;
        while(SPFA_min())
        {
            int flow=INF;
            for(int p=pre[T];p!=-;p=pre[edges[p].u])
                flow=min(flow,edges[p].cap);
            for(int p=pre[T];p!=-;p=pre[edges[p].u])
            {
                edges[p].cap-=flow;
                edges[p^].cap+=flow;
            }
            cost+=flow*dist[T];
        }
        return cost;
    }

    bool vis[MAXV];
    int b[MAXV];
    int sum=;

    void calc(int S,int x,int fa)
    {
        sum++;
        if(b[S]==x) return;
        if(!vis[a[x]])
        {
            vis[a[x]]=true;
            calc(S,a[x],x);
        }
    }

    void solve_min()
    {
        memset(head,-,sizeof(head));
        nCount=;
        for(int i=;i<=n;i++)
            for(int j=;j<=n;j++) //让j作为b[i]
            {
                if(i==j) continue;
                for(int k=;k<=n;k++)
                    vis[k]=false;
                b[i]=j;
                sum=;
                vis[i]=true;
                calc(i,i,);
                add(i,j+n,sum,);
            }
        for(int i=;i<=n;i++)
            add(S,i,,),add(i+n,T,,);
        int ans=MCMF_min();
        for(int i=;i<=nCount-*n;i+=)
            if(!edges[i].cap)
                b[edges[i].u]=edges[i].v-n;
        printf("%d\n",ans);
        for(int i=;i<=n;i++) printf("%d ",b[i]);
        printf("\n");
    }

    void solve_max()
    {
        memset(head,-,sizeof(head));
        nCount=;
        for(int i=;i<=n;i++)
            for(int j=;j<=n;j++) //让j作为b[i]
            {
                if(i==j) continue;
                for(int k=;k<=n;k++)
                    vis[k]=false;
                b[i]=j;
                sum=;
                vis[i]=true;
                calc(i,i,);
                add(i,j+n,sum,);
            }
        for(int i=;i<=n;i++)
            add(S,i,,),add(i+n,T,,);
        int ans=MCMF_max();
        for(int i=;i<=nCount-*n;i+=)
            if(!edges[i].cap)
                b[edges[i].u]=edges[i].v-n;
        printf("%d\n",ans);
        for(int i=;i<=n;i++) printf("%d ",b[i]);
        printf("\n");
    }

    void solve()
    {
        solve_min();
        solve_max();
    }
}

int main()
{
    scanf("%d",&n);
    for(int i=;i<=n;i++)
        scanf("%d",&a[i]);
    if(n<=)
    {
        using namespace bruteforce;
        solve();
    }
    else
    {
        using namespace KM;
        solve();
    }
    return ;
}