The 2022 ICPC Asia Regionals Online Contest (II) 解题报告

发布于：2022-12-02 ⋅ 阅读:(162) ⋅ 点赞:(0)

A

将一个位数不超过 1 0 6 10^6 106 的数拆分成若干 0 0 0 - 9 9 9 的数，以第 i i i 位开头，每 j j j 位的数字求和定义为 a i j a_{ij} aij​，给出该数组 a a a 的最多前 100 100 100 行，求原数对于除 2 2 2， 5 5 5 以外的 100 100 100 以内素数的取模

数组 a a a 的行数和模数范围一致，可以很容易想到费马小定理

a p − 1 ≡ 1 (   m o d     p ) a^{p - 1}\equiv 1(\bmod\ p) ap−1≡1(mod p)

那么我们找到第 p − 1 p-1 p−1 行，取包含个位的那一个数，它组成部分的每项增长均为 1 0 p − 1 10^{p - 1} 10p−1，这些在取余后等于 1 1 1，都没有贡献，于是就等同于求系数的和，而其它对其进行乘若干 10 10 10 的操作即可也将 10 10 10 的幂取模变为 1 1 1，即可用有限的数计算出结果

#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstring>
#include <algorithm>
#include <queue>

#define file(s) freopen(s".in", "r", stdin), freopen(s".out", "w", stdout);
#define dbg(x) cerr<<"In Line"<<__LINE__<<" the "<<#x<<" = "<<x<<'\n';
#define abs(x) ((x) < 0 ? -(x) : (x))

using namespace std;

const int N = 2e6 + 10;

inline int read() {
	bool sym = 0; int res = 0; char ch = getchar();
	while (!isdigit(ch)) sym |= (ch == '-'), ch = getchar();
	while (isdigit(ch)) res = (res << 3) + (res << 1) + (ch ^ 48), ch = getchar();
	return sym ? -res : res;
}

int n, q, a[110][110];

int main() {
	int T = read();
	while (T--) {
		n = read();
		for (int i = 1; i <= min(n, 100); i++) for (int j = 1; j <= i; j++) a[i][j] = read();
		q = read();
		if (n <= 100) {
			for (int i = 1; i <= q; i++) {
				int mod = read(), c = 0;
				for (int i = 1; i <= n; i++) c = (c * 10 + a[n][i]) % mod;
				printf("%d\n", c);
			}
		} else {
			for (int i = 1; i <= q; i++) {
				int mod = read(), c = 0;
				for (int i = n % (mod - 1) + 1; i <= mod - 1; i++) c = (c * 10 + a[mod - 1][i]) % mod;
				for (int i = 1; i <= n % (mod - 1); i++) c = (c * 10 + a[mod - 1][i]) % mod;
				printf("%d\n", c);
			}
		}
	}
	return 0;
}

B

给定一个不降序列，你将进行 k k k轮操作，每轮操作可以按顺序执行下面两个子操作

  1. 选取一个数删掉，或者不做任何操作

  2. 选取一个数，使其变为另一个数，并使得新序列依旧不降

对于 k ∈ { 1 , n } k\in \{1, n\} k∈{1,n}，若 k k k 轮操作后序列长度为 n n n，求出 ∑ i = 2 n ( a i − a i − 1 ) 2 \sum_{i = 2}^{n} (a_i - a_{i - 1}) ^ 2 ∑i=2n​(ai​−ai−1​)2 的最大值

两个操作等价，发现贡献有区间性，后面删的数不会影响前面的贡献，考虑 d p dp dp， f i j f_{ij} fij​ 表示前 i i i 个数保留 j j j 个数且一定保留头尾的最大价值，枚举上一个转移过来的位置，将沿途的数全部删掉，记录贡献即可

#include<iostream>
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<cstring>
#include<queue>

using namespace std;

const int N = 2e6 + 10;

int read() {
	int res = 0; bool sym = 0; char ch = getchar();
	while (!isdigit(ch)) sym |= (ch == '-'), ch = getchar();
	while (isdigit(ch)) res = (res << 3) + (res << 1) + (ch ^ 48), ch = getchar();
	return sym ? -res : res;
}

int n, m, a[N];

long long f[110][110];

int main() {
	n = read();
	for (int i = 1; i <= n; i++) a[i] = read();
	for (int i = 2; i <= n; i++) f[i][2] = 1ll * (a[i] - a[1]) * (a[i] - a[1]);
	for (int k = 3; k <= n - 2; k++) {
		for (int i = 2; i <= n; i++) {
			for (int j = 2; j < i; j++) {
				f[i][k] = max(f[i][k], f[j][k - 1] + 1ll * (a[i] - a[j]) * (a[i] - a[j]));
			}
		}
	}
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) printf("%d ", f[i][j]); printf("\n");
	}
	for (int i = 2; i <= n << 1; i += 2) printf("%lld\n", f[n][n - min(i, n - 2)]);
	return 0;
}

C

D

E

给定 k k k，构造序列使得

∀ i ∈ [ 1 , n ] ， a i > 1 ∀ i ∈ [ 2 , n ] ， gcd ⁡ ( a i − 1 , a i ) = 1 a 1 = k \forall i\in [1,n]，a_i > 1 \\ \forall i\in [2,n]，\gcd(a_{i−1},a_i) = 1 \\ a_1 = k ∀i∈[1,n]，ai​>1∀i∈[2,n]，gcd(ai−1​,ai​)=1a1​=k

最小化

∑ i = 1 n a i \sum_{i = 1}^n a_i i=1∑n​ai​

签到题，找到最小的质因数的下一个质数一定是某个数最小的互质的数，然后 2 2 2 和 3 3 3 循环即可

#include<iostream>
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<cstring>
#include<queue>

using namespace std;

const int N = 2e6 + 10;

int read() {
	int res = 0; bool sym = 0; char ch = getchar();
	while (!isdigit(ch)) sym |= (ch == '-'), ch = getchar();
	while (isdigit(ch)) res = (res << 3) + (res << 1) + (ch ^ 48), ch = getchar();
	return sym ? -res : res;
}

int n, m, prime[N], cnt;

bool vis[N];

int main() {
	n = read(); int ans = read();
	for (int i = 2; i <= 1000; i++) {
		if (!vis[i]) prime[++cnt] =  i;
		for (int j = 1; j <= cnt && i * prime[j] <= 1000; j++) {
			vis[i * prime[j]] = 1; if (i % prime[j] == 0) break;
		}
	}
	int x = 1; while (ans % prime[x] == 0) x++;
	ans += prime[x];
	if (x == 1) for (int i = 3; i <= n; i++) ans += 2 + (i & 1);
	else for (int i = 3; i <= n; i++) ans += 2 + !(i & 1);
	printf("%d", ans);
	return 0;
}

F

一棵树，最初只有 1 1 1 号点，每秒对于树上所有点按编号依次生成 k k k 个子节点，求 x x x， y y y的LCA

签到题， m m m 轮后树有 k m k^m km 个节点，一个节点 x x x 的父亲可以通过上一轮的数量推算出这一轮该节点是第几个生成的，从而算出父亲，因为树高是 l o g log log 的，可以暴力爬父亲找LCA

#include<iostream>
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<cstring>
#include<queue>

#define mp(x, y) make_pair(x, y)

using namespace std;

const int N = 2e6 + 10;

long long read() {
	long long res = 0; bool sym = 0; char ch = getchar();
	while (!isdigit(ch)) sym |= (ch == '-'), ch = getchar();
	while (isdigit(ch)) res = (res << 3) + (res << 1) + (ch ^ 48), ch = getchar();
	return sym ? -res : res;
}

int n, m;

double pw[N];

int main() {
	int T = read();
	while (T--) {
		long long k = read(), x = read(), y = read(); if (x < y) swap(x, y); pw[1] = 1;
		for (int i = 2; i <= 100000; i++) {
			pw[i] = pw[i - 1] * (k + 1); if (pw[i] >= x) break;
		}
		// for (int i = 2; pw[i - 1] <= x; i++) printf("%lld ", pw[i]); printf("\n");
		while (x != y) {
			// printf("%lld %lld\n", x, y);
			if (x < y) swap(x, y); int t = 1; while (pw[t] < x) t++;
			// printf("%lld\n", t);
			x = (x - (long long)pw[t - 1] + k - 1ll) / k;
		}
		printf("%lld\n", x);
	}
	return 0;
}

G

给定多个二元组 l , r l,r l,r，每个二元组表示的区间仅存在包含和不交的关系，你需要构造排列，对于任意给定的二元组 l , r l,r l,r均满足 max ⁡ i = l r a i − m i n i = l r a i = r − l \max_{i = l}^{r}a_i - min_{i = l}^{r}a_i = r - l maxi=lr​ai​−mini=lr​ai​=r−l，求可构造的排列数量

区间包含或者不交意味着是类似于树形结构，于是考虑对于每个二元组作为节点，构建一棵树，父子关系表示包含关系，那么一个区间的答案为

f u = ( l e n ( u ) − ∑ v ∈ s o n ( u ) l e n ( v ) − 1 ) × ∏ v ∈ s o n ( u ) f v f_{u} = \Bigg(len(u) - \sum_{v\in son(u)} len(v) - 1\Bigg)\times \prod_{v\in son(u)} f_v fu​=(len(u)−v∈son(u)∑​len(v)−1)×v∈son(u)∏​fv​

#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstring>
#include <algorithm>
#include <queue>

#define file(s) freopen(s".in", "r", stdin), freopen(s".out", "w", stdout);
#define dbg(x) cerr<<"In Line"<<__LINE__<<" the "<<#x<<" = "<<x<<'\n';
#define abs(x) ((x) < 0 ? -(x) : (x))

using namespace std;

const int N = 2e6 + 10, mod = 1e9 + 7;

inline int read() {
	bool sym = 0; int res = 0; char ch = getchar();
	while (!isdigit(ch)) sym |= (ch == '-'), ch = getchar();
	while (isdigit(ch)) res = (res << 3) + (res << 1) + (ch ^ 48), ch = getchar();
	return sym ? -res : res;
}

int n, m, fa[N], head[N], cnt, f[N], mul[N];

struct DAT {
	int l, r, len;
} dat[N];

struct EDGE {
	int u, v, nxt;
} edge[N];

bool cmp(DAT a, DAT b) {
	return a.l == b.l ? a.r > b.r : a.l < b.l;
}

void add(int u, int v) {
	edge[++cnt] = (EDGE){u, v, head[u]}; head[u] = cnt;
}

void dfs(int u) {
	f[u] = 1; int cnt = 0, sum = 0;
	for (int e = head[u]; e; e = edge[e].nxt) {
		int v = edge[e].v; if (v == fa[u]) continue; dfs(v);
		cnt++; sum += dat[v].len; f[u] = 1ll * f[u] * f[v] % mod;
	}
	f[u] = 1ll * f[u] * mul[dat[u].len - sum + cnt] % mod;
}

int main() {
	n = read(); m = read(); mul[1] = 1;
	for (int i = 2; i <= n; i++) mul[i] = 1ll * mul[i - 1] * i % mod;
	for (int i = 1; i <= m; i++) {
		dat[i].l = read(); dat[i].r = read(); dat[i].len = dat[i].r - dat[i].l + 1;
	}
	sort(dat + 1, dat + m + 1, cmp);
	// for (int i = 1; i <= m; i++) printf("%d %d %d\n", dat[i]);
	int u = 0; dat[0].len = n;
	for (int v = 1; v <= m; v++) {
		while (dat[v].l > dat[u].r && u) u = fa[u]; add(u, v); fa[v] = u; u = v;
	}
	dfs(0); printf("%d", f[0]);
	return 0;
}

H

I

J

A和B轮流从一个序列中取数，每次取的数必须严格比上一个人取的数大，且只能取序列的头和尾部的数，A先手，第一个不能取数的人判负，问两人最优解下获胜者

首尾均是一段连续的可操作序列，那么有两种情况，取两边大的，那么就只能将这一边去取到底，直接可以判断胜负，取小的把选择权交给对面，若两边相等，可以同时判断两边的胜负，存在奇数即获胜，不存在一定输

#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstring>
#include <algorithm>
#include <queue>

#define file(s) freopen(s".in", "r", stdin), freopen(s".out", "w", stdout);
#define dbg(x) cerr<<"In Line"<<__LINE__<<" the "<<#x<<" = "<<x<<'\n';
#define abs(x) ((x) < 0 ? -(x) : (x))

using namespace std;

const int N = 2e6 + 10;

inline int read() {
	bool sym = 0; int res = 0; char ch = getchar();
	while (!isdigit(ch)) sym |= (ch == '-'), ch = getchar();
	while (isdigit(ch)) res = (res << 3) + (res << 1) + (ch ^ 48), ch = getchar();
	return sym ? -res : res;
}

int n, m, a[N];

int main() {
	n = read();
	for (int i = 1; i <= n; i++) a[i] = read();
	int lc = 1, rc = n, l = 1, r = n;
	while (a[lc] < a[lc + 1]) lc++; while (a[rc] < a[rc - 1]) rc--; rc = n - rc + 1;
	// printf("%d %d\n", lc, rc);
	for (int i = 1; i <= n; i++) {
		// printf("%d\n", i);
		if (!lc) if (rc & 1) {puts(i & 1 ? "Alice" : "Bob"); break;}
		if (!rc) if (lc & 1) {puts(i & 1 ? "Alice" : "Bob"); break;}
		if (a[l] == a[r]) {
			if (lc & 1 || rc & 1) {puts(i & 1 ? "Alice" : "Bob"); break;}
			else if (lc) l++, lc--; else r--, rc--;
		} else
		if (a[l] > a[r]) {
			if (lc & 1) {puts(i & 1 ? "Alice" : "Bob"); break;} else r--, rc--;
		} else
		if (a[r] > a[l]) {
			if (rc & 1) {puts(i & 1 ? "Alice" : "Bob"); break;} else l++, lc--;
		}
	}
	return 0;
}

K

L

多次询问一个字符串中ICPC子序列的出现次数

满足差分性质，直接差分即可

#include<iostream>
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<cstring>

using namespace std;

const int N = 2e6 + 10, mod = 998244353;

int read() {
	int res = 0; bool sym = 0; char ch = getchar();
	while (!isdigit(ch)) sym |= (ch == '-'), ch = getchar();
	while (isdigit(ch)) res = (res << 3) + (res << 1) + (ch ^ 48), ch = getchar();
	return sym ? -res : res;
}

int n, q, l[N], r[N];

char ch[N];

struct DAT {
	int i, c, p, ic, cp, pc, icp, cpc, icpc;
} dat[N];

DAT operator +(const DAT &a, const DAT &b) {
	DAT c;
	c.i = a.i + b.i; c.c = a.c + b.c; c.p = a.p + b.p;
	c.ic = (a.ic + b.ic + 1ll * a.i * b.c) % mod;
	c.cp = (a.cp + b.cp + 1ll * a.c * b.p) % mod;
	c.pc = (a.pc + b.pc + 1ll * a.p * b.c) % mod;
	c.icp = (a.icp + b.icp + 1ll * a.i * b.cp + 1ll * a.ic * b.p) % mod;
	c.cpc = (a.cpc + b.cpc + 1ll * a.c * b.pc + 1ll * a.cp * b.c) % mod;
	c.icpc = (a.icpc + b.icpc + 1ll * a.i * b.cpc + 1ll * a.ic * b.pc + 1ll * a.icp * b.c) % mod;
	return c;
}

DAT operator -(const DAT &a, const DAT &b) {
	DAT c;
	c.i = a.i - b.i; c.c = a.c - b.c; c.p = a.p - b.p;
	c.ic = ((a.ic - b.ic - 1ll * b.i * c.c % mod) + mod) % mod;
	c.cp = ((a.cp - b.cp - 1ll * b.c * c.p % mod) + mod) % mod;
	c.pc = ((a.pc - b.pc - 1ll * b.p * c.c % mod) + mod) % mod;
	c.icp = ((a.icp - b.icp - 1ll * b.i * c.cp - 1ll * b.ic * c.p) % mod + mod) % mod;
	c.cpc = ((a.cpc - b.cpc - 1ll * b.c * c.pc - 1ll * b.cp * c.c) % mod + mod) % mod;
	c.icpc = ((a.icpc - b.icpc - 1ll * b.i * c.cpc - 1ll * b.ic * c.pc - 1ll * b.icp * c.c) % mod + mod) % mod;
	return c;
}

int main() {
    n = read(); q = read(); scanf("%s", ch + 1);
	int x = read(), a = read(), b = read(), p = read();
	for (int i = 1; i <= q; i++) x = (1ll * a * x + b) % p, l[i] = x % n + 1;
	for (int i = 1; i <= q; i++) x = (1ll * a * x + b) % p, r[i] = x % n + 1;
	// for (int i = 1; i <= q; i++) printf("%d %d\n", l[i], r[i]);
	for (int i = 1; i <= n; i++) dat[i] = (DAT){ch[i] == 'I', ch[i] == 'C', ch[i] == 'P', 0, 0, 0, 0, 0, 0};
	for (int i = 2; i <= n; i++) dat[i] = dat[i - 1] + dat[i];
	// for (int i = 1; i <= n; i++) printf("%d %d %d %d %d %d %d %d %d\n", dat[i]);
	int res = 0;
	for (int i = 1; i <= q; i++) {
		if (l[i] > r[i]) swap(l[i], r[i]);
		// printf("%d %d\n", l[i], r[i]);
		DAT ans = dat[r[i]] - dat[l[i] - 1];
		// printf("%d\n", ans.icpc);
		res = (res + ans.icpc) % mod;
	}
	printf("%d", res);
	return 0;
}

网站公告

今日签到

点亮在社区的每一天
去签到

热门文章

最新发布