https://codeforces.com/gym/102500

按难度排序

I. Inverted Deck

 

题意：给定一个序列，问能否翻转一个区间后变为非递减。

找到一个尽量大的非递增的区间，把它翻过来。判断结果是否满足非递减。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int INF = 0x3f3f3f3f;
const ll inf = 0x3f3f3f3f3f3f3f3f;
const int N = 1e6 + 10;
int n;
int a[N];
int main() {
	scanf("%d", &n);
	for (int i = 1; i <= n; i++)scanf("%d", &a[i]);
	int L = INF, R = 0;
	for (int i = 2; i <= n; i++) {
		if (a[i] < a[i - 1])L = min(L, i - 1), R = max(R, i);
	}
	if (L == INF) { puts("1 1"); return 0; }
	for (; L > 1 && a[L] == a[L - 1]; L--);
	for (; R < n && a[R] == a[R + 1]; R++);
	reverse(a + L, a + R + 1);
	for (int i = 2; i <= n; i++)if (a[i] < a[i - 1]) { puts("impossible"); return 0; }
	printf("%d %d\n", L, R);
	return 0;
}

 

F. Firetrucks Are Red

 

题意：n个人，每个人都有几个数字，如果两个人有相同的数字，则他们联通，问能否使得所有人联通，联通有传递性。

显然是并查集，维护有那些人有数字x，把他们连在一起，遍历每个数字。最后判断联通。

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
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int INF = 0x3f3f3f3f;
const ll inf = 0x3f3f3f3f3f3f3f3f;
const int N = 2e5 + 10;
int n;
int par[N];
void ini(int n) { for (int i = 0; i <= n; i++)par[i] = i; }
int find(int x) { return par[x] == x ? x : par[x] = find(par[x]); }
void uni(int x, int y) { par[find(x)] = find(y); }
map<int, vector<int> >vc;
struct X
{
	int u, v, w;
};
vector<X>ans;
int main() {
	scanf("%d", &n);
	for (int i = 1; i <= n; i++) {
		int m, x;
		scanf("%d", &m);
		for (int j = 1; j <= m; j++) {
			scanf("%d", &x);
			vc[x].push_back(i);
		}
	}
	ini(n);
	for (auto p : vc) {
		if ((int)p.second.size() <= 1)continue;
		int u = p.second[0];
		for (int i = 1; i < (int)p.second.size(); i++) {
			if (find(u) != find(p.second[i])) {
				uni(u, p.second[i]);
				ans.push_back(X{ u,p.second[i],p.first });
			}
		}
	}
	for (int i = 2; i <= n; i++) {
		if (find(i) != find(1)) { puts("impossible"); return 0; }
	}
	for (X p : ans) {
		printf("%d %d %d\n", p.u, p.v, p.w);
	}
	return 0;
}

 

C. Canvas Line

 

题意：有n个区间，区间长度远大于夹子大小，每个区间要求恰放两个夹子，初始时已经有一些夹子，求最少夹子数。

贪心

尽量放区间相交处，所以就判断能不能放，不能放的话就随便找个其他地方。

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
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int INF = 0x3f3f3f3f;
const ll inf = 0x3f3f3f3f3f3f3f3f;
const int N = 2e5 + 10;
const double eps = 1e-6;
int n, m;
map<int, int>vis;
vector<int>vc, ans;
int l[N], r[N], cnt[N];
int main() {
	scanf("%d", &n);
	for (int i = 1; i <= n; i++) {
		scanf("%d%d", &l[i], &r[i]);
	}
	scanf("%d", &m);
	for (int i = 1; i <= m; i++) {
		int x;
		scanf("%d", &x);
		vc.push_back(x);
		vis[x] = 1;
	}
	for (int i = 1; i <= n; i++) {
		int L = lower_bound(vc.begin(), vc.end(), l[i]) - vc.begin();
		int R = upper_bound(vc.begin(), vc.end(), r[i]) - vc.begin();
		cnt[i] = R - L;
		if (cnt[i] >= 3) { puts("impossible"); return 0; }
	}
	for (int i = 1; i < n; i++) {
		if (cnt[i] == 2)continue;
		if (cnt[i + 1] >= 2 || vis[r[i]] || r[i] != l[i + 1]) {
			for (int j = l[i] + 1; j < r[i] && cnt[i] < 2; j++) {
				if (!vis[j]) { ans.push_back(j); cnt[i]++; }
			}
		}
		else {
			ans.push_back(r[i]);
			cnt[i]++; cnt[i + 1]++;
			for (int j = l[i] + 1; j < r[i] && cnt[i] < 2; j++) {
				if (!vis[j]) { ans.push_back(j); cnt[i]++; }
			}
		}
	}
	for (int i = l[n] + 1; i <= r[n] && cnt[n] < 2; i++) {
		if (!vis[i]) { ans.push_back(i); cnt[n]++; }
	}
	sort(ans.begin(), ans.end());
	printf("%d\n", (int)ans.size());
	for (int u : ans)printf("%d ", u);
	return 0;
}

 

E. Expeditious Cubing

 

题意：有五次成绩，去掉最高和最低，如果平均值小于等于给定值，则获胜。已知四次成绩，问最后一次最多为多少，能够获胜。

最后一次可能作为最大值被去掉，也可能作为最小值被去掉，这两种情况可以直接判断出impossible或infinite。

否则最后一次一定被记入答案，那么计入答案的三次成绩都已知了。

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
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int INF = 0x3f3f3f3f;
const ll inf = 0x3f3f3f3f3f3f3f3f;
const int N = 2e5 + 10;
const double eps = 1e-6;
double a[10], t;
int main() {
	for (int i = 0; i < 4; i++)scanf("%lf", &a[i]);
	sort(a, a + 4);
	scanf("%lf", &t);
	t *= 3.0;
	if (a[1] + a[2] + a[3] - t<= eps) { puts("infinite"); }
	else if (a[0] + a[1] + a[2] - t> eps)puts("impossible");
	else {
		double ans = a[3];
		for (; 1 ; ans -= 0.01) {
			if (ans + a[1] + a[2] - t<= eps) {
				printf("%.2lf\n", ans);
				break;
			}
		}
	}
	return 0;
}

 

G. Gnoll Hypothesis

 

题意：有n个数，随机选m个，没被选的数加到后面第一个被选的数上，问每个数的期望值。

对于每个数，枚举有多少数加到它上，这是个连续的区间，所以枚举区间长度即可。

区间内的数和区间旁边的数选和不选都已经确定。

期望就是

∑k=0n−m+1(Cn−2−km−2/Cnm⋅∑j=0kai−j)\sum_{k=0}^{n-m+1}(C_{n-2-k}^{m-2}/C_n^m\cdot \sum_{j=0}^ka_{i-j})

O(n3)O(n^3)，但是改成 O(n2)O(n^2)也是可以的，可以枚举其它数对它的贡献，其它的一个数被加到这个数上，说明它们中间的数都没有选，所以是

∑k=0n−mCn−1−km−1/Cnm⋅ai−k\sum_{k=0}^{n-m}C_{n-1-k}^{m-1}/C_n^m \cdot a_{i-k}

求组合数的话由于没有取模，所以直接求，但是要用long double 存下。

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
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int INF = 0x3f3f3f3f;
const ll inf = 0x3f3f3f3f3f3f3f3f;
const int N = 2e5 + 10;
long double C[1010][1010];
int n, m;
long double a[N];
int main() {
	scanf("%d%d", &n, &m);
	for (int i = 0; i <= n; i++)C[i][i] = C[i][0] = 1;
	for (int i = 2; i <= n; i++) {
		for (int j = 1; j < i; j++) {
			C[i][j] = C[i - 1][j - 1] + C[i - 1][j];
		}
	}
	for (int i = 0; i < n; i++)scanf("%Lf", &a[i]);
	if (m == 1) {
		long double ans = 0;
		for (int i = 0; i < n; i++) {
			ans += a[i];
		}
		for (int i = 0; i < n; i++)printf("%.12Lf\n", ans / n);
		return 0;
	}
	for (int i = 0; i < n; i++) {
		long double ans = 0;
		for (int k = 0; k <= n - m + 1; k++) {
			long double tmp = 0;
			for (int j = 0; j <= k; j++)tmp += a[(i - j + n) % n];
			ans += C[n - 2 - k][m - 2] * tmp / C[n][m];
		}
		printf("%.12Lf\n", ans);
	}
	return 0;
}

 

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
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int INF = 0x3f3f3f3f;
const ll inf = 0x3f3f3f3f3f3f3f3f;
const int N = 2e5 + 10;
long double C[1010][1010];
int n, m;
long double a[N];
int main() {
	scanf("%d%d", &n, &m);
	for (int i = 0; i <= n; i++)C[i][i] = C[i][0] = 1;
	for (int i = 2; i <= n; i++) {
		for (int j = 1; j < i; j++) {
			C[i][j] = C[i - 1][j - 1] + C[i - 1][j];
		}
	}
	for (int i = 0; i < n; i++)scanf("%Lf", &a[i]);
	for (int i = 0; i < n; i++) {
		long double ans = 0;
		for (int k = 0; k <= n - m; k++) {
			ans += C[n - 1 - k][m - 1] * a[(i - k + n) % n] / C[n][m];
		}
		printf("%.12Lf\n", ans);
	}
	return 0;
}

 

A. Average Rank

 

题意：有m天，n个人，每天有一些人得分，名次等于分数比它高的人数+1，每天结束都会结算当天的排名，问每个人m天的排名平均值。

考虑什么时候会有排名改变，一定是与他同分的人加分了，那么其它同分的人排名+1，加分的人排名减小。

但是直接维护人肯定不行，所以要维护分数的排名，考虑分数的排名什么时候会变，即拥有这个分数的人的排名什么时候会变。一定是这个分数里有人加分了。

一个人的分数在m天里一定是非递减的，且最终一定会不变。就像下面这样。

对于每个分数，维护它在全部m天里的排名之和。

如果一个人始终没有加分，即他的分数始终没变，那么他这m天的排名之和就是这个分数这m天的排名之和。

而如果这个人的分数有变化，那么由于之前分数比现在分数要低，所以之前的排名一定更大（数值大），所以他的排名之和应该是现在分数的全m天排名之和加上一个数，这个数就是加分前的分数的在加分这天之前排名和与加分后的分数在加分这天的排名和的差值。即补上这些值之后，他就可以和原来就在这个分数的人一起操作了，而之所以要加，就是因为分数越低，排名越大（数值大）。

仅当一个人被加分时，才会改变他的增加的值，其它人只要跟随他们的分数的排名之和即可。

所以维护每个分数的m天排名之和，以及每个人的额外增加值。

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
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int INF = 0x3f3f3f3f;
const ll inf = 0x3f3f3f3f3f3f3f3f;
const int N = 1e6 + 10;
const ll mod = 998244353;
ll n, m, k, c;
ll sum[N], rk[N], add[N], pts[N];//分数m天的排名和，分数当天的排名，人的额外增加值，人的分数
ll presum(ll x, ll d) {
	return sum[x] - rk[x] * (m - d + 1);
}
int main() {
	scanf("%lld%lld", &n, &m);
	rk[0] = 1; sum[0] = m;
	for (int i = 1; i <= m; i++) {
		scanf("%d", &k);
		for (ll j = 0; j < k; j++) {
			scanf("%d", &c);
			ll p = pts[c];
			ll s1 = presum(p, i);
			if (rk[p + 1] == 0) {
				rk[p + 1] = 1;
				sum[p + 1] = m;
			}
			ll s2 = presum(p + 1, i);
			add[c] += s1 - s2;
			rk[p]++; sum[p] += m - i + 1;
			pts[c]++;
		}
	}
	for (int i = 1; i <= n; i++) {
		printf("%.9lf\n", 1.0*(sum[pts[i]] + add[i]) / m);
	}
	return 0;
}