/ ALGORITHM

福州大学第十四届程序设计竞赛

Contest Information

source: It’s from the FZU OJ

Problem A

给出一个长度为 $n$ 的 $01$ 串,选择一个区间 $[L, R]$ 将其中的 $0$ 变成 $1$ ,$1$ 变成 $0$。 至少翻转一个数字,求最多能有多少个 $1$ ?

数据范围:$ n ≤ 10^{5}$

Solution

我们新开一个数组把 $ 0$ 对应的位置记录为 $1$ , $1$ 对应的位置记录为 $-1$ ,那么新数组的最大子段和就是对于原数组的 $1$ 的最大增量

AC code

int n,AA[MaxN],tot;
void solve()
{
    int a,b,A,B,mx,sum;
    sum = mx = -100100;
    for(int i=1;i<=n;i++)  
    {  
        if(sum+AA[i] < AA[i])  
            sum = AA[i] , a = b = i;      //a、b记录当前连续子序列的起始、结束位置  
        else  
            sum += AA[i] , ++b;  
        if(mx < sum)  
            mx = sum , A = a , B = b;  
    }  
    int ans = tot + mx;
   // debug(A) debug(B)
    printf("%d\n", ans);
}
int main()
{
    //std::ios::sync_with_stdio(false);
    while(~scanf("%d", &n))
    {
        int x;
        tot = 0;
        for(int i=1;i<=n;i++) 
        {
            scanf("%d", &x);
            if(x) AA[i] = -1,tot++;
            else AA[i] = 1;
        }
        solve();
    }
    //system("pause");
    //printf("%lld\n", (x%mod+mod)%mod );
}

Problem B

YellowStar准备了 $n$ 个需要背的单词,每个单词的长度均为 $m$

YellowSatr准备采用联想记忆法来背诵这 $n$ 个单词:

1、如果YellowStar凭空背下一个新词 $T$ ,需要消耗单词长度 $m$ 的精力

2、如果YellowSatr之前已经背诵了一些单词,它可以选择其中一个单词 $S_i$,然后通过联想记忆的方法去背诵新词T,需要消耗的精力为 $hamming(S_i, T) \times w$

$ hamming(S_i, T) $指的是字符串 $S_i$ 与 $T$ 的汉明距离,它表示两个等长字符串之间的汉明距离是两个字符串对应位置的不同字符的个数。

由于YellowStar还有大量繁重的行政工作,因此它想消耗最少的精力背诵下这 $n$ 个单词,请问它最少需要消耗多少精力。

数据范围:$ 1 ≤ n ≤ 10^{3}, 1 ≤ m,w ≤ 10$

Solution

如果联想记忆更划算那么边权设为联想记忆,否则设置为直接记忆,然后求最小生成树即可

AC code

int n,m,w;
char str[1010][11];
struct Edge
{
    int u,v,w;
    bool operator<(const Edge &a)const
    {
        return w<a.w;
    }
    Edge(){}
    Edge(int a,int b, int c):u(a),v(b),w(c){}
}edge[MaxM];
int cont;
int father[MaxN];

int getFather(int x)  //并查集找父亲
{
    int r = x;
    while(father[r]!=r)
        r = father[r];
    int j = x;
    while(j!=r)
    {
        int k = father[j];
        father[j] = r;
        j = k;
    }
    return r;
}

int Kruskal()
{
    for(int i=0;i<=n;i++)
        father[i]=i;

    int cnt=1;   //记录加入的点数
    int ans = 0; //记录建边的花费
    for(int i=0;i<cont;i++)
    {
        int u=edge[i].u, v=edge[i].v;
        int w=edge[i].w;
        int fu=getFather(u),fv=getFather(v);
        if(fu==fv)
            continue;
        ans+=w;          //加入该边
        father[fv] = fu;
        cnt++;
        if(cnt==n) break;
    }
    return ans;
}

void check(int a, int b)
{
    int cnt = 0;
    for(int i=1;i<=m;i++)
    {
        if(str[a][i]!=str[b][i]) cnt++;
    }
    int x = min(m,cnt*w);
    edge[cont++] = Edge(a,b,x);
}
void solve()
{
    cont = 0;
    for(int i=1;i<=n;i++)
    {
        for(int j=i+1;j<=n;j++)
        {
            check(i,j);
        }
    }
    sort(edge,edge+cont);
    int ans = Kruskal()+m;
    printf("%d\n", ans);
}
int main()
{
    //std::ios::sync_with_stdio(false);
    while(~scanf("%d%d%d", &n,&m, &w))
    {
        for(int i=1;i<=n;i++) scanf("%s", str[i]+1);
        solve();
    }
    //system("pause");
    //printf("%lld\n", (x%mod+mod)%mod );
}

Problem C

遥远的YS星球上,生活着两种物种名为Yellow和Star,简称物种Y和物种S。

神奇的是物种Y的体重始终为50kg,物种S的体重始终为100kg。

这天,$n$ 只生物结伴出行,在路途中,它们被一条长长的河流挡住了去路。所幸岸边停靠着一条船,船上写着:负重 $m$ kg。

YS星球上的物种有很强的时间观念,它们需要找出一种最快的方案过河:

1、要开船每次至少要有一只生物在船上

2、载着的生物总重量不能超过船的负重 $m$

3、无论载多少只生物,船每次从岸边到另一岸边需要的时间相同,并且不考虑中间换乘时间(换句话说,要求的是最少的开船次数)

请你帮助这些Yellow、Star们,找出最少的开船次数,并且求出最少次数下的有多少种不同的方案数。

当存在某轮开船时,两个方案乘客的集合不同,认为这两个方案是不同的。

数据范围:$ 1 ≤ n ≤ 50, 100 ≤ m ≤ 10^3$

Solution

我们发现在奇数次开船时总是从岸这边运输往岸那边,即岸这边的生物数减少;在偶数次时则是从岸那边运回来,即岸这边生物数增多。

那么我们定义 $ DP[i][j][k]$ 为在第 $k$ 次开船时,岸这边还剩下 $i$ 只Y生物和 $j$ 只S生物时的方案数。初始状态 $DP[num_{50}][num_{100}][0] = 1$ ,然后我们枚举岸这边可能的生物数的所有状态,对于每一个状态在奇数轮枚举可能运过去的所有转移,在偶数轮枚举可能运回来的所有转移:

奇数轮:$ DP[i][j][k] = DP[i+x][j+y][k-1] \times C^{x}_{i+x} \times C^{y}_{j+y}$

偶数轮:$ DP[i][j][k] = DP[i-x][j-y][k-1] \times C^{x}_{num_{50}-i+x} \times C^{y}_{num_{100}-j+y}$

最后取第一个有值的 $DP[0][0][k]$

AC code

int n,m,A[55],m50,m100;
LL DP[55][55][200];
LL C[61][61];

void solve()
{
    DP[m50][m100][0] = 1;
    for(int k=1;k<=100;k++)
    {
        for(int i=0;i<=m50;i++)
        {
            for(int j=0;j<=m100;j++)
            {
                for(int x=0;x<=m50;x++)
                {
                    if(x*50>m) continue;
                    for(int y=0;y<=m100;y++)
                    {
                        if(k&1)
                        {
                            if( (x+y==0) || i+x>m50 || j+y>m100 || (x*50+y*100)>m ) continue;
                            DP[i][j][k] = (DP[i][j][k]+(((DP[i+x][j+y][k-1]%mod)*C[i+x][x])%mod*C[j+y][y])%mod)%mod;
                            //debug(k) debug(i) debug(j) debug(DP[i][j][k])
                        }
                        else
                        {
                            if( (x+y==0) || i-x<0 || j-y<0 || (x*50+y*100)>m      ) continue;
                            DP[i][j][k] = (DP[i][j][k]+(((DP[i-x][j-y][k-1]%mod)*C[m50-i+x][x])%mod*C[m100-j+y][y])%mod)%mod;
                        }
                    }
                }
            }
        }
    }
    int ans = INF,loc;
    for(int i=0;i<=150;i++)
    {
        //debug(DP[0][0][i])
        if(DP[0][0][i]>0) 
        {
            ans = DP[0][0][i];
            loc = i;
            break;
        }
    }
    printf("%d\n%d\n",loc, ans);
}
void init()
{
    for(int i=0;i<=50;i++) //最大为60
        for(int j=0;j<=i;j++)
        {
            if(!j || i==j)
                C[i][j] = 1;
            else
                C[i][j] = C[i-1][j-1] + C[i-1][j];
                    //cout << i << "  " << j << ":  " << C[i][j] << endl;
        }
    return;
}
int main()
{
    //std::ios::sync_with_stdio(false);
    init();
    while(~scanf("%d%d", &n, &m))
    {
        m50 = m100 = 0;
        CLR(DP);
        for(int i=1;i<=n;i++) 
        {
            scanf("%d", &A[i]);
            if(A[i]==50) m50++;
            else m100++;
        }
        solve();
    }
    //system("pause");
    //printf("%lld\n", (x%mod+mod)%mod );
}

Problem D

某一天,YellowStar在人生的道路上迷失了方向,迷迷糊糊之中,它误入了一座迷宫中,幸运的是它在路口处发现了一张迷宫的地图。

经过它的观察,它发现这个迷宫一共有 $n$ 个房间,并且这 $n$ 个房间呈现一个有根树结构,它现在所在的 $1$ 号房间为根,其它每个房间都有一个上级房间,连接第 $i$ 个房间和它的上级房间 $P_i$ 的道路长度为 $W_i$ 。

在地图的背面,记载了这个迷宫中,每个房间拥有一个时空传送门,第 $i$ 个房间的传送门可以花费 $D_i$ 单位的时间传送到它的任意一个下级房间中(如果 $x$ 是 $y$ 的下级房间,并且 $y$ 是 $z$ 的下级房间,那么 $x$ 也是 $z$ 的下级房间)。

YellowStar的步行速度为 $1$ 单位时间走 $1$ 长度,它现在想知道从 $1$ 号房间出发,到每一个房间的最少时间。

数据范围:$ 1 ≤ n ≤ 10^5, 1 ≤ D_i, W_i ≤ 10^9$

Solution

对于每个节点,每次记录从父节点走过来的最小花费,同时记录从祖先节点飞过来的最小花费,每次取最小的即可。

AC code

int n;
LL D[MaxN];
struct Edge
{
    int u,v,next;
    LL w;
}edge[MaxM];
int cont, head[MaxN];
void add(int u,int v,LL w)
{
    edge[cont].u = u, edge[cont].v = v,  edge[cont].w = w, edge[cont].next = head[u], head[u] = cont++;
    //debug(u) debug(head[u])
}
LL dis[MaxN];
struct Node
{
    int id;
    LL minfei;
    Node(){}
    Node(int a, LL b):id(a),minfei(b){}
};
void BFS()
{
    dis[1] = 0;
    queue<Node> Q;
    Q.push(Node(1,D[1]));
    while(!Q.empty())
    {
        Node tmp = Q.front();
        int u = tmp.id;
        Q.pop();
        for(int i=head[u];i!=-1;i=edge[i].next)
        {
            int v = edge[i].v;
            dis[v] = min2(dis[u]+edge[i].w, tmp.minfei);
            Q.push(Node(v,min2(tmp.minfei, dis[v]+D[v])));
        }
    }
}
void solve()
{
    BFS();
    for(int i=1;i<=n;i++) printf("%lld ", dis[i]);
    puts("");
}
void init()
{
    cont = 0, MST(head,-1);
}
int main()
{
    //std::ios::sync_with_stdio(false);
    while(~scanf("%d", &n))
    {
        init();
        int p;LL w;
        for(int i=1;i<=n;i++) scanf("%lld", &D[i]);
        for(int i=1;i<n;i++)
        {
            scanf("%d%lld", &p, &w);
            add(p,i+1,w);
        }
        solve();
    }
    //system("pause");
    //printf("%lld\n", (x%mod+mod)%mod );
}

Problem E

给出一个初始值为 $1$ 的 $N \times M$ 的矩阵,每次随机挑选一个子矩阵将里面的数值置 $0$,问在 $K$ 次挑选后能够置换的 $1$ 的个数的期望为多少?

数据范围:$ 0 ≤ K ≤ 10^4, 1 ≤ N,M ≤ 10^3$

Solution

因为每个格子被置换是相互独立的,所以 $K$ 次置换后被置换的 $1$ 的个数的期望 $E$ 等于每个格子在 $K$ 次置换后被置换的 $1$ 的个数的期望 $E_{ij}$ 的和: $E = \sum^{n}_{i=1}\sum^{m}_{j=1}E_{ij},\ E_{ij} = 1 - (1-P_{该格一次被置换的概率})^K $

AC code

int K,N,M;
double Pow(double x,int k) {
    double res = 1;
    while (k) {
        if (k & 1)res = res*x;
        x = x*x;
        k >>= 1;
    }
    return res;
}

int main()
{
    //std::ios::sync_with_stdio(false);
    while(~scanf("%d%d%d", &K, &N, &M))
    {
        double ans = 0;
        for(int i=1;i<=N;i++)
        {
            for(int j=1;j<=M;j++)
            {
                double pij = ((double)(2.0*i*(N-i+1)-1)/Sqr(N)) * ((double)(2.0*j*(M-j+1)-1)/Sqr(M));
                ans += (1-Pow(1.0-pij, K));
            }
        }
        //debug(ans);
        ans = round(ans);
        printf("%.0f\n", ans);
    }
    //system("pause");
    //printf("%lld\n", (x%mod+mod)%mod );
}

Problem G

有如下取牌游戏:

  1. 桌面上有 $n$ 张卡牌从左到右排成一行,每张卡牌上有一个数字;

  2. 游戏按轮次进行,每一轮中取掉所有比左边数值小的卡牌;

  3. 当无牌可取的时候则游戏结束。

比如初始卡牌为 ${5, 6, 3, 7, 4, 1, 2}$,共需 $2$ 轮取牌。取牌过程如下(小括号为每轮取掉的牌):

${5, 6, 3, 7, 4, 1, 2}$

==> ${5, 6, (3), 7, (4), (1), 2}$

==> ${5, 6, 7, 2}$

==> ${5, 6, 7, (2)}$

==> ${5, 6, 7}$

现按顺序给定初始的卡牌数字,请求出游戏结束时取牌的总轮次,并输出结束时桌上剩余的卡牌序列。

数据范围:$ 0 ≤ n ≤ 10^6, 1 ≤ a_i ≤ 10^9$

Solution

首先,第一张卡片是必须留下的,往后比它小的最后都会被删除,那么下一个被留下的就是第一张比它大的卡片,依次类推,最终留下的卡片序列就是从第一张开始的一个非降子序列。然后我们再判断需要多少轮才能够将其他牌取完,我们先将原序列构建成一个双向链表,那么把第一次就能够被删除的节点丢入队列中,那么对于队列中的每一个节点,如果它的后继节点没有进过队列并且比当前节点的值大,比当前节点的前驱节点要小,那么它就是下一轮需要被删除的节点。所以我们每次取出队列中的节点,并判断能否产生新的节点入队,最后保存最大回合数就是答案,队列里剩下的节点就是最后的序列。

AC code

int N;
struct Node
{
    int loc,turn;
    Node(){}
    Node(int a, int b):loc(a),turn(b){}
};
struct List
{
    int val,pre,next;
}L[MaxN];

bool vis[MaxN];
queue<Node> Q;
void solve()
{
    int ans = 0;
    while(!Q.empty())
    {
        Node tmp = Q.front();
        Q.pop();
        int pre = L[tmp.loc].pre, nxt = L[tmp.loc].next;
        L[pre].next = nxt, L[nxt].pre = pre;
        ans = max(ans, tmp.turn);
        if(!vis[nxt])
        {
            if(L[pre].val>L[nxt].val)
            {
                //vis[nxt] = 1;
                Q.push(Node(nxt,tmp.turn+1));
            }
        }
    }
    printf("%d\n", ans);
    bool flag = false;
    int st = 1;
    while(st<=N)
    {
        if(flag) printf(" ");
        flag = true;
        printf("%d", L[st].val);
        st = L[st].next;
    }
    puts("");
}
int A[MaxN];
int main()
{
    //std::ios::sync_with_stdio(false);
    while(~scanf("%d", &N))
    {
        while(!Q.empty()) Q.pop();
        int x;
        for(int i=1;i<=N;i++) 
        {
            scanf("%d", &A[i]);
            L[i].val = A[i];
            L[i].pre = i-1;
            L[i].next= i+1;
            vis[i] = 0;
            if(A[i-1]>A[i]) Q.push(Node(i,1)),vis[i] = 1;
        }
        L[N+1].val = 1000000001;              
        solve();
    }
    //system("pause");
    //printf("%lld\n", (x%mod+mod)%mod );
}