目录
Contest InfoSolutions A. PERFECT NUMBER PROBLEMD. Match Stick GameG. tsy's numberH. Coloring Game'I. Max answerJ. Distance on the treeK. MORE XORM. SubsequencePractice Link
SolvedABCDEFGHIJKLM8/13O--O--OOOOO-O O 在比赛中通过Ø 赛后通过! 尝试了但是失败了- 没有尝试签到题。
#include <bits/stdc++.h> using namespace std; int main() { int a[] = { 6, 28, 496, 8128, 33550336 }; for (int i = 0; i < 5; ++i) { printf("%d\n", a[i]); } return 0; }题意： 定义一个区间\([l, r]\)的值为：\[ \begin{eqnarray*} f(l, r) = (max_{i = l}^r a_i) \cdot (\sum\limits_{i = l}^r a_i) \end{eqnarray*} \]
思路一： 单调栈求出当前点左边第一个比它小的位置，当前点右边第一个比它小的位置。 然后就算出管辖范围，然后线段树维护一下最大最小区间前后缀即可。 代码一：
#include <bits/stdc++.h> using namespace std; #define ll long long #define N 500010 #define INF 0x3f3f3f3f #define INFLL 0x3f3f3f3f3f3f3f3f int n, a[N]; ll sum[N]; int f[N], g[N]; int Sta[N], top; struct SEG { struct node { ll Max, Min; node () { Min = INFLL; Max = -INFLL; } node (ll Max, ll Min) : Max(Max), Min(Min) {} node operator + (const node &other) const { node res = node(); res.Max = max(Max, other.Max); res.Min = min(Min, other.Min); return res; } }t[N << 2], res; void build(int id, int l, int r) { if (l == r) { t[id] = node(sum[l], sum[l]); return; } int mid = (l + r) >> 1; build(id << 1, l, mid); build(id << 1 | 1, mid + 1, r); t[id] = t[id << 1] + t[id << 1 | 1]; } void query(int id, int l, int r, int ql, int qr) { if (ql > qr) { return; } if (l >= ql && r <= qr) { res = res + t[id]; return; } int mid = (l + r) >> 1; if (ql <= mid) query(id << 1, l, mid, ql, qr); if (qr > mid) query(id << 1 | 1, mid + 1, r, ql, qr); } }seg; int main() { while (scanf("%d", &n) != EOF) { for (int i = 1; i <= n; ++i) { scanf("%d", a + i); } for (int i = 1; i <= n; ++i) { sum[i] = sum[i - 1] + a[i]; } seg.build(1, 1, n); ll res = 0; a[0] = a[n + 1] = -INF; top = 0; Sta[++top] = 0; for (int i = 1; i <= n; ++i) { while (a[i] <= a[Sta[top]]) { --top; } f[i] = Sta[top]; Sta[++top] = i; } top = 0; Sta[++top] = n + 1; for (int i = n; i >= 1; --i) { while (a[i] <= a[Sta[top]]) { --top; } g[i] = Sta[top]; Sta[++top] = i; } // for (int i = 1; i <= n; ++i) { // printf("%d %d %d\n", i, f[i], g[i]); // } for (int i = 1; i <= n; ++i) { if (a[i] == 0) { continue; } else if (a[i] < 0) { seg.res = SEG::node(); ll x = 0, y = 0; seg.query(1, 1, n, f[i], i); if (f[i] == 0) { x = max(x, seg.res.Max); } else { x = seg.res.Max; } seg.res = SEG::node(); seg.query(1, 1, n, i, g[i] - 1); y = seg.res.Min; res = max(res, (y - x) * a[i]); } else { seg.res = SEG::node(); ll x = 0, y = 0; seg.query(1, 1, n, f[i], i); if (f[i] == 0) { x = min(x, seg.res.Min); } else { x = seg.res.Min; } seg.res = SEG::node(); seg.query(1, 1, n, i, g[i] - 1); y = seg.res.Max; res = max(res, (y - x) * a[i]); } } printf("%lld\n", res); } return 0; }思路二： 建出笛卡尔树，然后就确定了区间最小值，再考虑中序遍历是原序列。 那么左右子树分别维护区间和、区间最大最小前后缀，然后向上统计答案并合并
#include <bits/stdc++.h> using namespace std; #define ll long long #define N 500010 #define INF 0x3f3f3f3f int n, a[N]; ll res; struct Cartesian_Tree { struct node { int id, val, fa; // 0 前缀最值 // 1 后缀最值 ll Min[2], Max[2], sum; int son[2]; node() {} node (int id, int val, int fa) : id(id), val(val), fa(fa) { memset(son, 0, sizeof son); memset(Min, 0, sizeof Min); memset(Max, 0, sizeof Max); sum = 0; } bool operator < (const node &other) const { return id < other.id; } }t[N]; int root; void init() { t[0] = node(0, -INF, 0); } void build(int n, int *a) { for (int i = 1; i <= n; ++i) { t[i] = node(i, a[i], 0); } for (int i = 1; i <= n; ++i) { int k = i - 1; while (t[k].val > t[i].val) { k = t[k].fa; } t[i].son[0] = t[k].son[1]; t[k].son[1] = i; t[i].fa = k; t[t[i].son[0]].fa = i; } root = t[0].son[1]; } void DFS(int u) { if (!u) return; int ls = t[u].son[0], rs = t[u].son[1]; DFS(ls); DFS(rs); res = max(res, t[u].val * (t[u].val + t[ls].Min[1] + t[rs].Min[0])); res = max(res, t[u].val * (t[u].val + t[ls].Max[1] + t[rs].Max[0])); t[u].sum = t[ls].sum + t[rs].sum + t[u].val; t[u].Min[0] = min(t[ls].Min[0], t[ls].sum + t[u].val + t[rs].Min[0]); t[u].Min[1] = min(t[rs].Min[1], t[rs].sum + t[u].val + t[ls].Min[1]); t[u].Max[0] = max(t[ls].Max[0], t[ls].sum + t[u].val + t[rs].Max[0]); t[u].Max[1] = max(t[rs].Max[1], t[rs].sum + t[u].val + t[ls].Max[1]); } }CT; int main() { while (scanf("%d", &n) != EOF) { for (int i = 1; i <= n; ++i) { scanf("%d", a + i); } res = -1e18; CT.init(); CT.build(n, a); CT.DFS(CT.root); printf("%lld\n", res); } return 0; }题意： 给出串\(S\)，以及若干串\(T_i\)，每次询问\(T_i\)是否是\(S\)的一个子序列。
思路： 建出序列自动机，暴力跑即可。 时间复杂度：\(\mathcal{O}(26|S| + \sum T_i)\)
代码：
#include <bits/stdc++.h> using namespace std; #define N 100010 int n, m, q; char s[N], t[N]; int T[N][30], nx[30]; int main() { while (scanf("%s", s + 1) != EOF) { n = strlen(s + 1); for (int i = 0; i < 30; ++i) nx[i] = n + 1; for (int i = n; i >= 0; --i) { for (int j = 0; j < 26; ++j) { T[i][j] = nx[j]; } if (i) { nx[s[i] - 'a'] = i; } } scanf("%d", &q); while (q--) { scanf("%s", t + 1); m = strlen(t + 1); int it = 0; for (int i = 1; i <= m; ++i) { it = T[it][t[i] - 'a']; if (it == n + 1) break; } puts(it == n + 1 ? "NO" : "YES"); } } return 0; }转载于:https://www.cnblogs.com/Dup4/p/11154237.html
相关资源：JAVA上百实例源码以及开源项目