Znzryb's Blog
0%

Posted on Edited on

题目大意

题目要求总结：

给定多组测试。每组有 n 个任务，必须按编号从 1 到 n 依次处理。你初始体力为 S=1。

对每个任务 i（参数为 c_i, p_i）只有两种选择：

  • 放弃：本任务得分不变，体力不变。

  • 完成：本任务获得 S * c_i 分，然后体力变为S = S * (1 - p_i / 100)。

目标是在处理完所有任务后，使总得分最大。

输入规模：多组数据，sum(n) <= 1e5。

输出要求：每组输出一个实数最大值，误差满足 1e-6 即可。

样例：

1
2
3
4
5
6
7
8
9
10
11
12
13
Input
2
2
10 0
20 5
3
10 5
10 80
20 5

Output
30.0000000000
29.0000000000

样例解释：

  • 第 1 组：做第 1、2 个任务最优。
    第 1 个得 1*10=10，且 p=0 体力不变；第 2 个得 1*20=20；总分 30。

  • 第 2 组：最优是做第 1 个，放弃第 2 个，做第 3 个。
    做完第 1 个后体力 S=1*(1-5/100)=0.95；第 3 个得 0.95*20=19；总分 10+19=29。

思路讲解

这道题目，就是主要要注意到，就是我们不难发现，最后一个数，我们肯定是要选的，因为最后一个数对整体的贡献一定是有的，一定是正的。或者，你可以这样想，我们前面先选了一堆数，那么最后一个数一定是要选的，因为选择他，对你的答案一定是增加的，你也不用考虑后续节点的情况，因为他后面也没有东西了。

我们说白了，选不选一个数，我们就是怕这个后效性嘛，我们直接反过来，直接对所有选择的后缀进行这个乘法衰减。

但是，再前面的数字，那就不一定了，其对整体的贡献，就是新的答案 ans*(100-p)/100.0+A[i].c，如果说比原来的 ans 还小，那就开摆，否则就算了。

1
2
3
4
5
6
for (ll i=N;i>=1;--i) {
    ll c=A[i].c,p=A[i].p;
    if (ans*(100-p)/100.0+A[i].c>ans) {
        ans=ans*(100-p)/100.0+A[i].c;
    }
}

AC代码

AC

https://codeforces.com/contest/2208/submission/366718643

心路历程（WA，TLE，MLE……）

Posted on Edited on

题目大意

题目描述
定义集合 SS 的 kk-mex 为未在 SS 中出现的第 kk 小的非负整数。例如，集合 [1,2,1][1, 2, 1] 的 11-mex 是 00，22-mex 是 33。

给定一个长度为 nn 的非负整数数组 a1,a2,…,ana_1, a_2, \ldots, a_n。你需要判断是否存在一个非负整数数组 b1,b2,…,bnb_1, b_2, \ldots, b_n（其中 0≤bi≤1090 \le b_i \le 10^9），使得对于所有 1≤i≤n1 \le i \le n，前缀 [b1,…,bi][b_1, \ldots, b_i] 的 (n−i+1)(n-i+1)-mex 恰好等于 aia_i。

如果存在这样的数组，请构造并输出任意一个满足条件的数组 bb；如果不存在，请报告无解。

输入格式
第一行包含一个整数 tt（1≤t≤1041 \le t \le 10^4），表示测试用例的数量。
每个测试用例的第一行包含一个整数 nn（1≤n≤2⋅1051 \le n \le 2 \cdot 10^5），表示数组 aa 的长度。
第二行包含 nn 个整数 a1,a2,…,ana_1, a_2, \ldots, a_n（0≤ai≤1090 \le a_i \le 10^9）。
保证所有测试用例中 nn 的总和不超过 2⋅1052 \cdot 10^5。

输出格式
对于每个测试用例，如果存在满足条件的数组 bb，第一行输出 YES（不区分大小写），第二行输出 nn 个整数 b1,b2,…,bnb_1, b_2, \ldots, b_n（0≤bi≤1090 \le b_i \le 10^9）。
如果不存在，仅输出一行 NO。

样例数据

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
Input:
6
3
3 3 1
3
2 1 3
1
0
1
2
4
7 5 2 2
6
6 6 6 4 3 3

Output:
YES
2 0 2
NO
YES
67
NO
NO
YES
5 2 1 5 2 0

样例解释
在第一组测试用例中，a=[3,3,1]a = [3, 3, 1]。我们可以验证数组 b=[2,0,2]b = [2, 0, 2] 满足条件：

  • 当 i=1i=1 时，需要计算前缀 [b1]=[2][b_1] = [2] 的 (3−1+1)(3-1+1) 即 33-mex。未在数组中出现的非负整数依次为 0,1,3,4,…0, 1, 3, 4, \dots，其中第 33 小的是 33，等于 a1a_1。

  • 当 i=2i=2 时，需要计算前缀 [b1,b2]=[2,0][b_1, b_2] = [2, 0] 的 (3−2+1)(3-2+1) 即 22-mex。未在数组中出现的非负整数依次为 1,3,4,…1, 3, 4, \dots，其中第 22 小的是 33，等于 a2a_2。

  • 当 i=3i=3 时，需要计算前缀 [b1,b2,b3]=[2,0,2][b_1, b_2, b_3] = [2, 0, 2] 的 (3−3+1)(3-3+1) 即 11-mex。未在数组中出现的非负整数依次为 1,3,4,…1, 3, 4, \dots，其中第 11 小的是 11，等于 a3a_3。

在第二组测试用例中，a=[2,1,3]a = [2, 1, 3]。可以证明不存在任何满足条件的数组 bb，因此输出 NO。

在第三组测试用例中，a=[0]a = [0]。构造 b=[67]b = [67] 满足条件，因为前缀 [b1]=[67][b_1] = [67] 的 11-mex 是 00，恰好等于 a1a_1。

思路讲解

首先，需要这样子想，每一个 a 代表什么？可以这样子想：

image

不难发现：（使用归纳法）

image

当然，我们可以换成这个 i。

image

为什么可以 = 呢？

image

其实这个规律还是没有那么难以观察出来的，毕竟这个 a1 代表第 n 个空，a2 代表第 n-1 个空，你也很难想象第 n-1 个空在第 n 个空后面是吧？

我觉得上面 AI 的这个角度还是挺好的，但是我其实觉得稍微有点扯。

然后我们还是没有想到怎么做？那应该是对 a 的性质探索的还不够多！（继续沿着探索 a 的性质的这条路走）

其实光有这个递减性质，其实还是不够的，我们不妨多探索一些性质，比如说 ai+1 其取值范围到底是在哪里？

image

image

通过上面的推导，我们不难得出如下结论：

image

这道题目，我们的做法需要用到 dsu on next 技巧。那么要注意这个合并方向。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
vector<ll> B(N + 2);
ll cur;
vector<ll> wp;
ll top_b = 0;
for (int i = 1; i <= N; ++i) {
  // 我觉得一般来说，你还是不要用哨兵节点，老老实实特判比较好，确保初值正确
    if (i == 1) {
        if (A[i] > N) {
            cout << "NO\n";
            return;
        }
        if (A[i] == N) {
            wp.push_back(i);
            cur = N;
        } else if (A[i] == N - 1) {
            B[i] = mod;
            cur = N - 1;
        } else {
            cout << "NO\n";
            return;
        }
        merge(A[i], A[i] - 1);
        continue;
    }
    if (A[i] == cur) {
      // wp 存储的就是我们存下来的，等待填充的 B 数组中的位置
        wp.push_back(i);
    } else {
        ll fcur = find(cur);
        if (fcur < A[i]) {
            cout << "NO\n";
            return;
        }
        // 之所以要 merge A[i] 和 A[i-1]，是因为 A[i] 是一个空，也不要填充 b 了。
        merge(A[i], A[i] - 1);
        for (ll j = fcur; j > A[i]; --j) {
            merge(j, j - 1);
            if (wp.empty()) {
                cout << "NO\n";
                return;
            }
            B[wp.back()] = j;
            wp.pop_back();
        }
        cur = A[i];
        B[i] = mod;
    }
}
while (!wp.empty()) {
    if (!merge(top_b, top_b - 1)) {
        cout << "NO\n";
        return;
    }
    B[wp.back()] = top_b;
    wp.pop_back();
    top_b++;
}
cout << "YES\n";
for (int i=1;i<=N;++i) {
    cout<<B[i]<<" ";
}

AC代码

AC
https://codeforces.com/contest/2207/submission/367198322

心路历程（WA，TLE，MLE……）

对拍拍出来的数据。

1
2
3
4
1
4
4 4 3 1

Posted on Edited on

【G09 筛法求欧拉函数】 https://www.bilibili.com/video/BV1VP411p7Bs/?share_source=copy_web&vd_source=6ca0bc05e7d6f39b07c1afd464edae37

The 6th Liaoning Provincial Collegiate Programming Contest-2025-辽宁省赛-B. Be knocked off 被抠的键盘（构造题，我们需要思考的就是，我们有没有办法化繁为简？）（一般这种构造题目，无解情况不会特别多）

image

这个对的原因是，显然，和 pkp^k 不互素的只有 p 的倍数，因此就是 ϕ(pk)=pk−(p的倍数的数量)\phi(p^k)=p^k-(p 的倍数的数量)。

1⋅p,2⋅p,3⋅p,4⋅p,5⋅p,6⋅p,…,(pk−1−2)⋅p,(pk−1−1)⋅p,pk−1⋅p1 \cdot p,\quad 2 \cdot p,\quad 3 \cdot p,\quad 4 \cdot p,\quad 5 \cdot p,\quad 6 \cdot p,\quad \ldots,\quad (p^{k-1} - 2) \cdot p,\quad (p^{k-1} - 1) \cdot p,\quad p^{k-1} \cdot p

p 的倍数的系数可以从 11 一直取到 pk−1p^{k-1}，所以一共 pk−1p^{k-1} 个。最后一项 pk−1⋅p=pkp^{k-1} \cdot p = p^k，刚好是上界。

因此 ϕ(pk)=pk−pk−1\phi(p^k)=p^k-p^{k-1}。

有了上面的这个公式，就不难推出如下式子。

image

其实这个式子，形象化的理解，就是不断的把 n 里面，p 的倍数（p 都是质数，因此倍数与倍数之间互不干扰）给筛掉。

当然，如果进行朴素相减，会出现问题。

image

不过，那为什么乘积不会出现这个问题呢？答案就是容斥原理。

image

这就是乘法的容斥原理。因为乘法的本质就是在枚举子集，只要一个负号，让其符合这个容斥原理的奇减偶加特性即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

/*
 * 试除法求一个数的欧拉函数（也就是求 [1,n] 内与其互素的数的个数）
 * 2026-03-13: AC https://codeforces.com/gym/106380/submission/366492238
 */
long long euler_phi(long long n) {
    long long res = n;
    // p 从 2 开始，逐个递增，试到 sqrt(n) 为止
    for (long long p = 2; p * p <= n; p++) {
        // 如果 p 能整除 n，那么 p 一定是质数。
        // 为什么？因为如果 p 是合数，比如 p = 6 = 2 × 3，
        // 那么在 p=2 和 p=3 的时候，n 中的 2 和 3 已经被除干净了，
        // 此时 n 不可能被 6 整除，所以 n % 6 != 0，这个 if 进不来。
        // 因此能进到这个 if 里的 p，一定是质因子。
        if (n % p == 0) {
            // 发现质因子 p，对 res 乘上 (1 - 1/p) 这个因子
            // 即 res = res / p * (p - 1)
            res = res / p * (p - 1);
            // 把 n 中所有的 p 除干净
            // 这样后续更大的 p 的倍数就不可能再整除 n 了
            while (n % p == 0) n /= p;
        }
    }
    // 循环结束后，如果 n > 1，说明 n 还剩一个大于 sqrt(原始n) 的质因子
    // （一个数最多只有一个大于 sqrt 的质因子）
    if (n > 1) {
        res = res / n * (n - 1);
    }
    return res;
}

image

那么都有上面的，非常符合直觉的计算公式了，我们也是非常 easy 的能够证明这个东西。

image

只要把这个东西全部列出来，就非常容易的可以证明。当然，要求 n，m 互素，否则他们的质数项一定会有交集，那么就失效了，积性函数性质。

image

这是 Euler 定理（欧拉定理）。

对于任意正整数 mm 和整数 aa，若 gcd⁡(a,m)=1\gcd(a, m) = 1，则

aφ(m)≡1(modm)a^{\varphi(m)} \equiv 1 \pmod{m}

image

证明：考虑模 mm 的缩系（即 11 到 mm 中所有与 mm 互素的数构成的集合 SS，共 φ(m)\varphi(m) 个元素）。当 gcd⁡(a,m)=1\gcd(a, m) = 1 时，把 SS 中每个元素都乘以 aa，得到的集合模 mm 后恰好还是 SS（因为乘以 aa 是模 mm 缩系上的一个双射）。于是把所有元素的乘积写出来：

∏x∈S(ax)≡∏x∈Sx(modm)\prod_{x \in S} (ax) \equiv \prod_{x \in S} x \pmod{m}

左边提出 aa：

aφ(m)×∏x∈Sx≡∏x∈Sx(modm)a^{\varphi(m)} \times \prod_{x \in S} x \equiv \prod_{x \in S} x \pmod{m}

因为 ∏x∈Sx\prod_{x \in S} x 与 mm 互素（因为 SS 中每个元素都与 mm 互素，这里我们用到了 S 的定义）（说白了，只要是除数和 m 互素，就有逆元，就可以除），可以两边消掉，就得到 aφ(m)≡1(modm)a^{\varphi(m)} \equiv 1 \pmod{m}。

它的特殊情况是 Fermat 小定理：当 m=pm = p 为素数时，φ(p)=p−1\varphi(p) = p - 1，即 ap−1≡1(modp)a^{p-1} \equiv 1 \pmod{p}。

Posted on Edited on

线性筛

线性筛的作用就是为了保证每个合数都只被其【最小的】那个质因数标记一次。

image

这下面👇讲的比较一般啊。

线性筛只有可能标记一个数字一次。

image

这个讲的有点复杂了，最后是关键，就是每个数只会以唯一方式被标记。

m=np1=p1m1−1×p2m2×p3m3×⋯×pkmkm=\frac{n}{p_1}=p_{1}^{m_1-1}\times p_{2}^{m_2}\times p_{3}^{m_3} \times \cdots \times p_{k}^{m_k}

n 只会在遍历到 m 时被标记。

假设这个n，在遍历到 m 之前就被标记，假设该数字是 m‘，但是 m’×minp[m′]=nm’\times \text{minp}[m']=n 是必须满足的条件，if(p==minp[i]) break; ，m‘ 只会标记到这个最小素因子*自身，因此 m’ 想标记 n，当且仅当 m’×minp[m′]=nm’\times \text{minp}[m']=n。显然，m‘=m，得证。

https://qoj.ac/submission/995868

https://cp-algorithms.com/algebra/prime-sieve-linear.html

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
//  minp[i] 存储的是i的最小素因数
// https://www.luogu.com.cn/record/221554377
vector<ll> minp,primes;
void sieve(ll n){
    minp.assign(n+5,0);
    // minp[1]=1;  // 加了这句话可能把 1 误判成素数，要小心
    for(int i=2;i<=n;++i){
        if(minp[i]==0){		// 是素数
            minp[i]=i;
            primes.push_back(i);
        }
        for(auto p:primes){
            if(i*p>n){	// 超范围了
                break;
            }
            minp[i*p]=p;
            // 为了保证每个合数都只被其【最小的】那个质因数标记一次 break
            // i * p_next = (p * k) * p_next 最小的应该是p
            if(p==minp[i]){
                break;
            }
        }
    }
}

使用线性筛的minp分解素因数更快，效率更高。

1
2
3
4
5
6
7
vector<ll> prs;
for(int j=W[i];j>1;j/=minp[j]){		// 素因数分解
	ll p=minp[j];
	prs.pb(p);
}
sort(all(prs));
prs.resize(unique(all(prs))-prs.begin());

Posted on Edited on

题目大意

题目描述
你有一个包含数字 00 到 99 的键盘。给定一个正整数 mm，你的目标是使用键盘打出一个正整数，使其为 mm 的倍数。

但是，键盘上有 kk 个正整数按键损坏了（数字 00 的按键一定完好，只有 11 到 99 中的部分按键可能损坏）。你只能使用剩下的完好按键来打出这个数字。

输入格式
第一行包含一个整数 TT（1≤T≤5×1041 \le T \le 5 \times 10^4），表示测试数据的组数。

对于每组测试数据：
第一行包含两个整数 mm 和 kk（1≤m≤1071 \le m \le 10^7，0≤k≤90 \le k \le 9），表示目标数字必须是 mm 的倍数，且有 kk 个按键损坏。

用其他剩余按键，敲出 m 的倍数。

第二行包含 kk 个互不相同的整数 pip_i（1≤pi≤91 \le p_i \le 9），具体表示哪些数字按键被损坏。

输出格式
对于每组测试数据：
如果存在合法的构造方案，请以“连续按下某数字 aa 共 bb 次”的操作序列形式输出：
第一行输出一个整数 nn（1≤n≤1001 \le n \le 100），表示操作的数量。
接下来 nn 行，每行输出两个整数 aa 和 bb（0≤a≤90 \le a \le 9，1≤b≤10181 \le b \le 10^{18}），表示按下数字 aa 共 bb 次。

如果不存在任何合法的方案，仅输出一行 -1。

样例

1
2
3
4
5
6
7
8
9
10
11
12
输入:
2
37 7
2 3 5 6 7 8 9
7 9
1 2 3 4 5 6 7 8 9

输出:
2
1 3
0 1
-1

样例解释
对于第一组样例，给出的操作为：按下数字 11 共 33 次，然后按下数字 33 共 11 次。这样按出来的正整数是 11101110。由于 1110=37×301110 = 37 \times 30，它是 3737 的倍数，并且只使用了未损坏的按键 11 和 00，符合题目要求。

对于第二组样例，数字 11 到 99 的按键全部损坏，唯一能打出的是由数字 00 组成的数（值为 00）。但题目要求打出的必须是一个正整数，因此无法完成任务，输出 -1。

思路讲解

呃，首先我们还是一步一步来吧，就是首先，我们可以想到，就是 m 当中的这个因数还是越少越好嘛，想办法先消掉一些。

下面这一步也是比较自然的，因为注意到，0 是永远都在的。

我们可以把这个 m 当中的因数 2,5 给除掉（因为如果原数字不满足，就加 0 即可），得到的新 m 和这个 10 互质（反正应该就是想办法让原数和 10 互质，可以通过不断除以 10，记录一下除 10 的这个个数，最后 +0 即可）。

然后，就可以想到欧拉定理（其实我们的构造目标就是一个同余式，我们得到的任何东西，也要想办法化为同余式）：

这是 Euler 定理（欧拉定理）。

对于任意正整数 mm 和整数 aa，若 gcd⁡(a,m)=1\gcd(a, m) = 1，则

aφ(m)≡1(modm)a^{\varphi(m)} \equiv 1 \pmod{m}

image

不难得出如下结论：

image

我们现在是构出来了，但是万一 9 被扣了我们不就炸了？

我们发现，只要我们能够勾出来一个全 1 的，我们能够非常自然的勾出全 d 的。

image

这个最后一步，也挺难的，反正我确实不大能够推出来。使用了变量直接代换的这个技巧，把一个 9 带到了这个整除符号的两边。

image

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
ll cnt2=0;
while (M%2==0) {
    M/=2;
    cnt2++;
}
ll cnt5=0;
while (M%5==0) {
    M/=5;
    cnt5++;
}
ll phi=euler_phi(M);
ll cnt0=max(cnt2,cnt5);
if (cnt0==0) {
    cout<<1<<"\n";
}else {
    cout<<2<<"\n";
}
cout<<*keys.rbegin()<<" "<<9*phi<<"\n";
if (cnt0!=0) {
    cout<<0<<" "<<cnt0<<"\n";
}

AC代码

AC
https://codeforces.com/gym/106380/submission/366492238

心路历程（WA，TLE，MLE……）3737111≤b≤10181 \le b \le 10^{18}