0821 复赛模拟

T1

洛谷 P7398

裸的模拟，对得丑陋

#include <bits/stdc++.h>

using namespace std;
const int N = 1e4 + 50;

int ans;
string s;

bool vis[N];

int main() {
	cin >> s;

	for (int i = 0; i < s.size(); i++) {
		if (s[i] >= 'a' && s[i] <= 'z') continue;
		else {
			int num;
			if (s[i + 1] >= 'a' && s[i + 1] <= 'z') {
				num = abs(s[i] - '0');
				i += 0;
				if (!vis[num]) ans++, vis[num] = true;
				else continue;
			} else {
				if (s[i + 2] >= 'a' && s[i + 2] <= 'z') {
					num = abs(s[i] - '0') * 10 + abs(s[i + 1] - '0');
					i += 1;
					if (!vis[num]) ans++, vis[num] = true;
					else continue;
				} else {
					num = abs(s[i] - '0') * 100 + abs(s[i + 1] - '0') * 10 + abs(s[i + 2] - '0');
					i += 2;
					if (!vis[num]) ans++, vis[num] = true;
					else continue;
				}
			}
		}
	}
	
	cout << ans << endl;
	return 0;
}

T2

洛谷 P8039

考试的时候看到 \(1e10\) 的数据范围其实已经是慌了，想到的也不是正解，想用分块+二分但是不会写，最后写了份带前缀和的暴力却因为用优先队列维护有序还写挂了

正解是用等差数列知识推式子，将求和的过程转变为求因数，已知要求

我们可以运用等差数列的求和公式：

转化一下式子，两边同时 \(\times 2\) 易得

那么通过求 \(2N\) 的因数来获取 \(l\) 和 \(r\) 的话，时间复杂度就会下降到 \(\sqrt{2N}\)

假设计算出来之后得出一对因数 \(x\) 和 \(y\) ， 且：

通过简单的加减消元不难得到：

最后是个坑点，需要注意判断奇偶性，我们最后得到的 \(x \times y\) 是个偶数（即 \(xy \mod{2} = 0\)） ，也就是说 \(r + l\) 和 \(r - l + 1\) 的奇偶性不相同，我们从加减消元的过程中可以得到， \(r\) 和 \(l\) 在相加相减后能被 \(2\) 整除，而满足这一性质的只可能两个数奇偶性相同，但是由于 \(r - l\) 之后还加上了 \(1\) 使得两者的奇偶性发生了改变，所以其实一开始 \(x\) 和 \(y\) 的奇偶性是相反的

那么我们打一下代码，

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

ll n;

int main() {
	scanf("%lld", &n);
	
	n *= 2;
	
	for (ll x = 1; x * x <= n; x++) {
		if (n % x == 0) {
			ll y = n / x;
			ll l = (y - x + 1) / 2;
			ll r = (x + y - 1) / 2;
			
			if ((l != r) && ((x % 2) != (y % 2)))
				printf("%lld %lld\n", l, r);
		}
	}
	
	return 0;
}

T3

洛谷 P8268

T3 暴露出自己很大的问题，就是码力严重不足，想出正解之后却没有能力实现，实现出来万紫千红

其实这题我没有想的什么二分和 DFS ，整道题制造金属无非只有 \(3\) 种情况：

1. 本身已经有这种类型的金属
2. 没有这种金属，且没有生产这种金属的配方
3. 没有这种金属，有这种生产金属的配方，那么就询问是否有足够的原料生产所需金属

显然可以以此写出代码，考场我自己用的是数组套结构体套数组实现的，本身实现难度比较大，自己的代码能力又菜，所以死透了（实际上输入还读错了），就对了一个点，寄

使用 vector 写出代码如下

#include <bits/stdc++.h>

using namespace std;
const int N = 1e3 + 50;

int n, k, l, m, ans;
int a[N];
vector<int> v[N];

bool check(int x) {
	if (a[x]) return a[x]--;	// 有 x 金属
	if (v[x].empty() && !a[x]) return false;	// 没有配方，没有材料
	for (int i = 0; i <= v[x].size() - 1; i++) 
		if (!check(v[x][i]))
			return false;
	return true;
}

int main() {
	scanf("%d", &n);
	for (int i = 1; i <= n; i++)
		scanf("%d", &a[i]);
	scanf("%d", &k);
	while (k--) {
		scanf("%d %d", &l, &m);
		for (int i = 1, in; i <= m; i++) {
			scanf("%d", &in);
			v[l].push_back(in);
		}
	}
	
	while (check(n))		// 能生产就生产 
		ans++;

	printf("%d\n", ans);
	return 0;
}

T4

P9014 [USACO23JAN] Following Directions S