牛客算法周周练7

A

Soltuion

这题怎么说呢?八仙过海各显神通吧。

仅针对本题而言， $O(n)：$ 做法直接计算 $(minx,miny)$ 和 $(maxx,maxy)$ 的曼哈顿距离的两倍即可。
dfs/next_permutation 暴力 $n!$ 。
数据范围大一点，改一下题不能用做法1和做法2的时候，应当是状压DP。

Code

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int>P;
const double eps = 1e-8;
const int NINF = 0xc0c0c0c0;
const int INF  = 0x3f3f3f3f;
const ll  mod  = 1e9 + 7;
const ll  maxn = 1e6 + 5;

void solve(){
    int n,m,sx,sy,t;
    cin>>n>>m>>sx>>sy>>t;
    pair<int,int> a[10];
    for(int i=0;i<t;i++){
        cin>>a[i].first>>a[i].second;
    }
    sort(a,a+t);
    int ans=INF;
    do{
        int tmp=abs(sx-a[0].first)+abs(sy-a[0].second);
        for(int i=1;i<t;i++){
            tmp+=abs(a[i].first-a[i-1].first)+abs(a[i].second-a[i-1].second);
        }
        tmp+=abs(sx-a[t-1].first)+abs(sy-a[t-1].second);
        ans=min(ans,tmp);
    }while(next_permutation(a,a+t));
    cout<<"The shortest path has length "<<ans<<"\n";
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    int T;cin>>T;
    while(T--){
        solve();
    }
    return 0;
}

B

Soltuion

DFS+剪枝
考虑到 $R$ 和 $H$ 都是整数，且存在 $V$ 和 $S$ 制约 $R$ 的选择范围，所以可以将R的数据范围大致确定，然后dfs枚举。
我们令下面为 $M$ 层,最上面为第 $1$ 层，则每层对应的最小 $minR_i=i$ 。

预处理每层的最小 $R$ 对应的最小 $V$ ，最小 $S$
DFS再可能有解的数据范围内枚举

由于该数据范围依旧过大，会 $TLE$ 。
我们考虑剪枝:

已选择的 $S$ +剩下体积能转换的的最小 $S$ >=已知最优解的 $S$
已选择的 $S$ +所能选的最小的 $S$ >=已知最优解的 $S$
已选择的 $V$ +所能选的最小的 $V$ >= $n$

Code

#include<bits/stdc++.h>
#define fi first
#define se second
#define mp make_pair
using namespace std;
typedef long long ll;
typedef pair<int,int>P;
const double eps = 1e-8;
const int NINF = 0xc0c0c0c0;
const int INF  = 0x3f3f3f3f;
const ll  mod  = 1e9 + 7;
const ll  N = 1e6 + 5;

int ans=INF;
int n,m;
int mins[N],minv[N],preS[N],preV[N];

void dfs(int r,int h,int s,int v,int k){
    if(k==0){
        if(v==n) ans=min(ans,s);
        return;
    }
    if(s+2*(n-v)/r>ans) return;
    if(v+minv[k]>n) return;
    if(s+mins[k]>ans) return;
    for(int i=r-1;i>=k;i--){
        if(k==m) s=i*i;
        int mxh=min(h-1,(n-v-minv[k-1])/(i*i));
        for(int j=mxh;j>=k;j--){
            dfs(i,j,s+2*i*j,v+i*i*j,k-1);
        }
    }
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin>>n>>m;
    for(int i=1;i<=m;i++){
        mins[i]=mins[i-1]+2*i*i;
        minv[i]=minv[i-1]+i*i*i;
    }
    int mx=(int)sqrt(n);
    dfs(mx,n,0,0,m);
    if(ans==INF) cout<<0;
    else cout<<ans;
    return 0;
}

C

Soltuion

DP，01背包变形

Code

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int>P;
const double eps = 1e-8;
const int NINF = 0xc0c0c0c0;
const int INF  = 0x3f3f3f3f;
const ll  mod  = 1e9 + 7;
const ll  maxn = 1e6 + 5;
const ll  N = 4e2 + 5;

char s[N];
int f[N][N];

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n,m;
    cin>>n>>m>>s+1;
    memset(f,0x3f,sizeof(f));
    f[0][0]=0;
    for(int i=1;i<=n;i++){
        for(int j=i;j>=1;j--){
            for(int k=1;k<=j;k++){
                f[j][0]=min(f[j][0],f[j][k]);
                if(s[i]=='1') f[j][k]=min(f[j][k],f[j-1][k-1]+k);
            }
        }
    }
    int ans=0;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=i;j++)
            if(f[i][j]<=m) ans=i;
    cout<<ans;
    return 0;
}

D

Soltuion

Tarjan求割边模板题
答案为总边数减掉割边

下面讲讲如何利用Tarjan求割边。
Tarjan求割边:
Tarjan有两个数组 $low$ 和 $dfn$ ， $low$ 表示能回到的最早的时间戳的编号， $dfn$ 表示遍历的时间戳编号。
问题关键在于如何判断是否为割边？

$low[son]>dfn[father]$ 的时候这条边就 $father-son$ 的边即为割边，这表示当前子节点无法从其他路径回到父节点，即父节点和子节点这条边是桥。

Code

#include<bits/stdc++.h>
#define fi first
#define se second
#define mp make_pair
using namespace std;
typedef long long ll;
typedef pair<int,int>P;
const double eps = 1e-8;
const int NINF = 0xc0c0c0c0;
const int INF  = 0x3f3f3f3f;
const ll  mod  = 1e9 + 7;
const ll  N = 1e5 + 5;

int n,m,cnt,low[N],dfn[N],cut[N],ans;
vector<int> G[N];

void tarjan(int x,int fa){
    low[x]=dfn[x]=++cnt;
    for(auto c:G[x]){
        if(!dfn[c]){
            tarjan(c,x);
            low[x]=min(low[x],low[c]);
            if(low[c]>dfn[x]) ans++;
        }
        else if(c!=fa) low[x]=min(low[x],dfn[c]);//c!=fa表明不是父亲节点
    }
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin>>n>>m;
    for(int i=1;i<=m;i++){
        int u,v;cin>>u>>v;
        G[u].push_back(v);
        G[v].push_back(u);
    }
    tarjan(1,1);
    cout<<m-ans<<'\n';
    return 0;
}

E

Soltuion

高中数学题，比较 $x^y$ 和 $y^x$ ，我们可以由对数函数的单调性去比。
图片说明

Code

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int>P;
const double eps = 1e-8;
const int NINF = 0xc0c0c0c0;
const int INF  = 0x3f3f3f3f;
const ll  mod  = 1e9 + 7;
const ll  maxn = 1e6 + 5;

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    int x,y;cin>>x>>y;
    double u=y*log10(x),v=x*log10(y);
    if(u>v)    cout<<">";
    else if(u<v) cout<<"<";
    else cout<<"=";
    return 0;
}