http://codeforces.com/contest/1279

B. Verse For Santa

 

题意：规定从前往后处理n个物品，中间允许跳过1次，限制在s时间内，要处理最多的物品，问如果要跳过，跳过哪一个。

模拟题。

从前往后遍历，如果和大于s，则试着跳过，由于之前可能已经跳过一次了，所以要重新选最大的跳过，如果跳过后能小于等于s，则更新答案。

注意当和即使跳过也无法小于等于s时，不能直接break，类似s=100，a=[111，1]的答案就是如此。只有当以上情况且之前已经跳过了才可以break。当然也可以一直循环下去。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
#include<bits/stdc++.h>
using namespace std;
#define ll long long
typedef pair<int, int> pii;
const int INF = 0x3f3f3f3f;
const int maxn = 1e6 + 10;
int T;
int a[maxn];
int main() {
	scanf("%d", &T);
	while (T--) {
		int n, s;
		scanf("%d%d", &n, &s);
		ll sum = 0;
		int ans = 0, mx = 0;
		for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
		for (int i = 1; i <= n; i++) {
			sum += a[i];
			if (a[mx] < a[i])mx = i;
			if (sum > s) {
				if (sum - a[mx] <= s)	//还不能直接break
					ans = mx;
				else if (ans != 0)break;	//以前跳过一次
			}
		}
		printf("%d\n", ans);
	}
	return 0;
}

 

D. Santa’s Bot

 

题意：n个人中任选1个作x，再从他的列表中任选一个物品作y，再从所有n个人中任选一个作z，仅当y也在z的列表中时合法。求三元组 (x,y,z)(x,y,z) 合法的概率。

要注意以上所有选择都是等概率的。

所以起初我想的是合法的三元组情况除以总共的三元组情况。但样例一始终不对，我算的是5/6，答案是7/8. 这是因为我列出的总共的三元组为 (1,1,1),(1,1,2),(1,2,1),(1,2,2),(2,1,1),(2,1,2)(1,1,1),(1,1,2),(1,2,1),(1,2,2),(2,1,1),(2,1,2) ，但实际上这是不对的，这样得到的取第一个人和第二个人的概率不同。所以实际上 (2,1,1)(2,1,1) 和 (2,1,2)(2,1,2) 的占比要多一倍。

正确的做法应该是 ans=∑i=1n1n∑j∈vc[i]1k[i]⋅cnt[j]nans=\sum_{i=1}^{n}\frac{1}{n}\sum_{j\in vc[i]}\frac{1}{k[i]}\cdot \frac{cnt[j]}{n}

把该合并的合并之后得到 ans=1n2∑i=1n(1k[i]⋅∑j∈vc[i]cnt[j])ans=\frac{1}{n^2}\sum_{i=1}^{n}(\frac{1}{k[i]}\cdot \sum_{j\in vc[i]}cnt[j])

则可以 O(n)O(n) 解决了。还要注意求快速幂以及最后 ans⋅n2ans\cdot n^2 时 ansans 先mod一下。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
#include<bits/stdc++.h>
using namespace std;
#define ll long long
typedef pair<int, int> pii;
const int INF = 0x3f3f3f3f;
const int maxn = 1e6 + 10;
const ll mod = 998244353;
int n;
int k[maxn];
ll x;
ll y;
ll cnt[maxn];
vector<int>vc[maxn];
inline ll ksm(ll a, ll b)
{
	ll ret = 1;
	a %= mod; b %= mod;
	while (b)
	{
		if (b & 1)ret = (ret*a) % mod;
		a = (a*a) % mod;
		b >>= 1;
	}
	return ret;
}
ll gcd(ll a, ll b) {
	if (b == 0)return a;
	if (a < b)swap(a, b);
	return gcd(b, a%b);
}
int main() {
	scanf("%d", &n);
	for (int i = 1; i <= n; i++) {
		scanf("%d", &k[i]);
		y += 1ll * k[i] * n;
		for (int j = 1; j <= k[i]; j++) {
			int p;
			scanf("%d", &p);
			vc[i].push_back(p);
			cnt[p]++;
		}
	}
	ll ans = 0;
	for (int i = 1; i <= n; i++) {
		ll tmp = 0;
		for (int j : vc[i])tmp += cnt[j];
		ans += tmp * ksm(k[i], mod - 2) % mod;
	}
	ans %= mod;
	ans = ans * ksm(1ll*n*n, mod - 2) % mod;
	cout << ans << endl;
	return 0;
}