天天看點
傳回

[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 ;
}
uoj 比賽題解 比賽賽題
上一篇: MySQL資料庫系列之Centos6.5系統下RPM包安裝MySQL5.6
下一篇: 【UOJ77】A + B Problem

繼續閱讀