最近刷一些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;
}