继续stl

1.CF808D Array Division

题目描述

Vasya has an array $ a $ consisting of positive integer numbers. Vasya wants to divide this array into two non-empty consecutive parts (the prefix and the suffix) so that the sum of all elements in the first part equals to the sum of elements in the second part. It is not always possible, so Vasya will move some element before dividing the array (Vasya will erase some element and insert it into an arbitrary position).

Inserting an element in the same position he was erased from is also considered moving.

Can Vasya divide the array after choosing the right element to move and its new position?

输入格式

The first line contains single integer n ( 1<=n<=100000 ) — the size of the array.

The second line contains n integers a1,a2… a**n ( 1<=a**i<=109 ) — the elements of the array.

输出格式

Print YES if Vasya can divide the array after moving one element. Otherwise print NO.

题意翻译

给你一组数，问可以最多移动一个数，使得这一串数可以分成两个部分，每一部分所有数的和相等。

输入输出样例 #1

输入 #1

1
2
3
1 3 2

输出 #1

1
YES

输入输出样例 #2

输入 #2

1
2
5
1 2 3 4 5

输出 #2

1
NO

输入输出样例 #3

输入 #3

1
2
5
2 2 3 4 5

输出 #3

1
YES

说明/提示

In the first example Vasya can move the second element to the end of the array.

In the second example no move can make the division possible.

In the third example Vasya can move the fourth element by one position to the left.

今日题解：

愚钝未想出好的解决办法，只会暴力，不写了肯定爆，我看了大佬的题解，以下是自己复现的（抄的 :-）。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
#include<bits/stdc++.h>
using namespace std;
using ll = long long;

map<ll, int> mapl, mapr;//表示左右区间分别包含的数
bool flag=0;
ll sum;//sum表示前半数和，ans表示前缀和


int main() {
	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	int n;cin>>n;
	vector<ll> a(n+1);
	vector<ll> ans(n+1);
	for(int i=1;i<=n;++i) {
		cin>>a[i];
	}
	for(int i=1;i<=n;++i) {
		ans[i]=ans[i-1]+a[i];
		mapr[a[i]]++;
	}
	
	if(ans[n] % 2 != 0) {
		cout<<"NO\n";
		return 0;
	}
	sum=ans[n]/2;
	
	for(int i=1;i<n;++i) {
		if(ans[i]==sum) {
			cout<<"YES\n";
			return 0;
		}
		//模拟切割，左半某数的个数加一，右半某数的个数减一
		mapl[a[i]]++;
		mapr[a[i]]--;
		//如果左半小于的数刚好在右半有，则可以
		if(ans[i]<sum && mapr[sum-ans[i]]) {
			flag=1;
			break;
		}
		
		if(ans[i]>sum && mapl[ans[i]-sum]) {
			flag=1;
			break;
		}
	}
	
	if(flag) {
		cout<<"YES\n";
	}
	else cout<<"NO\n";
	
    return 0;
}

2.CF81A Plug-in

题目描述

Polycarp thinks about the meaning of life very often. He does this constantly, even when typing in the editor. Every time he starts brooding he can no longer fully concentrate and repeatedly presses the keys that need to be pressed only once. For example, instead of the phrase “how are you” he can type “hhoow aaaare yyoouu”.

Polycarp decided to automate the process of correcting such errors. He decided to write a plug-in to the text editor that will remove pairs of identical consecutive letters (if there are any in the text). Of course, this is not exactly what Polycarp needs, but he’s got to start from something!

Help Polycarp and write the main plug-in module. Your program should remove from a string all pairs of identical letters, which are consecutive. If after the removal there appear new pairs, the program should remove them as well. Technically, its work should be equivalent to the following: while the string contains a pair of consecutive identical letters, the pair should be deleted. Note that deleting of the consecutive identical letters can be done in any order, as any order leads to the same result.

输入格式

The input data consists of a single line to be processed. The length of the line is from 1 to 2⋅105 characters inclusive. The string contains only lowercase Latin letters.

输出格式

Print the given string after it is processed. It is guaranteed that the result will contain at least one character.

题意翻译

给你一个仅由小写字母构成的字符串（字符串长度小于等于200000），求删除这个字符串里所有重复字串后的结果。

UPD: 删除连续字母对，若删除后出现了新的字母对，也要删除。

输入输出样例 #1

输入 #1

1
hhoowaaaareyyoouu

输出 #1

1
wre

输入输出样例 #2

输入 #2

1
reallazy

输出 #2

1
rezy

输入输出样例 #3

输入 #3

1
abacabaabacabaa

输出 #3

1
a

今日题解：

算是水题，去重重复字符

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
#include<bits/stdc++.h>
using namespace std;
using ll = long long;


int main() {
	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);

	string s;
	cin>>s;
	vector<char> stk;

	for(int i=0; i<s.size(); ++i) {
		if(!stk.empty()) {
			if(s[i]!=stk.back()) {
				stk.push_back(s[i]);
			}
			else stk.pop_back();
		}
		else stk.push_back(s[i]);
	}
	for(auto c : stk) {
		cout<<c;
	}

	return 0;
}

3.CF821C Okabe and Boxes

题目描述

Okabe and Super Hacker Daru are stacking and removing boxes. There are n boxes numbered from 1 to n . Initially there are no boxes on the stack.

Okabe, being a control freak, gives Daru 2n commands: n of which are to add a box to the top of the stack, and n of which are to remove a box from the top of the stack and throw it in the trash. Okabe wants Daru to throw away the boxes in the order from 1 to n . Of course, this means that it might be impossible for Daru to perform some of Okabe’s remove commands, because the required box is not on the top of the stack.

That’s why Daru can decide to wait until Okabe looks away and then reorder the boxes in the stack in any way he wants. He can do it at any point of time between Okabe’s commands, but he can’t add or remove boxes while he does it.

Tell Daru the minimum number of times he needs to reorder the boxes so that he can successfully complete all of Okabe’s commands. It is guaranteed that every box is added before it is required to be removed.

输入格式

The first line of input contains the integer n ( 1<=n<=3⋅105 ) — the number of boxes.

Each of the next 2n lines of input starts with a string “add” or “remove”. If the line starts with the “add”, an integer x ( 1<=x<=n ) follows, indicating that Daru should add the box with number x to the top of the stack.

It is guaranteed that exactly n lines contain “add” operations, all the boxes added are distinct, and n lines contain “remove” operations. It is also guaranteed that a box is always added before it is required to be removed.

输出格式

Print the minimum number of times Daru needs to reorder the boxes to successfully complete all of Okabe’s commands.

题意翻译

Okabe 和 Daru 正在向一个栈中加入和删除盒子。盒子编号从 1 到 n，最开始栈中没有盒子。
作为一个控制狂，Okabe 给了 Daru 2×n 个命令：n 个命令让他将某一个盒子加入栈中， n 个命令让他弹出栈顶。Okabe 希望弹出栈顶的盒子顺序是从 1 到 n。当然，这意味着，Daru 可能在他的命令下做不到按顺序弹出。
但是 Daru 可以在两个命令之间调整整个栈中的盒子顺序。当然，这个时候他不能执行命令。
Daru 想问你最少的调整次数。保证一个盒子在需要被弹出之前一定被加入过。
n≤3×105
By:Call_me_Eric

输入输出样例

输入 #1

1
2
3
4
5
6
7
3
add 1
remove
add 2
add 3
remove
remove

输出 #1

1
1

输入输出样例 #2

输入 #2

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
7
add 3
add 2
add 1
remove
add 4
remove
remove
remove
add 6
add 7
add 5
remove
remove
remove

输出 #2

1
2

说明/提示

In the first sample, Daru should reorder the boxes after adding box 3 to the stack.

In the second sample, Daru should reorder the boxes after adding box 4 and box 7 to the stack.

今天题解：

加操作正常加即可，移除操作得判断是否可以顺序移除，top记录该移除的数，如果栈顶的元素不是该数，清空栈，操作数加一。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
#include<bits/stdc++.h>
using namespace std;
using ll = long long;


int main() {
	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	
	int n;cin>>n;
	string s;
	int x;
	vector<int> v;
	int ans=0, top=0;
	for(int i=0;i<(n<<1);++i) {
		cin>>s;
		if(s=="add") {
			cin>>x;
			v.push_back(x);
		}
		else {
			top++;
			if(v.empty()){
				continue;
			}
			if(v.back()!=top) {
				ans++;
				v.clear();
			}
			else v.pop_back();
		}
		
	}
	cout<<ans;
    return 0;
}