Codeforces Round 918 (Div. 4)赛后总结（前缀和）（set部分用法）

Codeforces Round 918 (Div. 4)赛后总结

a,b题没啥好说的

c题典中典

没开long long 一回事，还有判断数a是否为完全平方数直接用sqrt(a)\(^2\)=a的判断就可以

d题经典字符串问题

首先，我们以一个字符数组的形式存数据。再根据已知cv,cvc两种形式，我们只需要判断c的时候看v是否有用过（可以给一个变量赋值再判断变量值来判断），有用过就判断它的下一个是c还是v，是c就先输出c再输出'.',是v就先输出'.'在输出c。（注意更新判断是否为v的值）。其他直接输出就可以秒。

#include <iostream>
#include <string>
#include <math.h>
#include <algorithm>
#include <iomanip>
using namespace std;
char a[200001];

int main() {
	int t;
	cin >> t;
	for (int i = 1; i <= t; i++) {
		int n;
		cin >> n;
		int num = 0;
		for (int j = 1; j <= n; j++) {
			cin >> a[j];
		}

		for (int j = 1; j <= n - 1; j++) {
			if (a[j] == 'a' || a[j] == 'e') {
				num = 1;
				cout << a[j];
			} else {
				if (num == 1) {
					if (a[j + 1] == 'a' || a[j + 1] == 'e') {
						cout << "." << a[j];
						num = 0;
					} else {
						cout << a[j] << ".";
						num = 0;
					}
				} else {
					cout << a[j];
				}
			}

		}
		cout << a[ n] << endl;
	}
}

E题典型前缀和问题

前缀和

对于给定数组a,我们另建数组s,s数组表示的是从a数组初下标到目标下标下的求和。

实现

s[i]=s[i-1]+a[i]

对于给定区间和

通过这种方法，我们可以用s[l]-s[r-1] (l>r)表示从下标l到下标r的值的求和。

如何判断区间和为0

如果我们具体知道区间范围和下标直接用上面给的方式判断s[l]-s[r-1]为0.
那如果要判断是否有区间和为0，就可以前缀和数组做判断，如果前缀和数组中的数有重复，那就代表着有部分区间的和为0.

set

意义

set就是集合的意思，集合的特点就是不会出现重复的内容。一般用来作查重或去重操作。

定义

set<数据类型>变量名

set成员函数

insert()//插入元素
count()//判断容器中是否存在某个元素
size()//返回容器的尺寸，也可以元素的个数
erase()//删除集合中某个元素
clear()//清空集合
empty()//判断是否为空
begin()//返回第一个节点的迭代器
end()//返回最后一个节点加1的迭代器
rbegin()//反向迭代器
rend()//反向迭代器

解题思路

题目本质就是对于区间是否有子区间和为0的判断

那么我们便可以用到上面所说的方法：用前缀和数组是否用重复来判断。
同时这里可以用set来做查重的操作。

具体

由于题目判断区间奇数和是否等于偶数和。
那么我们可以将每两个数做差为一组再用前缀和思想再判断是否有重复的。（由于划分的不一定是偶数，这里可能有多出来的一个数，我们再对其做单独判断）
同理，我们需要对初始为1和2分别重新遍历。
代码如下

#include <iostream>
#include <string>
#include <math.h>
#include <algorithm>
#include <iomanip>
#include <set>
#define ll long long
using namespace std;
long long a[200005];

int main() {
	int t;
	cin >> t;

	for (int i = 1; i <= t; i++) {

		int n;
		cin >> n;
		bool flag = false;//通过这个来判断是否成立
		ll pre;
		set<ll> s;
		s.insert(0);//0是需要提前插入的，（前缀和可能存在为0情况符合条件但不重复）
		pre = 0;//用前缀和思想遍历数组的值
		for (int j = 1; j <= n; j++) {//以1为初始遍历
			cin >> a[j];
		}
		for (int j = 1; j + 1 <= n; j += 2) {//记得j+1<=n，不然会越界
			pre += a[j] - a[j + 1];
			if (s.count(pre) || j <= n - 2 && s.count(pre + a[j + 2])) {//由于两个为一组，所以对于可能多出来的奇数用j+2判定。
				flag = true;
			}
			s.insert(pre);
		}
		s.clear();//记得清空
		s.insert(0);
		pre = 0;
		for (int j = 2; j + 1 <= n; j += 2) {//以2为初始遍历
			pre += a[j] - a[j + 1];
			if (s.count(pre) || j <= n - 2 && s.count(pre + a[j + 2])) {
				flag = true;
			}
			s.insert(pre);
		}
		if (flag) {
			cout << "YES" << endl;
		} else {
			cout << "NO" << endl;
		}
		s.clear();
	}
}