第一题《排列字母》

【问题描述】

小蓝要把一个字符串中的字母按其在字母表中的顺序排列。
例如,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;
}
03-14 17:34