【题解】牛客算法周周练7 A、C、D、E

前言：快期末了时间越来越少了，补题也不能做那么多了，这次B题只过了40个大概就不写了吧，只写了比较简单的剩余4个题（其实C、D没见过这种题还真的不是那么简单）

A 收集纸片

这是小白月赛里面的题，我打过那场小白月赛，我当时用的方法是旅行商问题的DP，也就是先处理好两点间的距离dis[i][j]，然后dp[i][j]表示终点为i时，此时已经经过点的状态为j，（状态因为是二进制数，1表示已经经过，0表示还未经过）花费的距离是多少。
三重循环，第一重循环是：枚举状态，然后枚举起点，最后枚举终点。
dp转移方程为： $图片说明$

因为n只有10，其实用next_permutation枚举所有的情况也可以。

代码

#include<bits/stdc++.h>

using namespace std;

const int maxn=1<<15;

int dp[25][maxn];

int x[25],y[25];

int dis[20][20];

int main(){
    int T;
    scanf("%d",&T);
    while(T--){
        int rx,ry;
        scanf("%d%d",&rx,&ry);
        scanf("%d%d",x+0,y+0);
        int n;
        scanf("%d",&n);
        for(int i=1;i<=n;i++){
            scanf("%d",x+i);scanf("%d",y+i);
        }
        for(int i=0;i<=n;i++){
            for(int j=0;j<=n;j++){
                dis[i][j]=dis[j][i]=abs(x[i]-x[j])+abs(y[i]-y[j]);
            }
        }
        int N=1<<(n+1);
        memset(dp,0x3f,sizeof(dp));
        for(int i=1;i<N;i++){
            for(int j=0;j<=n;j++){
                if(dp[j][i]==0x3f3f3f3f) continue;
                if((i>>j)&1){
                    for(int c=1;c<=n;c++){
                        dp[c][i^(1<<c)]=min(dp[c][i^(1<<c)],dp[j][i]+dis[j][c]);
                    }
                }
            }
        }
        int ans=0x3f3f3f3f;
        for(int i=0;i<=n;i++){
            ans=min(ans,dp[i][N-1]+dis[i][0]);
        }
        printf("The shortest path has length %d\n",ans);
    }
    return 0;
}

C Rabbit的工作(1)

很明显的DP了，但是这个题有意思的一点是要用滚动数组，不然会MLE。
首先看到n是400，400400400也不到1e8，可以用n^3的暴力。
所以联想到dp数组要开三维，正常来说是这三维：dp[i][j][k]
i表示前i天，j是已经工作了j天，k是到目前已连续工作了多少天。
那么很容易得到转移方程：
如果这天不工作或者这天本来就不用工作：dp[i][j][0]=min(dp[i][j][0],dp[i-1][j][k])
如果今天需要工作：dp[i][j][k]=min(dp[i][j][k],dp[i-1][j-1][k-1]+k)
但是因为会MLE，同时我们发现dp数组只跟dp[i-1]有关，所以我们可以把第一维压到2，通过奇偶来表示不同的上下两层就好了。

代码

#include<cstdio>
#include<iostream>
#include<cmath>
#include<algorithm>
#include<vector>
#include<cstring>
#include<queue>
#define fs first
#define se second
#define pb push_back
#define cppio ios::sync_with_stdio(false);cin.tie(0)
#define eps 1e-7
using namespace std;

typedef long long ll;
typedef pair<int,int> pii;
typedef vector<int> VI;

const int maxn=405;
const ll inf=0x3f3f3f3f;
const ll mod=1e9+7;

char s[maxn]; 

int dp[2][maxn][maxn];

int main(){
    int n,K;
    scanf("%d%d%s",&n,&K,s+1);
    memset(dp,0x3f,sizeof(dp));
    dp[0][0][0]=0;
    for(int i=1;i<=n;i++){
        memset(dp[i%2],0x3f,sizeof(dp[i%2]));
        for(int j=i;j>=0;j--){
            for(int k=0;k<=j;k++){
                dp[i%2][j][0]=min(dp[i%2][j][0],dp[(i+1)%2][j][k]);
                if(s[i]=='1'&&k>0){
                    dp[i%2][j][k]=min(dp[i%2][j][k],dp[(i+1)%2][j-1][k-1]+k);
                }
            }
        }
    }
    for(int i=n;i>=0;i--){
        for(int j=i;j>=0;j--){
            if(dp[n%2][i][j]<=K){
                printf("%d\n",i);return 0;
            }
        }
    }
    return 0;
}

D 华华和月月逛公园

这是tarjan求割边的模板题，因为之前没遇到这种题所以想了很久，最后才知道是用tarjan来求的。
割边：如果删掉这条边图就不连通了，那么这条边就是割边。
这道题就是求有多少条割边，然后取m减去割边数量。
怎么求？通过tarjan求强连通分量就行了，但是以前的tarjan是求有向图的，无向图怎么办。
挺简单的，首先我们知道dfn是dfs序，low是连通分量里面的最小值。
转移：
如果下一个点没被访问过：low[u]=min(low[u],low[to])
如果访问过并且不是父亲节点：low[u]=min(low[u],dfn[to])
这部分跟有向图基本上是一样的，判断割边只需要判断low[to]是不是大于dfn[u]就好，为什么？
因为low[to]如果大于dfn[u]，说明通过这条边只能连到dfs序之后的点，不会回到之前的点，既然回不去，那么这条边就很明显就是割边了，因为只有这一条路。

【题解】牛客算法周周练7 A、C、D、E

A 收集纸片

C Rabbit的工作(1)

D 华华和月月逛公园

E 数字比较

全站热榜