CSP2020 提高组题解

T1. 儒略日

题目链接：Link。

  • 首先为了方便讨论，先令 (r gets r + 1)，这样的话，求的就是 " 第几天 " 而不是 " 经过了几天 " 了。
  • 显然可以考虑把 " 时间轴 " 分成亿些 " 时间段 "，在每一段中根据 " 日期变化的周期性 " 计算答案。
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;

int Q;

int c[13] = { 0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31 };

int onelimit = 1721424;
int twolimit = 2299161;

bool isrn(long long x) {
	if (x % 4 != 0 || (x % 100 == 0 && x % 400 != 0)) return false;
	return true;
}

pair<int, int> turn(int x, bool rn) {
	int cnt = 0;
	for (int i = 1; i <= 12; i ++) {
		int delta = c[i];
		if (i == 2 && rn) delta ++;
		if (x <= cnt + delta) return make_pair(x - cnt, i);
		else cnt += delta;
	}
}

long long r;
int year;
long long cnt;

void work1() {
	if (r <= 366) {
		pair<int, int> ans = turn(r, 1);
		cout << ans.first << " " << ans.second << " " << 4713 << " BC" << endl;

		return;
	}

	r -= 366;

	cnt = (r - 1) / 1461 + 1;
	r -= (cnt - 1) * 1461;
	year = 4712 - (cnt - 1) * 4;

	cnt = (r - 1) / 365 + 1;
	if (r == 1461) cnt = 4;
	r -= (cnt - 1) * 365;
	year -= cnt - 1;

	pair<int, int> ans = turn(r, year % 4 == 1 ? 1 : 0);
	cout << ans.first << " " << ans.second << " " << year << " BC" << endl;
}

void work2() {
	r -= onelimit;

	cnt = (r - 1) / 1461 + 1;
	r -= (cnt - 1) * 1461;
	year = 1 + (cnt - 1) * 4;

	cnt = (r - 1) / 365 + 1;
	if (r == 1461) cnt = 4;
	r -= (cnt - 1) * 365;
	year += cnt - 1;

	pair<int, int> ans = turn(r, year % 4 == 0 ? 1 : 0);
	cout << ans.first << " " << ans.second << " " << year << endl;
}

void work3() {
	r -= twolimit;

	if (r <= 78) {
		if (r <= 17)
			cout << 14 + r << " " << 10 << " " << 1582 << endl;
		else if (r <= 47)
			cout << r - 17 << " " << 11 << " " << 1582 << endl;
		else
			cout << r - 47 << " " << 12 << " " << 1582 << endl;
		return;
	}

	r -= 78;

	if (r <= 731) {
		cnt = (r - 1) / 365 + 1;
		if (r == 731) cnt = 2;
		r -= (cnt - 1) * 365;
		year = 1582 + cnt;

		pair<int, int> ans = turn(r, cnt == 2 ? 1 : 0);
		cout << ans.first << " " << ans.second << " " << year << endl;

		return;
	}

	r -= 731;

	if (r <= 5844) {
		cnt = (r - 1) / 1461 + 1;
		r -= (cnt - 1) * 1461;
		year = 1585 + (cnt - 1) * 4;

		cnt = (r - 1) / 365 + 1;
		if (r == 1461) cnt = 4;
		r -= (cnt - 1) * 365;
		year += cnt - 1;

		pair<int, int> ans = turn(r, cnt == 4 ? 1 : 0);
		cout << ans.first << " " << ans.second << " " << year << endl;

		return;
	}

	r -= 5844;

	cnt = (r - 1) / 146097 + 1;
	r -= (cnt - 1) * 146097;
	year = 1601 + (cnt - 1) * 400;

	cnt = (r - 1) / 36524 + 1;
	if (r == 146097) cnt = 4;
	r -= (cnt - 1) * 36524;
	year += (cnt - 1) * 100;

	if (cnt == 4) {
		cnt = (r - 1) / 1461 + 1;
		if (r == 36525) cnt = 25;
		r -= (cnt - 1) * 1461;
		year += (cnt - 1) * 4;
	} else {
		cnt = (r - 1) / 1461 + 1;
		r -= (cnt - 1) * 1461;
		year += (cnt - 1) * 4;
	}

	cnt = (r - 1) / 365 + 1;
	if (r == 1461) cnt = 4;
	r -= (cnt - 1) * 365;
	year += cnt - 1;

	pair<int, int> ans = turn(r, isrn(year));
	cout << ans.first << " " << ans.second << " " << year << endl;
}

void work() {
	scanf("%lld", &r);
	r ++;

	if (r <= onelimit)
		work1();
	else if (r <= twolimit)
		work2();
	else
		work3();
}

int main() {
	scanf("%d", &Q);

	while (Q --)    work();

	return 0;
}

  • 但是这个做法比较 naive，有没有更给力点的？有没有更加短小精悍的？

  • 那当然还是有的：

    1. 对于 (4713.1.1 ext{BC} o 1600.12.31) 的每一个日期，可以通过 " day by day " 的方式将答案先预处理出来。
    2. 对于 (1601.1.1) 及以后的每一个日期，可以通过 " 日期变化的周期性 " 来计算答案。

  • 这样子做会少讨论许多的情况，比较好写。

T2. 动物园

题目链接：Link。

  • 注意到对于所有的约束关系 ((p_i, q_i))，所对应的 (q_i) 是互不相同的。
  • 那么，也就是说，如果我这里有一个动物编号，其中的第 (i) 位存在约束关系，那我的第 (i) 位就会固定的影响到清单中的若干位。
  • 约定变量：
    • ( ext{match}_j)：表示第 (j) 位是否存在约束关系。
    • ( ext{exist}_j)：表示是否存在一个 (a_i)，满足 (a_i) 的第 (j) 位为 (1)。
  • 那么当我们新加进去一个动物时，考虑每一位的取值。
    显然第 (j) 位填 (0) 是可以的，因为这样不可能会影响到清单。
    如果第 (j) 位填 (1)，当且仅当满足以下 (2) 个条件之一：
    1. ( ext{match}_j = 0)。
    2. ( ext{match}_j = 1 land ext{exist}_j = 1)。
  • 第一条显然。
    第二条指的是：虽然第 (j) 位存在约束关系，但是已经存在一个动物编号影响到了清单，那么我第 (j) 位填 (1) 也不会再次影响到清单了。
  • 记 " 有多少位可以填 (1) " 的数量为 ( ext{fre})，根据乘法原理，一共可以养 (2^ ext{fre}) 个动物。
  • 但是题目问的是 " 还可以养多少个 "，可以证明，养过的 (n) 个动物一定被包含在这 (2^ ext{fre}) 之内。
  • 故答案即为 (2^ ext{fre} - n)。
  • 这题数据范围比较刁钻，有几个 X 点：
    1. k == 64 && n == 0 && m == 0 ：会爆 unsigned long long，需要特判，直接输出 (2^{64}) 即可。
    2. fre == 64：使用 1ull << 64 时会爆炸，可以输出 (1ull << 63) - n + (1ull << 63)。
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 1001000;

int n, m, c, k;

unsigned long long a[N];

bool match[65];
bool exist[65];

int main() {
	scanf("%d%d%d%d", &n, &m, &c, &k);

	if (k == 64 && n == 0 && m == 0) {
		puts("18446744073709551616");
		return 0;
	}

	for (int i = 1; i <= n; i ++)
		scanf("%llu", &a[i]);

	for (int i = 1, p, q; i <= m; i ++) {
		scanf("%d%d", &p, &q);
		match[p] = 1;
	}

	for (int i = 1; i <= n; i ++)
		for (int j = 0; j < k; j ++)
			if (a[i] >> j & 1) exist[j] = 1;

	int fre = 0;
	for (int j = 0; j < k; j ++)
		if (!(match[j] && !exist[j])) fre ++;

	if (fre == 64) {
		unsigned long long ans = 0;
		ans += (1ull << 63);
		ans -= n;
		ans += (1ull << 63);
		printf("%llu
", ans);
	} else {
		printf("%llu
", (1ull << fre) - n);
	}

	return 0;
}

T3. 函数调用

题目链接：Link。

  • 不难看出，如果我把每个函数看成一个点。
    那么对于每个 (T_j = 3) 的函数 (j)，我让 (j) 向 (g_1^{(j)}, g_2^{(j)}, ..., g_{C_j}^{(j)}) 连边的话，会得到一张 DAG。

  • 记 " 调用函数 (i) 会使全局乘多少倍 " 为 ( ext{mul}_i)，该数组可以在 DAG 上记忆化搜索求出。

  • 注意到影响到答案最后取值的操作只有 " 单点加 " 和 " 全局乘 " 两种操作。
    那么我可以尝试把最终序列上，第 (i) 个位置上的数表示为下列该式的形式：

[a_i imes b + k_i ]

  • 其中：

    • (a_i) 表示：初始序列中第 (i) 个位置上的值。
    • (b) 表示：所有操作结束后，" 全局乘 " 的倍数。
    • (k_i) 表示：所有 " 单点加 " 操作对第 (i) 个位置的贡献。

  • 那现在关键是在于如何求出每个 (k_i)。

  • 一个重要的思想是：如果我进行了一次 " 值为 (a) 的单点加 "，然后我进行了一次 " 值为 (b) 的全局乘 "，那么我可以看作是进行了 (b) 次 " 值为 (a) 的单点加 "。

  • 记 " 函数 (i) 进行了多少次 " 为 (f_i)，对于每次调用，先在节点上打上标记，最后再用拓扑排序向下传递贡献。

  • 具体地，倒序处理每一个调用（因为只有时间更靠后的 " 全局乘 " 才能影响到 " 单点加 "），假设说我这次要调用第 (i) 个函数，那么：

    • 令 (f_i gets f_i + b)。
    • 令 (b gets b imes ext{mul}_i)。

  • 然后考虑拓扑排序，假设说我这次要处理第 (i) 个函数，那么：

    • 若 (T_i = 1)，则令 (k_{P_i} gets k_{P_i} + V_i imes f_i)。
    • 若 (T_i = 2)，则无视该操作。
    • 若 (T_i = 3)，则倒序处理每一个调用，假设说我现在要将贡献传递给函数 (j)，那么：
      • 令 (f_j gets f_j + f_i)。
      • 令 (f_i gets f_i imes ext{mul}_j)。

  • 拓扑排序完直接输出 (a_i imes b + k_i) 即可。

  • 时间复杂度 (mathcal{O(n + m + Q)})。

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
#include <vector>

using namespace std;

inline int read() {
	int x = 0, f = 1; char s = getchar();
	while (s < '0' || s > '9') { if (s == '-') f = -f; s = getchar(); }
	while (s >= '0' && s <= '9') { x = x * 10 + s - '0'; s = getchar(); }
	return x * f;
}

const int N = 100100;
const int mod = 998244353;

int n;

int a[N];

int m;

struct operation {
	int opt;
	int pos, val;
	vector<int> g;
} T[N];

int mul[N];

void calc(int u) {
	if (mul[u] != -1) return;

	switch (T[u].opt) {
		case 1: {
			mul[u] = 1;

			break;
		}

		case 2: {
			mul[u] = T[u].val;

			break;
		}

		case 3: {
			mul[u] = 1;
			for (int i = 0; i < (int)T[u].g.size(); i ++) {
				int v = T[u].g[i];
				calc(v);
				mul[u] = 1ll * mul[u] * mul[v] % mod;
			}

			break;
		}
	}
}

int Q;
int idx[N];

int b;
int f[N];

int deg[N];

int k[N];

void topsort() {
	queue<int> q;

	for (int i = 1; i <= m; i ++)
		if (deg[i] == 0) q.push(i);

	while (q.size()) {
		int u = q.front(); q.pop();

		switch (T[u].opt) {
			case 1: {
				k[T[u].pos] = (k[T[u].pos] + 1ll * f[u] * T[u].val) % mod; 

				break;
			}

			case 2: {
				break;
			}

			case 3: {
				for (int j = T[u].g.size() - 1; j >= 0; j --) {
					int v = T[u].g[j];
					f[v] = (f[v] + f[u]) % mod;
					f[u] = 1ll * f[u] * mul[v] % mod;
					if (-- deg[v] == 0) q.push(v);
				}

				break;
			}
		}
	}
}

int main() {
	n = read();

	for (int i = 1; i <= n; i ++)
		a[i] = read();

	m = read();

	for (int i = 1; i <= m; i ++) {
		T[i].opt = read();

		switch (T[i].opt) {
			case 1: {
				T[i].pos = read(), T[i].val = read();

				break;
			}

			case 2: {
				T[i].val = read();

				break;
			}

			case 3: {
				int C = read();
				for (int j = 1; j <= C; j ++) {
					int x = read();
					T[i].g.push_back(x);
				}

				break;
			}
		} 
	}

	memset(mul, -1, sizeof(mul));
	for (int i = 1; i <= m; i ++)
		if (mul[i] == -1) calc(i); 

	Q = read();

	for (int i = 1; i <= Q; i ++)
		idx[i] = read();

	b = 1;
	for (int i = Q; i >= 1; i --) {
		switch (T[idx[i]].opt) {
			case 1: {
				f[idx[i]] = (f[idx[i]] + b) % mod;

				break;
			}

			case 2: {
				b = 1ll * b * T[idx[i]].val % mod;

				break;
			}

			case 3: {
				f[idx[i]] = (f[idx[i]] + b) % mod;
				b = 1ll * b * mul[idx[i]] % mod;

				break;
			}
		}
	}

	for (int u = 1; u <= m; u ++) {
		if (T[u].opt != 3) continue;

		for (int j = 0; j < (int)T[u].g.size(); j ++) {
			int v = T[u].g[j];
			deg[v] ++;
		} 
	}

	topsort();

	for (int i = 1; i <= n; i ++)
		printf("%d ", (1ll * a[i] * b + k[i]) % mod);
	puts("");

	return 0;
}

T4. 贪吃蛇

题目链接：Link。

  • 题解在路上了。
【推广】 免费学中医，健康全家人
原文地址：https://www.cnblogs.com/cjtcalc/p/13976961.html