牛客小白月赛107题解

A.Cidoai的吃饭

Cidoai 喜欢吃饭。
它的饭卡中一开始有 $n$ 元钱。假设某次吃饭前，它的饭卡中剩下 $x$ 元钱，则他会做出如下选择：
1. 若 $x \ge a$ ，花费 $a$ 元购买套餐一；
2. 若不满足条件 1 且 $x \ge b$ ，花费 $b$ 元购买套餐二；
3. 若不满足条件 1、2 且 $x \ge c$ ，花费 $c$ 元购买套餐三；
4. 若上述三个条件都不满足，则吃不了饭。
给定 $n,a,b,c$ ，请问 Cidoai 一共能吃几顿饭。

没什么好说的，签个到即可


// C++

void solve(){
    int n;
    cin >> n;
    int ans = 0;
    ans += n / a;n %= a;
    ans += n / b;n %= b;
    ans += n / c;n %= c;
    cout << ans << endl;
}

B.Cidoai的听歌

Cidoai 喜欢听歌。
它拿到了一个长为 $n$ 的数列 $a_1,a_2,\cdots,a_n$ 。Cidoai 会循环进行以下两种操作，从操作 1 开始：
1. 选择数列中任意多个数+1;
2. 选择数列中任意多个数-1。单次操作中必须选择不同位置的数。它都希望使用最少的操作次数使得整个数列都相等，求最少的操作次数，以及整个数列最后等于的数
可以证明，在最少操作次数的时候，整个数列最后等于的数唯一。

我们设 $a_n$ 中的最大值为 $maxa$ 最小值为 $mina$ ,数组经过所有操作后所有元素都变成 $target$

很显然为了通过操作变成 $target$ ,数组中的所有其他元素需要的操作数都小于最大值与最小值需要的操作数

所以我们只需要在最短的操作里让最大值和最小值逼近同一个 $target$ 即可,其余元素会在这个过程中顺带地变成 $target$

显然需要的操作数 $q=maxa-mina$ ,而因为两种操作循环进行，且首先进行操作一，所以要么两种操作的次数一样，要么操作一比操作二多一次，所以最终结果 $target$ 为 $maxa$ 和 $mina$ 的平均数向上取整

q = maxa - mina ;target = \lceil {\frac {maxa mina}{2}}\rceil

// C++

void solve(){
    int n;
    cin >> n;
    int maxa = 0 , mina = INF;
    for(int i = 0 , a;i < n;i ++){
        cin >> a;
        maxa = max(maxa , a);
        mina = min(mina , a);
    }
    cout << maxa - mina << " " << ceil((maxa + mina) / 2) << endl;
}

C.Cidoai的植物

Cidoai 喜欢植物。
Cidoai 有一个 $n$ 行 $m$ 列的花园，这个花园初始没有植物，它会对这个花园做 $k$ 次如下操作之一：
1. 选择第 $i$ 列，在这一列上没有植物的位置上全部种下植物 $x$ ;
2. 选择第 $a$ 行第 $b$ 列，如果这个位置有植物，则铲除这株植物，否则不进行操作。现在它给了你 $n,m$ 以及它的操作序列，它想知道操作完后花园的状态。由于输入量过大，操作数列不会被直接输入，而是由参数生成，如下：

# Python代码略

rnd 函数的 C++ 代码如下：

unsigned seed;
unsigned rnd(){
	unsigned ret=seed;
	seed^=seed<<13;
	seed^=seed>>17;
	seed^=seed<<5;
	return ret;
}

由于输出量过大，你不需要输出整个花园的状态，只需要输出如下值即可： $\bigoplus \limits_{i=1}^{n}\bigoplus \limits_{j=1}^{m} p_{i,j} \times ((i-1)\times m j)$ 。其中 $p_{i,j}$ 表示花园中第 $i$ 行第 $j$ 列的植物编号，若该位置没有植物，则编号为 $0$ 。这个式子表示枚举所有 $i=1,2,\cdots,n,j=1,2,\cdots,m$ ，求得所有 $p_{i,j} \times ((i-1)\times m j)$ 值后将其异或起来。

题目有点长,但题意很简单,只是一个对 $n$ 行 $m$ 列的花园的操作问题,理解到位就很简单,关键在于优化

题目的数据规模达到了 $1e11$ ,很显然暴力修改是行不通的。我们进一步分析,发现题目的复杂度主要来源于对每次操作一都进行暴力遍历加修改,而行数 $n$ 和操作数 $k$ 都很大。考虑到对半满的列我们只需要用操作一进行局部修改,所以主要考虑如何缩短局部修改中找点的过程,总结下来思路如下:

对于每一列的第一次 $op1$ ,因为每一个点位都需要填补,我们暴力修改这一列的每一个值
对于每一列的后续 $op1$ ,因为需要修改的点位都是通过 $op2$ 挖空后得到的,我们考虑在每次 $op2$ 时维护挖空的位置
对于每一次 $op2$ ,我们维护一个 $set$ 来保存挖空的位置,这样此后的 $op1$ 就只需要遍历 $set$ 就能快速找到挖空的位置并修改,我们只要维护出 $m$ 个 $set$ 就能存储每一列挖空的位置了

// C++

#define int long long //题目需要开long long

// 种子的获取方法直接复制即可
unsigned seed;
unsigned rnd(){
	unsigned ret=seed;
	seed^=seed<<13;
	seed^=seed>>17;
	seed^=seed<<5;
	return ret;
}

void solve(){
    int n , m , k;
    cin >> n >> m >> k >> seed;
    vector<vector<int>> g(n + 1 , vector<int>(m + 1 , 0));// 存储花园信息,每一个点位初始都是0;
    vector<set<int>> st(m + 1);// 维护每一列挖空的位置
    vector<int> flag(m + 1 , 1);// 标记每一列是否全空
    for(int i = 1;i <= k;i ++){
        int op = (rnd() % 2) + 1;// 获取op编号
        if(op == 1){
            int l = (rnd() % m) + 1;
            int x = (rnd() % (n * m)) + 1;
            // 全空,暴力修改整列
            if(flag[l]){
                for(int j = 1;j <= n;j ++) g[j][l] = x;
                flag[l] = 0;
                continue;
            }
            // 遍历该列的set,快速修改挖空的点位
            for(int j : st[l]){
                g[j][l] = x;
            }
            st[l].clear();// 及时清空
        }
        if(op == 2){
            int a = (rnd() % n) + 1;
            int b = (rnd() % m) + 1;
            if(g[a][b] != 0){
                g[a][b] = 0;
                st[b].insert(a);// 记录挖空的位置
            }
        }
    }
    int ans = 0;// 记录答案
    for(int i = 1;i <= n;i ++){
        for(int j = 1;j <= m;j ++){
            ans ^= g[i][j] * ((i - 1) * m + j);
        }
    }
    cout << ans << endl;
}

D.Cidoar的猫猫

Cidoai 喜欢猫猫。
它有一个长度 $n$ 的仅由小写字符构成的字符串 $s$ ，每个字符代表一只猫猫的品种。它想要合并一些长为 $k$ 的子串，从而得到一个新的字符串 $t$ 。
我们记 $t_{[i,j]}$ 表示由字符串 $t$ 中第 $i$ 位到第 $j$ 位的字符构成的子串。
字符串 $s$ 一共有 $n-k 1$ 个长为 $k$ 的子串，按照左端点从左往右的顺序分别记为 $p_1,p_2,\cdots,p_{n-k 1}$ 。使得存在一个非负整数序列 $a$ 同时满足如下三个条件：

$a_1=0$ 。

$\forall i \in [1,n-k],0 \le a_{i 1}-a_i \le 1$ ；

$\forall i \in [1,n-k 1],p_{i}=t_{[i-a_i,i k-1-a_i]}$ ；设对于 $k$ 生成的 $t$ 的最短长度为 $l_k$ 。
举例而言：对于字符串 $s=\text{aabbbaaa}$ 以及 $k=2$ 的情况。 $p_1=\text{aa},p_2=\text{ab},p_3=\text{bb},p_4=\text{bb},p_5=\text{ba},p_6=\text{aa},p_7=\text{aa}$ 。
最短的满足条件的字符串 $t$ 为 $\text{aabbaa}$ ，对应的 $a=\{0,0,0,1,1,1,2\}$ 。
由于 Cidoai 想要尝试不同的可能性，它想让你求出对于 $k=1,2,\cdots,n$ 的 $l_k$ 。为了避免输出量过大，它只需要你输出 $(1 \times l_1)\oplus(2 \times l_2) \oplus \cdots \oplus (n \times l_n)$ 。

题目信息写的太屎了,申请中译中

首先明确:

$s$ 是主串, $t$ 是压缩后最短的新串
$p_i$ 是主串 $s$ 中左端点为 $i$ 的长度为 $k$ 的子串
$t_{[i,j]}$ 是新串的子串
$a_i$ 表示主串 $s$ 的 $p_i$ 往前跳 $a_i$ 个索引后可以在新串 $t$ 的对应位置找到完全相同的子串,相邻的 $a_i$ 至多加1

很显然对任何一个字符串 $s$ ,构造一个序列 $a$ 使每个 $a_i$ 都是0一定是合法的,但这样会使得 $t=s$ ,不够短观察题目的例子: alt $a_n$ 是一个单调不减的序列,从 $a$ 的最前面开始观察:

$a_1=0$ ,这是题目规定的
$a_2=a_3=0$ ,这是由于对 $s$ 每一个的 $p_i$ ,往前推一位都找不到相同的子串,在这之前的内容无法被压缩,只能在 $t$ 中完整地保留下来
到 $a_4$ 开始发生变化,注意到 $p_4$ 和 $p_3$ 是完全相等的,并且在新串的前一个索引里已经记录了下来,即 $p_3=p_4$ 而 $p_4=t_{[4-1,5-1]}$ 这时便可以令 $a$ 加一,做出类似于将 $p_3$ 和 $p_4$ 合并的操作,这样就成功压缩掉了一个字符
$a_5=a_4=1$ 虽然主串中的 $p_5$ 和 $p_4$ 并不相同,但是因为在此之前已经压缩掉了一个字符,所以依然满足 $p_5=t_{[5-1,6-1]}$ ,即在新串中依然找得到对应位置的和 $p_5$ 相同的子串
到了 $a_7$ 再次发生变化,观察到 $p_7=p_6$ ,按照之前的逻辑可以再往前压缩一位了,而仍然由于在此之前已经压掉了一个字符,所以 $p_7$ 需要往前移动两个位置才能在新串中找到对应,再次将 $p_6$ 和 $p_7$ 合并,压掉第二个字符,压缩操作结束

经过压缩,我们通过压缩相同子串的方式压掉了两个字符,得到了图中所示的新串,主串和新串中对应的字符用相同颜色的下划线标出

分析压缩过程,我们不难发现, $a_i$ 是对于主串 $s$ 而言的,表示主串 $s$ 在 $i$ 这个位置之前最多可以压缩掉的字符数量,而压缩的原则是:对于 $p_i=p_{i 1}$ ,将其合并,即合并主串 $s$ 中连续相同字符构成的子串,使其长度不超过k

那么我们要做的就很简单了:对于每一个 $k$ ,将 $s$ 中长度超过 $k$ 的连续相同字符的长度变成 $k$ ,计算最后得到的长度即可;

// C++

void solve(){
    int n;
    cin >> n;
    string s;
    cin >> s;
    unordered_map<int , int> len;// 字典记录相同字符构成的字符块的长度出现的次数(普通的map会TLE)

    // 处理字符串s中的字符块
    int cnt = 1;
    int same = 0;
    int maxl = 0;
    for(int i = 1;i < n;i ++){
        if(s[i] == cur){
            cnt ++;
        }
        else{
            same ++;
            len[cnt]++;
            cur = s[i];
            maxl = max(cnt , maxl);
            cnt = 1;
        }
    }
    same ++;
    len[cnt] ++;
    maxl = max(cnt , maxl);// 记录最后一个字符块
    int ans = 0;
    int low = 0;
    int lowl = 0;// 存储不比k长的字符块的数量和总长度
    int k;
    for(k = 1;k < maxl;k ++){
        low += len[k];
        lowl += k * len[k];// 记录k的数量和长度,k增加后自动成为不比k长的字符块的数量和总长度
        int res = lowl;
        res += (same - low) * k;// 比k长的全压到k
        ans ^= res * k;
    }
    // 无法压缩,直接算,规避字典的查找效率问题
    for(;k <= n;k++){
        ans ^= n * k
    }
    cout << ans << endl;
}

E.Cidoai的可乐

Cidoai 喜欢可乐。
它有 $n$ 个点，每个点都有点权 $a_i$ 和一个度数限制 $d_i$ 。它想将它们连成一棵树，其中一条边的边权为它的两个端点的点权较小值。它希望这棵树中，所有点的度数都不大于度数限制，且边权和最小。你需要输出这个边权和。

为了让边权和最小,由题意可知,我们需要让点权小的节点去连尽可能多的边,而由于一棵树至多可以连 $n - 1$ 条边,所以把点权小的边连完之后剩余的节点可以直接作为叶子节点 alt 这应该是后面最简单的题,只要你别把度数看成深度就可以秒杀

// C++

struct Node{
    int value , d;
};
bool cmp(Node a , Node b){
    return a.value < b.value;
}
void solve(){
    int n;
    cin >> n;
    vector<Node> a(n);
    for(int i = 0;i < n;i ++) cin >> a[i].value;
    for(int i = 0;i < n;i ++) cin >> a[i].d;
    sort(a.begin() , a.end() , cmp);
    int ans = 0 , cnt = n - 1;// cnt表示剩下可以连的边数
    for(int i = 0;i < n;i ++){
        int temp = min(cnt , a[i].d);// 能连满尽量连满
        ans += temp * a[i].value;// 最小的节点引出的边的边权一定是该节点的点权
        cnt -= temp;// 更新剩余边数
    }
    cout << ans << endl;
}

F.Cidoai的自恋

Cidoai 喜欢小 C。
它某天和小 C 在玩一个游戏。小 C 需要猜一个在 $[1,n]$ 之间的数，它会先给小 C 一个长度为 $k$ 的询问列表 $a_1,a_2,\cdots,a_k$ ，Cidoai 会根据答案 $x$ 对列表上的每个数给出大于答案、小于答案或是等于答案的回答。
小 C 认为一次无效询问是：如果存在一个 $i<j$ 满足 $a_i<x$ 且 $a_j \le a_i$ 或满足 $a_i>x$ 且 $a_j \ge a_i$ ，则询问 $a_j$ 是一次无效询问。
Cidoai 想要捉弄一下小 C，因此它会根据询问列表确定答案 $x$ ，满足它不在小 C 的询问列表中且无效的询问次数最多，如果有多个满足条件的数，输出最小的那个。 Cidoai 保证，对于题目所给的所有数据，不存在无解的情况。由于输入量过大， $a$ 数列不会被直接输入，而是由参数生成，伪代码如下：

# Python代码略

其中 $seed$ 由输入给定。 rnd 函数的 C++ 代码如下：

unsigned seed;
unsigned rnd(){
	unsigned ret=seed;
	seed^=seed<<13;
	seed^=seed>>17;
	seed^=seed<<5;
	return ret;
}

为了让无效询问次数最多,我们就需要让有效询问次数最少,那么根据原题意,不难发现有效询问的条件其实就是真正的猜数游戏进行到某一次询问后有必要的询问即可以通过这次询问使答案的区间有效地逼近x

由题意可知：若存在 $i \neq j$ 且 $a_i = a_j$ ，即存在两次相同的询问，那么不管答案x是多少，后出现的那一次询问必定是一次无效的询问

那我们可以筛除所有的重复询问，再对 $a$ 进行研究

我们先研究向上逼近的情况，即对于某个x，把大于x的询问都筛掉，绘制一个散点图表示每一次询问 alt 很显然红线连接了所有的有效询问结论为：对于向上逼近的每一个凹函数段，有效询问一定出现在凹函数段的两端，这一点结合实际不难理解

对于向上逼近中的一次询问 $a_j$ (我们假设他是有效的)，一旦出现了一个 $i<j$ 使 $a_i>a_j$ ,那么 $a_j$ 立马就会变成一次无效询问,即对于两次询问,其数值的单调性与时序的单调性不一致,那便要保留最早出现的最大的询问,弹出所有晚出现的较小的询问,这符合单调栈的特性

我们构造一个数组pos[n]表示 $1$ ~ $n$ 的所有数在询问列表中第一次出现的位置,这样构造后便天然形成了一个去重之后的询问列表

对于一个答案x,对其向上逼近的有效询问一定分布在 $1$ 到 $x$ 之间。那么我们可以从1到n枚举x,构造一个单调栈 $pre$ ,将pos[x]入栈,根据单调栈的操作,若栈顶元素大于pos[x](即比x小的询问出现在了x之后,不符合我们需要的单调性),我们便弹出所有大于pos[x]的元素后令pos[x]入栈,这样就时刻维护出了一个上界为x的最长有效向上逼近询问序列,栈内元素的数量便是答案为x时有效上升询问的数量

对于向下逼近,我们可以用同样的方法维护出一个单调性相反的单调栈,维护每一个x对应的有效上升询问和有效下降询问的数量,找出其中的最小和即可,此时的x就是答案

注意Cidoai很坏,所以x不能是询问列表里面的数

// C++

// 随机数生成方法
unsigned seed;
unsigned rnd(){
	unsigned ret=seed;
	seed^=seed<<13;
	seed^=seed>>17;
	seed^=seed<<5;
	return ret;
}
void solve(){
    int n , k;
    cin >> n >> k >> seed;
    vector<int> pos(n + 1 , 0);// 构造数组记录每一个数在询问列表中第一次出现的位置(没出现标记为0)
    for(int i = 1;i <= k;i ++){
        int a = rnd() % n + 1;
        if(!pos[a]) pos[a] = i;// 记录第一次出现的位置,天然去重
    }
    vector<int> op(n + 1 , 0);// 存储每一个x对应的有效询问的数量
    stack<int> pre;// 构造一个向上逼近的单调栈
    // 遍历每一个可能的x
    for(int i = 1;i <= n;i ++){
        // 只需要对没有在询问列表中出现过的元素统计有效询问数量
        if(pos[i]){
            // 不满足单调性,将所有破坏单调性的元素弹出
            while(!pre.empty() && pre.top() > pos[i]){
                pre.pop();
            }
            // 当前元素入栈
            pre.push(pos[i]);
        }
        else op[i] += pre.size();// 记录x对应的向上逼近有效询问的数量
    }
    stack<int> suf;// 构造一个向下逼近的单调栈
    int minl = INF;// 记录有效询问的最小值
    int ans;// 记录最小值对应的x
    // 向下枚举x,其余操作同理
    for(int i = n;i >= 1;i --){
        // 只需要对没有在询问列表中出现过的元素统计有效询问数量
        if(pos[i]){
            // 将破坏单调性的元素弹出
            while(!suf.empty() && suf.top() > pos[i]){
                suf.pop();
            }
            // 当前元素入栈
            suf.push(pos[i]);
        }
        else{
            op[i] += suf.size();// 加上向下逼近有效询问的数量得到有效询问的总数量
            // 更新最少的有效询问数量和对应的x,注意当有效询问一样少时去最小的x,所有使用大于等于
            if(minl >= op[i] && op[i] != 0){
                minl = min(minl , op[i]);
                ans = i;
            }
        }
    }
    // 输出答案
    cout << ans << endl; 
}

总结

这次小白月赛题目出得很变态,有大量冗长晦涩的表述,但拆解每一道题的内核之后会发现每一道题的思想都很简单

A题B题签到题没什么好说

C题的题目一大半都是一个不需要我们来思考的随机数生成方法,把这一点看懂可以很大程度上方便我们对F题的理解。C题的重点在于时间,暴力修改和所谓延迟修改都无法达到题目的复杂度要求,这考验我们的思考能力,能想到缩短反复执行操作一的搜索过程

D题题目初见端倪,如此长的表述背后包含的只有把大于k的重复子序列压成k这一个目标,其他的重点也在于时间, $5e6$ 的数据规模要求我们必须找到一个线性复杂度的解法,这里用vector和umap都可以

E题非常简单,不用多说

F题更是重量级,集C题的废话表述和D题的变态表述于一体,背后藏得也是一个很符合常识的猜数游戏过程,考验我们的思维能力和阅读能力

~~对题目的评价有点尖锐，出题人不要打我（）~~

题解 | 小白月赛107悲愤补题后写的题解