2025 3.10~3.16

牛客周赛84

续上周

D

赛时用的数学方法，花的时间和代码量比较多。差分我写得少，这里用题解的差分方法补个题

用差分数组对每个k区间做修改，然后求和以及相邻数字绝对值差对陡峭值的贡献即可

#include <bits/stdc++.h> 
using namespace std;
const int maxn = 1e6+1;

int t[maxn],d[maxn];
int main(void){
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    int n,k,ans=0;
    cin >> n >> k;
    string s;
    cin >> s;
    for(int i=1,j=k;j<=n;i++,j++){
        d[i]++;
        d[j]--;
    }
    t[0]=0;
    for(int i=1;i<=n;i++){
        t[i] += t[i-1] + d[i];
        ans += t[i] * abs(s[i]-s[i-1]);
    }
    cout << ans << '\n';
    return 0;
}

E

题目

以1为根节点，用dfs搜出每个子树的陡峭值，然后再用dfs求出每个节点与其子树断开后的陡峭值之差的绝对值，ans取最小

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int maxn = 1e5+1;

vector <int> G[maxn];
int sum[maxn]={0},ans = 2LL<<60;

void dfs_sum(int u,int f){
    for(auto &v:G[u]){
        if(v == f)
            continue;
        dfs_sum(v,u);
        sum[u] += sum[v] + abs(u-v);
    }
}

void dfs_split(int u,int f){
    for(auto &v:G[u]){
        if(v == f)
            continue;
        ans = min(ans,abs(sum[v]-(sum[1]-sum[v]-abs(u-v))));
        dfs_split(v,u);
    }
}
signed main(void){
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    int n,u,v;
    cin >> n;
    for(int i=0;i<n-1;i++){
        cin >> u >> v;
        G[u].push_back(v);
        G[v].push_back(u);
    }
    dfs_sum(1,0);
    dfs_split(1,0);
    cout << ans << '\n';
    return 0;
}

CF1006 div.3

A

求最少操作次数，贪心，如果n*p < |k|了，肯定不行，否则就是k/p

#include <bits/stdc++.h>
using namespace std;

int main(void){
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    int t;
    cin >> t;
    while(t--){
        int n,k,p;
        cin >> n >> k >> p;
        if(n*p < abs(k)){
            cout << "-1\n";
        }
        else cout << ceil(1.0*abs(k)/p) << '\n';
    }
    return 0;
}

B

可以发现，数量最多的情况就是"--“尽可能呈对称的情况，”"全都放在中间。

特判就是n<3的时候无法组成图案

#include <bits/stdc++.h>
#define int long long
using namespace std;

signed main(void){
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    int t;
    cin >> t;
    while(t--){
        int n; string s;
        cin >> n >> s;
        if(n < 3){
            cout << "0\n";
            continue;
        }
        int num1 = 0,num2 = 0,si = s.size();
        for(int i=0;i<si;i++){
            if(s[i] == '-') num1++;
            else num2++;
        }
        int a1 = num1/2, a2 = num1-a1;
        cout << a1*num2*a2 << '\n';
    }
    return 0;
}

C

贪心，用num来模拟每个数按位或

因为按位或不会增加二进制位数，所以当第n个数或后都还小于x的话，直接输出x；中间某个数或x后大于x了(即x的二进制的某位是0)，那么从这个数以后都输出x

#include <bits/stdc++.h>
using namespace std;

int main(void){
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    int t;
    cin >> t;
    while(t--){
        int n,x;
        cin >> n >> x;
        int num=0;
        for(int i=0;i<n;i++){
            num |= i;
            if((num | x) > x){
                for(;i<n;i++)
                    cout << x << ' ';
                break;
            }
            if(i == n-1 && num < x){
                cout << x << ' ';
                break;
            }
            cout << i << ' ';
        }
        cout << '\n';
    }
    return 0;
}

D

贪心地想，要使得交换后逆序对尽可能少，那么就要让区间(l，r)上比al大的尽可能少，比al小的尽可能多。用da记录比al大的，xiao记录比al小的，xiao-da的值越大，就说明l和r交换后逆序对越少

这个算法是O(n²)的复杂度，题目给的数据范围内是可接受的

#include <bits/stdc++.h>
using namespace std;
vector <int> a(2001);

int main(void){
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    int t;
    cin >> t;
    while(t--){
        int n;
        cin >> n;
        a.clear();
        for(int i=1;i<=n;i++)
            cin >> a[i];
        int ans=0,l=1,r=1;
        for(int i=1;i<=n;i++){
            int da=0, xiao=0;
            for(int j=i;j<=n;j++){
                if(a[j] > a[i])
                    da++;
                else if(a[j] < a[i])
                    xiao++;
                if(ans < xiao - da){
                    ans = xiao - da;
                    l=i,r=j;
                }
            }
        }
        cout << l << ' ' << r << '\n';
    }
    return 0;
}

状压DP

状压DP是DP的一种优化方法

Hamilton旅行商问题

Hamilton问题是NP问题，没有多项式复杂度的解法，暴力解法复杂度是O(n*n!)，而状压DP可将复杂度将为O(n²*2n)

设S是图的一个子集；

dp[S][j]：表示“集合S内的最短Hamilton路径”，即从起点0出发经过S中所有点，到达终点j时的最短路径；集合S中包括j点；

让S从最小的子集逐步拓展到整个图，最后得到的dp[N][n-1]就是答案，N表示包含图上所有点的集合。

（S-j表示从集合S中去掉j，即不包含j点的集合）

设k为S-j中一个点，把从0到j的路径分为两部分：(0->…->k)+(k->j)。以k为变量枚举S-j中所有的点，找出最短路径

状态转移方程为：

dp[S][j] = min(dp[S-j][k] + dist(k,j))

状态压缩DP的技巧：用一个二进制数表示集合S，即把S压缩到一个二进制数中，S的每一位表示图上的一个点，0表示不包含，1表示包含

例如S = 0000 0101，表示包含2，0这两个点

if((S>>j) & 1)，判断当前的集合S中是否含有j点

if((S^(1<<j))>>k & 1) ,其中S^(1<<j)的作用是从集合中去掉j点，得到集合S-j，然后>> k & 1表示用k遍历集合中的1，这些1就是S-j中的点，这样就实现了"枚举集合S-j中所有的点" (S^(1<<j))也可以写成S-(1<<j)

Code

#include <bits/stdc++.h>
using namespace std;
int n,dp[1<<20][21];
int dist[21][21];

int main(void){
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    memset(dp,0x3f,sizeof(dp));		//初始化最大值 
    cin >> n;
    for(int i=0;i<n;i++)            //输出图 
        for(int j=0;j<n;j++) 
            cin >> dist[i][j];		//输入点之间的距离 
    dp[1][0] = 0;            //开始：集合中只有点0，起点和终点都是0 
    for(int S=1;S<(1<<n);S++)    //从小集合拓展到大集合，集合用S的二进制表示 
        for(int j=0;j<n;j++)	//枚举点j 
            if((S>>j) & 1)		//这个判断和下面的判断同时起作用 
                for(int k=0;k<n;k++)	//枚举到达j的点k，k属于集合S-j 
                    if((S^(1<<j)) >> k & 1)	//k属于集合S-j 
                        dp[S][j] = min(dp[S][j],dp[S^(1<<j)][k] + dist[k][j]);
    cout << dp[(1<<n)-1][n-1] << '\n';    //终点是n-1； 
    return 0;
}