文章目录

一、AcWing 4645. 选数异或（中等）

1. 实现思路

2. 实现代码

二、AcWing 4644. 求和（简单）

1. 实现思路

2. 实现代码

三、AcWing 4653. 数位排序（简单）

1. 实现思路

2. 实现代码

四、AcWing 4655. 重新排序（中等）

1. 实现思路

2. 实现代码

五、AcWing 4652. 纸张尺寸（简单）

1. 实现思路

2. 实现代码

一、AcWing 4645. 选数异或（中等）

题目描述

给定一个长度为 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 < 220，1 ≤ li ≤ ri ≤ n，0 ≤ Ai <220。

输入样例

4 4 1

1 2 3 4

1 4

1 2

2 3

3 3

输出样例

yes

no

yes

no

样例解释

显然整个数列中只有 2,3 的异或为 1。

具体实现

1. 实现思路

我们有 n 个数，然后在 n 个数当中进行 m 次询问（判断），每次询问给一个区间，判断这个区间是否有一对数的异或值等于 x，有的话输出 yes，没有的话输出 no。

由于 n，m 的数据范围是100000，因此，我们需要将时间复杂度控制在 O(nlogn)。

首先发现 a ^ b = x -> a ^ x = b -> b ^ x = a，也就是我们只要先把 x 跟每个数的异或值 b 提前算出，如果我们知道的了 b，那么只要 b 在 l ~ r 的范围内就符合题意了。这时输出 Yes 即可。

但是，直接暴力判断的话，要两层 for 循环，时间复杂度时 O(n2)，不符合要求。

如果在 l 到 r 当中存在，那么一定在 1 到 r 当中存在（用于缩减询问次数）。

假设，fi 是在 ai 左边，与 ai 配对的最近的一个数，那么 fi 一定是小于 r 的，我们只需要判断 fi 是否大于 l 即可。因此，我们只需要寻找这个 i 。

为了简便，我们可以设定一个数组 g[i] 用于表示 i 左边 fi 的最大值，只需要判断 g® 是否大于等于 l。

2. 实现代码

#include <bits/stdc++.h>
using namespace std;
// 1<<20 表示2的20次方，+10是为了防止溢出
const int N = 100010, M = (1 << 20) + 10; 
int n, m, x;
//last[M]表示每个数最后一次出现的位置
//g[N]表示用于表示 i 左边 f~i~ 的最大值
int last[M], g[N];
int main()
{
    cin >> n >> m >> x;
    for (int i = 1; i <= n; i ++ )
    {
        int a;
        cin >> a;
        //如果一个数字没有出现过，last数组是全局变量，就是0
        //递归
        g[i] = max(g[i - 1], last[a ^ x]);
        //更新last
        last[a] = i;
    }
    while (m -- )
    {
        int l, r;
        cin >> l >> r;
        if (g[r] >= l) 
        {
            puts("yes");
        }
        else
        {
            puts("no");
        }
    }
    system("pause");
    return 0;
}

二、AcWing 4644. 求和（简单）

题目描述

给定 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 ≤ a_i ≤ 100。

对于所有评测用例，1 ≤ n ≤ 200000，1 ≤ a_i ≤ 1000。

输入样例

4

1 3 6 9

输出样例

117

具体实现

1. 实现思路

• 如果直接采取暴力做法两个 for 循环直接会超时，因此，需要进行优化。
• 可以使用前缀和或者推导公式两种方法，递推公式整体比较复杂，在此不做过多叙述。
• 前缀和详见博文 基础算法-前缀和。

2. 实现代码

#include <bits/stdc++.h>
using namespace std;
const int N = 200010;
int n;
int a[N];
int main()
{
    cin >> n;
    long long sum = 0;
    for(int i = 1; i <= n; i ++ )
    {
        cin >> a[i];
        sum += a[i];
    }
    long long res = 0, cnt = 0;   
    for(int i = 1; i <= n; i ++ )
    {
        cnt += a[i];
        res += a[i] * (sum - cnt);
    }
    cout << res << endl;
    system("pause");
    return 0;
}

三、AcWing 4653. 数位排序（简单）

题目描述

小蓝对一个数的数位之和很感兴趣，今天他要按照数位之和给数排序。

当两个数各个数位之和不同时，将数位和较小的排在前面，当数位之和相等时，将数值小的排在前面。

例如，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 ≤ 106。

输入样例

13

5

输出样例

3

样例解释

1 到 13 的排序为：1,10,2,11,3,12,4,13,5,6,7,8,9。

第 5 个数为 3。

具体实现

1. 实现思路

• 不可以实时计算每一个数字的数位和，有可能会导致超时。
• 因此，我们可以使用一个数组，将每个数的数位之和存储进去，然后使用快速排序即可。
• 快速排序详见 基础算法-快速排序。

2. 实现代码

#include <bits/stdc++.h>
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()
{
    cin >> n >> m;
    for (int i = 1; i <= n; i ++ )
    {
        w[i] = i;
        for (int j = i; j != 0; j /= 10)
        {
            s[i] += j % 10;
        }
    }
    sort(w + 1, w + n + 1, cmp);
    cout << w[m] << endl;
    system("pause");
    return 0;
}

四、AcWing 4655. 重新排序（中等）

题目描述

给定一个数组 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 ≤ 105，1 ≤ Ai ≤ 106，1 ≤ Li ≤ Ri ≤ n。

输入样例

5

1 2 3 4 5

2

1 3

2 5

输出样例

4

样例解释

原来的和为 6+14=20，重新排列为 (1,4,5,2,3) 后和为 10+14=24，增加了 4。

具体实现

1. 实现思路

首先，我们可以先统计一下每一位数在答案当中会加多少次。

具体方法可以通过差分实现，当 l 到 r 这段区间被求和时，就 将 bl 加上 1，br+1 减去 1 就可以了。具体详见 基础算法-差分。

然后，重新排列，使得最大的相互对应，按照顺序去配对。

求和的过程就是前缀和的步骤，具体详见 基础算法-前缀和。

2. 实现代码

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 100010;
int n, m;
//w[N]表示原数组
//s[N]表示记录被加次数的数组
int w[N], s[N];
int main()
{
    cin >> n;
    for (int i = 1; i <= n; i ++ )
    {
        cin >> w[i];
    }
    cin >> m;
    while (m -- )
    {
        int l, r;
        cin >> 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];
    }
    cout << sum2 - sum1 << endl;
    system("pause");
    return 0;
}

五、AcWing 4652. 纸张尺寸（简单）

题目描述

在 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

具体实现

1. 实现思路

• 只需要依次递推计算即可，中间需要注意长边和短边的变换。
• 当 x 小于 y 的时候，下一次就是 y 折半，为了方便，这里直接将 x 与 y 交换即可。

2. 实现代码

#include <bits/stdc++.h>
using namespace std;
int main()
{
    int n;
    char s;
    cin >> s >> n;
    int x = 1189, y = 841;
    while (n -- )
    {
        x /= 2;
        if (x < y)
        {
            swap(x, y);
        }
    }
    cout << x << endl << y << endl;
    system("pause");
    return 0;
}