蓝桥杯算法赛第4场小白入门赛强者挑战赛

链接：
第 4 场 小白入门赛
第 4 场 强者挑战赛

小白1

直接用C++内置函数即可。

#include <bits/stdc++.h>
using namespace std;#include <bits/extc++.h>
using namespace __gnu_pbds;using llt = long long;
using Real = double;
using vi = vector<int>;int main(){
#ifndef ONLINE_JUDGEfreopen("z.txt", "r", stdin);
#endifios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(0);cout << __builtin_popcount(2024) << endl;return 0;
}

小白2

做个字典即可。

import os
import sys
p = {'yuanxing':1, 'zhengfangxing':2, 'changfangxing':3, 'sanjiaoxing':4, 'tuoyuanxing':5, 'liubianxing':6}n = int(input())
a = input().split()
ans = 0
for i in a:ans += p[i]
print(ans)

小白3

经典的NIM问题。当异或和为零时，先手必败。所以当石子数量为偶数时，分成两堆即可。当数量为奇数时，无论怎么分，最低位的1不可能异或为零，也就是说异或和必不为零，先手必胜。

#include <iostream>
using namespace std;
int main()
{int n; cin >> n;cout << (n % 2 == 0 ? "B" : "A") << "\n"; return 0;
}

强者1

很明显的贪心，无论轮到谁取，均取当前最大的数即可。

#include <bits/stdc++.h>
using namespace std;#include <bits/extc++.h>
using namespace __gnu_pbds;using llt = long long;
using Real = double;
using vi = vector<int>;
using pii = pair<int, int>;int N;
vi A;void proc(){    sort(A.begin(), A.end(), greater<int>());llt a[2] = {0};int o = 0;for(int i=1;i<N;i+=2){a[o] += A[i - 1];a[o ^ 1] += A[i];o ^= 1;}cout << a[0] << " " << a[1] << endl;
}int main(){
#ifndef ONLINE_JUDGEfreopen("z.txt", "r", stdin);
#endifios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(0);cin >> N;A.assign(N, {});for(auto & i : A) cin >> i;proc();return 0;
}

小白4强者2

抽屉原理。因为总取值范围为36500，所以当取数数量超过100时，必然有两个数之差在365及其以内。当数量不超过100时，排序以后逐个检验一下即可。

#include <bits/stdc++.h>
using namespace std;#include <bits/extc++.h>
using namespace __gnu_pbds;using llt = long long;
using Real = double;
using vi = vector<int>;int N;
int Q;
vi A;const array<string, 2> ANS = {"NO", "YES"};int proc(int s, int e){if(e >= s + 100) return 1;vi vec(A.begin() + s, A.begin() + e + 1);sort(vec.begin(), vec.end());for(int i=1,n=vec.size();i<n;++i){if(vec[i] - vec[i - 1] <= 365) return 1;}return 0;
}int main(){
#ifndef ONLINE_JUDGEfreopen("z.txt", "r", stdin);
#endifios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(0);cin >> N >> Q;A.assign(N, {});for(auto & i : A) cin >> i;for(int s,e,q=1;q<=Q;++q){cin >> s >> e;cout << ANS[proc(s - 1, e - 1)] << "\n"; }return 0;
}

小白5强者3

逆序对树状数组相关。首先把二元组的数组计算出来，每个元素是$(i,P_{A_i})$。这个很容易计算。将二元组数组看做是$(x,y)$的数组，所以该题的条件其实就是一个二维偏序的条件，即两个维度都要小。然后该题本质上就是对每一个点$(x_i,y_i)$求：
$$c_i\times x+i-\sum _{j是i左下的点}{x}_j$$

其中$c_i$是位于$i$点左下的所有点的数量。

弄两个树状数组，记作b1和b2，则对每一个点$(x,y)$:

• 在b1中查询[1, y)的和，该和表示一共有多少个点位于左下，记作c
• 在b2中查询[1, y)的和，该和表示左下点x坐标之和, 记作s
• 然后将 c * x - s 累加进去即可
• 然后将 b1[y] 加 1， b2[y] 加 x 即可

#include <bits/stdc++.h>
using namespace std;#include <bits/extc++.h>
using namespace __gnu_pbds;using llt = long long;
using Real = double;
using vi = vector<int>;struct FenwickTree{ // 树状数组using value_type = long long int;
using vec_type = vector<value_type>;int n;
vec_type c;FenwickTree() = default;static int lowbit(int x){return x & -x;}void init(int nn){this->c.assign((this->n=nn) + 1, 0);}void modify(int pos, value_type delta){for(int i=pos;i<=this->n;i+=lowbit(i)) this->c[i] += delta;
}value_type query(int pos)const{value_type ans = 0;for(int i=pos;i;i-=lowbit(i)) ans += this->c[i];return ans;
}value_type query(int s, int e)const{return this->query(e) - this->query(s - 1);}}Bt1, Bt2;using pii = pair<int, int>;int N;
vi A, B;void input(vi & v, int n){v.assign(n, {});for(auto & i : v) cin >> i;
}llt proc(){vi pos(N + 1, {});for(int i=0;i<N;++i) pos[B[i]] = i;vector<pair<int, int>> vec(N);for(int i=0;i<N;++i){vec[i] = {i + 1, pos[A[i]] + 1};}// sort(vec.begin(), vec.end(), [](pii a, pii b){return a.second < b.second;});llt ans = 0;Bt1.init(N); Bt2.init(N);for(int i=0;i<N;++i){auto k = vec[i].first;auto v = vec[i].second;auto c = Bt1.query(v);Bt1.modify(v, 1);auto s = Bt2.query(v);Bt2.modify(v, k);ans += c * k - s;}return ans;
}int main(){
#ifndef ONLINE_JUDGEfreopen("z.txt", "r", stdin);
#endifios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(0);cin >> N;input(A, N); input(B, N);cout << proc() << endl;return 0;
}

小白6强者4

概率推公式。有$N$个格子，第$i$格有$P_i$的概率到下一格（第$N$格的下一格是第1格），有$1-P_i$的概率就此停止。问每一格最终停下的概率，以及对这些概率排序。

对于第1格而言，有$1-P_1$的概率直接停下，或者转一圈回来以后再以$1-P_1$的概率，或者转二圈再以$1-P_1$的概率，……；
对于第2格而言，首先要到达第2格，这个概率是$P_1$，然后剩下的推导类似；
所以，首先令
$$\Pi =\prod _{i=1}^N{P}_i$$
即转一圈的概率。

对第$i$格，停止在此的概率是：
$$Q_i=P_1\times P_2\times \cdots \times P_{i-1}\times (1-P_i)\times (1+\Pi +{\Pi }^2+{\Pi }^3+\cdots )=P_1\times P_2\times \cdots \times P_{i-1}\times (1-P_i)\times \frac{1}{1-\Pi }$$

如果不考虑求逆的时间，在$O(N)$内即可求出上述每一个$Q_i$。

然后考虑排序，这个比较麻烦，因为要比较概率本身，而不能比较取模以后的数。

考虑$Q_i$和$Q_j$比较大小，不失一般性，假设$i<j$。则
$$Q_j=P_1\times P_2\times \cdots \times P_{i-1}\times (1-P_i)\times \frac{1}{1-\Pi }$$
$$Q_j=P_1\times P_2\times \cdots \times P_{i-1}\times P_i\times \cdots \times (1-P_j)\times \frac{1}{1-\Pi }$$

首先讨论特殊情况：

1. 当$P_i,P_j$全为1时，即不可能停在此2格，停下的概率为零，根据题意，$i$应该排在前面；
2. 当$P_i,P_j$任意为1时，可知一个停下的概率为零，另一个不为零，则大小关系可以确定。

然后讨论一般情况，即二者全不为1时。可以证明$Q_i\ge Q_j$。

$$\begin{array}{rl}{Q}_i\ge Q_j& \iff P_1\times P_2\times \cdots \times P_{i-1}\times (1-P_i)\times \frac{1}{1-\Pi }\ge P_1\times P_2\times \cdots \times P_{i-1}\times P_i\times \cdots \times (1-P_j)\times \frac{1}{1-\Pi }\\ & \iff 1-P_i\ge P_i\times \cdots \times (1-P_j)\end{array}$$
对最后一个不等式的右边做缩放，只需证明
$$1-P_i\ge P_i\times (1-P_j)\text{\hspace{1em}(*)}$$
即可

而$(\ast )$等价于
$$1-2P_i+P_i{P}_j\ge 0$$

注意到题目给出的概率的形式，当$P_i$不为1时，必有$P_i\le \frac{1}{2}$成立。因此最后一个不等式是成立的，从而可知$i$要排在$j$前面。

于是得到了一个不必计算概率的具体值就能排序的准则，$sort$一下即可。

#include <bits/stdc++.h>
using namespace std;#include <bits/extc++.h>
using namespace __gnu_pbds;using llt = long long;
using Real = double;
using vi = vector<int>;llt const MOD = 998244353;llt qpow(llt a, llt n){llt r = 1;while(n){if(n & 1) r = r * a % MOD;a = a * a % MOD;n >>= 1;}return r;
}llt inv(llt a){return qpow(a, MOD-2LL);}int N;
vector<llt> P;llt myhash(const vector<llt> & vec){llt ans = 0;llt k = 0;for(auto i : vec){ans = (ans + (++k) * i % MOD) % MOD;}return ans;
}void proc(){auto tmp = accumulate(P.begin(), P.end(), 0LL);auto pi = inv(qpow(2LL, tmp));auto fenmu = inv((MOD + 1 - pi) % MOD);vector<llt> ans(N);llt fenzi = 1;for(int i=0;i<N;++i){auto p = inv(qpow(2, P[i]));auto q = (MOD + 1 - p) % MOD;ans[i] = fenzi * q % MOD * fenmu % MOD;fenzi = fenzi * p % MOD;}vector<llt> rank(N);for(int i=0;i<N;++i) rank[i] = i + 1;sort(rank.begin(), rank.end(), [&](int i, int j){i -= 1, j -= 1;if(0 == P[i]){ // 100%会走，即停到此处的概率为0if(0 == P[j]) return i < j; return false; // 停在j的概率肯定比i大}if(0 == P[j]) return true;return i < j;});cout << myhash(ans) << endl;cout << myhash(rank) << endl;return;
}int main(){
#ifndef ONLINE_JUDGEfreopen("z.txt", "r", stdin);
#endifios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(0);cin >> N;P.assign(N, {});for(auto & i : P) cin >> i;proc();return 0;
}

强者5

预处理加$DP$。

注意到题目强调了每个用户是独立的，因此首先做一个预处理，计算出二维数组$User2Gain$。$User2Gain[i][j]$表示如果给第$i$个用户分配$j$个空间，其收益是多少。收益等于M - 缺页中断数。（为什么要减一下计算收益，因为笔者最开始弄错了，以为是一个分组背包，所以减一下刚好可以计算最大收益）

$User2Gain$辅助以数据结构应该比较容易算出来。假设用户的请求数量平均分配为$M/K$个，则预处理时间应该是$O(K\times \frac{M}{k}\log \frac{M}{K})$，最差情况可能是$O(M\log M)$。不太确定这个复杂度对不对。

接下来$DP$，令$D_{i,j}$表示前$i$个用户分配$j$个空间所能获得的最大收益，则
$$D_{i,j}=\max (D_{i-1,k}+User2Gain[i][j-k],k\in [0,j])$$

算出最大收益，再减回来就得到了最小的缺页数。

上述计算要三重循环，看起来是立方的，但实际上不是。考虑到每个用户平均分配到$\frac{M}{K}$个空间，因此，第1个用户只需计算到$\frac{M}{K}$，第2个用户只需计算到$\frac{2M}{K}$，第3个用户到$\frac{3M}{K}$，……

实际计算次数是
$$(\frac{M}{K}+\frac{2M}{K}+\frac{3M}{K}+\cdots +\frac{KM}{K})\times \frac{M}{K}\equiv O(M^2)$$

这似乎也是最差情况。同样不保证这个复杂度分析一定对，感觉没错。

#include <bits/stdc++.h>
using namespace std;#include <bits/extc++.h>
using namespace __gnu_pbds;using llt = long long;
using Real = double;
using vi = vector<int>;
using pii = pair<int, int>;__gnu_pbds::priority_queue<pii, function<bool(const pii &, const pii &)>> Q([](const pii & a, const pii & b){assert(a.second != b.second);return a.second < b.second;
});int N, K, M;
vector<pii> Req;
vi Lisan;
vector<vi> User2Gain;
vector<vi> D;int proc(const vi & req, int alloc){map<int, pair<vi, int>> req2pos;for(int i=0;i<req.size();++i) req2pos[req[i]].first.emplace_back(i);Q.clear();int k = 1;for(auto & p : req2pos){p.second.second = 0;p.second.first.emplace_back(M + M + k++);}vi flag(M + 1, 0);int ans = 0;int used = 0;for(int i=0;i<req.size();++i){auto r = req[i];if(0 == flag[r]){ans += 1;if(used < alloc){used += 1;}else{while(1){auto h = Q.top();Q.pop();if(h.second > i){flag[h.first] = 0;break;}}}}flag[r] = 1;auto & mm = req2pos[r];Q.push({r, mm.first[++mm.second]});}return ans;
}void proc(const vi & req, vi & gain){vi flag(M + 1, 0);int n = 0;for(auto i : req){if(flag[i] == 0){flag[i] = 1;n += 1;}}if(n > N) n = N;gain.assign(n + 1, 0);gain[0] = M - req.size();for(int i=1;i<=n;++i){gain[i] = M - proc(req, i);}return;
}int proc(){Lisan.clear(); Lisan.reserve(M + 1);Lisan.emplace_back(0);for(const auto & p : Req) Lisan.emplace_back(p.second);sort(Lisan.begin(), Lisan.end());Lisan.erase(unique(Lisan.begin(), Lisan.end()), Lisan.end());vector<vi> user2req(K + 1, vi());for(auto & p : Req){p.second = lower_bound(Lisan.begin(), Lisan.end(), p.second) - Lisan.begin();user2req[p.first].emplace_back(p.second);}User2Gain.assign(K + 1, vi());for(int i=1;i<=K;++i){proc(user2req[i], User2Gain[i]);// cout << i << ":";// for(auto j : User2Gain[i]){//     cout << " " << M - j;// }// cout << endl;}D.assign(K + 1, vi(N + 1, 0));int total = 0;for(int user=1;user<=K;++user){const auto & gain = User2Gain[user];total += gain.size() - 1;if(total >= N) total = N;for(int space=0;space<=total;++space){int ava = min((int)gain.size() - 1, space);auto & tmp = D[user][space];for(int i=0;i<=ava;++i){tmp = max(tmp, D[user-1][space-i] + gain[i]);}}}int ans = M * K;const auto & vec = D[K];for(int i=0;i<=N;++i){ans = min(ans, M * K - vec[i]);}return ans;
}int main(){
#ifndef ONLINE_JUDGEfreopen("z.txt", "r", stdin);
#endifios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(0);int nofkase = 1;cin >> nofkase;while(nofkase--){cin >> N >> K >> M;Req.assign(M, {});for(auto & p : Req) cin >> p.first >> p.second;cout << proc() << "\n";}return 0;
}

强者6

差分加树状数组。
假设第$i$个请求和第$j$个请求是同一个页面，则$j$有可能命中缓存。取决于$i,j$之间不同页面种类的数量与缓存空间的大小关系。为方便论述，称不同页面种类的数量为间隔数。例如：
$$1,2,3,4,2,3,4,1$$

上述两个页面1之间的间隔数为3，所以当缓存空间大于3时，第二个页面1必然是命中的；否则必然有缺页中断。基于简单的贪心可知，如果缓存空间为$K$时，某个$j$请求会有缺页中断，则缓存空间更小时，必然也会有缺页中断。因此只需要对相邻的相等页面，求出间隔数即可。这是一个典型的树状数组应用。

令$A$数组是页面请求数组，$B$是一个树状数组。pre[v]是数值v在数组$A$中前一个最近的位置。则：

for i,v in A:求B[pre[v], v]之间的和，记作s, s就是一个间隔数, 令cnt[s] += 1将B[pre[v]] -= 1将B[i] += 1pre[v] = i

由此就得到了每一个间隔数出现的数量，根据此就能算出缺页数（注意到此时，页面是几其实已经不重要）。

计算间隔数应该是$O(M\log M)$，根据间隔数计算$Ans$应该是$O(M)$。

#include <bits/stdc++.h>
using namespace std;#include <bits/extc++.h>
using namespace __gnu_pbds;using llt = long long;
using Real = double;
using vi = vector<int>;
using pii = pair<int, int>;struct FenwickTree{ // 树状数组using value_type = long long int;
using vec_type = vector<value_type>;int n;
vec_type c;FenwickTree() = default;static int lowbit(int x){return x & -x;}void init(int nn){this->c.assign((this->n=nn) + 1, 0);}void modify(int pos, value_type delta){for(int i=pos;i<=this->n;i+=lowbit(i)) this->c[i] += delta;
}value_type query(int pos)const{value_type ans = 0;for(int i=pos;i;i-=lowbit(i)) ans += this->c[i];return ans;
}value_type query(int s, int e)const{return this->query(e) - this->query(s - 1);}}Bt;int M;
vi A;
vi Ans;void proc(){    Bt.init(M);map<int, int> cnt;vi pre(1000000 + 1, 0);for(int p,v,i=0;i<M;++i){p = i + 1;v = A[i];if(pre[v]){Bt.modify(pre[v], -1);cnt[Bt.query(pre[v], p)] += 1;}else{cnt[M] += 1;}        Bt.modify(pre[v] = p, 1);}Ans.assign(M + 1, 0);int sum = 0;int another = M;for(auto it=cnt.rbegin(),jt=++cnt.rbegin(),et=cnt.rend();jt!=et;++it,++jt){int last = it->first;int start = jt->first;sum += it->second;fill(Ans.begin() + start + 1, Ans.begin() + last + 1, sum);}cout << (Ans[0] = M);for(int i=1;i<=M;++i) cout << " " << Ans[i];cout << endl;
}int main(){
#ifndef ONLINE_JUDGEfreopen("z.txt", "r", stdin);
#endifios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(0);cin >> M;A.assign(M, {});for(auto & i : A) cin >> i;proc();return 0;
}