大致感想
第一次到场蓝桥杯A组比赛，感觉自己的水平确实还远远不敷。。。
这篇文章算是督促自己补完这次蓝桥杯A组省赛的全部题目吧。
题目文件链接：第十五届蓝桥杯C/C++A组蓝桥杯省赛题目
题目解法思路要么是自己赛场上想到的，要么是在网上看到的思路分享，因本人水平有限，并且如今还没有能检验代码精确与否的地方，确实也不知道自己有些想法是对是错，若出现错误请帮忙指正，若有好的解法或思路也希望能在批评区分享一下。
试题 A: 艺术与篮球
题目解法
这是一道填空题，比赛时我也没什么多的想法，填空题就都是用暴力写的。惋惜这道题我比赛的时间还是写错了，当时闰年的判定不会写。。。2000年是闰年没算进去导致差了一天，确实有点幽默了。
大致思路：罗列20000101到20240413之间的数字，去判定数字代表的日期是否合法，然后对数字换算成其对应汉字的笔画总数，统计大于50的有多少。
代码
- #include<bits/stdc++.h>
- using namespace std;
- int a[10]={13,1,2,3,5,4,4,2,2,2};
- //换算成汉字笔画总数，若大于50则计数
- int getsum(int x){
- int sum = 0;
- while(x){
- sum += a[x%10];
- x /= 10;
- }
- return sum>50?1:0;
- }
- int main(){
- int ans = 0;
- for(int i = 20000101; i <= 20240413; i++){
- int y = i/10000, m = i/100%100, d = i%100;
- if(m == 0 || m > 12 || d == 0){//不合法日期
- continue;
- }
- //2月的天数要看是否为闰年
- if(m == 2){
- //判断是否为闰年
- if(y%4==0 && y%100!=0 || y%400==0){
- if(d > 29)continue;
- }
- else{
- if(d > 28)continue;
- }
- }//4,6,9,11为小月
- else if(m==4||m==6||m==9||m==11){
- if(d>30)continue;
- }//其他为大月
- else{
- if(d>31)continue;
- }
- ans += getsum(i);
- }
- cout << ans << endl;
- }
试题 B: 五子棋对弈
题目解法
这也是一道填空题，我当时想的是也就5*5,25个格子，罗列2^25种环境也不是特别多，暴力也可以很快出答案以是当时也没多想，就用25位的01串代替这个5行5列的棋盘。然后判定每种环境是否合法。
假定白为1，黑为0，因为白棋先下，以是终局时白字数量应该为13，黑子数量为12，同时要求平手，每一行每一列还有两个对角线都不能有5个相同的棋子相连。
代码
- #include<bits/stdc++.h>
- using namespace std;
- int a[5][5];
- int check(int x){
- int bai = 0;//白子数量
- for(int i = 0; i < 5; i++){
- for(int j = 0; j < 5; j++){
- a[i][j] = x % 2;
- bai += a[i][j];
- x /= 2;
- }
- }
- if(bai != 13)return 0;
-
- for(int i = 0; i < 5; i++){
- int baix = 0;//每一行统计白子数量
- for(int j = 0 ; j < 5; j++){
- baix += a[i][j];
- }
- if(baix == 5 || baix == 0)return 0;
- }
- for(int i = 0; i < 5; i++){
- int baiy = 0;//每一列统计白子数量
- for(int j = 0 ; j < 5; j++){
- baiy += a[j][i];
- }
- if(baiy == 5 || baiy == 0)return 0;
- }
- //两个对角线判断下
- int bai1 = 0, bai2 = 0;
- for(int i = 0; i < 5; i++){
- bai1 += a[i][i];
- bai2 += a[i][4-i];
- }
- if(bai1 == 5 || bai1 == 0)return 0;
- if(bai2 == 5 || bai2 == 0)return 0;
- return 1;
- }
- int main(){
- int ans = 0;
- for(int i = 0; i < (1<<25); i++){
- ans += check(i);
- }
- cout << ans << endl;
- }
试题 C: 练习士兵
题目解法
我赛场上看到这题最初的想法是这样的：
要不要举行组团练习，就是看组团练习花费的s金兵比如今还要举行练习的每个人的个人花费练习总和sum谁大谁小，如果s小那就举行团队练习。只要盘算出举行了几次组团练习，也就可以算出最小总花费是多少。实在我感觉应该是有点贪心的做法吧。
看代码再具体说一下具体做法吧。
代码
- #include<bits/stdc++.h>
- using namespace std;
- const int N = 1e5+10;
- struct node{
- long long p, c;
- bool operator<(const node &b){return c < b.c;}
- }a[N];
- //sum应该用map表示的
- const int NS = 1e6+10;
- long long sum[NS];//sum[i]代表训练次数为i的各士兵的个人花费的金币总数之和
- int main(){
- int n;
- long long s;
- cin >> n >> s;
- long long sumall = 0;
- for(int i = 1; i <= n; i++){
- cin >> a[i].p >> a[i].c;
- sumall += a[i].p;//先统计出总和
- sum[a[i].c] += a[i].p;
- }
-
- //按照其训练次数升序排序
- sort(a+1, a+n+1);
-
- //贪心的去计算要几次组团训练才能得到最少的总金币数量·
- int pre = 0, now = a[1].c;
- for(int i = 1; i <= n; i++){
- //当次数发生变化时，要减去now次数士兵的花费总数
- if(now != a[i].c){
- sumall -= sum[now];
- pre = now;
- now = a[i].c;
- }
- //当组团训练s花费大于个人花费之和时退出循环
- if(s > sumall)break;
- }
-
- //因为在now的时候s>sumall，所以说pre表示的数其实就是最多的团建数量
- //计算答案
- long long ans = pre*s;
- for(int i = 1; i <= n; i++){
- if(a[i].c <= pre)continue;
- ans += a[i].p*(a[i].c - pre);
- }
- cout << ans << endl;
- }
呵呵，就算我这样的做法真的是对的，复盘的时间发现我比赛期间码还是写错了，乐。这题目是越补越心凉了。算了，重在参与。
试题 D: 团建
题目解法
科场上有想法，也写了代码，但出科场后忽然发现想法有点题目，估计这题也寄了吧。
去学学其他正解吧，之后返来补题。
在B站看了一位大佬的教学，感觉他的解法挺对的，学习了下他好多题目的解法，接下来补题的D、E都是用的他的思路写的代码。
视频链接：蓝桥杯C++A组思路分享
对于恣意结点，其儿子结点的权重互不相同题目中这个条件确实很紧张，当时在科场上我确实是想利用这个条件做这题，但当时没想清楚，导致科场上代码写的很有题目，条件也没利用好，还是头脑和本领不行、熟悉不敷深入导致的。
这种解法主要的基本思想：
实在就是充分利用对于恣意结点，其儿子结点的权重互不相同这个条件，由于一个结点没有相同的分支，实在两棵树只会走一遍，不会回头重复处理。
我们可以把大小为n的树作为主树，利用set先预处理出大小为m的树中每个节点儿子的信息，再去遍历大小为n的树，利用set已经从小到大排序好的单调性举行二分查找是否存在有大小相称的结点，这样去罗列其前缀，纪录最长前缀的长度。时间复杂度应该是O(nlog)没得跑，时间上应该不会出题目。
题目代码
- #include<bits/stdc++.h>
- using namespace std;
- const int N = 2e5+10;
- int c[N], d[N];
- vector<int>g1[N],g2[N];//g1代表大小为n的树,g2代表大小为m的树
- set<pair<int, int> >s[N];//存放g2每个结点所有儿子的信息pair第一位存大小，第二位存其编号
- //遍历大小为m的树，预处理大小为m的树的信息
- void dfs_m(int u, int f){
- //遍历到每一个点时，将其加入到他的父节点的集合上
- if(f)s[f].insert({d[u], u});//第一位存大小，第二位存其编号
- for(auto v:g2[u]){
- if(v == f)continue;
- dfs_m(v, u);
- }
- }
- int ans = 0;
- //以大小为n的树为主树进行遍历，统计答案
- //u为n树遍历到的结点，f为u的父节点，u_m为n树中u对应于m树中的结点
- void dfs(int u, int f, int u_m, int sum){
- ans = max(ans, sum);
- for(auto v:g1[u]){
- if(v == f)continue;
- //找到v在m树里大小相等对应的结点
- auto v_m = s[u_m].lower_bound({c[v], 0});//这边查找以第一位为主要关键字，第二位0肯定找不到的，所以找到第一位大小相等就返回其迭代器位置，只要判断找到的数字和查找的数字是否相等即可。
- if((*v_m).first != c[v])continue;//找不到就不用继续往下搜索了
- //找到了就继续往下搜索
- dfs(v, u, (*v_m).second, sum+1);
- }
- }
- int main(){
- //输入数据
- int n, m;
- cin >> n >> m;
- for(int i = 1; i <= n; i++)cin >> c[i];
- for(int i = 1; i <= m; i++)cin >> d[i];
- for(int i = 1; i < n; i++){
- int u, v;
- cin >> u >> v;
- g1[u].push_back(v);
- g1[v].push_back(u);
- }
- for(int i = 1; i < m; i++){
- int u, v;
- cin >> u >> v;
- g2[u].push_back(v);
- g2[v].push_back(u);
- }
- //预处理大小为m的树的信息
- dfs_m(1, 0);
- //遍历大小为n的树，计算最长前缀
- if(c[1] == d[1])
- dfs(1, 0, 1, 1);
-
- cout << ans << endl;
- return 0;
- }
set和pair一起用具体服从什么规则我也不是很懂，测试了几个数据，set内嵌套pair好像是默认以pair的第一位为第一关键字，第二位为第二关键字从小到大排序。
虽然我觉得这种解法挺对的，但这种解法的代码还是很依赖C++的STL的，不熟悉STL就算想到了这种思路估计想写出来也还是很困难的。
试题 E: 结果统计
题目解法
这个是真不会，科场上就没什么思路。
这题还是学的那位B站大佬解法。
视频链接：蓝桥杯C++A组思路分享
假设我们没学过什么概率的相干知识，这边就用题目里的公式先推导一下均值(盼望)和方差的关系：
v ‾ = ∑ i = 1 k v i k \overline{v}={\sum_{i=1}^kv_i\over k} v=k∑i=1kvi
σ 2 = ∑ i = 1 k ( v i − v ‾ ) 2 k \sigma^2={\sum_{i=1}^k{(v_i-\overline v)^2}\over k} σ2=k∑i=1k(vi−v)2
因此有：
σ 2 = ∑ i = 1 k ( v i − v ‾ ) 2 k = ∑ i = 1 k ( v i 2 − 2 v i v ‾ + v ‾ 2 ) k \sigma^2={\sum_{i=1}^k{(v_i-\overline v)^2}\over k} ={\sum_{i=1}^k{(v_i^2-2v_i\overline v+{\overline v}^2)}\over k} σ2=k∑i=1k(vi−v)2=k∑i=1k(vi2−2viv+v2)
其中 v ‾ \overline v v可以看成常数， v i v_i vi作为唯一变量
故公式可化为：
σ 2 = ∑ i = 1 k ( v i 2 − 2 v i v ‾ + v ‾ 2 ) k = ∑ i = 1 k v i 2 − 2 v ‾ ∑ i = 1 k v i + ∑ i = 1 k v ‾ 2 k = ∑ i = 1 k v i 2 − 2 v ‾ ∑ i = 1 k v i + k v ‾ 2 k = ∑ i = 1 k v i 2 k − 2 v ˉ v ˉ + v ˉ 2 = ∑ i = 1 k v i 2 k − v ˉ 2 \sigma^2 ={\sum_{i=1}^k{(v_i^2-2v_i\overline v+{\overline v}^2)}\over k} ={\sum_{i=1}^k{v_i^2}-2\overline v\sum_{i=1}^kv_i+\sum_{i=1}^k{\overline v^2}\over k} ={\sum_{i=1}^k{v_i^2}-2\overline v\sum_{i=1}^kv_i+k{\overline v^2}\over k} ={\sum_{i=1}^kv_i^2\over k}-2\bar v\bar v+\bar v^2 ={\sum_{i=1}^kv_i^2\over k}-\bar v^2 σ2=k∑i=1k(vi2−2viv+v2)=k∑i=1kvi2−2v∑i=1kvi+∑i=1kv2=k∑i=1kvi2−2v∑i=1kvi+kv2=k∑i=1kvi2−2vˉvˉ+vˉ2=k∑i=1kvi2−vˉ2
即可得方差=平方的均值-均值的平方
故本题解法大致思想：
1.二分得到满足要求的最小人数，二分的时间是log(n)的
2.每次二分后，举行排序，由于方差是随机变量与其盼望间的关系，即随机变量颠簸性的体现，前x数中的最小方差必然是这x个数在排序后以某一位置开始连续取k个值的方差，这个排序sort是nlog(n)的时间。(这里就不证明为什么排序后连续的k个数会是最符合要求的了，实在可以感性理解下，真要证明或允许以交换选择的连续的k个数里的一个数和k个数表面的数，方差应该是变大了。。。)
3.然后就是去找是否满足条件，继续二分。
由此可得时间复杂度大概是 O ( n l o g 2 ( n ) ) O(nlog^2(n)) O(nlog2(n))
应该是不会超时的，感觉这种做法挺对的，写起来也不是特别困难，可能一些细节还是要小心把，比如int、long long数字大小会不会超什么的。
题目代码
- #include<bits/stdc++.h>
- using namespace std;
- const int N = 1e5+10;
- int a[N];
- int main(){
- //输入数据
- int n, k, T;
- cin >> n >> k >> T;
- for(int i = 1; i <= n; i++)
- cin >> a[i];
- //答案具有单调性，二分最少需要前多少个学生
- double M = 1.0*T*k*k;//作为方差答案比较
- int l = 1, r = n, res = n+1;
- while(l <= r){
- int mid = (l+r)/2;
- //将数据进行转换
- double b[n+1], pf[n+1], sum[n+1], ans = 1e21;
- for(int i = 1; i <= mid; i++){
- b[i] = a[i];
- }
- //从小到大排序，便于计算其最小方差
- sort(b+1, b+mid+1);
- //记录平方前缀和、前缀和
- for(int i = 1; i <= mid; i++){
- pf[i] = pf[i-1] + b[i]*b[i];
- sum[i] = sum[i-1] + b[i];
- }
- for(int i = k; i <= mid; i++){
- double res = k*(pf[i] - pf[i-k]) - (sum[i] - sum[i-k])*(sum[i] - sum[i-k]);
- ans = min(ans, res);
- }
- if(ans < M){
- r = mid - 1;
- res = min(res, mid);
- }
- else l = mid + 1;
- }
- if(res == n+1)
- cout << -1 << endl;
- else
- cout << res << endl;
- }
试题 F: 因数计数
题目解法
这个也不会,我下意识的想去统计因子对，然后再去算四元组，但也没想到接下来怎么去做，科场上就打了个O(N^4)的暴力,暴力去罗列ijkl的环境是否符合条件。
在B站上看到大佬发的题解视频，学习了一下解法
参考解法视频：2024年蓝桥杯C/C++ A组AK代码带写题解
这题与H题封印宝石算是这次比赛难度最高的题目了吧
容斥解法
题目大意：给定 n n n个正整数的数组 a 1 a_1 a1到 a n a_n an，问有多少个有序四元组 ( i , j , k , l ) (i,j,k,l) (i,j,k,l)，满足 a i ∣ a k a_i|a_k ai∣ak且 a j ∣ a l a_j|a_l aj∣al，即 a i a_i ai和 a j a_j aj分别是 a k a_k ak和 a l a_l al的因子，其中 i ≠ j ≠ k ≠ l i\neq{j}\neq{k}\neq{l} i=j=k=l。
1.有序二元组的盘算
我们想要盘算满足题目的有序四元组的数量，直接盘算有序四元组是很困难的，这个有序四元组可以看成两个有序二元组的组合， ( i , j , k , l ) (i,j,k,l) (i,j,k,l) 可以分为 ( i , k ) (i,k) (i,k)和 ( j , l ) (j,l) (j,l)，其中满足 a i ∣ a k a_i|a_k ai∣ak且 a j ∣ a l a_j|a_l aj∣al。
由此，我们先把题目变得简单，可以先盘算有序二元组的数量再去盘算有序四元组的数量。
那我们实在可以先想想在这个数量为n的正整数数组里怎么盘算有序二元组 ( p , q ) (p,q) (p,q)的总数量
我们要盘算的有序二元组 ( p , q ) (p,q) (p,q)要满足的要求肯定是 p ≠ q p\neq{q} p=q且 a p ∣ a q a_p|a_q ap∣aq。
假设我们已经知道了在这个数组中一个数字 i i i他有多少个倍数 f ( i ) f(i) f(i)（假设这个 f ( i ) f(i) f(i)的数量是包含了i自己的,i也是i的倍数），那我们肯定可以知道以这个数字i为第一位，i的倍数为第二位组成的有序二元组的数量是多少，实在也就是 i ∗ ( f ( i ) − 1 ) i*(f(i)-1) i∗(f(i)−1)，（减去1是因为f(i)里已经被选了一个i作为二元组的第一位）。
那有序二元组的总数的求法实在就可以罗列每一个因子 i i i，然后去乘以这个因子的倍数的数量 f ( i ) f(i) f(i)。
因此我们这里约定接下来出现的全部 f ( i ) f(i) f(i)都是表示以i为因子的数字的总数, c n t ( i ) cnt(i) cnt(i)表示 i i i出现的次数。
由于数组中整数范围从1到100000，即因子大小也是这个范围，那么就可以得到数组中有序二元组的数量 a n s 2 = ∑ i = 1 100000 c n t ( i ) ∗ ( f ( i ) − 1 ) ans2 = \sum_{i=1}^{100000}cnt(i)*(f(i)-1) ans2=∑i=1100000cnt(i)∗(f(i)−1)。（对于cnt(i)个i来说当第一位都是从f(i)里拿了一个数字出来当第一位，那f(i)里的选择是少一个的，因此乘法的时间f(i)要减1）
举个例子帮助理解有序二元组总数的盘算
- n为6
- 下一行为数组元素
- 1 1 2 3 4 6
- 其中
- 约定f(i)表示以i为因子的数字的总数,cnt(i)表示i出现的次数。
- i = 1, cnt(1) = 2, f(1) = 6
- i = 2, cnt(2) = 1, f(2) = 3
- i = 3, cnt(3) = 1, f(3) = 2
- i = 4, cnt(4) = 1, f(4) = 1
- i = 5, cnt(5) = 0, f(5) = 0
- i = 6, cnt(6) = 1, f(5) = 1
- i = 7, cnt(7) = 0, f(7) = 0........ i = 100000, cnt(100000) = f(100000) =0
- 有序二元组的总数就是2*5+1*2+1*1+1*0+0*(-1)+1*0+0*(-1)+...+0*0 = 13
由上述的1.有序二元组的盘算中可以得到有序二元组的数量 a n s 2 = ∑ i = 1 100000 c n t ( i ) ∗ ( f ( i ) − 1 ) ans2 = \sum_{i=1}^{100000}cnt(i)*(f(i)-1) ans2=∑i=1100000cnt(i)∗(f(i)−1)，那么由这些有序二元组中恣意取出两个举行分列，必然可以得到四元组的数量，只是得到的四元组中可能有不符合条件的四元组。
由二元组数量ans2可以得到四元组数量 a n s = a n s 2 ∗ ( a s n 2 − 1 ) ans=ans2*(asn2-1) ans=ans2∗(asn2−1)，就是ans2里取出两个元素做分列。
假设通过有序二元组中两个不重复的 ( i , k ) 和 ( j , l ) ( i 和 k 不同时分别等于 j 和 l ) (i,k)和(j,l)(i和k不同时分别等于j和l) (i,k)和(j,l)(i和k不同时分别等于j和l)天生了ans个四元组 ( i , j , k , l ) (i,j,k,l) (i,j,k,l)
根据其四元组数量得到的方法来看，其中不合法的四元组有四类（1中算得的二元组必然是合法的，即 对于 ( i , k ) 和 ( j , l ) 有 i ≠ k 和 j ≠ l 对于(i,k)和(j,l)有i\neq{k}和j\neq{l} 对于(i,k)和(j,l)有i=k和j=l）：
- i = j i=j i=j时，此时必不可能 k = l k=l k=l(由于盘算四元组时取出的是两个不同二元组的分列)的四元组
- k = l k=l k=l时，此时必不可能 i = j i=j i=j(原因与上种环境相同)的四元组
- i = l i=l i=l时，由二元组前者为后者因子得，有 a j < = a l = a i < = a k a_j<=a_l=a_i<=a_k aj<=al=ai<=ak此时包含了 a j < = a k a_j<=a_k aj<=ak的四元组
- k = j k=j k=j时，有 a i < = a k = a j < = a l a_i<=a_k=a_j<=a_l ai<=ak=aj<=al此时包含了 a i < = a l a_i<=a_l ai<=al的四元组
接下来就正式要举行分析容斥的部分，也就是最难盘算对的部分了。
前两部分即 i = j i=j i=j时和 k = l k=l k=l时得到的四元组必然没有交集，这是由于一个是第一位的下标相称，第二位不等；另一个则是第一位下标不等，第二位相称，他们两个环境之间是不存在交集的。
如今就是容斥的分析重点了，后两部分即 i = l i=l i=l时和 k = j k=j k=j时得到的四元组是有交集的，这个交集就是两种环境下都会出现 a i = a j = a k = a l a_i=a_j=a_k=a_l ai=aj=ak=al的环境，而这种环境产生的交集是 i = l 且 k = j i=l且k=j i=l且k=j，这个交集在处理的时间是会被处理两次的，我们在处理总数时会减去他两次但实在我们只用总数减去这个交集一次，以是我们要加上一次 a i = a j = a k = a l a_i=a_j=a_k=a_l ai=aj=ak=al的环境的四元组的数量。
上面说后两部分即 i = l i=l i=l时和 k = j k=j k=j时得到的四元组只会出现 a i = a j = a k = a l a_i=a_j=a_k=a_l ai=aj=ak=al即 i = l 且 k = j i=l且k=j i=l且k=j时的交集，如果还是不理解可以这样来看：
由整除关系可知， i = l i=l i=l的部分有 a j < = a l = a i < = a k a_j<=a_l=a_i<=a_k aj<=al=ai<=ak，可以看成 a j = a k = a i = a l 和 a j < a k a_j=a_k=a_i=a_l和a_j<a_k aj=ak=ai=al和aj<ak的四元组
同理， k = j k=j k=j的部分有 a i < = a k = a j < = a l a_i<=a_k=a_j<=a_l ai<=ak=aj<=al此时包含了 a i = a l = a k = a j 和 a i < a l a_i=a_l=a_k=a_j和a_i<a_l ai=al=ak=aj和ai<al的四元组
显然， i = l i=l i=l时， a j < a k 即 j ≠ k a_j<a_k即j\neq{k} aj<ak即j=k的四元组与k=j时的四元组无交集， k = j k=j k=j时 a i < a l 即 i ≠ l a_i<a_l即i\neq{l} ai<al即i=l的四元组与 i = l i=l i=l时的四元组无交集，只有 a i = a j = a k = a l 即此时出现 i = l 且 k = j a_i=a_j=a_k=a_l即此时出现i=l且k=j ai=aj=ak=al即此时出现i=l且k=j时出现交集。
那么后两部分即 i = l i=l i=l时和 k = j k=j k=j时和前两部分即 i = j i=j i=j时和 k = l k=l k=l时有没有交集呢？起首第一部分和第二部分不可能出现 i = j 且 k = l i=j且k=l i=j且k=l的环境，其次，由我们从二元组去盘算四元组的方法角度来看当 i = j 时必然有 i ≠ k 和 l ≠ j 即 l ≠ i 和 k ≠ j i=j时必然有i\neq{k}和l\neq{j}即l\neq{i}和k\neq{j} i=j时必然有i=k和l=j即l=i和k=j从中可知 i = j i=j i=j时与后两部分就已经没有了交集，同理可知 k = l k=l k=l时也是和后两部分没有交集的，因此前两部分和后两部分是没有交集的。以是这里用到容斥的地方只有一个，就是后两部分中的 i = l 且 k = j i=l且k=j i=l且k=j的环境
好了，分析完了通过二元组盘算所得四元组中的非法部分之间的关系，那么我们就可以去统计非法部分的具体数量了。
3.非法四元组的盘算
由2.有序四元组的盘算中可知
其盘算的有序四元组 ( i , j , k , l ) (i,j,k,l) (i,j,k,l)数量中不合法的四元组有四类：
- i = j i=j i=j时，此时必不可能 k = l k=l k=l(由于盘算四元组时取出的是两个不同二元组的分列)的四元组
- k = l k=l k=l时，此时必不可能 i = j i=j i=j(原因与上种环境相同)的四元组
- i = l i=l i=l时，由二元组前者为后者因子得，有 a j < = a l = a i < = a k a_j<=a_l=a_i<=a_k aj<=al=ai<=ak此时包含了 a j < = a k a_j<=a_k aj<=ak的四元组
- k = j k=j k=j时，有 a i < = a k = a j < = a l a_i<=a_k=a_j<=a_l ai<=ak=aj<=al此时包含了 a i < = a l a_i<=a_l ai<=al的四元组
且其中只有第三部分和第四部分有交集 i = l 且 k = j i=l且k=j i=l且k=j的环境
我们通过分列组合的方法直接盘算非法四元组数量：
第一部分的盘算我们通过盘算 ( i , i , k , l ) (i,i,k,l) (i,i,k,l)的分列，即盘算在cnt(i)中取三个数字做分列的数量是多少，数量为： ∑ i = 1 100000 c n t ( i ) ∗ ( f ( i ) − 1 ) ∗ ( f ( i ) − 2 ) \sum_{i=1}^{100000}cnt(i)*(f(i)-1)*(f(i)-2) ∑i=1100000cnt(i)∗(f(i)−1)∗(f(i)−2)
第二部分的盘算我们通过盘算 ( i , j , k , k ) (i,j,k,k) (i,j,k,k)的分列，在盘算第二部分的时间发现如果我们知道k作为倍数时，数组中有多少个数是k的因子可以方便盘算，因此我们可以统计一下数组中有多少数字是k的因子，记为 g ( k ) g(k) g(k)，那么盘算得数量为： ∑ k = 1 100000 c n t ( k ) ∗ ( g ( k ) − 1 ) ∗ ( g ( k ) − 2 ) \sum_{k=1}^{100000}cnt(k)*(g(k)-1)*(g(k)-2) ∑k=1100000cnt(k)∗(g(k)−1)∗(g(k)−2)
第三部分的盘算我们通过盘算 ( i , j , k , i ) (i,j,k,i) (i,j,k,i)，即cnt(i)里取一个数i，k从i的倍数f(i)里取，j从i的因数个数g(i)里取，得数量为： ∑ i = 1 100000 c n t ( i ) ∗ ( f ( i ) − 1 ) ∗ ( g ( i ) − 1 ) \sum_{i=1}^{100000}cnt(i)*(f(i)-1)*(g(i)-1) ∑i=1100000cnt(i)∗(f(i)−1)∗(g(i)−1)
第四部分的盘算我们通过盘算 ( i , k , k , l ) (i,k,k,l) (i,k,k,l)，与三的方法雷同盘算，得数量为： ∑ k = 1 100000 c n t ( k ) ∗ ( g ( k ) − 1 ) ∗ ( f ( k ) − 1 ) \sum_{k=1}^{100000}cnt(k)*(g(k)-1)*(f(k)-1) ∑k=1100000cnt(k)∗(g(k)−1)∗(f(k)−1)
可知第三部分和第四部分盘算得到的数量相同
末了处理一下第三部分和第四部分的交集 i = l 且 k = j i=l且k=j i=l且k=j的环境，可知盘算的四元组为 ( i , k , k , i ) (i,k,k,i) (i,k,k,i)，此时有 a i = a j = a k = a l a_i=a_j=a_k=a_l ai=aj=ak=al即从 c n t ( i ) cnt(i) cnt(i)中取出两个数字分列，得数量为 ∑ i = 1 100000 c n t ( i ) ∗ ( c n t ( i ) − 1 ) \sum_{i=1}^{100000}cnt(i)*(cnt(i)-1) ∑i=1100000cnt(i)∗(cnt(i)−1)
4.符合答案的有序四元组的盘算
约定在数组中 i 的数量为 c n t ( i ) ， i 有 f ( i ) 个数字作为倍数 , i 有 g ( i ) 个数字作为因子 i的数量为cnt(i)，i有f(i)个数字作为倍数,i有g(i)个数字作为因子 i的数量为cnt(i)，i有f(i)个数字作为倍数,i有g(i)个数字作为因子
由3.非法四元组的盘算可得符合答案的有序四元组数量ans的盘算公式：
a n s 2 = ∑ i = 1 100000 c n t ( i ) ∗ ( f ( i ) − 1 ) ans2=\sum_{i=1}^{100000}cnt(i)*(f(i)-1) ans2=i=1∑100000cnt(i)∗(f(i)−1)
a n s = a n s 2 ∗ a n s 2 − ∑ i = 1 100000 c n t ( i ) ∗ ( f ( i ) − 1 ) ∗ ( f ( i ) − 2 ) − ∑ i = 1 100000 c n t ( i ) ∗ ( f ( i ) − 1 ) ∗ ( f ( i ) − 2 ) − 2 ∑ i = 1 100000 c n t ( i ) ∗ ( f ( i ) − 1 ) ∗ ( g ( i ) − 1 ) + ∑ i = 1 100000 c n t ( i ) ∗ ( c n t ( i ) − 1 ) ans=ans2*ans2-\sum_{i=1}^{100000}cnt(i)*(f(i)-1)*(f(i)-2)-\sum_{i=1}^{100000}cnt(i)*(f(i)-1)*(f(i)-2)-2\sum_{i=1}^{100000}cnt(i)*(f(i)-1)*(g(i)-1)+\sum_{i=1}^{100000}cnt(i)*(cnt(i)-1) ans=ans2∗ans2−i=1∑100000cnt(i)∗(f(i)−1)∗(f(i)−2)−i=1∑100000cnt(i)∗(f(i)−1)∗(f(i)−2)−2i=1∑100000cnt(i)∗(f(i)−1)∗(g(i)−1)+i=1∑100000cnt(i)∗(cnt(i)−1)
注意：
1.那么接下来就可以写代码了，但是这边考虑一下极限环境就可以发现1e5个1,那答案就是 A 100000 4 = 1 0 5 ∗ ( 1 0 5 − 1 ) ∗ ( 1 0 5 − 2 ) ∗ ( 1 0 5 − 3 ) A_{100000}^4=10^5*(10^5-1)*(10^5-2)*(10^5-3) A1000004=105∗(105−1)∗(105−2)∗(105−3)这个结果就当做 1 0 20 10^{20} 1020，这个肯定是爆long long的，这边我感觉过程盘算可以用double大概__int128举行，也不知道蓝桥杯支不支持__int128,反正接下来的代码就用__int128来写。
2.在得到 f ( i ) 和 g ( i ) f(i)和g(i) f(i)和g(i)时可以利用调和级数举行统计，调和级数 1 + 1 2 + 1 3 + . . . + 1 n 1+{1\over2}+{1\over3}+...+{1\over n} 1+21+31+...+n1他是近似于 l n ( n ) ln(n) ln(n)级别的，因此这也可得时间复杂度差不多在 O ( n l o g ( n ) ) O(nlog(n)) O(nlog(n))级别。
题目容斥解法代码
- #include<bits/stdc++.h>
- using namespace std;
- typedef __int128 ll;
- const int N = 1e5 + 10;
- //约定在数组中i的数量为cnt(i)，i有f(i)个数字作为倍数,i有g(i)个数字作为因子
- ll cnt[N], f[N], g[N];
- void print(ll x){
- if(x > 9)print(x/10);
- putchar(x%10+'0');
- }
-
- int main(){
- int n;
- cin >> n;
- for(int i = 1; i <= n; i++){
- int a;
- cin >> a;
- cnt[a]++;
- }
- for(int i = 1; i < N; i++){
- for(int j = i; j < N; j+=i){
- //f[i]为i的倍数个数
- f[i] += cnt[j];
- //g[j]为j的因子个数
- g[j] += cnt[i];
- }
- }
- //计算二元组
- ll ans = 0;
- for(int i = 1; i < N; i++){
- ans += cnt[i]*(f[i]-1);
- }
-
- //计算四元组数量
- ans = ans*(ans-1);
- //减去非法四元组(i,j,k,l)数量
- //i==j
- for(int i = 1; i < N; i++){
- ans -= cnt[i]*(f[i]-1)*(f[i]-2);
- }
- //k==l
- for(int i = 1; i < N; i++){
- ans -= cnt[i]*(g[i]-1)*(g[i]-2);
- }
- //i==l,j==k
- for(int i = 1; i < N; i++){
- ans -= 2*cnt[i]*(f[i]-1)*(g[i]-1);
- }
- //加回多减的交集
- for(int i = 1; i < N; i++){
- ans += cnt[i]*(cnt[i]-1);
- }
- print(ans);
- return 0;
- }
题目解法
这题科场上是有点想法的，我是先统计每个结点到根节点能买到的零食种类和数量，对于恣意两个节点s，t去求近来公共祖先，那两节点能买到的零食种类数量实在就是sum+sum[t]-2*sum[lca(s,t)]+c[lca(s,t)]
当然这个sum只是抽象的描述几种种类和各种类的数量，具体写法我是用一个sum[N][20]去罗列的，不知道行不行，虽然是O(qlog(n))，但好像时间可能也会有点超也说不定，之后再补我赛场上写的代码吧，有更好的解法也可以说下。
代码
- #include<bits/stdc++.h>
- using namespace std;
- const int N = 1e5+10;
- //dep为深度，fa[i][j]为i点向上跳2^j个结点所能到达的结点，sum[i][j]表示i结点到根节点的路上j种类零食的数量
- int c[N], dep[N], fa[N][21], sum[N][21];
- vector<int>g[N];
-
- void dfs(int u, int f){
- fa[u][0] = f;
- dep[u] = dep[f] + 1;
- sum[u][c[u]]++;
- for(int i = 1; i <= 20; i++){
- sum[u][i] += sum[f][i];
- fa[u][i] = fa[fa[u][i-1]][i-1];
- }
- for(auto v:g[u]){
- if(v == f)continue;
- dfs(v, u);
- }
- }
-
- int lca(int x, int y){
- //默认x深度低，即x在y上边
- if(dep[x] > dep[y])swap(x, y);
- int tmp = dep[y] - dep[x];
- for(int i = 0; i <= 20; i++){
- if(tmp & (1 << i))
- y = fa[y][i];
- }
- if(x == y)return x;
- //在两个分支上
- for(int i = 20; i >= 0; i--){
- if(fa[x][i] != fa[y][i]){
- x = fa[x][i];
- y = fa[y][i];
- }
- }
- return fa[x][0];
- }
-
- int main(){
- //输入数据
- int n, q;
- cin >> n >> q;
- for(int i = 1; i <= n; i++){
- cin >> c[i];
- }
- for(int i = 1; i < n; i++){
- int u, v;
- cin >> u >> v;
- g[u].push_back(v);
- g[v].push_back(u);
- }
- //预处理
- dfs(1, 0);
- while(q--){
- int s, t;
- cin >> s >> t;
- int fst = lca(s, t);
- int res[21] = {0};
- for(int i = 1; i <= 20; i++){
- res[i] = sum[s][i] + sum[t][i] - 2*sum[fst][i];
- }
- res[c[fst]]++;
- int ans = 0;
- for(int i = 1; i <= 20; i++)
- if(res[i])ans++;
- cout << ans << endl;
- }
- return 0;
- }
题目解法
科场上没怎么看这题，没什么思路，之后补题吧。
题解看的一个大佬发的贪心线段树代码。。。
参考解法链接：第15届蓝桥杯大学A组C++题解
贪心解法
题目大意：给定 n n n个数 a 1 , a 2 , . . . , a n a_1,a_2,...,a_n a1,a2,...,an，并且给定一个长度k，要求从 a a a数组转变成的 b b b数组字典序最大且恣意 b i 和 b i + 1 若都不为 − 1 则不允许相同 b_i和b_{i+1}若都不为-1则不允许相同 bi和bi+1若都不为−1则不允许相同，转变方法为：对恣意 b i b_i bi只能从后面k个数中，即 a i , a i + 1 , . . . , a m i n ( i + k , n ) a_i,a_{i+1},...,a_{min(i+k,n)} ai,ai+1,...,amin(i+k,n)中选取一个，若选取的为其中的 a j ( i < = j < = i + k ) a_j(i<=j<=i+k) aj(i<=j<=i+k)，则 k k k会变成 k − ( j − i ) k-(j-i) k−(j−i)（k会在b的选择中不断更新），且被选取后的数组不再允许被选取；若 b i b_i bi不举行选取，则 b i = − 1 b_i=-1 bi=−1。由此输出 b b b的最大字典序。
字典序的比较：显然此时比较的b数组长度都相称, b = [ 1 , 2 , 3 , 4 , 5 ] b={[1,2,3,4,5]} b=[1,2,3,4,5]大于 b = [ 1 , 2 , 3 , − 1 , 6 ] b={[1,2,3,-1,6]} b=[1,2,3,−1,6]，从左往右只要有一位大的数组则较大。
因为按照字典序比较的原因，我们可以选择贪心的解法，贪心的从高位到低位即从 b 1 b_1 b1往 b n b_n bn去选择每一位的最大值或次大值。
对于每一次选择可能有不同的 k k k(注意这里所描述的k不是给的初值，是不断更新的)，贪心选择 b i b_i bi的方式为：
1.区间 ( i , m i n ( i + k , n ) ) (i,min(i+k,n)) (i,min(i+k,n))，若 a i , a i + 1 , . . . , a m i n ( i + k , n ) a_i,a_{i+1},...,a_{min(i+k,n)} ai,ai+1,...,amin(i+k,n)中下标最小的最大值 a j a_j aj与 b i − i b_{i-i} bi−i的值不同则选择下标最小的最大值 a j a_j aj，更新k，标记 a j a_j aj已经被选择。（选下标最小是为了尽量使k的消耗小，可以使之后的选择更优）
2…区间 ( i , m i n ( i + k , n ) ) (i,min(i+k,n)) (i,min(i+k,n))，若 a i , a i + 1 , . . . , a m i n ( i + k , n ) a_i,a_{i+1},...,a_{min(i+k,n)} ai,ai+1,...,amin(i+k,n)中下标最小的最大值与 b i − i b_{i-i} bi−i的值相同，其中下标最小的次大值 a j 2 a_{j2} aj2与 b i − i b_{i-i} bi−i的值不同则选择 a j 2 a_{j2} aj2，更新k，标记 a j 2 a_{j2} aj2已经被选择。
3.若最大值和次大值都没有，就说明区间内的数已经都被选完了， b i b_i bi为-1。
由此方法贪心得到的b数组的字典序必然是最大的，也就是答案了。
举个例子：
- 7 8
- 8 7 9 5 6 9 5
- 七个数字,k=8
- 1.区间为(i,min(i+k,n))
- 从a1到a7中选择最近的最大值a3=9
- b1=9,k=8-(3-1)=6
- 8 7 9(已选择) 5 6 9 5
- 2.
- 因为要求相邻不同，则从a2到a7中选择最近的次大值a2=7
- b2=7,k=6-(2-2)=6
- 8 7(已选择) 9(已选择) 5 6 9 5
- 3.
- 从a3到a7中选择最近的最大值a6=9
- b3=9,k=6-(6-3)=3
- 8 7(已选择) 9(已选择) 5 6 9(已选择) 5
- 4.
- 从a4到a7中选择最近的最大值a5=6
- b4=6,k=3-(5-4)=2
- 8 7(已选择) 9(已选择) 5 6(已选择) 9(已选择) 5
- 5.
- 从a5到a7中选择最近的最大值a7=5
- b5=5,k=2-(7-5)=0
- 8 7(已选择) 9(已选择) 5(已选择) 6 9(已选择) 5(已选择)
- 6.
- 从a6到a6中选择最近的最大值，已被选择
- b6=-1,k=0
- 8 7(已选择) 9(已选择) 5(已选择) 6 9(已选择) 5(已选择)
- 7.
- 从a7到a7中选择最近的最大值，已被选择
- b7=-1,k=0
- 8 7(已选择) 9(已选择) 5(已选择) 6 9(已选择) 5(已选择)
- 由此得到最大字典序b={9,7,9,6,5,-1,-1}
利用这种方法实在就是相称于在做n次区间查询最大值和次大值，并且陪同着单点修改。采用线段树来举行单点修改和区间查询，时间复杂度在 O ( n l o g n ) O(nlogn) O(nlogn)。
线段树学习链接：线段树-OI Wiki
贪心线段树代码
- #include<bits/stdc++.h>
- using namespace std;
-
- const int N = 1e5+10;
- //定义线段树结点维护最大值和次大值
- //maxw为最大值，maxn为最大值的下标
- //maxw2为次大值，maxn2为次大值的下标
- struct node{
- int maxw,maxn,maxw2,maxn2;
- }t[4*N];//线段树建树需4倍空间
- int a[N], b[N];
-
- //方便维护，定义max()函数方便维护结点信息
- struct node max(struct node p1, struct node p2){
- struct node ans;
- //维护区间内下标最小的最大值和次大值信息
- //维护最大值
- if(p1.maxw > p2.maxw){
- ans.maxw = p1.maxw,ans.maxn = p1.maxn;
- //维护次大值
- //p1最大值大于p2时，比较p1次大值和p2最大值
- if(p1.maxw2>p2.maxw){
- ans.maxw2=p1.maxw2,ans.maxn2=p1.maxn2;
- }
- else if(p1.maxw2 < p2.maxw){
- ans.maxw2=p2.maxw,ans.maxn2=p2.maxn;
- }
- else{
- ans.maxw2=p1.maxw2,ans.maxn2=min(p1.maxn2,p2.maxn);
- }
- }
- else if(p1.maxw < p2.maxw){
- ans.maxw = p2.maxw,ans.maxn = p2.maxn;
- //维护次大值
- //p1最大值小于p2时，比较p2次大值和p1最大值
- if(p2.maxw2>p1.maxw){
- ans.maxw2=p2.maxw2,ans.maxn2=p2.maxn2;
- }
- else if(p2.maxw2 < p1.maxw){
- ans.maxw2=p1.maxw,ans.maxn2=p1.maxn;
- }
- else{
- ans.maxw2=p2.maxw2,ans.maxn2=min(p2.maxn2,p1.maxn);
- }
- }
- else{
- //当两个最大值相同的时候
- //比较两个次大值，确保次大值和最大值不同
- ans.maxw = p1.maxw,ans.maxn = p1.maxn;
- if(p1.maxw2 < p2.maxw2){
- ans.maxw2=p2.maxw2,ans.maxn2=p2.maxn2;
- }
- else if(p1.maxw2 > p2.maxw2){
- ans.maxw2=p1.maxw2,ans.maxn2=p1.maxn2;
- }
- else{
- ans.maxw2=p1.maxw2,ans.maxn2=min(p1.maxn2,p2.maxn2);
- }
- }
- return ans;
- }
- //建树
- void build(int l, int r, int m){//l，r左右区间，m为当前节点编号
- if(l==r){
- t[m].maxw=a[l];
- t[m].maxn=l;
- return;
- }
- int mid = (l+r)/2;
- build(l, mid, 2*m);//左子节点
- build(mid+1, r, 2*m+1);//右子节点
- //由左右子树向上传递最大值信息
- t[m] = max(t[2*m],t[2*m+1]);
- }
- //查找区间内满足答案
- struct node getsum(int L, int R, int l, int r, int m){
- //[L,R]为查询区间，[l,r]为查找过程中当前节点包含区间，m为当前节点编号
- if(l >= L && r <= R){
- return t[m];
- }
- int mid = l + (r-l)/2;
- struct node ans={};
- //左儿子代表区间[l,mid]与查询区间[L,R]有交集，则递归查询左儿子
- if(mid >= L)
- ans = max(ans, getsum(L,R,l,mid,2*m));
- //右儿子代表区间[mid+1,r]与查询区间[L,R]有交集，则递归查询右儿子
- if(mid < R)
- ans = max(ans, getsum(L,R,mid+1,r,2*m+1));
- return ans;
- }
- //单点更新
- void update(int l, int r, int x, int m){
- if(l == r){
- t[m] = {};
- return;
- }
- int mid = (l+r)/2;
- //左儿子代表区间[l,mid]与查询区间[x,x]有交集，则递归查询左儿子
- if(mid >= x)
- update(l, mid, x, 2*m);
- //右儿子代表区间[mid+1,r]与查询区间[x,x]有交集，则递归查询右儿子
- if(mid < x)
- update(mid+1, r, x, 2*m+1);
- t[m] = max(t[2*m], t[2*m+1]);
- }
-
- int main(){
- //输入数据
- int n,k;
- cin >> n >> k;
- for(int i = 1; i <= n; i++){
- cin >> a[i];
- }
- //建树
- build(1,n,1);
- for(int i = 1; i <= n; i++){
- struct node p = getsum(i, i+k, 1, n, 1);
- //前一个数字和现在的最大值不相同
- if(b[i-1] != p.maxw){
- //若存在最大值
- if(p.maxw){
- b[i] = p.maxw;
- k -= p.maxn - i;
- update(1, n, p.maxn, 1);
- }
- else{//没有最大值了，也就是没有可以选择的数字了
- b[i] = -1;
- }
- }
- else{//前一个数字和现在的最大值相同
- //选择次大值，若存在次大值
- if(p.maxw2){
- b[i] = p.maxw2;
- k -= p.maxn2 - i;
- update(1, n, p.maxn2, 1);
- }
- else{
- b[i] = -1;
- }
- }
- }
- //输出答案
- for(int i = 1; i <= n; i++){
- cout << b[i] << ' ';
- }
- cout << endl;
- return 0;
- }
实在说真话，虽然我没学过线段树，但这好像就是最最底子的线段树的使用，也是最简单的单点修
改和区间查询，也可能是大佬的理解比较深刻，代码写的简单吧，或许这道题甚至可以当做线段树入门题加深理解吧。。。
总结
一道题可能也有很多解法，但我这边也不再纪录了，补题就这样算补完了吧。。。
实在也没什么好总结的，这些题目赛场上想不出来那就是想不出来，接触的知识点无论是广度还是深度实在都不敷，就算想出来了一些题目，但代码打错了，那也是说明水平确实不敷，细节考虑不到位，虽然OI赛制确实恶心人，但确实反映了一些题目吧。。。
实在还是收获很多的，希望自己以后写题目也能像这次蓝桥杯比赛后一样坚持补题吧，毕竟这种算法比赛代码水平的进步还是在于补题嘛。。。
末了预祝各人蓝桥杯得到抱负结果吧。
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。 |
