第一题《排列字母》
【问题描述】
小蓝要把一个字符串中的字母按其在字母表中的顺序排列。
例如，LANQIAO 排列后为AAILNOQ。
又如，GOODGOODSTUDYDAYDAYUP 排列后为AADDDDDGGOOOOPSTUUYYY。
请问对于以下字符串，排列之后字符串是什么?
WHERETHEREISAWILLTHEREISAWAY
【答案提交】
本题为填空题，只需要算出结果后，在代码中使用输出语句将所填结果输出即可。
【思路】简单模拟
【代码】
#include <iostream>
#include<algorithm>
using namespace std;
int main()
{
string s;
cin >> s;
sort(s.begin(),s.end());
cout << s;
return 0;
}【答案】
第二题《特殊时间》
【问题描述】
2022年2月22日22:20是一个很有意义的时间,年份为2022,由3个2和1个0组成,如果将月和日写成
4位,为0222,也是由3个2和1个0组成,如果将时间中的时和分写成4位,还是由3个2和1个0组成。
小蓝对这样的时间很感兴趣,他还找到了其它类似的例子,比如 111年10月11日01:11,2202年2月22日
22:02等等.
请问,总共有多少个时间是这种年份写成4位、月日写成4位、时间写成4位后由3个一种数字和1个另一种数字组成。注意 1111 年11月11日11:11不算，因为它里面没有两种数字。
【答案提交】
本题为填空题，只需要算出结果后，在代码中使用输出语句将所填结果输出即可。
【思路】模拟
【代码】
1月：0111 4*1*4=16
2月：0222 4*1*4=16
3月——9月：0 日最大不会超过31日，也不能出现00日的情况。
10月：1011 4*1*4=16
11月：1101 1110 1112 1113 1114 1115 1116 1117 1118 1119 1121
4*1*4 4*1*4 4*1*4 4*1*3 4*1*3 4*1*3 4*1*2 4*1*2 4*1*2 4*1*2 4*1*4 =16+16+16+12+12+12+8+8+8+8+16=64+36+32=132
12月：1211 1222 4*1*4 + 4*1*4 =32
总 ： 16+16+16+132+32 = 212;【答案】
第三题《纸张尺寸》
【问题描述】
在 ISO 国际标准中定义了 A0 纸张的大小为 1189mm×841mm，将 A0 纸沿长边对折后为 A1纸，大小为 841mm×594mm，在对折的过程中长度直接取下整（实际裁剪时可能有损耗）。
将 A1 纸沿长边对折后为 A2 纸，依此类推。
输入纸张的名称，请输出纸张的大小。
【输入格式】
输入一行包含一个字符串表示纸张的名称，该名称一定是 A0、A1、A2、A3、A4、A5、A6、A7、A8、A9 之一。
【输出格式】
输出两行，每行包含一个整数，依次表示长边和短边的长度。
【输入样例1】
【输出样例1】
【输入样例2】
【输出样例2】
【思路】简单模拟
【代码】
#include<iostream>
using namespace std;
int main(){
string str;
cin >> str;
int length = 1189,width=841;
int n = str[1] - '0';
while(n--){
if(length > width) length /= 2;
else width /= 2;
}
if(length > width){
printf("%d\n%d",length,width);
}else{
printf("%d\n%d",width,length);
}
return 0;
}第四题《求和》
【问题描述】
给定 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，表示所求的和。
请使用合适的数据类型进行运算。
【数据范围】
对于 30% 的数据，1≤n≤1000，1≤ai≤100。
对于所有评测用例，1≤n≤200000，1≤ai≤1000。
【输入样例】
【输出样例】
【思路】简单模拟 / 前缀和
【代码】
#include<iostream>
using namespace std;
const int N = 200010;
int a[N],n;
long long res;
int main(){
long long s = 0;
scanf("%d",&n);
for(int i = 1;i<=n;i++) {
scanf("%d",&a[i]);
s += a[i];
}
for(int i = 1;i<n;i++){
s -= a[i];
res += a[i] * s;
}
printf("%lld",res);
return 0;
}第五题《数位排序》
【问题描述】
小蓝对一个数的数位之和很感兴趣，今天他要按照数位之和给数排序。
当两个数各个数位之和不同时，将数位和较小的排在前面，当数位之和相等时，将数值小的排在前面。
例如，2022 排在 409 前面，因为 2022 的数位之和是 6，小于 409 的数位之和 13。
又如，6 排在 2022 前面，因为它们的数位之和相同，而 6 小于 2022。
给定正整数 n，m，请问对 1 到 n 采用这种方法排序时，排在第 m 个的元素是多少？
【输入格式】
输入第一行包含一个正整数 n。
第二行包含一个正整数 m。
【输出格式】
输出一行包含一个整数，表示答案。
【数据范围】
对于 30% 的评测用例，1≤m≤n≤300。
对于 50% 的评测用例，1≤m≤n≤1000。
对于所有评测用例，1≤m≤n≤10的6次方。
【输入样例】
【输出样例】
【样例解释】
1 到 13 的排序为：1,10,2,11,3,12,4,13,5,6,7,8,9。
第 5 个数为 3。
【思路】自定义排序规则 + 提取每一位数字。
对如何提取每一位数字不熟悉的可以参考AcWing. 466 / NOIP2016普及组《回文日期》（C++）。
【代码】
#include<iostream>
#include<algorithm>
using namespace std;
const int N = 1000010;
int n,m;
int w[N],s[N];
bool cmp(int a,int b){
if(s[a] != s[b]) return s[a]<s[b];
return a < b;
}
int main(){
scanf("%d%d",&n,&m);
for(int i = 1;i<=n;i++){
w[i] = i;
for(int j = i;j;j /= 10){
s[i] += j % 10;
}
}
sort(w+1,w+n+1,cmp);
printf("%d",w[m]);
return 0;
}第六题《选数异或》
【问题描述】
给定一个长度为 n 的数列 A1,A2,⋅⋅⋅,An 和一个非负整数 x，给定 m 次查询，每次询问能否从某个区间 [l,r] 中选择两个下标不同的数使得他们的异或等于 x。
【输入格式】
输入的第一行包含三个整数 n,m,x。
第二行包含 n 个整数 A1,A2,⋅⋅⋅,An。
接下来 m 行，每行包含两个整数 li,ri 表示询问区间 [li,ri]。
【输出格式】
对于每个询问，如果该区间内存在两个数的异或为 x 则输出 yes，否则输出 no。
【数据范围】
对于 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次方
【输入样例】
【输出样例】
【样例解释】
显然整个数列中只有 2,3 的异或为 1。
【思路】
状态表示：last[i] ： a[i] 左侧与 a[i] 配对的最近一个数的下标 ，g[i] : f[i]前缀的最大值
状态转移：g[i] = max(f[1],f[2] ..... f[i]);
补充 ：a ^ b = x 等价于 b = a ^ x 。
【代码】
#include<iostream>
using namespace std;
int n,m,x;
const int N = 100010,M = (1 << 20) + 10;
int last[M],g[N];
int main(){
scanf("%d%d%d",&n,&m,&x);
for(int i = 1;i<=n;i++){
int a;
scanf("%d",&a);
g[i] = max(g[i-1],last[a^x]);
last[a] = i;
}
while(m--){
int l,r;
scanf("%d%d",&l,&r);
if(g[r] >= l) puts("yes");
else puts("no");
}
return 0;
}第七题《消除游戏》
【问题描述】
在一个字符串 S 中，如果 Si=Si−1 且 Si≠Si+1，则称 Si 和 Si+1 为边缘字符。
如果 Si≠Si−1且 Si=Si+1，则 Si−1 和 Si 也称为边缘字符。
其它的字符都不是边缘字符。
对于一个给定的串 S，一次操作可以一次性删除该串中的所有边缘字符（操作后可能产生新的边缘字符）。
请问经过 2的64次方 次操作后，字符串 S 变成了怎样的字符串，如果结果为空则输出 EMPTY。
【输入格式】
输入一行包含一个字符串 S。
【输出格式】
输出一行包含一个字符串表示答案，如果结果为空则输出 EMPTY。
【数据范围】
对于 25% 的评测用例，|S|≤10的3次方，其中 |S| 表示 S 的长度；
对于 50% 的评测用例，|S|≤10的4次方；
对于 75% 的评测用例，|S|≤10的5次方；
对于所有评测用例，|S|≤10的6次方，S 中仅含小写字母。
【输入样例1】
【输出样例1】
【输入样例2】
【输出样例2】
【思路】链表
【代码】
#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
using namespace std;
const int N = 1000010;
int n;
char s[N];
int l[N], r[N];
vector<int> q, w;
bool st[N];
void insert(int k)
{
if (!st[k])
{
st[k] = true;
w.push_back(k);
}
}
void filter_dels()
{
w.clear();
for (int k: q)
{
int a = l[k], b = k, c = r[k];
if (s[a] == s[b] && s[b] != s[c] && s[c] != '#')
{
insert(b);
insert(c);
}
else if (s[a] != s[b] && s[b] == s[c] && s[a] != '#')
{
insert(a);
insert(b);
}
}
}
int main()
{
scanf("%s", s + 1);
n = strlen(s + 1);
s[0] = s[n + 1] = '#';
for (int i = 1; i <= n; i ++ )
{
l[i] = i - 1, r[i] = i + 1;
q.push_back(i);
}
r[0] = 1, l[n + 1] = n;
while (true)
{
filter_dels();
if (w.empty()) break;
q.clear();
for (int k: w)
{
int a = l[k], b = k, c = r[k];
if (!st[a] && a && (q.empty() || a != q.back())) q.push_back(a);
if (!st[c] && c != n + 1) q.push_back(c);
r[a] = c, l[c] = a;
}
}
if (r[0] == n + 1) puts("EMPTY");
else
{
for (int i = r[0]; i != n + 1; i = r[i])
printf("%c", s[i]);
}
return 0;
}第八题《重新排序》
【问题描述】
给定一个数组 A 和一些查询 Li,Ri，求数组中第 Li 至第 Ri 个元素之和。
小蓝觉得这个问题很无聊，于是他想重新排列一下数组，使得最终每个查询结果的和尽可能地大。
小蓝想知道相比原数组，所有查询结果的总和最多可以增加多少?
【输入格式】
输入第一行包含一个整数 n。
第二行包含 n 个整数 A1,A2,⋅⋅⋅,An，相邻两个整数之间用一个空格分隔。
第三行包含一个整数 m 表示查询的数目。
接下来 m 行，每行包含两个整数 Li、Ri，相邻两个整数之间用一个空格分隔。
【输出格式】
输出一行包含一个整数表示答案。
【数据范围】
对于 30% 的评测用例，n,m≤50；
对于 50% 的评测用例，n,m≤500；
对于 70% 的评测用例，n,m≤5000；
对于所有评测用例，1≤n,m≤10的5次方，1≤Ai≤10的6次方，1≤Li≤Ri≤n。
【输入样例】
【输出样例】
【样例解释】
原来的和为 6+14=20，重新排列为 (1,4,5,2,3) 后和为 10+14=24，增加了 4。
【思路】差分 + 贪心 + 排序不等式
不了解差分的可以参考【模板】AcWing797.《差分》(C++)
不了解排序不等式的可以参考模板：排序不等式】AcWing913.《排队打水》(C++)
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long LL;
const int N = 100010;
int n, m;
int w[N], s[N];
int main()
{
scanf("%d", &n);
for (int i = 1; i <= n; i ++ ) scanf("%d", &w[i]);
scanf("%d", &m);
while (m -- )
{
int l, r;
scanf("%d%d", &l, &r);
s[l] ++, s[r + 1] -- ;
}
for (int i = 1; i <= n; i ++ )
s[i] += s[i - 1];
LL sum1 = 0;
for (int i = 1; i <= n; i ++ )
sum1 += (LL)s[i] * w[i];
LL sum2 = 0;
sort(s + 1, s + n + 1);
sort(w + 1, w + n + 1);
for (int i = 1; i <= n; i ++ )
sum2 += (LL)s[i] * w[i];
printf("%lld\n", sum2 - sum1);
return 0;
}
第九题《技能升级》
【问题描述】
小蓝最近正在玩一款 RPG游戏。
他的角色一共有 N 个可以加攻击力的技能。
其中第 i 个技能首次升级可以提升 Ai 点攻击力，以后每次升级增加的点数都会减少 Bi。
⌈Ai/Bi⌉（上取整）次之后，再升级该技能将不会改变攻击力。
现在小蓝可以总计升级 M 次技能，他可以任意选择升级的技能和次数。
请你计算小蓝最多可以提高多少点攻击力？
【输入格式】
输入第一行包含两个整数 N 和 M。
以下 N 行每行包含两个整数 Ai 和 Bi。
【输出格式】
输出一行包含一个整数表示答案。
【数据范围】
对于 40% 的评测用例，1≤N,M≤1000；
对于 60% 的评测用例，1≤N≤10的4次方，1≤M≤10的7次方；
对于所有评测用例，1≤N≤10的5次方，1≤M≤2×10的9次方，1≤Ai,Bi≤10的6次方。
【输入样例】
【输出样例】
【思路】贪心 + 多路归并 + 二分
【代码】
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long LL;
const int N = 100010;
int n, m;
int a[N], b[N];
bool check(int mid)
{
LL res = 0;
for (int i = 0; i < n; i ++ )
if (a[i] >= mid)
res += (a[i] - mid) / b[i] + 1;
return res >= m;
}
int main()
{
scanf("%d%d", &n, &m);
for (int i = 0; i < n; i ++ ) scanf("%d%d", &a[i], &b[i]);
int l = 0, r = 1e6;
while (l < r)
{
int mid = l + r + 1 >> 1;
if (check(mid)) l = mid;
else r = mid - 1;
}
LL res = 0, count = 0;
for (int i = 0; i < n; i ++ )
if (a[i] >= r)
{
int cnt = (a[i] - r) / b[i] + 1;
count += cnt;
int end = a[i] - (cnt - 1) * b[i];
res += (LL)(a[i] + end) * cnt / 2;
}
printf("%lld\n", res - (count - m) * r);
return 0;
}第十题《重复的数》
【问题描述】
给定一个数列 A=(a1,a2,⋅⋅⋅,an)，给出若干询问，每次询问某个区间 [li,ri] 内恰好出现 ki 次的数有多少个。
【输入格式】
输入第一行包含一个整数 n 表示数列长度。
第二行包含 n 个整数 a1,a2,⋅⋅⋅,an，表示数列中的数。
第三行包含一个整数 m 表示询问次数。
接下来 m 行描述询问，其中第 i 行包含三个整数 li,ri,ki 表示询问 [li,ri] 区间内有多少数出现了 ki次。
【输出格式】
输出 m 行，分别对应每个询问的答案。
【数据范围】
对于 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。
【输入样例】
【输出样例】
【思路】莫队
【代码】
#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];
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;
}