Codeforces Round 921 Div 2

发表于 更新于 分类于

A - We Got Everything Covered!

很显然，最短的方案长度一定是\(n \times k\)，直接循环输出即可。

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
// Problem: A. We Got Everything Covered!
// Contest: Codeforces - Codeforces Round 921 (Div. 2)
// URL: https://codeforces.com/contest/1925/problem/A
// Memory Limit: 256 MB
// Time Limit: 1000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

//#pragma GCC optimize(2)
#include <bits/stdc++.h>
using namespace std;

const int N = 2e5 + 10;
const int inf = 1 << 30;
const long long llinf = 1ll << 60;
const double PI = acos(-1);

#define lowbit(x) (x&-x)
typedef long long ll;
typedef double db;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef pair<db, db> pdd;
typedef pair<ll, int> pli;

int n, m, k, q;

void work()
{
	cin >> n >> m;
	string s;
	for (int i = 1; i <= n; i++)
	{
		for (int j = 1; j <= m; j++)
		{
			s.push_back(j + 'a' - 1);
		}
	}
	cout << s << endl;
}
int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	int t;
	cin >> t;
	while (t --> 0)
	{
		work();
	}
}

B - A Balanced Problemset?

一个显而易见的结论是，如果答案是\(y\)，那么一定有\(x \mid y\)。那么直接枚举\(x\)的因子，判断\(\frac y x\)是否大于等于\(n\)即可。时间复杂度\(\Theta(T\sqrt 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
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
// Problem: B. A Balanced Problemset?
// Contest: Codeforces - Codeforces Round 921 (Div. 2)
// URL: https://codeforces.com/contest/1925/problem/B
// Memory Limit: 256 MB
// Time Limit: 1500 ms
// 
// Powered by CP Editor (https://cpeditor.org)

//#pragma GCC optimize(2)
#include <bits/stdc++.h>
using namespace std;

const int N = 2e5 + 10;
const int inf = 1 << 30;
const long long llinf = 1ll << 60;
const double PI = acos(-1);

#define lowbit(x) (x&-x)
typedef long long ll;
typedef double db;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef pair<db, db> pdd;
typedef pair<ll, int> pli;

int n, m, k, q;

vector<int> primes;
bool isprime[N];
void preProcess()
{
	fill(isprime + 2, isprime + N, true);
	for (int x = 2; x < N; x++)
	{
		if (isprime[x])
			primes.push_back(x);
		for (int y : primes)
		{
			if (x * y >= N)
				break;
			isprime[x * y] = 0;
			if (x % y == 0)
				break;
		}
	}
}
void work()
{
	cin >> n >> m;
	int ans = 1;
	for (int i = 1; i * i <= n; i++)
	{
		if (n % i == 0)
		{
			if (n / i >= m)
				ans = max(ans, i);
			if (i >= m)
				ans = max(ans, n / i);
		}
	}
	cout << ans << endl;
}
int main()
{
	preProcess();
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	int t;
	cin >> t;
	while (t --> 0)
	{
		work();
	}
}

C - Did We Get Everything Covered?

一开始想了个最短路做法（写一半发现太麻烦了）。

可以用一个桶记录字母的出现情况，每次桶里前k个字符都不为空了，就清空桶，总轮数加一，记录下出现次数最少的那个字母（也就是最后一个字母）。最后再检查总轮数是否大于等于n。如果不满足，就在记录下的字母后面添任意字母，直到长度为n，输出即可。

下面是包含写fake了的最短路的代码（

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
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
// Problem: C. Did We Get Everything Covered?
// Contest: Codeforces - Codeforces Round 921 (Div. 2)
// URL: https://codeforces.com/contest/1925/problem/C
// Memory Limit: 256 MB
// Time Limit: 2000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

//#pragma GCC optimize(2)
#include <bits/stdc++.h>
using namespace std;

const int N = 4000;
const int inf = 1 << 30;
const long long llinf = 1ll << 60;
const double PI = acos(-1);

#define lowbit(x) (x&-x)
typedef long long ll;
typedef double db;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef pair<db, db> pdd;
typedef pair<ll, int> pli;

int n, m, k, q;
int cnt[N], from[N];
int nxt[N][26];
namespace Graph
{
	vector<pli> to[N];
	
	void add(int x, int y, ll val)
	{
		to[x].push_back({val, y});
	}
	bool vis[N];
	ll   dis[N];
	int  from[N];
	void shortest_path(int fr)
	{
		// using Dijkstra
		priority_queue<pli, vector<pli>, greater<pli> > q;
		q.push(make_pair(0, fr));
		memset(dis, 0x3f, sizeof dis);
		memset(vis, 0, sizeof vis);
		memset(from, 0, sizeof from);
		dis[fr] = 0;
		while (!q.empty())
		{
			auto [nowval, x] = q.top();
			q.pop();
			if (vis[x])
				continue;
			vis[x] = 1;
			for (auto [val, y] : to[x])
				if (dis[y] > dis[x] + val)
				{
					dis[y] = dis[x] + val;
					from[y] = x;
					q.push(make_pair(dis[y], y));
				}
		}
	}
}
/*
void work()
{
	cin >> n >> k >> m;
	string s;
	cin >> s;
	s = ' ' + s;
	for (int i = 0; i <= m; i++)
		Graph::to[i].clear();
	for (int i = 0; i <= m + 1; i++)
		for (int j = 0; j < k; j++)
			nxt[i][j] = m + 1;
	for (int i = m; i >= 0; i--)
	{
		for (int j = 0; j < k; j++)
			nxt[i][j] = nxt[i + 1][j];
		if (i > 0)
			nxt[i][s[i] - 'a'] = i;
		for (int j = 0; j < k; j++)
		{
			if (nxt[i][j] == m + 1)
				Graph::add(i, nxt[i + 1][j], 0);
			else
				Graph::add(i, nxt[i + 1][j], 1);
			//cout << i << ' ' << nxt[i + 1][j] << endl;
		}
	}
	Graph::shortest_path(0);
	if (Graph::dis[m + 1] < n)
	{
		cout << "NO\n";
		string st;
		int now = m + 1;
		while (now != 0)
		{
			if (now != m + 1)
				st.push_back(s[now]);
			now = Graph::from[now];
		}
		reverse(st.begin(), st.end());
		int p = Graph::from[m + 1];
		for (int j = 0; j < k; j++)
			if (nxt[p][j] == m + 1)
			{
				st.push_back(j + 'a');
				break;
			}
		while (st.size() < n)
			st.push_back('a');
		cout << st << endl;
	}
	else
	{
		cout << "YES\n";
	}
	
}
*/
void work()
{
	cin >> n >> k >> m;
	int round = 0;
	vector<int> but(26);
	string s;
	cin >> s;
	string ans;
	for (int i = 0; i < m; i++)
	{
		if (!but[s[i] - 'a'])	
			but[s[i] - 'a'] = i + 1;
		bool flag = 1;
		for (int j = 0; j < k; j++)
			if (but[j] == 0)
			{
				flag = 0;
				break;
			}
		if (flag)
		{
			round++;
			int id = 0;
			for (int j = 1; j < k; j++)
				if (but[id] < but[j])
					id = j;
			ans.push_back(id + 'a');
			for (int j = 0; j < k; j++)
				but[j] = 0;
		}
	}
	if (round >= n)
	{
		cout << "YES\n";
	}
	else
	{
		cout << "NO\n";
		for (int j = 0; j < k; j++)
			if (but[j] == 0)
			{
				while (ans.size() < n)
					ans.push_back(j + 'a');
				break;
			}
		cout << ans << endl;
	}
}
int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	int t;
	cin >> t;
	while (t --> 0)
	{
		work();
	}
}

D - Good Trip

题目作者的表述感觉emmm，最大的障碍是读懂题意？

令每轮老师选人前，所有可能被选中的两人队的友谊值期望为\(E_i\)，题目其实就是让我们求 \[ \sum_{i=1}^{n}E_i \] 每次可能有\(\frac{n(n+1)}2\)个不同的队被选中，令有友谊值的朋友的友谊值和为\(sum_i\)，总共\(k\)对朋友，那么很显然有： \[ E_i=\frac{sum_i}{\frac{n(n+1)}2} \] 然后\(sum_i\)的推导也很简单： \[ sum_i=sum_{i-1} + \frac{k}{\frac{n(n+1)}2} \] 直接简单递推就行了。

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
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
// Problem: D. Good Trip
// Contest: Codeforces - Codeforces Round 921 (Div. 2)
// URL: https://codeforces.com/contest/1925/problem/D
// Memory Limit: 256 MB
// Time Limit: 1000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

//#pragma GCC optimize(2)
#include <bits/stdc++.h>
using namespace std;

const int N = 2e5 + 10;
const int inf = 1 << 30;
const long long llinf = 1ll << 60;
const double PI = acos(-1);

#define lowbit(x) (x&-x)
typedef long long ll;
typedef double db;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef pair<db, db> pdd;
typedef pair<ll, int> pli;

int n, m, k, q;
const ll mod = 1e9 + 7;
ll ksm(ll base, ll k)
{
	ll ans = 1;
	while (k)
	{
		if (k & 1)
			ans = (ans * base) % mod;
		base = (base * base) % mod;
		k >>= 1;
	}
	return ans;
}
void work()
{
	cin >> n >> m >> k;
	ll sum = 0;
	for (int i = 1, x, y, z; i <= m; i++)
	{
		cin >> x >> y >> z;
		sum += z;
		sum %= mod;
	}
	ll cnt = ((ll)(n) * (ll)(n - 1) / 2LL) % mod;
	ll cntmod = ksm(cnt, mod - 2);
	ll ans = 0;
	for (int i = 1; i <= k; i++)
	{
		ans = (sum * cntmod % mod + ans) % mod;
		sum = (sum + (m * cntmod % mod)) % mod;
	}
	cout << ans << endl;
}
int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	int t;
	cin >> t;
	while (t --> 0)
	{
		work();
	}
}

E - Space Harbour

一个数据结构好题。

询问操作，很显然可以拆分为\(query(r)-query(l-1)\)的操作。那么我们考虑用树状数组维护每个点的贡献。

但是很显然，每次插入港口，都会对很多个位置的贡献造成改变，显然不能直接维护贡献。

考虑一下一整段点贡献的性质，很容易发现的是，对于两个港口\(pos_i,pos_{i-1}\)​之间的位置，他们的贡献和可以表示为： \[ V_{pos_i} \times (1+2+3+\dots +(pos_i-pos_{i-1}-1)) \\\\ =V_{pos_i} \times \frac{(pos_i-pos_{i-1})(pos_i-pos_{i-1}-1)}{2} \] 考虑维护每一个坐标左边的最近港口的值，显然可以用树状数组差分完成。

那么，对于维护贡献，我们可以不维护全部点的贡献，转而维护连续整段的贡献。

具体的，我们算出两个港口之间答案的和，将这个答案存放在\(pos_i+1\)的位置上。这样，当查询\(x\)位置的贡献和时，对于整段区间，直接前缀和算出；对于结尾的小段，再单独计算即可。

然后是加入港口操作。显然，我们是把原来的一整段区间分成了两个区间。用个set维护港口的下标，求出上一个港口和下一个港口的坐标后，再更新一下两个树状数组即可。

这题小细节很多，要格外注意。

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
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
// Problem: E. Space Harbour
// Contest: Codeforces - Codeforces Round 921 (Div. 2)
// URL: https://codeforces.com/contest/1925/problem/E
// Memory Limit: 256 MB
// Time Limit: 2000 ms
// Author: MaxDYF
// 
// Powered by CP Editor (https://cpeditor.org)

//#pragma GCC optimize(2)
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 3e5 + 10;
const int inf = 1 << 30;
const long long llinf = 1ll << 60;
const double PI = acos(-1);

#define lowbit(x) (x&-x)
typedef long long ll;
typedef double db;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef pair<db, db> pdd;
typedef pair<ll, int> pli;

int n, m, k, q;
	
void add(ll *a, ll x, ll v)
{
	for (; x <= n; x += lowbit(x))
		a[x] += v;
};
ll query(ll *a, ll x)
{
	ll ans = 0;
	for (; x; x -= lowbit(x))
		ans += a[x];
	return ans;
}
set<ll> harbour;

ll near[N];
// 差分记录上一个最近港口的val，
// 用树状数组维护


ll ans[N];
// 记录当前区间段的总答案
// 假设两个相邻港口的位置为l, r
// 则[l+1, r-1]的答案之和统一存储在l+1上
// 用树状数组维护



// 插入新的港口
// 注意: 1和n的港口需要单独处理
void new_harbour(ll x, ll v)
{
	// 删去上一个near对x之后造成的影响
	// 同时删去x对下一个near之后的的数造成的影响
	auto old_val = query(near, x);
	add(near, x, -old_val);
	
	add(near, x, v);
	auto it = harbour.upper_bound(x);
	ll nxt = *it;
	ll pre = *(--it);
	
	add(near, nxt, -v);		
	add(near, nxt, old_val);	
	
	
	
	
	// 下面更新用于记录答案的ans
	

	if (pre + 1 <= nxt - 1)
	{
		
		auto old_ans = query(ans, pre + 1) - query(ans, pre);
		add(ans, pre + 1, -old_ans);
		// x左边区间的答案
		ll cnt1 = x - pre - 1;
		ll val1 = query(near, pre + 1);
		add(ans, pre + 1, val1 * (cnt1 + 1LL) * cnt1 / 2LL);
		
		
		
		// x右边区间的答案
		ll cnt2 = nxt - x - 1;
		ll val2 = v;
		add(ans, x + 1, val2 * (cnt2 + 1LL) * cnt2 / 2LL);
	}
	
	
	harbour.insert(x);
}

ll getvalue(int x)
{
	if (x == 0)
		return 0;
	auto it = harbour.lower_bound(x);
	ll now = query(ans, x);
	if ((*it) - x - 1 <= 0)
	{
		return now;
	}
	ll val = query(near, x);
	ll cnt = (*it) - x - 1;
	now -= val * (cnt + 1LL) * cnt / 2LL;
	return now;
}

pll initHarbour[N];
void work()
{
	cin >> n >> m >> q;
	for (int i = 1; i <= m; i++)
		cin >> initHarbour[i].first;
	for (int i = 1; i <= m; i++)
		cin >> initHarbour[i].second;
	sort(initHarbour + 1, initHarbour + m + 1);
	
	
	// 下面单独插入1和n位置的港口
	harbour.insert(1);
	harbour.insert(n);
	ll cnt = n - 2;
	add(near, 1, initHarbour[1].second);
	add(near, n, -initHarbour[1].second);
	add(ans, 2, initHarbour[1].second * (cnt + 1LL) * cnt / 2LL);
	
	// 下面再插入非1和n位置的港口
	for (int i = 2; i < m; i++)
		new_harbour(initHarbour[i].first, initHarbour[i].second);
	for (int i = 1; i <= q; i++)
	{
		ll opt, l, r;
		cin >> opt >> l >> r;
		if (opt == 1)
			new_harbour(l, r);
		else
		{
			ll ans1 = getvalue(r), ans2 = getvalue(l - 1);
			cout << ans1 - ans2 << '\n';
			
		}
	}
	
}
signed main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	work();
}