【LGR-067】洛谷 1 月月赛 II & CSGRound 3 Div.2 题解

【LGR-067】洛谷 1 月月赛 II & CSGRound 3 Div.2

压岁钱

模拟。

封印的钱拿个数组记录就行了。

const int N = 1e6 + 7;
int n, o, x, y, ans;
ll c[N], now;

int main() {
	rd(n);
	for (int i = 1; i <= n; i++) {
		now += c[i], rd(o), rd(x);
		switch (o) {
			case 1 : now += x; break;
			case 2 :
				if (now < x) ++ans;
				else now -= x;
				break;
			case 3 :
				now -= x, rd(y), c[y] += x;
		}
	}
	print(ans);
	return 0;
}

斗牛

选 $n-2$ 张牌相当于选两张牌，同时如果有解，答案一定是 $((\Sigma - 1) \bmod 10) + 1$。

开个大小为 $10$ 的桶即可。

const int N = 1e6 + 7;
int n, a[N], s, c[10];

int main() {
	rd(n);
	for (int i = 1; i <= n; i++) rd(a[i]), a[i] %= 10, s += a[i];
	for (int i = 1; i <= n; i++) {
		int x = (s % 10 - a[i] + 10) % 10;
		if (c[x]) return print((s - 1) % 10 + 1), 0;
		c[a[i]%10] = 1;
	}
	print(0);
	return 0;
}

游戏

枚举先手取牌的张数，贪心出此时合法的 $X$ 的范围，差分即可。

贪心时二分可以做到 $\mathcal O(n \log n)$，双指针可以做到 $\mathcal O(n)$。

const int N = 1e6 + 7;
int n, k, c[N];
ll a[N];

int main() {
	rd(n);
	for (int i = 1; i <= n; i++) rd(a[i]), a[i] += a[i-1];
	a[++n] = 1e18, rd(k);
	for (int i = 1, p = 2; i < n; i++) {
		while (a[p] < 2 * a[i]) ++p;
		if (a[i] <= k) ++c[a[i]];
		if (a[p] - a[i] <= k) --c[a[p]-a[i]];
	}
	vi ans;
	for (int i = 1; i <= k; i++)
		if ((c[i] += c[i-1])) ans.pb(i);
	print(ans.size());
	for (auto x : ans) print(x, ' ');
	return 0;
}

出游

套路题。

给定一张 $n$ 个点的有向图，一开始选择一些点，这些点每次走一步，问 $T$ 步后这些点可能在哪些位置。

类似这样的问题都可以用 bitset 优化矩阵乘法做到 $\mathcal O(\frac{n^3\log T}w)$，比如 CF576D Flights for Regular Customers。

我这题代码就是从那题的代码改的。

最终你会得到一个矩阵 $a$，$a_{i,j}$ 表示一开始如果 $i$ 被选择了，那么最终 $j$ 会被选。

那么 $j$ 最后不参加的概率就是所有 $a_{i,j} = 1$ 的 $i$ 一开始不参加的概率。

人数的期望就是所有人参加的概率之和。

const int N = 500;
int n, m;
modint p[N], ans;
#define bt bitset<N>
struct mt {
	bt a[N];
	inline friend mt operator * (mt x, mt y) {
		mt z;
		for (int i = 0; i < n; i++)
			for (int j = 0; j < n; j++)
				if (x.a[i][j]) z.a[i] |= y.a[j];
		return z;
	}
} a, b;

inline void ksm(mt x, int y, mt &z) {
	while (y) {
		if (y & 1) z = z * x;
		x = x * x, y >>= 1;
	}
}

int main() {
	rd(n), rd(m);
	for (int i = 0, k; i < n; i++) {
		rd(p[i]), rd(k);
		for (int j = 0, x; j < k; j++)
			rd(x), a.a[--x][i] = 1;
		b.a[i][i] = 1;
	}
	ksm(a, m, b);
	for (int i = 0; i < n; i++) {
		modint o = 1;
		for (int j = 0; j < n; j++)
			if (b.a[j][i]) o *= 1 - p[j];
		ans += 1 - o;
	}
	print(ans);
	return 0;
}