最近刷一些cf2000到2100的题目

一周7题以上 周末为主

2000的题先来20道

F. Array Partition（线段树 + 二分）

这道题我当时已经想到了固定左端点，然后右端点二分了

但是我发现没有像二分答案那样的单调性，并不是像000011111那样

然后就卡住了

实际上确实没有单调性，是像二分查找那样000010000

所以就是查中间一个符合答案的点，所以就不断向中间逼近

#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 + 树）

自己想的时候很就知道不断跳Next就可以求出所有前缀和后缀匹配

之前做过类似的题目

但是不知道这么统计次数

正解用到了树的思想，很秀

也就是隐式图，一个看起来和图无关的东西隐含着图

首先一个前缀，如果在另一个地方出现，那么把这另一个地方作为后缀的字符串来说，前后缀是匹配的

这时的Next数组不一定是这个长度，但是如果一直跳Next的话是会跳到这个长度的

跳Next的过程转化到树上，节点为0到len，代表长度为0到len的前缀

i可以跳到Next[i] 那么就是Next[i]是父亲，i是儿子

那么考虑这个前缀出现的所有地方，它们不断跳Next一定可以跳到它

先初始化每一个节点的值为1，代表本身出现了一次

那么子树和就是其出现的次数

太秀了

#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

一.离线 + 树状数组 (自己的做法)

这道题我独立想出了，我用的是离线+树状数组的方法，网上貌似没有这个做法

之前做过几道用离线+树状数组做的题目，这道题也可以

首先可以发现，先不管区间，如果原来可以匹配，那么在某个区间种也一定是一定是这一对匹配，如果有括号不能匹配，那么在区间中也不能匹配

一个括号不能匹配是因为少了另一个括号，区间只会使得括号更少，因此还是不能匹配

所以我先预处理了每个括号如果可以匹配，那么存一下与其匹配的括号的位置

对于一对匹配的括号，我用右括号的位置赋值为1表示这个括号

先将询问的区间进行左端点排序，左端点相同的时候右端点无所谓

然后设置一个l和r，先将r向右拓展

每次遇到一个右括号，如果与它匹配的左括号在当前的[l, r]中，也就是位置大于等于l的时候，那么右括号这个位置就赋值为1，用树状数组维护

之后将l向右拓展，每次遇到一个左括号，如果其匹配的右括号的值已经赋为1，那么因为这一对括号失去了左括号就无法对答案贡献，于是就将其赋值为0

最后，就用树状数组对询问的区间求和，答案就是有多少对括号匹配了

每次的右端点不同没有关系，因为求和的区间已经考虑了这个问题

也就是说l向左拓展时删除右端点限制了询问的左端点，每次询问的区间又限制了询问的右端点

#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;
}

二.线段树做法

线段树做法非常简单粗暴

是从宏观上考虑的

把括号分成未匹配的括号和匹配的括号

左边的未匹配的左括号和右边的未匹配的右括号可以匹配

#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（质因数分解 + 互质）

这题如果知道一个知识点就很好做了

若a, b互质 则gcd(a + b, ab) = 1

gcd(a, b) = 1 可以推出 gcd(a + b, b) = 1   gcd(a + b, a) = 1 (辗转相除法)

那么a + b 与a, b的质因数集合都没有交集

所以a + b与ab的质因数集合没有交集

这道题要求gcd(d1 + d2, ai) = 1

那么就令ab = ai就行了

所以就是把ai分解成两个互质的数b, c使得bc=ai

所以就可以把a质因数分解，选择不同的质因数集合就行了

质因数分解的话，ai给的1e7 可以用欧拉筛求出每个数的最小质因子

用最小质因子去筛，可以在logai的时间内求出质因数分解

#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;   //求最小质因子的时候注意质数是本身，不要漏
		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（二分答案 + 贪心）

看了题目之后啥思路都没有

看来题解竟然是二分答案

我觉得这道题就难在想到二分答案，想到二分答案就很容易了

固定一个答案后，分奇位置和偶位置两种情况，然后贪心去构造序列，看能否超过k就好了

#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;
}

最近就刷2000题单

半个小时之内没有明显的思路就可以看题解，但一定要先自己思考

保证做题的效率

B. The least round way(dp + 方案)

如果到终点的某条路径，2的个数为a，5的个数为b

那么这条路径的答案就是min(a, b)

也就是2的个数与5的个数取最小值

那么什么时候min(a, b)最小呢

显然要分类讨论，a最小或者b最小

这两个的其中之一一定就是答案

答案不可能比这个更小

所以我们就dp两次，得出2和5的最小值，然后记录方案就行了

这里有一个特例

就是有0的情况，如果矩阵中有0，那么可以经过这个点，使得最终的值为0

这时0的个数为1

所以如果前面得出的答案大于1，就用这条经过0的路线

#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（暴力）

我以为要找出什么规律什么性质

没想到直接暴力……

注意不一定是最大值1e4 

两倍，可能2e4会更优

#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（枚举 + dp）

独立做出

注意到ai的范围非常反常很小

很多题目，有一些数据范围很反常的时候，往往是突破口

因为很小，所以可以直接枚举最大值

对于每一段小于最大值的区间，可以dp求出连续区间的最大值，然后更新答案

#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;
}