2024 National Invitational of CCPC (Zhengzhou), 2024 CCPC Henan Provincial Collegiate Programming Contest

2024 年中国大学生程序设计竞赛全国邀请赛（郑州）暨第六届 CCPC 河南省大学生程序设计竞赛

比赛链接

这场的题说实话难度其实都不大（除了 E E E 和 I I I），但是做法很固定，考思维，想到了一拍脑袋就出，想不到就寄，因此很多强队都翻车了。这场 13 13 13 题其中的 11 11 11 题我觉得都可以赛时出。

是时候祭出这张图了：

Problem A. Once In My Life

题意：

对于小 A A A 而言，数位包含 1 ∼ 9 1 ∼ 9 1∼9，并且至少两个数位是 d （ 1 ≤ d ≤ 9 ） d（1 ≤ d ≤ 9） d（1≤d≤9）的十进制正整数都是幸运数。

当 d = 3 d = 3 d=3 时，显然 1234567890123 1234567890123 1234567890123 是小 A A A 的幸运数，但 987654321 987654321 987654321 因为数位 3 3 3 仅出现了一次而不是幸运数， 998244353 998244353 998244353 因为缺少数位 1 , 6 , 7 1, 6, 7 1,6,7 而不是幸运数。

现在小 A A A 有一个正整数 n n n，并给出正整数 d d d。他想找到正整数 k k k 使得二者的乘积 n ⋅ k n · k n⋅k 是幸运数。

你能用计算机辅助他的计算吗？

输出保证 k ≤ 2 ∗ 1 0 10 k\le 2*10^{10} k≤2∗1010

思路：

本质是个构造题，需要一点点数论知识。

我们想要 n k nk nk 得到的数里有 123456789 123456789 123456789 和额外的一个 d d d，那么我们就构造出来，假设结果是 123456789 d 123456789d 123456789d，构造得到的数不一定是 n n n 的倍数，但是我们可以加一些数让它成为倍数，不过这就破坏了这十个位置上的数字。

考虑到当 k k k 乘以 10 10 10 的时候， 123456789 d 123456789d 123456789d 也会乘以 10 10 10，相当于整体向左移动一位，低位就空出来了，这时我们给低位增加一些数字的时候，就不会影响到高处的十个位置了。最简单的想法就是反正 n ≤ 1 0 8 n\le10^8 n≤108，所以我们只要低八位空出来就行了，这时就会得到 123456789 d 00000000   m o d   n = x 123456789d00000000\bmod n=x 123456789d00000000modn=x，我们再加上 ( n − x )   m o d   n (n-x)\bmod n (n−x)modn 就是乘积，除以 n n n 就是 k k k 了。

不过题目要求 k ≤ 2 ∗ 1 0 10 k\le 2*10^{10} k≤2∗1010，当 n ≤ 1 0 7 n\le 10^7 n≤107 时，上面构造出来的数铁定 > 2 ∗ 1 0 10 \gt 2*10^{10} >2∗1010。考虑到我们没必要低位留 8 8 8 位，比如 n n n 只有一位数的时候，我们低位就只留一位就行了，如果 n n n 是 t t t 位数，那么我们低位就只留 t t t 位就可以了，这样构造出来的数 k k k 就是一个小于 2 ∗ 1 0 10 + t − 1 2*10^{10+t-1} 2∗1010+t−1 的数，除以一个大于 1 0 t − 1 10^{t-1} 10t−1 的数，得到的数肯定小于 2 ∗ 1 0 10 2*10^{10} 2∗1010。

code：

#include 
#include 
using namespace std;
typedef long long ll;
int T;
ll n,d;
ll pw[20];
int main(){
	cin.tie(0)->sync_with_stdio(false);
	
	pw[0]=1;
	for(int i=1;i<=18;i++)pw[i]=pw[i-1]*10;
	
	cin>>T;
	while(T--){
		cin>>n>>d;
		int i=0;
		while(pw[i] 
 
Problem B. 扫雷 1
 
题意：
 
T0xel 喜欢玩扫雷，但是他玩的扫雷游戏有名为 “地雷探测器” 的特殊道具。
 
具体来说，T0xel 会进行  
     
      
       
       
         n 
        
       
      
        n 
       
      
    n 轮扫雷。每轮扫雷开始之前，T0xel 会获得  
     
      
       
       
         1 
        
       
      
        1 
       
      
    1 枚扫雷币。扫雷币在每轮扫雷结束后不会回收，可以保留至下一轮扫雷。T0xel 知道，在第  
     
      
       
       
         i 
        
       
      
        i 
       
      
    i 轮 
     
      
       
       
         （ 
        
       
         1 
        
       
         ≤ 
        
       
         i 
        
       
         ≤ 
        
       
         n 
        
       
         ） 
        
       
      
        （1 ≤ i ≤ n） 
       
      
    （1≤i≤n）扫雷中，花费  
     
      
       
        
        
          c 
         
        
          i 
         
        
       
      
        c_i 
       
      
    ci​ 枚扫雷币可以购买一个地雷探测器，清除地图中的一个雷。地雷探测器在一轮扫雷中可以购买任意次。
 
现在 T0xel 想知道，在这  
     
      
       
       
         n 
        
       
      
        n 
       
      
    n 轮扫雷中最多能购买多少个地雷探测器呢？
 
思路：
 
签到，是个贪心。因为我们在一轮中某个探测器可以买任意次，所以如果后面的轮中如果有一个很便宜的探测器，那么我们直接留着钱只买这个就行了，能买多少就买多少。如果后面有一个稍贵的探测器，因为我们不能买前面轮次的探测器，所以我们也有可能买这个探测器。
 
这种如果有一个  
     
      
       
       
         o 
        
       
         i 
        
       
      
        oi 
       
      
    oi 比你强还比你年轻（这个题里就是探测器既便宜又靠后），那么你就没用了的思想，就很单调栈。所以用一个单调栈模拟一下，然后从前到后贪心买探测器即可。
 
或者可以按探测器价格排序，然后按顺序枚举，升序地选择购买探测器
 
如果把  
     
      
       
       
         ( 
        
       
         i 
        
       
         , 
        
        
        
          c 
         
        
          i 
         
        
       
         ) 
        
       
      
        (i,c_i) 
       
      
    (i,ci​) 看成一个点，其实相当于一个下凸壳，所以求下凸壳的思想也可以做。
 
code1：
 
单调栈
 
#include 
#include 
#include 
#define pii pair
using namespace std;
int n;
vector sta;
int main(){
	cin>>n;
	for(int i=1,c;i<=n;i++){
		cin>>c;
		while(!sta.empty() && sta.back().first>=c)sta.pop_back();
		sta.push_back({c,i});
	}
	int p=0,rm=0,ans=0;
	for(auto [c,i]:sta){
		rm+=i-p;
		p=i;
		ans+=rm/c;
		rm-=rm/c*c;
	}
	cout< 
code2：
 
队友赛时代码，排序后升序选点。
 
#include
using namespace std;
int a[200005];
typedef pair PII;
int main(){
	int n;
	cin>>n;
	vector pos;
	for(int i = 1;i<=n;i++){
		cin>>a[i];
		pos.push_back({a[i],i});
	}
	sort(pos.begin(),pos.end());
	int p = 1;
	int ans = 0;
	int was = 0;
	for(PII pii : pos){
		if(pii.second < p) continue;
		int le = pii.second - was;
		int t = le/pii.first;
		ans += t;
		was += t * pii.first;
		p = pii.second;
	}
	cout< 
 
Problem C. 中二病也要打比赛
 
题意：
 
在被中二病彻底占领的世界中，存在着一个被称为 “现实” 的神秘领域。在这个领域中，小鸟游六花，一位坚信自己拥有着非凡力量的中二病少女，发现了一串神秘的数字序列  
     
      
       
       
         A 
        
       
      
        A 
       
      
    A。这个序列包含了  
     
      
       
       
         n 
        
       
      
        n 
       
      
    n 个元素，每个元素  
     
      
       
        
        
          A 
         
        
          i 
         
        
       
      
        A_i 
       
      
    Ai​ 是  
     
      
       
       
         1 
        
       
      
        1 
       
      
    1 到  
     
      
       
       
         n 
        
       
      
        n 
       
      
    n 之间的整数。据说，只有当这个序列满足单调不降的性质时，隐藏在其中的超自然力量才会觉醒。
 
六花相信，通过解开这个序列的秘密，她可以进一步证明自己的 “邪王真眼” 的力量。然而，她很快就意识到，要驯服这个序列，需要一种特殊的魔法——一个能将  
     
      
       
       
         A 
        
       
      
        A 
       
      
    A 转化为另一个序列的函数  
     
      
       
       
         f 
        
       
      
        f 
       
      
    f，其定义域与值域均为  
     
      
       
       
         [ 
        
       
         1 
        
       
         , 
        
       
         n 
        
       
         ] 
        
       
         ∩ 
        
       
         Z 
        
       
      
        [1, n] ∩ Z 
       
      
    [1,n]∩Z。使用这个魔法后， 
     
      
       
       
         A 
        
       
      
        A 
       
      
    A 会变成  
     
      
       
       
         B 
        
       
      
        B 
       
      
    B，其中  
     
      
       
        
        
          B 
         
        
          i 
         
        
       
         = 
        
       
         f 
        
       
         ( 
        
        
        
          A 
         
        
          i 
         
        
       
         ) 
        
       
      
        B_i = f(A_i) 
       
      
    Bi​=f(Ai​)。但是，这个魔法的使用是有代价的，其成本由  
     
      
       
       
         [ 
        
       
         1 
        
       
         , 
        
       
         n 
        
       
         ] 
        
       
         ∩ 
        
       
         Z 
        
       
      
        [1, n] ∩ Z 
       
      
    [1,n]∩Z 中  
     
      
       
       
         f 
        
       
         ( 
        
       
         x 
        
       
         ) 
        
       
         ≠ 
        
       
         x 
        
       
      
        f(x) \not= x 
       
      
    f(x)=x 的  
     
      
       
       
         x 
        
       
      
        x 
       
      
    x 数量决定。在这个充斥着中二病的世界中，六花必须以最小的代价激发序列中隐藏的力量。
 
现在，作为六花的冒险伙伴，你的任务是帮助她找到那个神奇的函数  
     
      
       
       
         f 
        
       
      
        f 
       
      
    f，将  
     
      
       
       
         A 
        
       
      
        A 
       
      
    A 转化为单调不降序列，并以最小的代价揭示序列中隐藏的超自然力量。
 
思路：
 
我们队出的最后一题，赛时我想到了前半缩点部分，猜测后边做法可能是个带懒节点的线段树优化  
     
      
       
       
         d 
        
       
         p 
        
       
      
        dp 
       
      
    dp（不过并不是），因为时间不太够了，简单讲完后我直接上手写了（写了个缩点部分和带懒节点线段树），之后队友讨论出了后半做法是个最长上升子序列，接着我的部分写完，一遍  
     
      
       
       
         A 
        
       
         C 
        
       
      
        AC 
       
      
    AC，这就是我们热血沸腾的组合技啊！
 
10
1 10 2 6 10 8 9 6 4 5
 
比如上面的一个样例，我们可以发现被两个  
     
      
       
       
         10 
        
       
      
        10 
       
      
    10 包含起来的这段区间一定只能同时等于一个值， 
     
      
       
       
         10 
        
       
      
        10 
       
      
    10 的区间内部有一个  
     
      
       
       
         6 
        
       
      
        6 
       
      
    6，而外部也有一个  
     
      
       
       
         6 
        
       
      
        6 
       
      
    6，因为内部的  
     
      
       
       
         6 
        
       
      
        6 
       
      
    6 被固定住了，那么外部的  
     
      
       
       
         6 
        
       
      
        6 
       
      
    6 也会随之固定，这两个  
     
      
       
       
         6 
        
       
      
        6 
       
      
    6 之间的部分也被迫同时等于  
     
      
       
       
         10 
        
       
      
        10 
       
      
    10 包含区间的值，同理其他数。
 
既然它们都等于一个值，那么我们就可以把它们看成一个点或者一个块。一个块内所有数都会转化成一个相同的数。我们上面缩块的过程就保证了一种数字只有可能出现在一个块内，否则的话，两个块肯定在缩块的时候就被缩在一起了。因此对序列  
     
      
       
       
         A 
        
       
      
        A 
       
      
    A 中出现过的某种数字  
     
      
       
       
         x 
        
       
      
        x 
       
      
    x，它在且仅在一个块内。
 
不难发现，如果一个块内出现了  
     
      
       
       
         s 
        
       
         z 
        
       
      
        sz 
       
      
    sz 个不同的数，那么如果这个块等于块内含有的某个值，代价是  
     
      
       
       
         s 
        
       
         z 
        
       
         − 
        
       
         1 
        
       
      
        sz-1 
       
      
    sz−1，否则如果变成块内没有出现过的其他值的话，代价就是  
     
      
       
       
         s 
        
       
         z 
        
       
      
        sz 
       
      
    sz。因为上面推出过每种出现过的数在且仅在一个块内的结论，因此若原本出现过  
     
      
       
       
         t 
        
       
         o 
        
       
         t 
        
       
      
        tot 
       
      
    tot 种数，那么所有块的  
     
      
       
       
         s 
        
       
         z 
        
       
      
        sz 
       
      
    sz 之和就是  
     
      
       
       
         t 
        
       
         o 
        
       
         t 
        
       
      
        tot 
       
      
    tot，也就是  
     
      
       
       
         ∑ 
        
       
         s 
        
       
         z 
        
       
         = 
        
       
         t 
        
       
         o 
        
       
         t 
        
       
      
        \sum sz=tot 
       
      
    ∑sz=tot。假设有  
     
      
       
       
         t 
        
       
      
        t 
       
      
    t 个块选择等于块内含有的某个值，这时候代价就是  
     
      
       
       
         t 
        
       
         o 
        
       
         t 
        
       
         − 
        
       
         t 
        
       
      
        tot-t 
       
      
    tot−t。我们求最小代价，就是求最多能有几个块可以选择等于块内含有的某个值。
 
这样问题就转化为了：若干个位置上，每个位置上可以取一些值的一个，求最长上升子序列长度。
 
code：
 
#include 
#include 
#include