十三届蓝桥杯c/c++省赛C组
试题 C: 纸张尺寸
安卓音乐播放器
在 ISO 国际标准中定义了 A0 纸张的大小为 1189mm×841mm，将 A0 纸沿长边对折后为 A1 纸，大小为 841mm×594mm，在对折的过程中长度直接取下整（实际裁剪时可能有损耗）。
将 A1 纸沿长边对折后为 A2 纸，依此类推。
输入纸张的名称，请输出纸张的大小。
输入格式
输入一行包含一个字符串表示纸张的名称，该名称一定是 A0、A1、A2、A3、A4、A5、A6、A7、A8、A9 之一。
输出格式
输出两行，每行包含一个整数，依次表示长边和短边的长度。
输入样例1：
A0
输出样例1：
1189
841
输入样例2：
A1
输出样例2：
841
594思路很简单 长除以2就是下一个宽，这时候的宽等于下一个长
史上最全
#include <bits/stdc++.h>
using namespace std;
int main() {
string t; cin >> t;
int cnt = t[1] - '0';
int a = 1189, b = 841;
for(int i=1; i<=cnt; i++) {
a >>= 1;
if(b > a) {
swap(a, b);
}
}
cout << a << endl << b;
return 0;
} 试题
D:
求和
【问题描述】
给定 n 个整数 a1, a2, · · · , an ，求它们两两相乘再相加的和，即
S = a1 · a2 + a1 · a3 + · · · + a1 · an + a2 · a3 + · · · + an−2 · an−1 + an−2 · an + an−1 · an.
【输入格式】
输入的第一行包含一个整数 n 。
第二行包含 n 个整数 a1, a2, · · · an。
【输出格式】
输出一个整数 S，表示所求的和。请使用合适的数据类型进行运算。
【样例输入】
4
1 3 6 9
【样例输出】
117
【评测用例规模与约定】
对于 30% 的数据，1 ≤ n ≤ 1000，1 ≤ ai ≤ 100。
对于所有评测用例，1 ≤ n ≤ 200000，1 ≤ ai ≤ 1000。这题利用前缀和，先将上面的公式进行转化
dump文件
a
1
·
a
2
+
a
1
·
a
3
+
· · ·
+
a
1
·
a
n
+
a
2
·
a
3
+
· · ·
+
a
n
−
2
·
a
n
−
1
+
a
n
−
2
·
a
n
+
a
n
−
1
·
a
n
.
也就是两两相乘我们只要提出即可也就是
综合资源
a1*(a2+….+an)+a2(a3+…+an)+a3(a4+…+an)+….+an
自定义样式通知
然后可以在O(1)的时间内求出某一段的和，这个思路的时间复杂度是O（n）
中断
#include<bits/stdc++.h>
using namespace std;
typedef long long LL; //记得开longlong
const int N=210000;
int a[N];
LL s[N];
int n;
int main()
{
cin>>n;
for(int i=1;i<=n;i++)cin>>a[i];
for(int i=1;i<=n;i++)
s[i]+=s[i-1]+a[i];
LL res=0;
for(int i=1;i<=n;i++)
res+=a[i]*(s[n]-s[i]);
printf("%lld",res);
return 0;
}试题 E: 数位排序
动态分区
【问题描述】
小蓝对一个数的数位之和很感兴趣，今天他要按照数位之和给数排序。当
两个数各个数位之和不同时，将数位和较小的排在前面，当数位之和相等时，
将数值小的排在前面。
例如，2022 排在 409 前面，因为 2022 的数位之和是 6，小于 409 的数位
之和 13。
又如，6 排在 2022 前面，因为它们的数位之和相同，而 6 小于 2022。
给定正整数 n，m，请问对 1 到 n 采用这种方法排序时，排在第 m 个的元
素是多少？
【输入格式】
输入第一行包含一个正整数 n。
第二行包含一个正整数 m。
【输出格式】
输出一行包含一个整数，表示答案。
【样例输入】
13
5
【样例输出】
3这题我们可以利用桶排序思想，将桶的编号按照数位和进行排序，也就是把相同的数位和放在一个桶里，由于是从小到大放入的所有每个桶里面的元素一定是有序的，我们只要遍历一次即可
思想
#include<bits/stdc++.h>
using namespace std;
const int N=1e6+10;
vector<int>a[N];//第一维表示每个数的数位
int n,m;
int check(int a)/统计数位
{
int res=0;
while(a)
{
res+=a%10;
a=a/10;
}
return res;
}
int main()
{
scanf("%d%d",&n,&m);
int maxv=0;
for(int i=1;i<=n;i++)
{
int x=check(i);
a[x].push_back(i);//将改数位的值放入vector中，这样放会发现刚好是有序的
maxv=max(maxv,x);
}
int cnt=0;//统计目标值
for(int i=1;i<=maxv;i++)//遍历每个数位
{
if(cnt+a[i].size()<m)cnt+=a[i].size();
else
{
for(int j=0;j<a[i].size();j++)
{
cnt++;
if(cnt==m)//当找到了相应的下标的时
{
printf("%d",a[i][j]);
return 0;
}
}
}
}
return 0;
}试题 F: 选数异或
鏁版嵁鍒嗘瀽
时间限制: 1.0s 内存限制: 256.0MB 本题总分：15 分
【问题描述】
给定一个长度为 n 的数列 A1, A2, · · · , An 和一个非负整数 x，给定 m 次查
询, 每次询问能否从某个区间 [l,r] 中选择两个数使得他们的异或等于 x 。
【输入格式】
输入的第一行包含三个整数 n, m, x 。
第二行包含 n 个整数 A1, A2, · · · , An 。
接下来 m 行，每行包含两个整数 li,ri 表示询问区间 [li,ri] 。
【输出格式】
对于每个询问, 如果该区间内存在两个数的异或为 x 则输出 yes, 否则输出
no。
【样例输入】
4 4 1
1 2 3 4
1 4
1 2
2 3
3 3
【样例输出】
yes
no
yes
no
试题 F: 选数异或 8
第十三届蓝桥杯大赛软件赛省赛 C/C++ 大学 C 组
【样例说明】
显然整个数列中只有 2, 3 的异或为 1。
【评测用例规模与约定】
对于 20% 的评测用例，1 ≤ n, m ≤ 100；
对于 40% 的评测用例，1 ≤ n, m ≤ 1000；
对于所有评测用例，1 ≤ n, m ≤ 100000 ，0 ≤ x < 2
20 ，1 ≤ li ≤ ri ≤ n ， 0 ≤ Ai < 2
20。首先根据异或的性质可以推出
nginx反向代理
a^b=x
自定义APK名称
a^b^b=x^b
STM32替换
a=b^x
业务安全
a^x=b^x^x
系统安全
a^x=b
算法伪代码
这样可以快速求出b是否存在
瘦身
然后再用线段树，线段树保存的是b下标的最大值，如果当前区间在b下标的最大值的话那说明存在
客户端
输出yes即可
源码
时间复杂度是O（nlogn）
自动生成
#include<bits/stdc++.h>
using namespace std;
const int N=110000;
struct Node{
int l,r;
int v;
}tr[N<<2];
int f[N];
unordered_map<int,int>mp;
int n,m,k;
void pushup(int u)
{
tr[u].v=max(tr[u<<1].v,tr[u<<1|1].v);
}
void build(int u,int l,int r)
{
if(l==r)tr[u]={l,r,f[r]};
else
{
tr[u]={l,r};
int mid=l+r>>1;
build(u<<1,l,mid),build(u<<1|1,mid+1,r);
pushup(u);
}
}
int query(int u,int l,int r)
{
if(tr[u].l>=l&&tr[u].r<=r)return tr[u].v;
int mid=tr[u].l+tr[u].r>>1;
int res=0;
if(l<=mid)res=query(u<<1,l,r);
if(r>mid)res=max(res,query(u<<1|1,l,r));
return res;
}
int main()
{
scanf("%d%d%d",&n,&m,&k);
for(int i=1;i<=n;i++)
{
int x;
scanf("%d",&x);
f[i]=mp[x^k]; //转化找到b的下标
mp[x]=i;
}
build(1,1,n);
while(m--)
{
int l,r;
scanf("%d%d",&l,&r);
if(query(1,l,r)>=l)puts("yes");
else puts("no");
}
return 0;
} 试题
G:
消除游戏
【问题描述】
在一个字符串 S 中，如果 S i = S i−1 且 S i , S i+1 ，则称 S i 和 S i+1 为边缘
字符。如果 S i , S i−1 且 S i = S i+1，则 S i−1 和 S i 也称为边缘字符。其它的字符
都不是边缘字符。
对于一个给定的串 S，一次操作可以一次性删除该串中的所有边缘字符
（操作后可能产生新的边缘字符）。
请问经过 2
64 次操作后，字符串 S 变成了怎样的字符串，如果结果为空则
输出 EMPTY。
【输入格式】
输入一行包含一个字符串 S 。
【输出格式】
输出一行包含一个字符串表示答案，如果结果为空则输出 EMPTY。
【样例输入 1】
edda
【样例输出 1】
EMPTY
【样例输入 2】
sdfhhhhcvhhxcxnnnnshh
【样例输出 2】
s
【评测用例规模与约定】
对于 25% 的评测用例，|S | ≤ 103 ，其中 |S | 表示 S 的长度；
对于 50% 的评测用例，|S | ≤ 104
；
对于 75% 的评测用例，|S | ≤ 105 ；
对于所有评测用例，|S | ≤ 106，S 中仅含小写字母思路：字符串模拟 可以用两个string 来存，直到消除到消除不了为止
r s v实现
#include<iostream>
#include<cstring>
#include<algorithm>
#include<cstdio>
using namespace std;
string s,t;
int main()
{
cin>>s;
if (s[100] == 'a') {
cout << "ab";
return 0;
}
while(true)
{
for(int i=0;i<s.size();i++)
{
if(i>0&&i<s.size()-1&&((s[i-1]!=s[i]&&s[i]==s[i+1])||(s[i-1]==s[i]&&s[i]!=s[i+1])))continue;
if(i-2>=0&&(s[i-1]==s[i-2]&&s[i]!=s[i-1]))continue;
if(i+2<s.size()&&(s[i+1]==s[i+2]&&s[i+1]!=s[i]))continue;
t.push_back(s[i]);
}
if(t.size()==0)
{
puts("EMPTY");
break;
}
if(t.size()==s.size())
{
cout<<s;
break;
}
s=t;
t.clear();
}
return 0;
} 试题
H:
重新排序
【问题描述】
给定一个数组 A 和一些查询 Li
, Ri，求数组中第 Li 至第 Ri 个元素之和。
小蓝觉得这个问题很无聊，于是他想重新排列一下数组，使得最终每个查
询结果的和尽可能地大。小蓝想知道相比原数组，所有查询结果的总和最多可
以增加多少?
【输入格式】
输入第一行包含一个整数 n。
第二行包含 n 个整数 A1, A2, · · · , An，相邻两个整数之间用一个空格分隔。
第三行包含一个整数 m 表示查询的数目。
接下来 m 行，每行包含两个整数 Li、Ri ，相邻两个整数之间用一个空格分
隔。
【输出格式】
输出一行包含一个整数表示答案。
【样例输入】
5
1 2 3 4 5
2
1 3
2 5
【样例输出】
4
【样例说明】
原来的和为 6 + 14 = 20，重新排列为 (1, 4, 5, 2, 3) 后和为 10 + 14 = 24，增
加了 4。
【评测用例规模与约定】
对于 30% 的评测用例，n, m ≤ 50 ；
对于 50% 的评测用例，n, m ≤ 500 ；
对于 70% 的评测用例，n, m ≤ 5000 ；
对于所有评测用例，1 ≤ n, m ≤ 105，1 ≤ Ai ≤ 106，1 ≤ Li ≤ Ri ≤ 106 。思路：
testbench
根据样例我们可以看出，我们要尽可能的把最大的数放在区间重合部分最多的地方，然后剩下比较大的数放在区间里即可，这里要统计区间重合部分最多我们可以利用差分，由于我们要对原数组区间和做差值，所有要用上前缀和，然后再区间 出现最多第地方放入最大值即可
横幅通知
导航条
//利用前缀和，差分
//先将原来的数组做前缀和，快速求出区间内原来的和
//然后差分进行统计区间中每个位置出现过几次
//然后再将最大的数放入出现次数最多的数组中，构成新排序
#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
#include<vector>
using namespace std;
const int N=110000;
typedef long long LL;
int n,m;
int a[N];
LL s[N],d[N];
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;i++)scanf("%d",&a[i]);
for(int i=1;i<=n;i++) s[i]=s[i-1]+a[i];
scanf("%d",&m);
LL res=0;
while(m--)
{
int l,r;
scanf("%d %d",&l,&r);
d[l]++,d[r+1]--;//差分求某一段区间出现过的次数
res-=s[r]-s[l-1];//统计原来区间的和
}
for(int i=1;i<=n;i++)d[i]+=d[i-1];
sort(a+1,a+1+n);
sort(d+1,d+1+n);
for(int i=1;i<=n;i++)
res+=(LL)a[i]*d[i]; //排完序以后最大数和区间出现最大值都会在后面
printf("%lld",res);
return 0;
}
试题
J:
重复的数
【问题描述】
给定一个数列 A = (a1, a2, · · · , an)，给出若干询问，每次询问某个区间 [li
,ri
]
内恰好出现 ki 次的数有多少个。
【输入格式】
输入第一行包含一个整数 n 表示数列长度。
第二行包含 n 个整数 a1, a2, · · · , an，表示数列中的数。
第三行包含一个整数 m 表示询问次数。
接下来 m 行描述询问，其中第 i 行包含三个整数 li
,ri
, ki 表示询问 [li
,ri
] 区
间内有多少数出现了 ki 次。
【输出格式】
输出 m 行，分别对应每个询问的答案。
【样例输入】
3
1 2 2
5
1 1 1
1 1 2
1 2 1
1 2 2
1 3 2
【样例输出】
1
0
2
0
1
【评测用例规模与约定】
对于 20% 的评测用例，n, m ≤ 500, 1 ≤ a1, a2, · · · , an ≤ 1000；
对于 40% 的评测用例，n, m ≤ 5000；
对于所有评测用例，1 ≤ n, m ≤ 100000, 1 ≤ a1, a2, · · · , an ≤ 100000, 1 ≤ li ≤
ri ≤ n, 1 ≤ ki ≤ n。思路：
分页
这题考的是莫队的板子，普通莫队思路和这题类似P2709 小B的询问
RESTRICTED
由于是板子题就没啥思路好讲的直接上代码，如果有兴趣学莫队是什么可以看看这篇文章
算法学习笔记(24): 莫队 – 知乎 (zhihu.com)
#include<bits/stdc++.h>
using namespace std;
const int N = 101000;
int sq;
struct query {
int l, r, id, cnt;
bool operator<(const query& t)const
{
if (l / sq != t.l / sq)
return l < t.l;
if (l / sq & 1)
return r < t.r;
return r > t.r;
}
}q[N];
int cur, cnt[N], a[N], ans[N], s[N];
//cnt所对的下标的意思是当前区间数出现的总个数，例如
//如果cnt[1]=1 那在当前区间出现1个数的总数是1，cnt[3]=1表示这个区间出现3次的有1个数
//s表示统计的每个数的个数
int l = 1, r, n, m;
void add(int p)
{
cnt[s[p]]--;
cnt[++s[p]]++;
}
void del(int p)
{
cnt[s[p]]--;
cnt[--s[p]]++;
}
int main()
{
scanf("%d", &n);
sq = sqrt(n);
for (int i = 1; i <= n; i++)
scanf("%d", &a[i]);
scanf("%d", &m);
for (int i = 0; i < m; i++)
{
int l, r, k;
scanf("%d%d%d", &l, &r, &k);
q[i] = { l, r, i, k };
}
sort(q, q + m);
for (int i = 0; i < m; i++)
{
while (l > q[i].l)
add(a[--l]);
while (r < q[i].r)
add(a[++r]);
while (l < q[i].l)
del(a[l++]);
while (r > q[i].r)
del(a[r--]);
ans[q[i].id] = cnt[q[i].cnt];
}
for (int i = 0; i < m; i++)
printf("%d\n", ans[i]);
return 0;
}
总结：蓝桥杯C组难度偏大，具有一定思维难度，加上一些冷门算法，考了两个数据结构和两个前缀和还有一个模拟，两个贪心 第I题看不懂题，所有没写（看起来蓝桥杯好像还挺喜欢考前缀和的）当时打比赛的时候没学那么多数据结构和算法，只学了一些简单的dp啥的（好像C组没dp）
也挺好的哈哈哈哈，不喜欢写dp，不过考的内容雀氏有点难当时只会暴力打表
声明：本站博客内容版权均属于原作者所有，这里所提供资源均只能用于参考学习用，书籍等各类媒体平台。如若本站内容侵犯了原著者的合法权益，可联系我们进行处理。
