The Preliminary Contest for ICPC China Nanchang National Invitational

目录

• Contest Info
• Solutions
  • A. PERFECT NUMBER PROBLEM
  • D. Match Stick Game
  • G. tsy's number
  • H. Coloring Game'
  • I. Max answer
  • J. Distance on the tree
  • K. MORE XOR
  • M. Subsequence

Contest Info

---

[Practice Link](https://www.jisuanke.com/contest/2290?view=challenges)

8/13

O

-

-

O

-

-

O

O

O

O

O

-

O

• O 在比赛中通过
• Ø 赛后通过
• ! 尝试了但是失败了
• - 没有尝试

Solutions

---

A. PERFECT NUMBER PROBLEM

签到题。

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

}

D. Match Stick Game

G. tsy's number

H. Coloring Game'

I. Max answer

题意：

定义一个区间\([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;

}

J. Distance on the tree

K. MORE XOR

M. Subsequence

题意：

给出串\(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;

}