这是关于算法题的整理及思考

题目来源不一定，主要来源应该是CF、洛谷等

也会包含一些关于比赛的反思等

Codeforces Round 982 (Div. 2) B

标签：

• 暴力枚举（brute force）
• 贪心（greedy）

题目：

1. Problem-B-Codeforces
2. Stalin Sort-洛谷

题目大意

给出一个数组，问是否可以通过对其任意子数组进行多次斯大林排序，使得最终的数组是非增的。

*子数组指的是任意一段连续子数组，斯大林排序指将严格降序的元素剔除，具体定义见题目

思路分析：

通过斯大林排序的定义可知

• 任何一段数组进行斯大林排序后第一个元素都不会改变

• 如果处理完的数组元素大于等于两个，则按非降序排列

进一步分析

• 对于使用斯大林排序的任意子数组，如果存在大于第一个元素的其他元素则会被保留，而小于第一个元素的一定会被剔除
  因此要使最后是非降序的，就必须要把子数组中大于第一个元素的其他元素都剔除掉
• 那么要使剔除后的数组是可以通过对其任意子数组进行多次斯大林排序，使得最终的数组是非增的
  就要使剔除后的数组的首元素最大
• 接下来只需要从头遍历整个数组，找到有最多元素的满足首元素最大的数组（不一定连续）即可
• 即对数组中的每个元素寻找有多少个（k）在他之后的不大于他的元素，并记录下最大值（f）
• 将元素总个数减去（最大值+1）就是其他要剔除的元素的个数

可能的疑问

问题一：对每个元素只考虑后面的其他元素，为什么不用考虑前面的其他元素就把他们全部剔除

答：

• 如果前面的元素大于等于该元素，则前面元素遍历时的值k1就会大于该值k2，那么f就会等于k1，不影响
• 如果前面的元素小于该元素，则必须剔除，否则剔除后的数组的首元素就不是最大的，那么就不满足要求

思路误区：

比赛时想的是减序列通过斯大林排序一定会消失，所以先对整个数组进行一次斯大林排序，得到非减序列，再把第一次出现的最大值前的元素全部剔除掉，那么剩下的就是非增序列了，问题在于在第一次通过斯大林排序时删掉的元素仍在剔除元素后的数组之中，此时数组还可能存在递增序列，不满足题意

代码：

#include <bits/stdc++.h>

using namespace std;

int main() {
    int t;
    cin >> t; // 读取测试用例数量  
    while (t--)
    {
        int n;
        cin >> n;
        int* a = new int[n + 1];
        for (int i = 0; i < n; i++)
        {
            cin >> a[i];
        }
        int f = 0;
        for (int i = 0; i < n - 1; i++)
        {
            int k = 0;
            for (int j = i + 1; j < n; j++)
            {
                if (a[j] <= a[i])
                    k++;
            }
            f = max(f, k);
        }
        cout << n - (f + 1) << endl;
        delete[] a;
    }
    return 0;
}

Educational Codeforces Round 115 (Rated for Div. 2) C

标签：

• 暴力

题目：

1. Problem - C - Codeforces

题目大意

从数组中删掉两个数使得数学平均值不变，问一共有多少组

思路分析：

First of all, instead of the mathematic mean, let’s consider the sum of elements. If the mathematic mean is , then the sum of elements of the array is . Let’s denote the sum of elements in the original array as . Note is always an integer.

If we remove two elements from the array, the resulting sum of elements should become . So, the sum of the elements we remove should be exactly .

If is not an integer, the answer is (to check that, you can simply compare with ). Otherwise, we have to find the number of pairs such that and . This is a well-known problem.

To solve it, you can calculate the number of occurrences of each element and store it in some associative data structure (for example, map in C++). Let be the number of occurrences of element . Then, you should iterate on the element you want to remove and check how many elements match it, that is, how many elements give exactly if you add to them. The number of these elements is just . Let’s sum up all these values for every element in the array.

Unfortunately, this sum is not the answer yet. We need to take care of two things:

• if for some index , , then matches itself, so you have to subtract the number of such elements from the answer;
• every pair of elements is counted twice: the first time when we consider the first element of the pair, and the second time — when we consider the second element of the pair. So, don’t forget to divide the answer by .

代码：

#include <bits/stdc++.h>

using namespace std;

int main() {
  int t;
  scanf("%d", &t);
  while (t--) {
    int n;
    scanf("%d", &n);
    vector<int> a(n);
    map<int, int> cnt;
    for (auto &x : a) {
      scanf("%d", &x);
      cnt[x] += 1;
    }
    long long sum = accumulate(a.begin(), a.end(), 0LL);
    if ((2 * sum) % n != 0) {
      puts("0");
      continue;
    }
    long long need = (2 * sum) / n;
    long long ans = 0;
    for (int i = 0; i < n; ++i) {
      int a1 = a[i];
      int a2 = need - a1;
      if (cnt.count(a2)) ans += cnt[a2];
      if (a1 == a2) ans -= 1;
    }
    printf("%lld\n", ans / 2);
  }
}

P9236 [蓝桥杯 2023 省 A] 异或和之和

标签：

• 前缀和
• 位运算

题目：

P9236 蓝桥杯 2023 省 A 异或和之和

题目大意

给定一个数组 ，分别求其每个子段的异或和，并求出它们的和。或者说，对于每组满足 1≤L≤R≤n 的 L,R，求出数组中第 L 至第 R 个元素的异或和。然后输出每组 L,R 得到的结果加起来的值。

思路分析：

首先考虑使用暴力求解，穷举L、R的所有组合，此时时间复杂度为 ，对每种情况从L到R求异或和，则此时时间复杂度为 ，能过30%的数据。

继续优化，使用前缀异或和，因为每个数和自己的异或和都是0，每个数和零的异或和都是它本身，因此求L到R的异或和就是求 1到L-1的异或和 和 1到R的异或和 的异或和，这样在输入每个数时就能一边输入一边求出前缀异或和并存在数组中。求L到R的异或和只需要将前缀和 与前缀和 求异或和即可。时间复杂度是 ，能够60%的数据。

继续优化，可以发现前缀和 与前缀和 的异或和的第 （从0开始）位为1时才对结果有贡献 ，而所有L和R的组合恰好是把所有前缀和两两求异或和再求和，因此，我们可以统计出所有前缀和的第 位的1的个数 和0的个数 ，只有第 位是1和0搭配时异或和的第 （从0开始）位才为1，则根据乘法原理一共在第 位的贡献是 ，又因为，因此结果为：，时间复杂度为 ，可以通过该题。具体实现可以对于每一个 前缀和，我们将其按位拆分，并将结果加入计数数组 中。其中 i 表示第 i 个二进制位，j 表示这一位上为 j（只能为 0 或 1）， 表示在所有数中，第 i 个二进制位上为 j 的有 个。

代码：

#include <bits/stdc++.h>
#include<iostream>
#include<string>
#include<cstring>
#include<algorithm> 
#include<queue>
#include<stack>
#include<vector>
#include<cmath>
using namespace std;

int main()
{
	int n;
	long long sum=0;
	long long flag=0;
	long long A;
	long long w[25][3]={0}; 
	cin>>n;
	long long *mem=new long long [n+1];
	mem[0]=0;
	for(int i=1;i<=n;i++)
	{
		cin>>A;
		mem[i]=mem[i-1]^A;
	}
	for(int i=0;i<=n;i++)
	{
		for(int j=0;j<=20;j++)
		{
			w[j][mem[i]>>j&1]++;
		}
	}
	for(int i=0;i<=20;i++)
		sum+=w[i][0]*w[i][1]*pow(2,i);
	cout<<sum<<endl;
	return 0;
} 

P8773 [蓝桥杯 2022 省 A] 选数异或

标签：

• 线段树
• ST表

题目：

蓝桥杯 2022 省 A] 选数异或

题目大意

给定一个长度为 的数列 和一个非负整数 , 给定 次查询, 每次询问能否从某个区间 中选择两个数使得他们的异或等于 。

思路分析：

因为提前给出了，而要^=，则可以根据得出=^，因此可以在输入时就对其进行预处理。我们可以用map记录某个元素最后出现的位置，然后对每一个输入的 我们可以找到其之前的与其异或后为的最后一个元素的位置，记作=^，且可知<并且若不存在则，那么要使区间 中有两个数使得他们的异或等于 ，只需使得该区间内有一个元素的在该区间内即可，即只需要的最大值大于等于即可。我们可以设为 中的最大值，那么只需>=，就能保证在区间 中有至少有两个数使得他们的异或等于 。同时在具体实现上我们可以用在输入数据时就进行预处理。

代码：

#include<iostream>
#include<string>
#include<cstring>
#include<algorithm> 
#include<queue>
#include<stack>
#include<vector>
#include<cmath>
#include<map>
using namespace std;

int main()
{
	int n,m,x;
	cin>>n>>m>>x;
	map<int,int> a;
	int A;
	int *f=new int[n+1];
	for(int i=0;i<=n;i++)
	{
		f[i]=0; 
	}
	for(int i=1;i<=n;i++)
	{
		cin>>A;
		f[i]=max(f[i-1],a[A^x]);
		a[A]=i;
	}
	for(int j=0;j<m;j++)
	{
		int l,r;
		cin>>l>>r;
		if(f[r]>=l)
			cout<<"yes"<<endl;
		else
			cout<<"no"<<endl;
	}
	return 0;
} 

附记