个人题解 | 牛客周赛 Round 86 A-F

A：小苯跑外卖

语法题，注意是上取正

#include <bits/stdc++.h>

using namespace std;

inline int read(){
    char ch = getchar();
    int x =0,f =1;
    for(;!isdigit(ch);ch =  getchar())
        if(ch == '-') f = -1;
    for(; isdigit(ch);ch = getchar())
        x = (x << 1) + (x << 3) + ch - '0';
    return f * x;
}

void slove(){
    int x= read(),y = read();
    cout << (y + x - 1) / x;
}

signed main(){
    int T = 1;
    //T = read();
    while(T --){
        slove();
    }
    return 0;
}

B：小苯的区间删除

能进行无限次操作，所以负贡献都需要删去，还是语法题。

注意多测

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

inline int read(){
    char ch = getchar();
    int x =0,f =1;
    for(;!isdigit(ch);ch =  getchar())
        if(ch == '-') f = -1;
    for(; isdigit(ch);ch = getchar())
        x = (x << 1) + (x << 3) + ch - '0';
    return f * x;
}

void slove(){
    int n = read(),k = read();
    int res = 0;
    for(int i = 1;i <= n;i ++){
        int x = read();
        if(x > 0) res += x;
    }
    cout << res << endl;
}
signed main(){
    int T = 1;
    T = read();
    while(T --){
        slove();
    }
    return 0;
}

C：小苯的数字消除

由于只有相邻两项相同时，消去这两项，不难想到括号匹配

我们先用类似括号匹配的方式将串变成 101010101，接着考虑修改操作，显然每次修改都会使得串的长度 -2 ，所以如果是用栈实现括号匹配，答案就是 。

注意多测

#include <bits/stdc++.h>
//#define ull unsigned long long int 
#define int long long int
#define endl '\n'
#define pb push_back
using namespace std;

const int N = 1E6 + 70,mod = 998244353,INF = 0x3f3f3f3f3f3f3f3f;

inline int read(){
    char ch = getchar();
    int x =0,f =1;
    for(;!isdigit(ch);ch =  getchar())
        if(ch == '-') f = -1;
    for(; isdigit(ch);ch = getchar())
        x = (x << 1) + (x << 3) + ch - '0';
    return f * x;
}

char s[N];

void slove(){
    int n = read();
    stack<int > sta;
    char ch;
    for(int i = 1;i <= n;i ++){
        cin >> ch;
        int x = ch - '0';
        if(sta.empty() || sta.top() != x) sta.push(x);
        else if(sta.top() == x) sta.pop();
    }
    cout << sta.size() / 2 << endl;
}
signed main(){
    int T = 1;
    T = read();
    while(T --){
        slove();
    }
    return 0;
}

D：小苯的数字集合

首先读题，发现一个重要的点，数字集合 是 可重集合 ,这意味着里面可以出现重复数字。

所以对于任意的 ，我们都能够通过 次操作得到 。例:

所以我们只需考虑能否通过少于 次的操作得到

详细见代码

#include <bits/stdc++.h>
//#define ull unsigned long long int 
#define int long long int
#define endl '\n'
#define pb push_back
using namespace std;

const int N = 1E6 + 70,mod = 998244353,INF = 0x3f3f3f3f3f3f3f3f;

inline int read(){
    char ch = getchar();
    int x =0,f =1;
    for(;!isdigit(ch);ch =  getchar())
        if(ch == '-') f = -1;
    for(; isdigit(ch);ch = getchar())
        x = (x << 1) + (x << 3) + ch - '0';
    return f * x;
}

char s[N];

void slove(){
    int x = read(),y = read();
    if(x == y || (x & y) == 0) cout << 1 << endl;
    else {
        int c = x & y;
        if((c & x) == 0 || (c & y) == 0 || c == x || c == y){
            cout << 2 << endl;
            return;
        }
        c = x | y;
        if((c & x) == 0 || (c & y) == 0|| c == x || c == y){
            cout << 2 << endl;
            return;
        }
        c = x ^ y;
        if((c & x) == 0 || (c & y) == 0 || c == x || c == y){
            cout << 2 << endl;
            return;
        }
        c = __gcd(x,y);
        
        if((c & x) == 0 || (c & y) == 0|| c == x || c == y){
            cout << 2 << endl;
            return;
        }
        
        cout << 3 << endl;
    }
}

signed main(){
    int T = 1;
    T = read();
    while(T --){
        slove();
    }
    return 0;
}

我不会告诉你我赛时写了两个 c == y导致我WA的

E：小苯的Polygon

赛时看到凸多边形想了一下三角形不等式就跑了

由三角形不等式我们可知，对于三角形的三条边 ,有:

即最长边小于两边之和，对于所有的凸多边形我们也有类似的结论:

记凸多边形的边集为 ， 为凸多边形的所有边的长度之和， 为边集 中的最长边。

则有

我们可以枚举 ，用 01背包 来记录所有小于 的边所能组合成的边集 的 。

遍历一遍看看 和 能否组成凸多边形。

如何枚举 ? 只需保证前面的边都小于等于当前的边即可(std::sort)。

类似分析思想的小 题目 NWERC 2024 D

#include <bits/stdc++.h>
//#define ull unsigned long long int 
#define int long long int
#define endl '\n'
#define pb push_back
using namespace std;

const int N = 1E5 + 70,mod = 998244353,INF = 0x3f3f3f3f3f3f3f3f;
double exps = 1e-4;

typedef pair<int,int> PII;
typedef pair<double,double> PDD;

inline int read(){
    char ch = getchar();
    int x =0,f = 1;
    for(;!isdigit(ch);ch =  getchar())
        if(ch == '-') f = -1;
    for(; isdigit(ch);ch = getchar())
        x = (x << 1) + (x << 3) + ch - '0';
    return f * x;
}

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

void slove(){
    int n = read();
    int sum = 0;
    for(int i = 1;i <= n;i ++) a[i]= read(),sum += a[i];
    for(int i = 1;i <= sum;i ++)f[i] = 0;
    f[0] = 1;
    sort(a + 1,a  +1 + n);
    int res = INF;
    for(int i = 1;i <= n;i ++){
        for(int j =  a[i] + 1;j <= sum;j ++){
            //S(E) - max(E) >= max(E) + 1 >  max(E)
            if(f[j]) {res = min(j + a[i] ,res);break;}
        }
        for(int j = sum;j >= a[i];j --){
            f[j] |= f[j - a[i]];
        }
    }
    if(res == INF) res = -1;
    cout << res << endl;
}

signed main(){
    int T = 1;
    T = read();
    while(T --){
        slove();
    }
    return 0;
}

F：小苯的线性dp

我们显然能够想到将一串连续的数合并起来与未合并的数比较相减。

即

注意到

大胆跑

我这里是采用 st表 来 的获取

#include <bits/stdc++.h>
//#define ull unsigned long long int 
#define int long long int
#define endl '\n'
#define pb push_back
using namespace std;

const int N = 1E6 + 70,mod = 998244353,INF = 0x3f3f3f3f3f3f3f3f;
double exps = 1e-4;

typedef pair<int,int> PII;
typedef pair<double,double> PDD;

inline int read(){
    char ch = getchar();
    int x =0,f =1;
    for(;!isdigit(ch);ch =  getchar())
        if(ch == '-') f = -1;
    for(; isdigit(ch);ch = getchar())
        x = (x << 1) + (x << 3) + ch - '0';
    return f * x;
}

int a[N],st[N][20],sum[N];
int n;
void init(){
    sum[0] = 0;
    for( int i = 1;i <= n;i ++) st[i][0] = a[i],sum[i] = sum[i - 1] + a[i];
	for( int j = 1;j <= 20;j ++){
        int t =(1 << (j - 1));
		for( int l = 1;l <= n - t;l ++){
			st[l][j] = min(st[l][j - 1],st[l + t][j - 1]);
		}
	}
}

inline int query(int l,int r){
    if(l > r) return INF;
	int k = __lg(r - l + 1);
    return min(st[l][k],st[r - (1 << k) + 1][k]);
}

void slove(){
    n = read();
    for(int i = 1;i <= n;i ++) a[i] = read();
	init();
    for(int k = 1;k < n;k ++){
        int res = 0;
        for(int i = k;i <= n;i ++){
            int t = (sum[i] - sum[i - k]) - min(query(1,i - k),query(i + 1,n));
            res = max(t,res);
        }
        cout << res << " ";
    }
    cout << 0 << endl;
}

signed main(){
    int T = 1;
    T = read();
    while(T --){
        slove();
    }
    return 0;
}

交上去一看，怎么 了？

手造数据发现类似于 1000,9000,1,10,100 ，不合并 这个数显然更优，也就是 [1000,9000],1,[10,100] 此时合并 次与合并 次的结果是一样的。

我没注意到结论，然后赛时没改出来

所以我们就可以记录上一次的答案与当前作比较取 。

最重要的一点是，只有当合并次数 ， 时我们才能够与上一次的结果取，因为当 时，合并后就剩下了 个数字，当 处在中间时， 一定会合并掉 。

#include <bits/stdc++.h>
//#define ull unsigned long long int 
#define int long long int
#define endl '\n'
#define pb push_back
using namespace std;

const int N = 1E6 + 70,mod = 998244353,INF = 0x3f3f3f3f3f3f3f3f;
double exps = 1e-4;

typedef pair<int,int> PII;
typedef pair<double,double> PDD;

inline int read(){
    char ch = getchar();
    int x =0,f =1;
    for(;!isdigit(ch);ch =  getchar())
        if(ch == '-') f = -1;
    for(; isdigit(ch);ch = getchar())
        x = (x << 1) + (x << 3) + ch - '0';
    return f * x;
}

int a[N],st[N][20],sum[N];
int n;
void init(){
    sum[0] = 0;
    for( int i = 1;i <= n;i ++) st[i][0] = a[i],sum[i] = sum[i - 1] + a[i];
	for( int j = 1;j <= 20;j ++){
        int t =(1 << (j - 1));
		for( int l = 1;l <= n - t;l ++){
			st[l][j] = min(st[l][j - 1],st[l + t][j - 1]);
		}
	}
}

inline int query(int l,int r){
    if(l > r) return INF;
	int k = __lg(r - l + 1);
    return min(st[l][k],st[r - (1 << k) + 1][k]);
}

void slove(){
    n = read();
    for(int i = 1;i <= n;i ++) a[i] = read();
	init();
    int last = -1;
    for(int k = 1;k < n;k ++){
        //我这边的 k 是合并的区间长度，合并次数是 k - 1
        int res = 0;
        for(int i = k;i <= n;i ++){
            int t = (sum[i] - sum[i - k]) - min(query(1,i - k),query(i + 1,n));
            res = max(t,res);
        }
        if(k < n - 1)res = max(res,last);
        last = res;
        cout << res << " ";
    }
    cout << 0 << endl;
}

signed main(){
    int T = 1;
    T = read();
    while(T --){
        slove();
    }
    return 0;
}

可能有人会问 的更新为什么是正确的，因为 ，若连续合并 次比合并 次优,那么合并 的最优解一定是连续合并 次 与 在上一轮合并的状态中另找两个数合并 的两者中取 ，我扔个数据在这:

input :
1
6
1000 9000 1 9 999 9000

output :
8999 9999 10007 10007 0