牛客小白月赛117题解

明天是端午放假，先祝大家端午快乐，今天来水一下月赛。比赛链接牛客小白月赛117

A

题目大意

题目要求判断一个字符串（内容为26个大小写字母）是否对于任意一个字符，其大写及小写字母均出现。

样例	样例输入	样例输出
1	4 abAB	YES
2	2 ab	NO

思路

我们可以用一个数组来记录每个字符是否出现，然后判断每个字符的大写及小写是否均出现即可。

代码

#include <bits/stdc++.h>
using namespace std;
int n;
string s;
map<char,int> cnt;

int n;
string s;
map<char,int> cnt;

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	cin >> n >> s;
	for(int i=0; i<n; i++)cnt[s[i]]++;
	for(int i=0; i<n; i++)
	{
		if(s[i]<='z'&&s[i]>='a'&&!cnt[s[i]-'a'+'A'])
		{
			cout << "NO" << endl;
			return 0;
		}
		else if(s[i]<='Z'&&s[i]>='A'&&!cnt[s[i]-'A'+'a'])
		{
			cout << "NO" << endl;
			return 0;
		}
	}
	cout << "YES" << endl;

	return 0;
}

B

题目大意

题目输入一个长度为 $n$ 的数组 $a$ ， $a_i$ 有如下定义：

• 对于大小为 $n$ 的样本数据，若其平均数为 $x$，第 $i$ 个数据
  • 大于 $x$ 则 $a_i=1$
  • 小于 $x$ 则 $a_i=-1$
  • 等于 $x$ 则 $a_i=0$

那么考虑在这样的数组 $a$ 作用下，其平均数是否不变？

样例1

样例输入：

4
0 0 0 0

样例输出：

YES

样例2

样例输入：

5
1 1 1 1 1

样例输出：

NO

说明：

如果给每个数都加上某个正数 ，那么平均数肯定会改变。

思路

我们知道，对于样本容量 $n$ 的数据 $A$，其平均数 $x$ 满足：$\sum_{i=1}^{n}\frac{A_i}{n}=x$

那么对于施加 $a$ 后，变为: $x+\frac{1}{n}\sum_{i=1}^{n}a_i$

显然只要考虑 $\sum_{i=1}^{n}a_i$ 是否为 $0$ 即可。

显然地，若存在 $a_p=\sum a_i$ 或者 $a_1=a_2= \cdots = a_n = 0$，那么 $x$ 的值不变。

那么代码就很容易得到了，我们统计一下 $a$ 中 $1$ 和 $-1$ 的个数，然后按照上面的比较即可。

代码

int n;
int a,p=0,q=0;

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	cin >> n;
	for(int i=0; i<n; i++)
	{
		cin>>a;
		if(a==1)p++;
		if(a==-1)q++;
	}
	cout << (((p&&q)||(q==0&&p==0))?"YES":"NO") << endl;
	return 0;
}

C

题目大意

给出在正整数集合内范围为 $[l,r]$ ，在其中选定两个子集 $\mathbb{S}_1$ 、$\mathbb{S}_2$ ，其中 $gcd(\mathbb{S}_1)=1 , gcd(\mathbb{S}_2) \neq 1 且 \mathbb{S}_1 \cup \mathbb{S}_2=[l,r]$ ，求 $\min{abs(|\mathbb{S}_1|-|\mathbb{S}_2|)}$ ，如果不存在则输出-1。

样例1

样例输入：

2
2 3
4 6

样例输出：

-1
1

说明：

• 对于第一次询问，不存在满足条件的 $\mathbb{S}_1$ 和 $\mathbb{S}_2$ ，所以输出 -1。
• 对于第二次询问，可以分组为 $\mathbb{S}_1={4,5},\mathbb{S}_2={6}$

思路

我们注意到：

• 对于区间长度为偶数时，我们总可以构造出 $\mathbb{S}_1$ 取区间内奇数， $\mathbb{S}_2$ 取区间内偶数，这样 $\mathbb{S}_1$ 的 $gcd$ 为 $1$ ， $\mathbb{S}_2$ 的 $gcd$ 为 $2$ ，此时差为0。
• 同理对于区间长度为奇数，我们也可以这样构造，此时差为1。

那么我们只需要判断区间长度是奇数还是偶数即可。

但值得注意的是，这样的代码不能AC，还要考虑区间l=1,r=2的特例，这个肯定是能构造出来的，此时差为1。

代码

#include <bits/stdc++.h>
ll q,l,r;

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	cin >> q;
	while(q--)
	{
		cin >> l >> r;
		if(r==2&&l==1)cout << 0 << endl;
		else if(r==l||r-l==1)cout << -1 << endl;
		else cout << ((r-l+1)%2==0? 0 : 1) << endl;;
	}
	return 0;
}

D

题目大意

给定一个长度为$n$的序列，可以选择其中两个元素分别+1和-1，求所有可能操作后的众数（如果频数都一样，则输出最大那个元素）

样例1

样例输入：

5
1 4 4 4 5

样例输出：

4 5

样例2

样例输入：

4
1 2 3 4

样例输出：

1 2 3 4 5

说明：

如果对1进行+1，对3进行-1，那么序列变为2 2 2 4，众数为2。

如果对2进行+1，对4进行-1，那么序列变为1 3 3 3，众数为3。

以此类推，所有可能的众数为1 2 3 4 5。

思路

本蒟蒻的做题经历

2025-05-30

19:50

起初看到这题时，根本没有头绪，因为 $0 \le n \le 10^5,1 \le a_i \le 10^6$，如果用暴力枚举的话，时间复杂度是 $O(n^2)$ （还不加上每次+1 -1的操作复杂度），肯定会超时。

19:55

看到排行榜上大佬们开E题的通过率高，便转向了E题。

20:25

E题跟着题目思路模拟就行，现在又返回来写D题。先用一个dfs来暴力枚举试试：

#include <bits/stdc++.h>
#define ll long long
const ll MAXN = 1e5+5;
ll n;
vector<ll> a(MAXN),vis(2);
set<ll> s;

ll getans(const vector<ll> &b)
{
    unordered_map<ll,ll> cnt;
    ll m=0, ans=LLONG_MIN;
    for(ll x : b)
    {
        ll c=++cnt[x];
        if (c>m || (c==m&&x>ans))m=c, ans=x;
    }
    return ans;
}

void dfs(ll x, ll y)
{
    if(x==2)
    {
        vector<ll> b(a.begin(), a.begin()+n);
        b[vis[0]]++, b[vis[1]]--;
        // pnt(getans(b));
        s.insert(getans(b));
        return;
    }
    for(int i=0; i<n; i++)
    {
        if(x==1 && i==y) continue;  
        vis[x]=i;
        dfs(x+1, i);
    }
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	cin >> n;
	for(int i=0; i<n; i++)cin >> a[i];
	dfs(0, -1);
	bool f=true;
	for(ll x: s)
	{
		if(!f)cout << " ";
		f=false;
		cout << x;
	}
	
	return 0;
}

很好，显然超时了。

21:05

折腾到现在（比赛结束），还是没想到怎么优化，去各大acm群里找大佬交流后，发现可以用set维护这个数组里的num和cnt两个属性，每次枚举只要维护set即可，这样修改的操作复杂度会大大降低。应该可以卡过。

22:05

服了，才发现这题的时间限制是4s，一直以为是2s，导致不敢去用暴力枚举。但现在想想也对，如果我只用数组来暴力，遍历的时间复杂度是 $O(n^2)$，每次遍历内操作的时间复杂度是 $O(n)$ ，但遍历一次要4次操作，再加一次找到众数的时间复杂度 $O(n)$ ，那么最后时间复杂度为 $O(4n^4)$，显然在4s内是过不了的。

那么还是要转到用set来维护。

那么我们现在的思路就变成了构造一个set，里面存入的元素为{num,cnt},然后重构set的排序方式，使得cnt大的元素排在前面，cnt相同则num大的排在前面。

修改时，先把要修改的元素保存为temp，然后在set中删除该元素，修改后重新插入即可。

遍历时，先按照i j的顺序遍历，并维护set的元素，然后输出set中最前面的元素的num，之后回溯，把temp重新插入set中。

代码

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define endl '\n'
const ll MAXN = 1e5+5;
struct cmp
{
	// 构造cmp函数，使得cnt大的排在前面，cnt相同则num大的排在前面
    bool operator()(const pair<int, int>& a, const pair<int, int>& b) const
    {
        if (a.second!=b.second) return a.second > b.second; 
        return a.first > b.first;
    }
};


ll n;
set<pair<int, int>,cmp> s;
vector<int> a(MAXN);
map<int,int> mp;
set<int> ans;

void add(int x)
{
	int t=mp[x];         // 保存当前元素出现的次数
	s.erase({x,t});      // 删除当前元素
	mp[x]++;             // 当前元素出现次数+1
	s.insert({x,t+1});   // 更新set
}

void del(int x)
{
	int t=mp[x];
	s.erase({x,t});
	mp[x]--;
	if(mp[x]>0)s.insert({x,t-1});
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	cin >> n;
	for(int i=0; i<n; i++)cin >> a[i];
	for(int i=0; i<n; i++)mp[a[i]]++;
	for(int i=0; i<n; i++)s.insert({a[i], mp[a[i]]});
	for(int i=0; i<n; i++)
	{
		for(int j=0; j<n; j++)
		{
			if(i==j)continue;
			del(a[i]), del(a[j]);
			a[i]++, a[j]--;  // 完成题目要求的操作
			add(a[i]), add(a[j]);
			// cout << s <<endl;
			ans.insert(s.begin()->first);
			del(a[i]), del(a[j]);
			a[i]--, a[j]++;
			add(a[i]), add(a[j]);
			// cout << s <<endl;
		}
	}
	for(auto &x : ans)
		cout << x << " ";
	return 0;
}

最后时间复杂度平均在 $O(n^2 \log n)$ 左右，还是挺不错的。

E

题目大意

给定长度为 $n$ 的序列 $a$ ，在 $r$ 次操作后， 序列中所有元素都相等，求 $r$ 的最小值（可以为0）。

• 每次操作遍历 $a$ ，使得 $a_i$ 变为 $\max{(0,a_i-x)}$ ，其中 $x$ 为序列 $a$ 中的元素种类数。

样例1

样例输入：

5
10 0 9 1 10

样例输出：

3

说明：

• 第一轮， $x=4$ ， $a$ 变为 $6 0 5 0 5$ 。
• 第二轮， $x=3$ ， $a$ 变为 $3 0 2 0 3$ 。
• 第三轮， $x=2$ ， $a$ 变为 $0 0 0 0 0$ 。

样例2

样例输入：

5
1 3 6 10 16

样例输出：

5

思路

显然地，在最终 $r$ 次操作后，序列 $a$ 中的所有元素都为 0，而且在“还没出现新的 0”之前，每一轮对剩余正数都减去的值是一致的。

每轮操作前，先把当前数组中到底有多少个不同数值（如果数组里已经有一两个 0，也把“0”算作一类）数一遍，记作 $k$。然后对所有大于 0 的元素一次性减去这个 $k$。这样，如果这一轮中某些正数正好被减到 0，那么下一轮再数不同数值时就会把 0 自动当成一个新类别计入到 $k$ 里。

但是 $n$ 最多到 $10^5$、而且每个 $a_i$ 最多到 $10^{18}$，要是直接每轮都对每个元素模拟减法，肯定会超时。为了避免一轮一轮地走，我们可以先把序列排序并去重，只保留不同的数值。这样原来若干个相同的 $a_i$ 就当作一类看，它们在减法里总是同步被处理，不用反复遍历，每次只看那一类“值”的进度就行了。

接下来，我们给每个去重后的值都加上一个指针 $p$ 和一个累计量 tot：

• p 表示“有多少个去重后最小的值已经被前面累计减到 $\le0$”；
• tot 表示“到目前为止，对每个正数已经减掉的总量”；
• f=false 标记“是否已经出现过真正的 0”。

只要当前去重后的第 $p$ 个值（记作 $s[p]$）满足 $s[p]−\text{tot}≤0$，就说明它已经被累积减成 0，就把 p++，并把标志 f=true（表示已经出现过真正的 0，从下一轮开始 “0” 就要算进 $k$ 里）。否则 $s[p]$ 还在正区间，需要继续减掉 $s[p]−\text{tot}$ 才能变成 0。

假设此时“还在正区间的不同值”一共有 $(m−p)$ 个，如果 f=false （还没出现 0），那么本轮的 $k = m−p$；如果 f=true （已经出现过至少一次 0），那么本轮的 $k = (m−p)+1$。既然在未来连续几轮里，“剩余那 $(m−p)$ 个不同的正数”和“是否出现过 0”都不会变，那它们每轮都会被统一减去同一个 $k$。要让当前最小的那一个 $s[p]$ 从“$\,>\text{tot}$”跳到“$\,\le\text{tot}$”，只要算出

$$\Delta = s[p] - \text{tot}, \quad t = \Bigl\lceil \frac{\Delta}{k} \Bigr\rceil = \frac{\,\Delta + k - 1\,}{\,k\,},$$

就能一次性做 $t$ 轮，把其余都等量减去 $k$。然后再更新r和tot，r+=t, tot+=t*k;

这一些a[p]结束后，新的 tot 会把所有满足 $s[p]-\text{tot} \le 0$ 的去重值一次性变成 0，于是做

while (p < m and s[p] ≤ tot):
    p++       // 这一批都算作已变成 0
    f = true  // 一旦某个去重值真从正数变成 0，就强制把“0”纳入 k

把指针 p 往右推进，此时所有 $\le\text{tot}$ 的都归为0。然后再算新一轮的 $k = (m-p) + (f?1:0)$。

这里对一些a[p]同时操作的思想，类似于“桶排序”的思想，把所有相同的元素都归为一类，然后一起处理。

代码

#include <bits/stdc++.h>
using namespace std;
#define ll long long
int n;
ll tot,p=0,r=0;

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	cin >> n;
	vector<ll> a(n);
	for(int i=0; i<n; i++)cin >> a[i];
	sort(a.begin(), a.end());
    a.erase(unique(a.begin(), a.end()), a.end());
    int m = a.size();
    vector<ll>& s = a;
    bool f=false;
    while(1)
    {
    	int k=(f? 1: 0) + (m-p);
    	if(k<=1)break;
    	if(s[p]<=tot)
    	{
    		f=true;
    		p++;
    		continue;
    	}
    	ll nn=s[p]-tot;
    	ll t=(nn + k -1)/k;
    	r+=t, tot+=t*k;
    	while(p<m && s[p]<=tot)f=true,p++;
    }
    cout << r << endl;

	return 0;
}

F

这题本蒟蒻没在比赛时做出来😭

题目大意