Sorted algorithm template collection: ACM template

Click me to see the algorithm family bucket series!!!

It is actually a new refining template integration plan

Educational Codeforces Round 114 (Rated for Div. 2)

Competition link: https://codeforces.com/contest/1574/

The first four questions are too simple ()

The last two questions are a little deadly ()

A. Regular Bracket Sequences

Problem

Solution

Only output required n n n for legal parentheses, we can move one of the right parentheses.

Code

// Problem: A. Regular Bracket Sequences
// Contest: Codeforces - Educational Codeforces Round 114 (Rated for Div. 2)
// URL: https://codeforces.com/contest/1574/problem/A
// Memory Limit: 512 MB
// Time Limit: 2000 ms
// 
// Powered by CP Editor (https://cpeditor.org)


#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int maxn = 1e5 + 6, INF = 0x3f3f3f3f;
int n, m, s, t;
ll ans;
int a[maxn];

void solve()
{
	cin >> n;
	for(int i = 1; i <= n; ++ i) {
		int cnt1 = n, cnt2 = n;
		for (int j = 1; j <= 2 * n; ++ j) {
			if(j == i + 1) {
				cnt2 -- ;
				putchar(')');
			}
			else {
				if(cnt1) {
					cnt1 -- ;
					putchar('(');
				}
				else if(cnt2) {
					cnt2 -- ;
					putchar(')');
				}
			}
		} 
		puts("");
	}
}

int main()
{
	cin >> t;
	while(t -- ) {
		solve();
	}
	return 0;
}

B. Combinatorics Homework

Problem

Solution

set up s u m = a + b + c sum=a+b+c sum=a+b+c

The most logarithms are obviously placed in order. There are r = s u m − 3 r = sum-3 r=sum − 3 pairs.

For the least logarithm, we use a smaller number of two letters h a c k = s u m − max ⁡ { a , b , c } hack=sum-\max\{a,b,c\} hack=sum − max{a,b,c}, to separate the largest number of letters, which can be separated altogether 2 × h a c k + 1 2\times hack+1 two × hack+1 same letters, the rest must be connected together, then the minimum logarithm is l = s u m − 2 × h a c k − 1 l = sum-2 \times hack-1 l=sum−2×hack−1

judge m m m is within the interval.

Code

// Problem: B. Combinatorics Homework
// Contest: Codeforces - Educational Codeforces Round 114 (Rated for Div. 2)
// URL: https://codeforces.com/contest/1574/problem/B
// Memory Limit: 256 MB
// Time Limit: 2000 ms
// 
// Powered by CP Editor (https://cpeditor.org)


#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int maxn = 1e5 + 6, INF = 0x3f3f3f3f;
int n, m, s, t;
ll ans;
int a, b, c;

void solve()
{
	cin >> a >> b >> c >> n;
	int hack = a + b + c - max({a, b, c});
	int l = a + b + c - 2 * hack - 1;
	int r = a + b + c - 3;
	if(l <= n && n <= r)
		puts("YES");
	else puts("NO");
}

int main()
{
	cin >> t;
	while(t -- ) {
		solve();
	}
	return 0;
}

C. Slay the Dragon

Problem

Solution

Directly lower after sorting_ Bound found greater than or equal to x x Hero of x p o s pos pos let him kill dragon.

Since we have enhanced functions, we need to judge p o s pos pos to kill and let p o s − 1 pos-1 After pos − 1 is strengthened, kill whoever is cheaper.

Code

// Problem: C. Slay the Dragon
// Contest: Codeforces - Educational Codeforces Round 114 (Rated for Div. 2)
// URL: https://codeforces.com/contest/1574/problem/C
// Memory Limit: 256 MB
// Time Limit: 2000 ms
// 
// Powered by CP Editor (https://cpeditor.org)


#include <bits/stdc++.h>
using namespace std;
#define int long long
using ll = long long;
const int maxn = 3e5 + 6, INF = 2e18;
int n, m, s, t;
ll ans;
int a[maxn];

void solve()
{
	cin >> n;
	int sum = 0;
	int maxx = -INF;
	for (int i = 1; i <= n; ++ i) 
		scanf("%lld", &a[i]), sum += a[i];
	sort(a + 1, a + 1 + n);
	cin >> m;
	while(m -- ) {
		int x, y;
		scanf("%lld%lld", &x, &y);
		ll ans = INF;
		int pos = lower_bound(a + 1, a + 1 + n, x) - a; 
		if(pos != n + 1) {
			int kill = a[pos];
			int rem = sum - kill;
			int res = max(0ll, y - rem);
			ans = min(ans, res);
		}
		if(pos != 1) {
			int kill = a[pos - 1];
			int rem = sum - kill;
			int res = max(0ll, y - (sum - a[pos - 1])) + x - a[pos - 1];
			ans = min(ans, res);
		}
		cout << ans << endl;
	}
}

signed main()
{
	// cin >> t;
	t = 1;
	while(t -- ) {
		solve();
	}
	return 0;
}

D. The Strongest Build

Problem

Solution

First, consider how to judge whether a certain selection scheme is ban. Obviously, you can directly use the hash table map O ( 1 ) O(1) O(1) query. We store the array in vector and directly use map to judge whether there is such a vector.

Due to the input a i j a_{ij} aij# is increasing. Considering violent search, we can choose from the outermost layer c i c_i ci, i.e max ⁡ { c i } , i ∈ [ 1 , n ] \max\{c_i\},i\in [1,n] max{ci}, i ∈ [1,n] starts to go in b f s bfs bfs search is enough, one step is subtracted each time, and the maximum value is found if it is not ban.

When we search for bfs, we first judge whether the optimal solution is ban. If it is ban, we judge the next layer of the optimal solution, that is, a certain i -- to judge whether it is ban at this time. It is not easy to realize. We find the scheme of ban dropping m ≤ 1 0 5 m\le 10^5 m ≤ 105, in fact, we can directly judge the next layer of all the selected schemes by ban.

For restricted option 3

Just judge its next layer: 2 2 3, 3 1 3, 3 2 2.

At this time, the time complexity is O ( n m ) = 1 × 1 0 6 O(nm)=1\times 10^6 O(nm)=1×106

Because from the optimal solution, only when the optimal solution and the scheme of the next layer are removed by ban, you need to look at the next layer, and the next layer will also judge its next layer in the list of ban. Therefore, only judging the next layer of the scheme to be ban can find the optional optimal value.

Code

// Problem: D. The Strongest Build
// Contest: Codeforces - Educational Codeforces Round 114 (Rated for Div. 2)
// URL: https://codeforces.com/contest/1574/problem/D
// Memory Limit: 256 MB
// Time Limit: 3000 ms
// 
// Powered by CP Editor (https://cpeditor.org)


#include <bits/stdc++.h>
using namespace std;
#define int long long
using ll = long long;
const int maxn = 2e5 + 6, INF = 0x3f3f3f3f, base = 13331, mod1 = 998244353, mod2 = 1e9 + 7;
int n, m, s, t; 
vector <int> a[10], ans, b[maxn];
map <vector <int> , int> mp;

void solve()
{
	cin >> n;
	for (int i = 0; i < n; ++ i) {
		int c;
		scanf("%lld", &c);
		ans.emplace_back(c - 1);
		for (int j = 0; j < c; ++ j) {
			int x;
			scanf("%lld", &x);
			a[i].emplace_back(x);
		}
	}

	cin >> m;
	for (int i = 0; i < m; ++ i) { 
		for (int j = 0; j < n; ++ j) {
			int x;
			scanf("%lld", &x);
			x -- ;
			b[i].emplace_back(x);
		}
		mp[b[i]] = 1;
	}  
	
	if(mp.find(ans) == mp.end()) {
		for (auto it : ans)
			cout << it + 1 << ' ';
		puts("");
		return ;
	}
	int res = 0;
	for (int i = 0; i < m; ++ i) {
		int sum = 0;
		for (int j = 0; j < n; ++ j)
			sum += a[j][b[i][j]];
		for (int j = 0; j < n; ++ j) {
			sum -= a[j][b[i][j]];
			if(b[i][j] == 0) continue;
			b[i][j] -- ;
			sum += a[j][b[i][j]];
			if(mp.find(b[i]) == mp.end()) 
				if(sum > res) 
					ans = b[i], res = sum;
			sum -= a[j][b[i][j]];
			b[i][j] ++ ;
			sum += a[j][b[i][j]];
		}
	}
	for (auto it : ans)
		cout << it + 1 << ' ';
	puts(""); 
}

signed main()
{
	// cin >> t;
	t = 1;
	while(t -- ) {
		solve();
	}
	return 0;
}

E. Coloring

Problem

Solution

Code

F. Occurrences

Problem

Solution

set up a i a_i ai = length i i The number of valid subarrays of i.

set up a i a_i Generating function of ai A ( x ) = ∑ i = 1 ∞ a i x i A(x)=\sum\limits_{i=1}^{\infin}a_ix^i A(x)=i=1∑∞​ai​xi​​​

Set generating function B ( x ) B(x) B(x) is the whole sequence a a The number of schemes of a is obviously constructed with a length of m m Sequence of m + a a a) the number of options is: [ x m ] B ( x ) [x^m]B(x) [xm]B(x)​​​​

yes:

B = 1 + A + A × A + A × A × A + ⋯ = ∑ i = 0 ∞ A i = 1 1 − A ( x ) \displaystyle B=1+A+A\times A+A\times A\times A+\cdots=\sum\limits_{i=0}^{\infin}A^i=\cfrac{1}{1-A(x)} B=1+A+A×A+A×A×A+⋯=i=0∑∞​Ai=1−A(x)1​

Polynomial inverse calculation 1 1 − A ( x ) \cfrac{1}{1-A(x)} 1 − A(x)1 − is enough.

Code