acm.sgu.ru-[140, 180)

Part 2: $[140, 180)$
acm.sgu.ru@CodeForces

140. Integer Sequences

给定一个行向量 $A,$ 构造列向量 $X$ 使得 $A \times X \equiv B \mod P$。
$P \leq 10000, A_i \leq 10 ^ 9$。

Sol

$\gcd$ 变化时暴力更新,复杂度是 $O(nd(n)) < O(n \log n)$ 的。 注意 $A_i > P$ 的情况。

#include < bits/stdc++.h >
using namespace std;

#define N 105
int n, P, B;
int a[N], X[N], q[10101], fr[10101];

void update(int v, int id) {
	int h = 0, t = 0;
	for (int i = 0; i < P; i++) {
		if (fr[i] != -1) {
			q[t++] = i;
		}
	}
	while (h < t) {
		int x = q[h++];
		int y = (x + v) % P;
		if (fr[y] == -1) {
			fr[y] = id;
			q[t++] = y;
		}
	}
}
int main() {
	scanf("%d%d%d", &n, &P, &B);
	for (int i = 1; i <= n; i++) scanf("%d", a + i), a[i] %= P;
	memset(fr, -1, sizeof fr);
	fr[0] = 0;
	int g = P;
	for (int i = 1; i <= n && fr[B] == -1; i++) {
		int ng = __gcd(g, a[i]);
		if (ng != g) {
			g = ng;
			update(a[i], i);	
		}
	}
	if (fr[B] == -1) return puts("NO") * 0;
	puts("YES");
	int x = B;
	while (x) {
		X[fr[x]] ++;
		x = (x + P - a[fr[x]]) % P;
	}
	for (int i = 1; i <= n; i++) {
		printf("%d%c", X[i], i == n ? '\n' : ' ');
	}
}

141. Jumping Joe

$$
P_1x_1 - N_1x_1 + P_2x_2 - N_2x_2 = P
P_1 + N_1 + P_2 + N_2 = K
$$ 给定 $x_1, x_2, P, K$,解方程。

Sol

exgcd,然后找找最小的解就好了。

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;

LL exgcd(LL a, LL b, LL &x, LL &y) {
	if (!b) return x = 1, y = 0, a;
	LL t = exgcd(b, a % b, y, x);
	y -= a / b * x;
	return t;
}

LL a, b, P, K;

void chk(LL x, LL y) {
	LL d = abs(x) + abs(y);
	if (d <= K && d % 2 == K % 2) {
		LL c = (K - d) / 2;
		printf("YES\n%lld %lld %lld %lld\n", c + (x > 0 ? x : 0), c + (x < 0 ? -x : 0), y > 0 ? y : 0, y < 0 ? -y : 0);
		exit(0);
	}
}

int main() {
	cin >> a >> b >> P >> K;
	LL x, y, g = exgcd(a, b, x, y);
	if (P % g) return puts("NO") * 0;
	x *= P / g, y *= P / g;
	LL u = b / g, v = a / g;
	chk(x, y);
	for (LL i = -3, base = x / u; i <= 3; i++) {
		chk(x - (base + i) * u, y + (base + i) * v);
	}
	for (LL i = -3, base = y / v; i <= 3; i++) chk(x + (base + i) * u, y - (base + i) * v);
	puts("NO");
}

142. Keyword

询问最短的没有出现过的子串。

Sol
#include <bits/stdc++.h>
using namespace std;

#define N 500111

unordered_set <int> s;
int n;
char t[N];
bool check(int mid) {
	s.clear();
	for (int i = mid; i <= n; i++) {
		int cur = 0;
		for (int j = 0; j < mid; j++) {
			cur = cur * 2 + (t[i - j] == 'b');
		}
		s.insert(cur);
	}
	return s.size() < (1 << mid);
}

void output(int mid) {
	printf("%d\n", mid);
	for (int i = 0; ; i++) if (!s.count(i)) {
		for (int j = 0; j < mid; j++) {
			putchar('a' + i % 2);
			i /= 2;
		}
		putchar('\n');
		return;
	}
}

int main() {
	scanf("%d%s", &n, t + 1);
	int l = 1, r = min(20, n);
	while (l < r) {
		int mid = (l + r) >> 1;
		if (check(mid)) r = mid;
		else l = mid + 1;
	}
	check(l);
	output(l);
}

143. Long Live the Queen

询问树上最大权连通块。

Sol
#include <bits/stdc++.h>
using namespace std;

#define N 16111

int n, a[N], c[N];
vector <int> E[N];

void dfs(int x, int y) {
	c[x] = a[x];
	for (auto v : E[x]) if (v != y) {
		dfs(v, x);
		c[x] += max(0, c[v]);
	}
}
int main() {
	scanf("%d", &n);
	for (int i = 1; i <= n; i++) scanf("%d", a + i);
	for (int i = 1; i < n; i++) {
		int u, v;
		scanf("%d%d", &u, &v);
		E[u].push_back(v);
		E[v].push_back(u);
	}
	dfs(1, - 1);
	int ans = -1e9;
	for (int i = 1; i <= n; i++) ans = max(ans, c[i]);
	printf("%d\n", ans);
}

144. Meeting

Sol
#include <bits/stdc++.h>
using namespace std;
double X, Y, Z;
int main() {
	scanf("%lf%lf%lf", &X, &Y, &Z);
	double a = (Y - X) * 60;
	printf("%.7lf\n", ((a - Z) / a * 2 + Z / a) * Z / a);
}

145. Strange People

求 $k$ 短简单路,输出方案。

Sol

二分或者 A\* 搞搞就好了。然而这题 SPJ 挂了。
#### 146. The Runner

Sol
原来刻意卡精度自古有之。

#include <bits/stdc++.h>
using namespace std;

double L;
long long s, ll;
int n;
int main() {
	scanf("%lf%d", &L, &n);
	ll = L * 10000 + 0.5;
	while (n--) {
		long long x, y;
		scanf("%lld%lld", &x, &y);
		s += x * y * 10000;
		s %= ll;
	}
	printf("%.4lf\n", min(s, ll - s) / 10000.);
}

147. Black-white king

棋盘上有两个王要约会,有另一个王要阻止他们。然而那个坏人很憨,要求任意时刻他都在他的起点到当前点的最短路上,路径长度定义为步数。另外两个王会沿着某条最短路见面,见面定义为走到相邻的格子里。三个人依次行动,问坏人是否有可能抓到两个人中的一个,能的话输出最快的有可能的步数;否则输出两个王之间的距离。

Sol

感觉题意没啥营养,就不写题解了。

#include <bits/stdc++.h>
using namespace std;

int n;
int p[3], q[3];

bool inter(int x, int yl, int yr, int i) {
	x -= p[2];
	yl -= q[2], yr -= q[2];
	if (abs(x) == i && (yl <= i && yr >= -i)) return true;
	if (abs(x) <= i && ((yl <= -i && yr >= -i) || (yl <= i && yr >= i))) return true;
	return false;
}
int dis;
bool ok(int x, int y) {
	return x >= 1 && x <= n && y >= 1 && y <= n && max(abs(x - p[0]), abs(y - q[0])) + max(abs(x - p[1]), abs(y - q[1])) == dis;
}

int check() {
	dis = abs(p[0] - p[1]);
	int dir = p[0] > p[1] ? -1 : 1;
	int l0, r0, l1, r1;
	l0 = r0 = q[0], l1 = r1 = q[1];
	for (int i = 1; i <= dis / 2 - 1; i++) {
		int p0 = p[0] + dir * i, p1 = p[1] - dir * i;
		if (ok(p0, l0 - 1)) l0--;
		if (ok(p0, r0 + 1)) r0++;
		while (!ok(p0, l0)) l0++;
		while (!ok(p0, r0)) r0--;
		if (inter(p0, l0, r0, i)) return i;
		if (ok(p1, l1 - 1)) l1--;
		if (ok(p1, r1 + 1)) r1++;
		while (!ok(p1, l1)) l1++;
		while (!ok(p1, r1)) r1--;
		if (inter(p1, l1, r1, i)) return i;
	}
	return -1;
}

int main() {
	scanf("%d", &n);
	for (int i = 0; i < 3; i++) scanf("%d%d", p + i, q + i);
	if ((p[0] == p[2] && q[0] == q[2]) || (p[1] == p[2] && q[1] == q[2])) return puts("YES\n0"), 0;
	if (abs(p[0] - p[1]) < abs(q[0] - q[1])) {
		for (int i = 0; i < 3; i++) swap(p[i], q[i]);
	}
	int ret = check();
	if (ret == -1) printf("NO\n%d\n", abs(p[0] - p[1]) - 1);
	else printf("YES\n%d\n", ret);
}

148. B-Station

每层车站现在有一些水,每层有一个容量上限。如果某层的水超过容量上限则这一层会被破坏掉,水会落入下一层;你也可以选择花费相应的代价炸掉一些层。询问破坏最后一层的最优解。

Sol

开始想了很久,还是被 sez 点了一下我才想通的,我好菜。
首先,我们一定会破坏一个后缀;那么破坏一层有两种方法,第一种是炸掉,第二种是淹没掉。显然,不同的后缀起点会导致每一层是炸还是淹没;而从每一层来观察,只要起点到他的水够了就会淹没,二分一下前缀和一下就没了。

#include <bits/stdc++.h>
using namespace std;
#define N 15111
int n;
int w[N], l[N], p[N], sum[N];
bool vis[N];
vector <int> c[N];
int main() {
	scanf("%d", &n);
	for (int i = 1; i <= n; i++) scanf("%d%d%d", w + i, l + i, p + i);
	for (int i = 1; i <= n; i++) sum[i] = sum[i - 1] + w[i];
	for (int i = n; i; i--) {
		int L = 1, R = i;
		while (L < R) {
			int mid = (L + R) / 2;
			if (sum[i] - sum[mid - 1] <= l[i]) R = mid;
			else L = mid + 1;
		}
		c[L].push_back(i);
	}
	int su = 0, ans = 0x3f3f3f3f, id = 0;
	for (int i = 1; i <= n; i++) {
		for (auto v : c[i]) su += p[v];
		if (su < ans) ans = su, id = i;
		su -= p[i];
	}
	for (int i = 1; i <= id; i++) {
		for (auto v : c[i]) vis[v] = 1;
		if (i < id) vis[i] = 0;
	}
	for (int i = 1; i <= n; i++) if (vis[i]) printf("%d\n", i);
}

149. Computer Network

求树上每个点最远点距离。

Sol

传 统 艺 能

#include <bits/stdc++.h>
using namespace std;
#define N 10111
int n, a[N], c[N];
struct edge {
	int v, w;
};
vector  E[N];
void dfs(int x) {
	for (auto v : E[x]) {
		dfs(v.v);
		c[x] = max(c[x], c[v.v] + v.w);
	}
}
void f(int x, int z) {
	a[x] = max(c[x], z);
	int ma = z, sma = -1e9;
	for (auto v : E[x]) { 
		int val = c[v.v] + v.w;
		if (val > ma) sma = ma, ma = val;
		else if (val > sma) sma = val;
	}
	for (auto v : E[x]) {
		int val = c[v.v] + v.w;
		f(v.v, v.w + (val == ma ? sma : ma));
	}
}
int main() {
	scanf("%d", &n);
	for (int i = 2; i <= n; i++) {
		int u, v;
		scanf("%d%d", &u, &v);
		E[u].push_back({i, v});
	}
	dfs(1);
	f(1, 0);
	for (int i = 1; i <= n; i++) printf("%d\n", a[i]);
}

150. Mr. Beetle II

从 $(x_1, y_1)$ 向 $(x_2, y_2)$ 画一条线,问线经过的第 $n$ 个格子是什么,无解输出无解。

Sol

暴力可过,但是我不想写暴力。
考虑在较长边(设为 $x$)上二分,这样每个 $x$ 的边对应至多两个 $y$,并且 $mid$ 个 $x$ 有 $$mid + \lfloor \frac {mid \Delta y } {\Delta x} \rfloor – \frac {mid} {\Delta x / \gcd (\Delta x, \Delta y)}$$ 个,枚举一下边界就做完了。我交换和调整了符号来减少代码量。

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
int main() {
	int x1, y1, x2, y2, n;
	cin >> x1 >> y1 >> x2 >> y2 >> n;
	if (x1 == x2 || y1 == y2) return puts("no solution") * 0; 
	int dx = x2 - x1, dy = y2 - y1;
	bool negx = 0, negy = 0, sw = 0;
	if (dx < 0) negx = 1, dx = -dx;
	if (dy < 0) negy = 1, dy = -dy; 
	if (dx < dy) sw = 1, swap(dx, dy);
	int g = __gcd(dx, dy);
	int totcell = dx + dy - g;
	if (totcell < n) return puts("no solution") * 0;
	int l = 0, r = dx;
	int xg = dx / g;
	while (l < r) {
		int mid = (l + r + 1) >> 1;
		int c = int(mid + (LL)dy * mid / dx - mid / xg);
		if (c < n) l = mid;
		else r = mid - 1;
	}
	int c = int(l + (LL)dy * l / dx - l / xg);
	int yy = int((LL)dy * l / dx);
	vector < pair > ans;
	ans.push_back({l, yy});
	if (int((LL)dy * (l + 1) / dx) > yy && ((LL)dy * (l + 1) % dx)) {
		ans.push_back({l, yy + 1});
	}
	int ansx = ans[n - c - 1].first, ansy = ans[n - c - 1].second;
	if (sw) swap(ansx, ansy);
	if (negx) {
		ansx = -ansx - 1;
	}
	if (negy) {
		ansy = -ansy - 1;
	}
	ansx += x1; ansy += y1;
	printf("%d %d\n", ansx, ansy);
}

151. Construct a triangle

构造一个满足从一个顶点 $A$ 出发的两条边 $b, c$ 和中线 $m$ 为给定值的三角形。

Sol

取短边所在的非 $A$ 角,可以发现中线长度关于这个角度是凸的。算角度可能比较麻烦,枚举高的话需要考虑锐角和钝角两种情况。第一种取 $h = 0$ 和 $h = m$ 都太小了但是 $m < (b + c) / 2$ 的情况,可以尝试用第二种构造,否则不用。 **BETTER:** 把 $A, B$ 固定在 $(0, 0), (c, 0)$,然后就是一个二次方程。

#include <bits/stdc++.h>
using namespace std;

double c, b, m, lp, rp, mp;

double chk1(double h) {
	lp = -sqrt(c * c - h * h);
	rp = sqrt(b * b - h * h);
	mp = (lp + rp) / 2;
	double l = sqrt(mp * mp + h * h);
	return l - m;
}

double chk2(double h) {
	lp = sqrt(c * c - h * h);
	rp = sqrt(b * b - h * h);
	mp = (lp + rp) / 2;
	double l = sqrt(mp * mp + h * h);
	return l - m;
}

int main() {
	cin >> c >> b >> m;
	if (m > (b + c) / 2.) return puts("Mission impossible") , 0;
	double l = 0, r = min(m, min(b, c));
	auto chk = chk1;
	if (chk1(l) < 0 && chk1(r) < 0) chk = chk2;
	for (int t = 0; t < 100; t++) {
		double lmid = (l * 3 + r) / 4, rmid = (l + r * 3) / 4;
		if (chk(lmid) > chk(rmid)) l = lmid;
		else r = rmid;
	}
	if (chk(l) > 0) return puts("Mission impossible"), 0;
	if (chk(0) >= 0) l = 0, swap(l, r);
	else r = min(m, min(b, c));
	for (int t = 0; t < 100; t++) {
		double mid = (l + r) / 2;
		if (chk(mid) > 0) r = mid;
		else l = mid;
	}
	printf("%.5lf %.5lf\n", 0., l);
	printf("%.5lf %.5lf\n", lp, 0.);
	printf("%.5lf %.5lf\n", rp, 0.);
}

152. Making round

Sol
#include <bits/stdc++.h>
using namespace std;
#define N 10111
int n;
int a[N], b[N], c[N];
int main() {
	scanf("%d", &n);
	int sum = 0;
	for (int i = 1; i <= n; i++) scanf("%d", a + i), sum += a[i];
	int tot = 100;
	for (int i = 1; i <= n; i++) {
		b[i] = a[i] * 100 / sum;
		if (a[i] * 100 % sum) c[i] = 1;
		tot -= b[i];
	}
	for (int i = 1; i <= n; i++) if (c[i] && tot) b[i]++, tot--;
	for (int i = 1; i <= n; i++) printf("%d%c", b[i], i == n ? '\n' : ' ');
}

153. Playing with matches

给定 $n \leq 10 ^ 9$ 个石子,给定操作集合为一个 $[1, 9]$ 的子集,两人轮流取石子,取到最后一个的输掉,问必胜者。

Sol

一个直观的感受是,sg 函数存在循环节。我最初认为循环节是 $9!$ 的约数,但是是错的。循环节很小,最大的循环节由 4 7 8 取到 $25$, for 一下就行了。
注意网上很多题解假了,循环节可能存在一个第一段不一样的情况,需要特判。Hack:

2
1 2
6 9
6 2
6 9

应该输出

SECOND PLAYER MUST WIN
FIRST PLAYER MUST WIN
#include <bits/stdc++.h>
using namespace std;


const int N = 3000;

int K, n, m;

bool dp[N + 1];
vector <int> a;
int ma;
void work() {
	scanf("%d%d", &n, &m);
	a.clear();
	for (int i = 0; i < m; i++) {
		int x; scanf("%d", &x);
		a.push_back(x);
	}
	dp[1] = 0;
	for (int i = 2; i <= N; i++) {
		dp[i] = dp[i - 1] == 0;
		for (auto v : a) {
			if (i > v) dp[i] |= dp[i - v] == 0;
		}
	}
	for (int j = 1; ; j++) {
		bool flag = 1;
		for (int i = j + 1; i + j < N; i++){
			if (dp[i] != dp[i + j]) {
				flag = 0;
				break;
			}
		}
		if (flag) {
			puts(dp[n < N ? n : n % j + j] ? "FIRST PLAYER MUST WIN" : "SECOND PLAYER MUST WIN");
			return;
		}
	}
	assert(0);
}

int main() {
	scanf("%d", &K);
	while (K--) work();
}

154. Factorial

输出最小的 $n!$ 末尾 0 的数量为给定值的 $n$,或者 No solution

Sol
#include <bits/stdc++.h>
using namespace std;

int main() {
	int n;
	cin >> n;
	int l = 1, r = 5e8;
	while (l < r) {
		int x = (l + r) / 2;
		int ans = 0;
		for (int y = x / 5; y; y /= 5) {
			ans += y;
		}
		if (ans >= n) r = x;
		else l = x + 1;
	}
	int ans = 0;
	for (int y = l / 5; y; y /= 5) {
		ans += y;
	}
	if (ans != n) puts("No solution");	
	else printf("%d\n", l);
}

155. Cartesian Tree

给定 $(\text{key}, \text{val})$ 构造笛卡尔树。

Sol
#include <bits/stdc++.h>
using namespace std;

#define N 50555

struct Node {
	int key, val, fa, L, R;
	bool operator < (const Node &a) const {
		return key < a.key;
	}
} a[N];

int n;
int id[N];
bool cmp(int x, int y) {
	return a[x].key < a[y].key;
}

int main() {
	scanf("%d", &n);
	for (int i = 1; i <= n; i++) {
		int key, val;
		scanf("%d%d", &key, &val);
		a[i] = {key, val, 0, 0, 0};
		id[i] = i;
	}
	sort(id + 1, id + n + 1, cmp);
	int x = 0;
	for (int i = 1; i <= n; i++) {
		int y = id[i];
		while (x != 0) {
			int fa = a[x].fa;
			if (a[y].val < a[x].val) {
				a[x].R = a[y].L;
				a[a[y].L].fa = x;
				a[y].L = x;
				a[x].fa = y;
				x = fa;
			}
			else {
				break;
			}
		}
		a[y].fa = x;
		a[x].R = y;
		x = y;
	}
	puts("YES");
	for (int i = 1; i <= n; i++) {
		printf("%d %d %d\n", a[i].fa, a[i].L, a[i].R);
	}
}

156. Strange Graph

称满足下列性质的无向连通图是 'strange' 的:

  1. $\forall v \in V, \text{deg}_v \geq 2$.
  2. $\forall v \in V \text{ s.t. deg}_v > 2:$
    • 存在且仅存在一个 $u \in \text{adj}_v, \text{deg}_u = 2$.
    • $\text{adj}_v \backslash u$ 是一个团.

给定一个 strange graph,寻找一条哈密顿回路,或者输出不存在。
$N \leq 10 ^ 4, M \leq 10 ^ 5$

Sol

把高度数的点缩起来,就是求欧拉回路。
输出方案很恶心,我调了很久但是过于弱智,选择了不缩点写法。
读题很重要,这道题少读一个限制就要多写一堆特判。

#include <bits/stdc++.h>
using namespace std;
#define N 10111
int n, m;
int bel[N];
bool vis[N];
vector <int> ans;
list <int> E[N];

void dfs(int x, bool go = 0) {
	vis[x] = 1;
	while (E[x].size()) {
		auto it = E[x].begin();
		int v = *it;
		E[x].erase(it);
		if (!vis[v]) {
			if (bel[x] == bel[v] && !go) {
				dfs(v, 1);
				ans.push_back(v);
			}
			else if (bel[x] != bel[v]){
				dfs(v, 0);
				ans.push_back(v);
			}
		}
	}
}

int main() {
	scanf("%d%d", &n, &m);
	for (int i = 1; i <= m; i++) {
		int u, v;
		scanf("%d%d", &u, &v);
		E[u].push_back(v);
		E[v].push_back(u);
	}
	for (int i = 1; i <= n; i++) if (!bel[i] && E[i].size() > 2) {
		for (auto v : E[i]) if (E[v].size() > 2) bel[v] = i;
	}
	for (int i = 1; i <= n; i++) if (!bel[i]) {
		bel[i] = i;
		if (E[i].size() & 1) {
			puts("-1");
			return 0;
		}
	}
	dfs(bel[1]);
	ans.push_back(bel[1]);
	for (auto v : ans) printf("%d ", v);
}

157. Patience

$[1, n - 1]$ 放在一列 $n$ 长度的格子里,包括一个空格。每一步里,(空格左边的数 $+1$) 移动到这个空格来;如果是空格在最左则移动 $1$;空格左侧为 $n - 1$ 则输掉游戏。问能够还原为 ($1, 2, \cdots, n - 1, $ 空格) 的初始局面总数。

Sol

> 标题是说你读题和打表都需要耐心?

打表即可。虽然我不知道在那个年代是怎么打这个表的,我的程序用了超过 4G 内存,外加现代计算机的几分钟。可能我是在用现代“科技”做题?

附为打表程序。
**UPD:** 我傻了,因为操作唯一,所以不用判重。

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair pii;
#define read(a) scanf("%d", &a)
#define x first
#define y second

typedef vector <int> vi;
#define N 15
int n;
LL id(vi &a) {
	LL ret = 1;
	for (auto & i : a) ret = ret * (n + 1) + i;
	return ret;
}

unordered_set<LL> vis;

void solve(vi &a) {
	LL x = id(a);
	if (vis.count(x)) return;
	vis.insert(x);
	int z;
	for (int i = 0; i < n; i++) {
		if (a[i] == 0) {
			z = i;
			break;
		}
	}
	for (int i = 0; i < n; i++) if (i != z) {
		if (a[i] != 0 && ((i == 0 && a[i] == 1) || (i != 0 && a[i] == a[i - 1] + 1 && a[i - 1]))) {
			swap(a[i], a[z]);
			solve(a);
			swap(a[i], a[z]);
		}
	}
}


int main() {
	for (n = 1; n <= 13; n++) {
		vis.clear();
		vi a;
		for (int i = 1; i < n; i++) a.push_back(i);
		a.push_back(0);
		solve(a);
		cout << "if (n == " << n << ") puts(\"" << vis.size() << "\");\n";
	}
}

158. Commuter Train

你是黑心火车司机。火车有 $n$ 个门,你知道 $m$ 个乘客的位置。给定一个可停车的区间,最大化乘客到最近门的距离和。

Sol

函数有 $nm$ 个断点,因此不管怎么搞都不会比这个更好了(吧),尽管是某种形式的自同构。数据范围很小,我就写了个暴力。cout 这个题可能会输出科学计数法,记得 fixed。

#include <bits/stdc++.h>
using namespace std;

const int N = 305;
const int Len = 10005;
int L, m, n;
int p[N], d[N];
vector <int> Event[Len]; 
int main() {
	scanf("%d%d", &L, &m);
	L *= 2;
	for (int i = 1; i <= m; i++) scanf("%d", p + i), p[i] *= 2;
	scanf("%d", &n);
	for (int i = 2; i <= n; i++) scanf("%d", d + i), d[i] *= 2;
	int ans = 0, id = 0;
	for (int i = 0; i + d[n] <= L; i++) {
		int tot = 0;
		for (int j = 1; j <= m; j++) {
			int k = lower_bound(d + 1, d + n + 1, p[j] - i) - d;
			int w = 1 << 30;
			if (k <= n) w = min(w, d[k] + i - p[j]);
			if (k > 1) w = min(w, p[j] - (d[k - 1] + i));
			tot += w;
		}
		if (tot > ans) {
			ans = tot;
			id = i;
		}
	}
	if (id % 2) printf("%d.5 ", id / 2);
	else printf("%d ", id / 2);
	id = ans;
	if (id % 2) printf("%d.5\n", id / 2);
	else printf("%d\n", id / 2);
}

159. Self-Replicating Numbers

给定长度 $n$ 以及 base $b$,输出所有 $n$ 位 $b$ 进制数 $x$ 满足 $x ^ 2 \equiv x \pmod {b ^ n}$,也即平方后低 $n$ 位不变。

Sol

一个 $n + 1$ 的答案的后 $n$ 位必然是 $n$ 的答案,同时每位满足条件的数都很少:考虑 $x \times (x – 1) \bmod b ^ n = 0$,并且 $\gcd(x,x-1)=1$,同时 $|x| = n$,因此 $b$ 的质因子需要分一部分给左边和右边。实测可能答案通常 $O(1)$ 个,因此 dfs 就可以了。注意到进位不超过 $n b ^ 2 (1 + \frac 1 b + \frac 1 {b ^ 2} + \cdots)$,因此可以用 int 存。

#include <bits/stdc++.h>
using namespace std;

const int N = 305;
const int Len = 10005;
int L, m, n;
int p[N], d[N];
vector <int> Event[Len]; 
int main() {
	scanf("%d%d", &L, &m);
	L *= 2;
	for (int i = 1; i <= m; i++) scanf("%d", p + i), p[i] *= 2;
	scanf("%d", &n);
	for (int i = 2; i <= n; i++) scanf("%d", d + i), d[i] *= 2;
	int ans = 0, id = 0;
	for (int i = 0; i + d[n] <= L; i++) {
		int tot = 0;
		for (int j = 1; j <= m; j++) {
			int k = lower_bound(d + 1, d + n + 1, p[j] - i) - d;
			int w = 1 << 30;
			if (k <= n) w = min(w, d[k] + i - p[j]);
			if (k > 1) w = min(w, p[j] - (d[k - 1] + i));
			tot += w;
		}
		if (tot > ans) {
			ans = tot;
			id = i;
		}
	}
	if (id % 2) printf("%d.5 ", id / 2);
	else printf("%d ", id / 2);
	id = ans;
	if (id % 2) printf("%d.5\n", id / 2);
	else printf("%d\n", id / 2);
}

160. Magic Multiplying Machine

$ \maxs (\prod{i \in S} a_i) \bmod m $

$n \leq 10^4$, $m \leq 10^3 $

Sol

感觉没什么太好的做法,就乱搞吧

#include <bits/stdc++.h>
using namespace std;

const int N = 1e4 + 5;
int n, m;
int a[N], vis[2][N], fr[N];

int main() {
	scanf("%d%d", &n, &m);
	vis[0][1] = -1;
	for (int i = 1; i <= n; i++) scanf("%d", a + i);
	for (int i = 1; i <= n; i++) {
		int w = a[i];
		memcpy(vis[1], vis[0], sizeof vis[0]);
		for (int j = 1; j < m; j++) if (vis[1][j]) {
			int to = j * w % m;
			if (!vis[0][to]) {
				vis[0][to] = i;
				fr[to] = j;
			}
		}
	}
	vector  ans;
	for (int i = m - 1; ; i--) {
		if (vis[0][i]) {
			printf("%d\n", i);
			int x = i;
			while (x > 1) {
				ans.push_back(vis[0][x]);
				x = fr[x];
			}
			for (int i = ans.size() - 1; ~i; i--) {
				printf("%d%c", ans[i], i == 0 ? '\n' : ' ');
			}
			return 0;
		}
	}
}

161. Intuitionistic Logic

看不懂题,溜了

162. Pyramids

给定六边长,求四面体体积。

Sol

板子题,不过精度要求挺高。

#include <bits/stdc++.h>
using namespace std;


int main() {
	vector  a, A;
	for (int i = 0; i < 3; i++) {int x; cin >> x; a.push_back(x);}
	for (int i = 0; i < 3; i++) {int x; cin >> x; A.push_back(x);}
	swap(A[0], A[2]);
	long double up = 4. * a[0] * a[0] * a[1] * a[1] * a[2] * a[2], uppi = 1;
	for (int i = 0; i < 3; i++) {
		long double cur = 1. * a[i] * (a[(i + 1) % 3] * a[(i + 1) % 3] + a[(i + 2) % 3] * a[(i + 2) % 3] - A[i] * A[i]) ;
		cur = cur * cur;
		up -= cur;
		uppi *= a[(i + 1) % 3] * a[(i + 1) % 3] + a[(i + 2) % 3] * a[(i + 2) % 3] - A[i] * A[i];
	}
	up += uppi;
	printf("%.4lf\n", double(sqrt(up) / 12));
}

163. Wise King

Sol
n = int(input())
k = int(input())
a = []
for i in input().split():
    a.append(int(i))
ans = 0
for i in a:
    if i ** k >= 0:
        ans += i ** k
print(ans)

164. Airlines

$n$ 个点的无向完全图,每个边有 $[m]$ 中的标号。你需要选择至多 $\lceil \frac {m} {2} \rceil$ 个标号,使得这些标号的边集的图上,任意两个点的距离不超过 $3$。输出方案或者 $-1$。

Sol

Lemma: 完全图 $G = (V, E)$ 中,任何一个边集 $E’ \in E$ 满足:要么 $G_1 = (V, E’)$ 满足题目要求,要么 $G_2 = (V, E \backslash E’)$ 满足题目要求。

Proof. 留给读者

const int N = 205;
int n, m;
int a[N][N], g[N][N];

int inrange(int x, int l, int r) {
	return x == 0 ? 0 : (l <= x && x <= r ? 1 : 0x3f3f3f3f);
}

void check(int l, int r) {
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			g[i][j] = inrange(a[i][j], l, r);
		}
	}
	for (int k = 1; k <= n; k++) {
		for (int i = 1; i <= n; i++) {
			for (int j = 1; j <= n; j++) {
				g[i][j] = min(g[i][j], g[i][k] + g[k][j]);
			}
		}
	}
	for (int i = 1; i <= n; i++) {
		for (int j = 1;  j <= n; j++) {
			if (g[i][j] > 3) return;
		}
	}
	printf("%d\n", r - l + 1);
	for (int i = l; i <= r; i++) {
		printf("%d%c", i, i == r ? '\n' : ' ');
	}
	exit(0);
}

int main() {
	scanf("%d%d", &n, &m);
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			scanf("%d", a[i] + j);
		}
	}
	check(1, (m + 1) / 2);
	check((m + 1) / 2 + 1, m);
}

165. Basketball

给定 $n$ 个篮球运动员的身高,保证在 $[1.95, 2.05]$ 之间,构造一个身高的排列使得任意子串的和与 $2\times \text{Length}$ 的差不超过 $0.05$。

Sol
const int N = 6055;
int n;
pair <int, int> a[N];
int main() {
	scanf("%d", &n);
	for (int i = 1; i <= n; i++) {
		double x; scanf("%lf", &x);
		a[i].first = int(x * 1e6 + 0.5) - 2000000;
		a[i].second = i;
	}
	sort(a + 1, a + n + 1);
	puts("yes");
	int x = 0, i = 1, j = n;
	while (i <= j) {
		int ans;
		if (abs(x + a[i].first) <= 50000) ans = a[i].second, x += a[i++].first;
		else ans = a[j].second, x += a[j--].first;
		printf("%d%c", ans, i <= j ? ' ' : '\n');
	}
}

发表评论

邮箱地址不会被公开。 必填项已用*标注