怎么做提升自己的网站,kuler网站,全国有哪些做服装的网站,制作图片app蓝桥杯算法赛第4场小白入门赛强者挑战赛 小白1小白2小白3强者1小白4强者2小白5强者3小白6强者4强者5强者6 链接#xff1a; 第 4 场 小白入门赛 第 4 场 强者挑战赛
小白1
直接用C内置函数即可。
#include bits/stdc.h
using namespace std;#include bits… 蓝桥杯算法赛第4场小白入门赛强者挑战赛 小白1小白2小白3强者1小白4强者2小白5强者3小白6强者4强者5强者6 链接 第 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 vectorint;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 vectorint;
using pii pairint, int;int N;
vi A;void proc(){ sort(A.begin(), A.end(), greaterint());llt a[2] {0};int o 0;for(int i1;iN;i2){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 vectorint;int N;
int Q;
vi A;const arraystring, 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 i1,nvec.size();in;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,q1;qQ;q){cin s e;cout ANS[proc(s - 1, e - 1)] \n; }return 0;
}小白5强者3
逆序对树状数组相关。首先把二元组的数组计算出来每个元素是 ( i , P A i ) (i, P_{A_i}) (i,PAi)。这个很容易计算。将二元组数组看做是 ( x , y ) (x,y) (x,y)的数组所以该题的条件其实就是一个二维偏序的条件即两个维度都要小。然后该题本质上就是对每一个点 ( x i , y i ) (x_i,y_i) (xi,yi)求 c i × x i − ∑ j 是 i 左下的点 x j c_i\times{xi} - \sum_{j是i左下的点}{x_j} ci×xi−j是i左下的点∑xj
其中 c i c_i ci是位于 i i i点左下的所有点的数量。
弄两个树状数组记作b1和b2则对每一个点 ( x , y ) (x,y) (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 vectorint;struct FenwickTree{ // 树状数组using value_type long long int;
using vec_type vectorvalue_type;int n;
vec_type c;FenwickTree() default;static int lowbit(int x){return x -x;}void init(int nn){this-c.assign((this-nnn) 1, 0);}void modify(int pos, value_type delta){for(int ipos;ithis-n;ilowbit(i)) this-c[i] delta;
}value_type query(int pos)const{value_type ans 0;for(int ipos;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 pairint, 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 i0;iN;i) pos[B[i]] i;vectorpairint, int vec(N);for(int i0;iN;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 i0;iN;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 N N个格子第 i i i格有 P i P_i Pi的概率到下一格第 N N N格的下一格是第1格有 1 − P i 1-P_i 1−Pi的概率就此停止。问每一格最终停下的概率以及对这些概率排序。
对于第1格而言有 1 − P 1 1-P_1 1−P1的概率直接停下或者转一圈回来以后再以 1 − P 1 1-P_1 1−P1的概率或者转二圈再以 1 − P 1 1-P_1 1−P1的概率…… 对于第2格而言首先要到达第2格这个概率是 P 1 P_1 P1然后剩下的推导类似 所以首先令 Π ∏ i 1 N P i \Pi\prod_{i1}^{N}{P_i} Πi1∏NPi 即转一圈的概率。
对第 i i i格停止在此的概率是 Q i P 1 × P 2 × ⋯ × P i − 1 × ( 1 − P i ) × ( 1 Π Π 2 Π 3 ⋯ ) P 1 × P 2 × ⋯ × P i − 1 × ( 1 − P i ) × 1 1 − Π Q_iP_1\times{P_2}\times\cdots\times{P_{i-1}}\times{(1-P_i)}\times\big(1\Pi\Pi^2\Pi^3\cdots\big)P_1\times{P_2}\times\cdots\times{P_{i-1}}\times{(1-P_i)}\times\frac{1}{1-\Pi} QiP1×P2×⋯×Pi−1×(1−Pi)×(1ΠΠ2Π3⋯)P1×P2×⋯×Pi−1×(1−Pi)×1−Π1
如果不考虑求逆的时间在 O ( N ) O(N) O(N)内即可求出上述每一个 Q i Q_i Qi。
然后考虑排序这个比较麻烦因为要比较概率本身而不能比较取模以后的数。
考虑 Q i Q_i Qi和 Q j Q_j Qj比较大小不失一般性假设 i j i\lt{j} ij。则 Q j P 1 × P 2 × ⋯ × P i − 1 × ( 1 − P i ) × 1 1 − Π Q_jP_1\times{P_2}\times\cdots\times{P_{i-1}}\times{(1-P_i)}\times\frac{1}{1-\Pi} QjP1×P2×⋯×Pi−1×(1−Pi)×1−Π1 Q j P 1 × P 2 × ⋯ × P i − 1 × P i × ⋯ × ( 1 − P j ) × 1 1 − Π Q_jP_1\times{P_2}\times\cdots\times{P_{i-1}}\times{P_i}\times\cdots\times{(1-P_j)}\times\frac{1}{1-\Pi} QjP1×P2×⋯×Pi−1×Pi×⋯×(1−Pj)×1−Π1
首先讨论特殊情况
当 P i , P j P_i,P_j Pi,Pj全为1时即不可能停在此2格停下的概率为零根据题意 i i i应该排在前面当 P i , P j P_i,P_j Pi,Pj任意为1时可知一个停下的概率为零另一个不为零则大小关系可以确定。
然后讨论一般情况即二者全不为1时。可以证明 Q i ≥ Q j Q_i\ge{Q_j} Qi≥Qj。 Q i ≥ Q j ⇔ P 1 × P 2 × ⋯ × P i − 1 × ( 1 − P i ) × 1 1 − Π ≥ P 1 × P 2 × ⋯ × P i − 1 × P i × ⋯ × ( 1 − P j ) × 1 1 − Π ⇔ 1 − P i ≥ P i × ⋯ × ( 1 − P j ) \begin{aligned} Q_i\ge{Q_j} \Leftrightarrow{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}}\\ \Leftrightarrow{1-P_i}\ge{{P_i}\times\cdots\times{(1-P_j)}} \end{aligned} Qi≥Qj⇔P1×P2×⋯×Pi−1×(1−Pi)×1−Π1≥P1×P2×⋯×Pi−1×Pi×⋯×(1−Pj)×1−Π1⇔1−Pi≥Pi×⋯×(1−Pj) 对最后一个不等式的右边做缩放只需证明 1 − P i ≥ P i × ( 1 − P j ) (*) {1-P_i}\ge{{P_i}\times{(1-P_j)}}\tag{*} 1−Pi≥Pi×(1−Pj)(*) 即可
而 ( ∗ ) (*) (∗)等价于 1 − 2 P i P i P j ≥ 0 1-2P_iP_{i}P_j\ge{0} 1−2PiPiPj≥0
注意到题目给出的概率的形式当 P i P_i Pi不为1时必有 P i ≤ 1 2 P_i\le{\frac{1}{2}} Pi≤21成立。因此最后一个不等式是成立的从而可知 i i i要排在 j j j前面。
于是得到了一个不必计算概率的具体值就能排序的准则 s o r t sort 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 vectorint;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;
vectorllt P;llt myhash(const vectorllt 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);vectorllt ans(N);llt fenzi 1;for(int i0;iN;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;}vectorllt rank(N);for(int i0;iN;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
预处理加 D P DP DP。
注意到题目强调了每个用户是独立的因此首先做一个预处理计算出二维数组 U s e r 2 G a i n User2Gain User2Gain。 U s e r 2 G a i n [ i ] [ j ] User2Gain[i][j] User2Gain[i][j]表示如果给第 i i i个用户分配 j j j个空间其收益是多少。收益等于M - 缺页中断数。为什么要减一下计算收益因为笔者最开始弄错了以为是一个分组背包所以减一下刚好可以计算最大收益 U s e r 2 G a i n User2Gain User2Gain辅助以数据结构应该比较容易算出来。假设用户的请求数量平均分配为 M / K M/K M/K个则预处理时间应该是 O ( K × M k log M K ) O(K\times\frac{M}{k}\log{\frac{M}{K}}) O(K×kMlogKM)最差情况可能是 O ( M log M ) O(M\log{M}) O(MlogM)。不太确定这个复杂度对不对。
接下来 D P DP DP令 D i , j D_{i,j} Di,j表示前 i i i个用户分配 j j j个空间所能获得的最大收益则 D i , j max ( D i − 1 , k U s e r 2 G a i n [ i ] [ j − k ] , k ∈ [ 0 , j ] ) D_{i,j}\max(D_{i-1,k}User2Gain[i][j-k],k\in{[0,j]}) Di,jmax(Di−1,kUser2Gain[i][j−k],k∈[0,j])
算出最大收益再减回来就得到了最小的缺页数。
上述计算要三重循环看起来是立方的但实际上不是。考虑到每个用户平均分配到 M K \frac{M}{K} KM个空间因此第1个用户只需计算到 M K \frac{M}{K} KM第2个用户只需计算到 2 M K \frac{2M}{K} K2M第3个用户到 3 M K \frac{3M}{K} K3M……
实际计算次数是 ( M K 2 M K 3 M K ⋯ K M K ) × M K ≡ O ( M 2 ) \big(\frac{M}{K}\frac{2M}{K}\frac{3M}{K}\cdots\frac{KM}{K}\big)\times{\frac{M}{K}}\equiv{O(M^2)} (KMK2MK3M⋯KKM)×KM≡O(M2)
这似乎也是最差情况。同样不保证这个复杂度分析一定对感觉没错。
#include bits/stdc.h
using namespace std;#include bits/extc.h
using namespace __gnu_pbds;using llt long long;
using Real double;
using vi vectorint;
using pii pairint, int;__gnu_pbds::priority_queuepii, functionbool(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;
vectorpii Req;
vi Lisan;
vectorvi User2Gain;
vectorvi D;int proc(const vi req, int alloc){mapint, pairvi, int req2pos;for(int i0;ireq.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 i0;ireq.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 i1;in;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());vectorvi 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 i1;iK;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 user1;userK;user){const auto gain User2Gain[user];total gain.size() - 1;if(total N) total N;for(int space0;spacetotal;space){int ava min((int)gain.size() - 1, space);auto tmp D[user][space];for(int i0;iava;i){tmp max(tmp, D[user-1][space-i] gain[i]);}}}int ans M * K;const auto vec D[K];for(int i0;iN;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 i i个请求和第 j j j个请求是同一个页面则 j j j有可能命中缓存。取决于 i , j i,j i,j之间不同页面种类的数量与缓存空间的大小关系。为方便论述称不同页面种类的数量为间隔数。例如 1 , 2 , 3 , 4 , 2 , 3 , 4 , 1 1,2,3,4,2,3,4,1 1,2,3,4,2,3,4,1
上述两个页面1之间的间隔数为3所以当缓存空间大于3时第二个页面1必然是命中的否则必然有缺页中断。基于简单的贪心可知如果缓存空间为 K K K时某个 j j j请求会有缺页中断则缓存空间更小时必然也会有缺页中断。因此只需要对相邻的相等页面求出间隔数即可。这是一个典型的树状数组应用。
令 A A A数组是页面请求数组 B B B是一个树状数组。pre[v]是数值v在数组 A A 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 ) O(M\log{M}) O(MlogM)根据间隔数计算 A n s Ans Ans应该是 O ( M ) O(M) 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 vectorint;
using pii pairint, int;struct FenwickTree{ // 树状数组using value_type long long int;
using vec_type vectorvalue_type;int n;
vec_type c;FenwickTree() default;static int lowbit(int x){return x -x;}void init(int nn){this-c.assign((this-nnn) 1, 0);}void modify(int pos, value_type delta){for(int ipos;ithis-n;ilowbit(i)) this-c[i] delta;
}value_type query(int pos)const{value_type ans 0;for(int ipos;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);mapint, int cnt;vi pre(1000000 1, 0);for(int p,v,i0;iM;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 itcnt.rbegin(),jtcnt.rbegin(),etcnt.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 i1;iM;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;
}
