Brush some recently cf2000 To 2100 The subject of

a week 7 Above Mainly on weekends

2000 Come first 20 Avenue

F. Array Partition（ Line segment tree + Two points ）

At that time, I had thought of fixing the left endpoint , Then the right endpoint split

But I find that there is no monotony like the binary answer , It's not like 000011111 like that

Then it got stuck

In fact, there is no monotony , It's like binary search 000010000

So check the middle one that matches the answer , So keep approaching the middle

#include <bits/stdc++.h>
#define l(k) (k << 1) 
#define r(k) (k << 1 | 1) 
#define rep(i, a, b) for(int i = (a); i < (b); i++)
#define _for(i, a, b) for(int i = (a); i <= (b); i++)
using namespace std;

const int N = 2e5 + 10;
int tmax[N << 4], tmin[N << 4], a[N], n;

void up(int k)
{
	tmax[k] = max(tmax[l(k)], tmax[r(k)]);
	tmin[k] = min(tmin[l(k)], tmin[r(k)]);
}

void build(int k, int l, int r)
{
	if(l == r)
	{
		tmax[k] = tmin[k] = a[l];
		return;
	}
	int m = l + r >> 1;
	build(l(k), l, m);
	build(r(k), m + 1, r);
	up(k);
}

int query_max(int k, int l, int r, int L, int R)
{
	if(L <= l && r <= R) return tmax[k];
	int res = 0, m = l + r >> 1;
	if(L <= m) res = max(res, query_max(l(k), l, m, L, R));
	if(R > m) res = max(res, query_max(r(k), m + 1, r, L, R));
	return res;
}

int query_min(int k, int l, int r, int L, int R)
{
	if(L <= l && r <= R) return tmin[k];
	int res = 2e9, m = l + r >> 1;
	if(L <= m) res = min(res, query_min(l(k), l, m, L, R));
	if(R > m) res = min(res, query_min(r(k), m + 1, r, L, R));
	return res;
}

int main()
{
	int T; scanf("%d", &T);
	while(T--)
	{
		scanf("%d", &n);
		_for(i, 1, n) scanf("%d", &a[i]);
		build(1, 1, n);

		bool find = false;
		_for(x, 1, n)
		{
			int max1 = query_max(1, 1, n, 1, x);
			int l = x, r = n + 1;
			while(l + 1 < r)
			{
				int m = l + r >> 1;
				int min2 = query_min(1, 1, n, x + 1, m), max3 = query_max(1, 1, n, m + 1, n);
				if(min2 > max1 || max3 > max1) l = m;
				else if(min2 < max1 || max3 < max1) r = m;
				else 
				{
					find = true;
					printf("YES\n%d %d %d\n", x, m - x, n - m);
					break;
				}
			}
			if(find) break;
		}
		if(!find) puts("NO");
	}

    return 0;
}

D. Prefixes and Suffixes（kmp + Trees ）

When I think about it, I know to keep jumping Next You can find all prefix and suffix matches

I've done similar projects before

But I don't know such statistics

The positive solution uses the idea of trees , Very beautiful

That is, implicit graph , A seemingly unrelated thing implies a graph

First, a prefix , If it appears in another place , Then take this other place as the suffix string , The prefix and suffix are matched

At this moment Next The array is not necessarily this length , But if you keep jumping Next It will jump to this length

jump Next The process is transformed into a tree , The node is 0 To len, The representative length is 0 To len The prefix of

i You can jump to Next[i] So that is Next[i] It's the father ,i It's the son

Then consider all the places where this prefix appears , They keep jumping Next You can jump to it

First initialize the value of each node as 1, The representative himself appeared once

Then the subtree sum is the number of times it appears

It's so showy

#include <bits/stdc++.h>
#define rep(i, a, b) for(int i = (a); i < (b); i++)
#define _for(i, a, b) for(int i = (a); i <= (b); i++)
using namespace std;

const int N = 1e5 + 10;
int Next[N], dp[N], n;
char s[N];

void get_next()
{
	Next[0] = -1;
	int i = 0, j = -1;
	while(i < n)
	{
		if(j == -1 || s[i] == s[j])
		{
			i++; j++;
			Next[i] = j;
		}
		else j = Next[j];
	}
}

int main()
{
	scanf("%s", s);
	n = strlen(s);
	get_next();

	for(int i = n; i >= 0; i--) dp[i] = 1;
	for(int i = n; i >= 0; i--)
		if(Next[i] != -1)
			dp[Next[i]] += dp[i];
	
	set<pair<int, int>> ans;
	int cur = n;
	while(cur > 0)
	{
		ans.insert(make_pair(cur, dp[cur]));
		cur = Next[cur];
	}
	printf("%d\n", ans.size());
	for(auto x: ans) printf("%d %d\n", x.first, x.second);

    return 0;
}

C. Sereja and Brackets

One . offline + Tree array ( Your own way )

I came up with this problem independently , I use offline + Method of tree array , There seems to be no such practice on the Internet

I have done several offline courses before + The topic of tree array , This question can also

First of all, we can find , Let's ignore the interval , If it could match , Then it must be this pair of matches in a certain area , If there are parentheses, they cannot match , Then it can't match in the interval

One bracket cannot match because another bracket is missing , Intervals only make parentheses less , So it still can't match

So I preprocess each bracket first if it can match , Then save the position of the bracket that matches it

For a pair of matching parentheses , I assign the position of the right bracket to 1 Indicates this bracket

First, sort the left endpoint of the queried interval , When the left endpoint is the same, the right endpoint doesn't matter

Then set up a l and r, First the r Extend to the right

Every time you encounter a closing bracket , If the matching left parenthesis is in the current [l, r] in , That is, the position is greater than or equal to l When , Then the position of the right bracket is assigned as 1, Maintain with a tree array

After the l Extend to the right , Every time you encounter an open parenthesis , If the value of the matching right bracket has been assigned 1, Then because this pair of parentheses has lost the left parenthesis, it cannot contribute to the answer , So we assign it 0

Last , Just use the tree array to sum the asked intervals , The answer is how many pairs of parentheses match

It doesn't matter if the right endpoint is different every time , Because the sum interval has considered this problem

in other words l Deleting the right endpoint when expanding to the left limits the left endpoint of the query , The range of each query limits the right endpoint of the query

#include <bits/stdc++.h>
#define rep(i, a, b) for(int i = (a); i < (b); i++)
#define _for(i, a, b) for(int i = (a); i <= (b); i++)
using namespace std;

const int N = 1e6 + 10;
int f[N], L[N], ans[N], R[N], n, top;
pair<int, char> st[N];
struct query
{
	int l, r, id;
}q[N];

int lowbit(int x) { return x & -x; }

void add(int x, int p)
{
	for(; x <= n; x += lowbit(x))
		f[x] += p;
}

int sum(int x)
{
	int res = 0;
	for(; x; x -= lowbit(x))
		res += f[x];
	return res;
}

int ask(int l, int r)
{
	return sum(r) - sum(l - 1);
}

bool cmp(query x, query y)
{
	return x.l < y.l;
}

int main()
{
	string s;
	cin >> s;
	n = s.size();
	s = " " + s;

	_for(i, 1, n)
	{
		if(s[i] == '(') st[++top] = make_pair(i, '(');
		else if(top > 0)
		{
			R[st[top].first] = i;
			L[i] = st[top].first;
			top--;
		}
	}

	int m; scanf("%d", &m);
	_for(i, 1, m) scanf("%d%d", &q[i].l, &q[i].r), q[i].id = i;
	sort(q + 1, q + m + 1, cmp);

	int l = 1, r = 0;
	_for(i, 1, m)
	{
		while(r < q[i].r)
		{
			r++;
			if(L[r] && L[r] >= l) add(r, 1);
		}
		while(l < q[i].l)
		{
			if(R[l] && ask(R[l], R[l]) == 1) add(R[l], -1);
			l++;
		}
		ans[q[i].id] = ask(q[i].l, q[i].r) * 2;
	}
	_for(i, 1, m) printf("%d\n", ans[i]);

    return 0;
}

Two . Line tree approach

The method of line segment tree is very simple and rough

It is considered macroscopically

Divide the parentheses into unmatched parentheses and matched parentheses

The left unmatched left parenthesis and the right unmatched right parenthesis can match

#include <bits/stdc++.h>
#define l(k) (k << 1)
#define r(k) (k << 1 | 1)
#define rep(i, a, b) for(int i = (a); i < (b); i++)
#define _for(i, a, b) for(int i = (a); i <= (b); i++)
using namespace std;

const int N = 1e6 + 10;
string s;
struct node
{
	int a, b, c;
}t[N << 2];
int n;

node add(node x, node y)
{
	int temp = min(x.b, y.c);
	return node{x.a + y.a + temp, x.b + y.b - temp,x.c + y.c - temp};
}

void up(int k)
{
	t[k] = add(t[l(k)], t[r(k)]);
}

void build(int k, int l, int r)
{
	if(l == r)
	{
		if(s[l] == '(') t[k] = node{0, 1, 0};
		else t[k] = node{0, 0, 1};
		return;
	}
	int m = l + r >> 1;
	build(l(k), l, m);
	build(r(k), m + 1, r);
	up(k);
}

node query(int k, int l, int r, int L, int R)
{
	if(L <= l && r <= R) return t[k];
	node res = {0, 0, 0}; 
	int m = l + r >> 1;
	if(L <= m) res = add(res, query(l(k), l, m, L, R));
	if(R > m) res = add(res, query(r(k), m + 1, r, L, R));
	return res;
}

int main()
{
	cin >> s;
	n = s.size();
	s = " " + s;
	build(1, 1, n);

	int m; scanf("%d", &m);
	while(m--)
	{
		int l, r;
		scanf("%d%d", &l, &r);
		printf("%d\n", query(1, 1, n, l, r).a * 2);
	}

    return 0;
}

D. Two Divisors（ Prime factor decomposition + Coprime ）

This problem is easy to do if you know a knowledge point

if a, b Coprime be gcd(a + b, ab) = 1

gcd(a, b) = 1 Can be launched gcd(a + b, b) = 1   gcd(a + b, a) = 1 ( division )

that a + b And a, b There is no intersection between the prime factor sets of

therefore a + b And ab The prime factor set of has no intersection

This question requires gcd(d1 + d2, ai) = 1

Then make ab = ai That's it

So just put ai Decompose into two coprime numbers b, c bring bc=ai

So we can a Prime factor decomposition , Just choose a different set of prime factors

If the prime factor is decomposed ,ai Given 1e7 You can use Euler sieve to find the minimum quality factor of each number

Screening with minimum quality factor , Can be in logai Find the prime factor decomposition in time

#include <bits/stdc++.h>
#define rep(i, a, b) for(int i = (a); i < (b); i++)
#define _for(i, a, b) for(int i = (a); i <= (b); i++)
using namespace std;

const int N = 1e7 + 10;
bool vis[N];
vector<int> p;
int ans[N][2], mp[N], n;

void get_prime()
{
	vis[0] = vis[1] = 1;
	_for(i, 2, 1e7)
	{
		if(!vis[i]) p.push_back(i), mp[i] = i;   // When finding the minimum prime factor, pay attention to the prime number itself , Don't let it slip 
		for(int x: p)
		{
			if(i * x > 1e7) break;
			vis[i * x] = 1;
			mp[i * x] = x;
			if(i % x == 0) break;
		}
	}
}

int main()
{
	get_prime();
	scanf("%d", &n);
	_for(i, 1, n)
	{
		int cur; scanf("%d", &cur);
		int t = 1, x = mp[cur];
		while(cur % x == 0)
		{
			cur /= x;
			t *= x;
		}
		if(cur == 1) ans[i][0] = ans[i][1] = -1;
		else 
		{
			ans[i][0] = t;
			ans[i][1] = cur;
		}
	}

	_for(i, 1, n) printf("%d ", ans[i][0]); puts("");
	_for(i, 1, n) printf("%d ", ans[i][1]); puts("");

    return 0;
}

D. Odd-Even Subsequence（ Two points answer + greedy ）

After reading the title, there is no idea

It seems that the solution is actually a two-point answer

I think it's difficult to think of a two-point answer to this problem , It's easy to think of a two-point answer

After fixing an answer , There are two cases: odd position and even position , Then greedily construct the sequence , See if you can surpass k Just fine

#include <bits/stdc++.h>
#define rep(i, a, b) for(int i = (a); i < (b); i++)
#define _for(i, a, b) for(int i = (a); i <= (b); i++)
using namespace std;

const int N = 2e5 + 10;
int a[N], n, k;

bool check(int key)
{
	int res = 0;
	_for(t, 0, 1)
	{
		int len = 0, cur = t;
		_for(i, 1, n)
			if(cur || key >= a[i]) 
			{
				cur ^= 1;
				len++;
			}
		res = max(res, len);
	}
	return res >= k;
}

int main()
{
	scanf("%d%d", &n, &k);
	_for(i, 1, n) scanf("%d", &a[i]);

	int l = 0, r = 1e9;
	while(l + 1 < r)
	{
		int m = l + r >> 1;
		if(check(m)) r = m;
		else l = m;
	}
	printf("%d\n", r);

    return 0;
}

Brush it recently 2000 List of questions

You can read the solution without obvious ideas in half an hour , But you must think for yourself first

Ensure the efficiency of doing questions

B. The least round way(dp + programme )

If a path to the end ,2 The number of a,5 The number of b

Then the answer to this path is min(a, b)

That is to say 2 The number of 5 Take the minimum number of

So when min(a, b) The smallest

Obviously, it needs to be discussed in categories ,a Minimum or b Minimum

One of these two must be the answer

The answer cannot be smaller than this

So we just dp two , obtain 2 and 5 The minimum value of , Then record the plan

Here's a special case

There is 0 The situation of , If there is 0, Then you can go through this point , So that the final value is 0

At this time 0 The number of 1

So if the previous answer is greater than 1, Just use this one to pass 0 The route of the

#include <bits/stdc++.h>
#define rep(i, a, b) for(register int i = (a); i < (b); i++)
#define _for(i, a, b) for(register int i = (a); i <= (b); i++)
using namespace std;

const int N = 1e3 + 10;
int a[N][N], b[N][N][2], dp[N][N][2], p[N][N][2], n;

void cal(int x, int c[])
{
	while(x && x % 2 == 0) x /= 2, c[0]++;
	while(x && x % 5 == 0) x /= 5, c[1]++;
}

void print(int x, int y, int cur)
{
	if(!p[x][y][cur]) return;
	if(p[x][y][cur] == 1) 
	{
		print(x - 1, y, cur);
		printf("D");
	}
	else 
	{
		print(x, y - 1, cur);
		printf("R");
	}
}

void read(int& x)
{
	x = 0; char ch = getchar();
	while(!isdigit(ch)) ch = getchar();
	while(isdigit(ch)) { x = x * 10 + ch - '0'; ch = getchar(); }
}

int main()
{
	int find = 0, x, y;
	read(n);
	_for(i, 1, n)
		_for(j, 1, n)
		{
			read(a[i][j]);
			if(a[i][j] == 0)
			{
				find = 1;
				x = i; y = j;
			}
		}

	_for(i, 1, n)
		_for(j, 1, n)
			cal(a[i][j], b[i][j]);

	_for(i, 0, n) dp[i][0][0] = dp[0][i][0] = dp[i][0][1] = dp[0][i][1] = 1e9;
	dp[1][1][0] = b[1][1][0];
	dp[1][1][1] = b[1][1][1];

	_for(i, 1, n)
		_for(j, 1, n)
		{
			if(i == 1 && j == 1) continue;
			if(dp[i - 1][j][0] < dp[i][j - 1][0])
			{
				dp[i][j][0] = dp[i - 1][j][0] + b[i][j][0];
				p[i][j][0] = 1;
			}
			else
			{
				dp[i][j][0] = dp[i][j - 1][0] + b[i][j][0];
				p[i][j][0] = 2;
			}
			if(dp[i - 1][j][1] < dp[i][j - 1][1])
			{
				dp[i][j][1] = dp[i - 1][j][1] + b[i][j][1];
				p[i][j][1] = 1;
			}
			else
			{
				dp[i][j][1] = dp[i][j - 1][1] + b[i][j][1];
				p[i][j][1] = 2;
			}
		}
	
	int ans = min(dp[n][n][0], dp[n][n][1]);
	if(find && ans > 1)
	{
		puts("1");
		_for(i, 1, x - 1) printf("D");
		_for(i, 1, n - 1) printf("R");
		_for(i, 1, n - x) printf("D");
	}
	else
	{
		printf("%d\n", ans);
		if(dp[n][n][0] < dp[n][n][1]) print(n, n, 0);
		else print(n, n, 1);
	}

    return 0;
}

D. Three Integers（ violence ）

I think we should find out what kind of laws and properties

I didn't expect direct violence ……

Note that it is not necessarily the maximum 1e4 

twice as much , Probably 2e4 It will be better

#include <bits/stdc++.h>
#define rep(i, a, b) for(register int i = (a); i < (b); i++)
#define _for(i, a, b) for(register int i = (a); i <= (b); i++)
using namespace std;

int main()
{
	int T; scanf("%d", &T);
	while(T--)
	{
		int a, b, c, A, B, C, ans = 1e9;
		scanf("%d%d%d", &a, &b, &c);
		_for(x, 1, 2e4)
			for(int y = x; y <= 2e4; y += x)
				for(int z = y; z <= 2e4; z += y)
				{
					int cur = abs(a - x) + abs(b - y) + abs(c - z);
					if(cur < ans)
					{
						ans = cur;
						A = x;
						B = y;
						C = z;
					}
				}
		printf("%d\n%d %d %d\n", ans, A, B, C);
	}

    return 0;
}

D. Yet Another Yet Another Task（ enumeration + dp）

Make... Independently

be aware ai The range of is very abnormal and small

A lot of questions , There are times when the data range is abnormal , It is often a breakthrough

Because it's small , So you can enumerate the maximum values directly

For each interval less than the maximum value , Sure dp Find the maximum value of the continuous interval , Then update the answer

#include <bits/stdc++.h>
#define rep(i, a, b) for(register int i = (a); i < (b); i++)
#define _for(i, a, b) for(register int i = (a); i <= (b); i++)
using namespace std;

const int N = 1e5 + 10;
int a[N], dp[N], n;

int cal(vector<int> ve)
{
	int res = -1e9;
	dp[0] = ve[0];
	rep(i, 1, ve.size()) dp[i] = max(dp[i - 1], 0) + ve[i];
	rep(i, 0, ve.size()) res = max(res, dp[i]);
	return res;
}

int solve(int key)
{
	int res = 0;
	vector<int> ve;
	_for(i, 1, n)
	{
		if(a[i] <= key) ve.push_back(a[i]);
		else
		{
			if(ve.size()) res = max(res, cal(ve) - key);
			ve.clear();
		}
	}
	if(ve.size()) res = max(res, cal(ve) - key);
	return res;
}

int main()
{
	scanf("%d", &n);
	_for(i, 1, n) scanf("%d", &a[i]);

	int ans = 0;
	_for(i, -30, 30) ans = max(ans, solve(i));
	printf("%d\n", ans);

    return 0;
}