MaxDYF的随笔Blog

May all the beauty be blessed.

发表于 更新于 分类于

Problem D 茶和咖啡

思路

观察到能用的券只取决于最早的选择天数，设当前最早的喝咖啡日为pos，则每新增一天，我们有以下两种策略：

  1. 选择比目前最早的天数更早的一天，即从[1, pos-1]天中选择一天。
  2. 选择比pos更晚的一天，即[pos+1, n]天。

对于第一种，我们可以做优惠券的后缀和w[i]，表示第i天能享用的优惠券的总优惠，则可知选择第i天的贡献值为w[i]-w[pos]，则最优决策显然为：\(min_{i=1}^{pos-1}(w[i])-w[pos]\)，显然可以用std::set或权值线段树进行维护。

对于第二种，我们只需求[pos+1, n]中最小的a[i]，即\(min_{i=pos+1}^n(a[i])\)。同样用set或权值线段树维护即可。

然后对比两种决策，选更优的决策即可。

*当两种最优决策贡献值相等时，注意到前一种可以使下一次的决策数量增加更多，所以选择向前扩展。

总的复杂度\(O(Tnlog_2n)\)。

## Problem F 质数之谜

阅读全文 »

发表于 更新于 分类于

题意

  • 给你 \(n\) 条线段，告诉你每条线段的长度。
  • 你需要把它们放在一条无限长的数轴上。
  • 放置需满足当前线段的起点是前一个线段的终点，特别的第一个线段的起点为 00。

也就是说，若前一个线段的终点是 \(x\),当前长度为 \(d\), 那么这个线段必须放在\([x, x+d]\) ，或者\([x-d,x]\)

  • \(1≤t≤10^4,1≤n≤10^4\)

思路

最小覆盖长度，考虑二分答案，\(dp_{i,j}\)表示第\(i\)个线段终点落在\(j\)的可行性，注意此时\(j\)不表示实际坐标，而是表示实际覆盖区间的相对坐标。

初始时\(dp_{0,0...mid}\)全为\(true\)，因为线段1可以放在任何坐标上，容易写出转移方程：

$ dp_{i,j} = [dp{i-1,j - d_i} * (j - d_i lim)]  or  [dp_{i-1,j+d_i}*(j+d_i )$

单次check时间复杂度为\(O(n^2)\)，可用bitset优化时间，加上滚动数组优化掉第一维。

总时间复杂度为\(O(n^2log_2n)\)。

阅读全文 »

发表于 更新于 分类于

题意

给定一张\(n\) 个点的有向图，若 \(i\)<\(j\)则 \(i\) 到\(j\)有边。现要求用最小的颜色数量给边染色，使任意一条长度为 \(k\) 的路径不同色。输出方案。

思路

将\(1,2,3...k\)的边全部设置为1，将\(k+1,k+2,k+3...2k\)的边设为1，一直至\(k^2\)，然后在每个\(k\)的块内的边设为2，在\(k^2\)的块内的边设为3，以此类推，则最终答案数为\(\lceil log_kn\rceil\)。

Code

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
// Problem: Defender of Childhood Dreams
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/CF1583F
// Memory Limit: 500 MB
// Time Limit: 3000 ms
// Auther : MaxDYF
// 
// 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);
typedef pair<int, int> pii;
typedef long long ll;
int n, m, k, q;

void work()
{
	cin >> n >> k;
	cout << (int)(ceil(log(n) / log(k))) << endl;
	for (int i = 0; i < n; i++)
		for (int j = i + 1; j < n; j++)
		{
			int x = i, y = j;
			int col = 0;
			while (x != y)
			{
				x /= k;
				y /= k;
				col++;
			}
			cout << col << ' ';
		}
	cout << endl;
}
int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	work();
}

发表于 更新于 分类于

题意

有一个大小为\(n\)的排列，以某种顺序插入一个集合中，给出一个长度为\(n-1\)的字符串，第\(i\)位表示第\(i+1\)个插入的数在已有集合中的情况，\(<\)为最小，\(>\)为最大，\(?\)为其他情况，给出q个单次修改，每次修改后询问其顺序的可能数。

思路

先考虑静态，设当前为str[i],正在插入第\(i+1\)个数，则说明前面有\(i\)个数。若当前位为>或<，则说明该数在目前唯一确定；若为?，则共有\(i-1\)个空可插入，方案数应\(*(i-1)\)。在\(O(n)\)的时间内可预处理完毕。

考虑动态，因为某一位的情况没有后效性影响，因此可以\(O(1)\)动态维护每次方案，注意有模数，在除法时要使用逆元。

Code

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
// Problem: D. Monocarp and the Set
// Contest: Codeforces - Educational Codeforces Round 156 (Rated for Div. 2)
// URL: https://codeforces.com/contest/1886/problem/D
// Memory Limit: 256 MB
// Time Limit: 2000 ms
// Auther : MaxDYF
// 
// 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);
typedef pair<int, int> pii;
typedef long long ll;
int n, m, k, q;
const ll mod = 998244353ll;
void work()
{
	cin >> n >> m;
	string a;
	cin >> a;
	auto pw = [&](ll base, ll x)
	{
		ll ans = 1;
		while (x)
		{
			if (x & 1)
				ans = (ans * base) % mod;
			x >>= 1;
			base = (base * base) % mod;
		}
		return ans;
	};
	ll ans = 1, bj = 1;
	for (int i = 0; i < n; i++)
		if (a[i] == '?')
		{
			if (i == 0)
				bj = 0;
			else
				ans = (ans * i) % mod;
		}
	cout << ans * bj << endl;
	char ch;
	for (int i = 0, q; i < m; i++)
	{
		cin >> q >> ch;
		if (q == 1 && ch != '?')
			bj = 1;
		else if (q == 1 && ch == '?')
			bj = 0;
		else
		{
			if (a[q - 1] == '?' && ch != '?')
				ans = (ans * pw(q - 1, mod - 2) % mod);
			else if (a[q - 1] != '?' && ch == '?')
				ans = (ans * (q - 1)) % mod;
		}
		a[q - 1] = ch;
		cout << ans * bj << endl;
	}
}
int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	work();
}

发表于 更新于 分类于

题意

给定两个长度为\(n\)的序列\(a\)和\(b\)，每次操作可以选择一对\(\{l,r\}\)，将\(a_l, a_{l+1}, a_{l+2}...a_r\)变为其中的最大值，问是否能将\(a\)变为\(b\)。

思路

考虑能让\(a_i\)变成\(b_i\)的条件，分为三种情况：

  1. \(a_i=b_i\)，则必然可以。
  2. \(a_i> b_i\)，可知一定无解。
  3. \(a_i<b_i\)，则需要从两边寻找一个\(a_j=b_i\)使得\(a_i\)变成\(b_i\)。

对于第三种情况，可以发现如果要在不影响其他位置成立的情况下使得\(a_i\)变成\(b_i\)，其充分必要条件是对于\(a_{i...j}\)与\(b_{i...j}\)，满足 \[ a_k \leq b_i, for\ k\in[i, j]\\\ b_k \geq b_i, for\ k\in[i, j] \] 可以简化为 \[ max_{k=i}^{j}a_k\leq b_i \leq min_{k=i}^{j}b_k \]

从前往后、从后往前分别扫一遍，最值操作用st表或线段树预处理即可，时间复杂度\(\Theta(n log_2n)\)。

代码

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
// Problem: D2. Set To Max (Hard Version)
// Contest: Codeforces - Codeforces Round 914 (Div. 2)
// URL: https://codeforces.com/contest/1904/problem/D2
// Memory Limit: 256 MB
// Time Limit: 4000 ms
// Auther : MaxDYF
// 
// 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;
int a[N];
int b[N];
int vis[N];
int l2[N];
int st1[N][30], st2[N][30];
int lst[N];
void work()
{
	cin >> n;
	fill(vis, vis + n + 1, 0);
	
	for (int i = 1; i <= n; i++)
		for (int j = 0; j <= l2[n]; j++)
		{
			st1[i][0] = 0;
			st2[i][0] = inf;
		}
	for (int i = 1; i <= n; i++)
	{
		cin >> a[i];
		st1[i][0] = a[i];
	}	
	for (int i = 1; i <= n; i++)
	{
		cin >> b[i];
		st2[i][0] = b[i];
	}
	for (int t = 1; t <= l2[n]; t++)
		for (int i = 1; i + (1 << t) - 1 <= n; i++)
			st1[i][t] = max(st1[i][t - 1], st1[i + (1 << (t - 1))][t - 1]);
	
	for (int t = 1; t <= l2[n]; t++)
		for (int i = 1; i + (1 << t) - 1 <= n; i++)
			st2[i][t] = min(st2[i][t - 1], st2[i + (1 << (t - 1))][t - 1]);
	auto query1 = [&](int l, int r)
	{
		int t = l2[r - l + 1];
		return max(st1[l][t], st1[r - (1 << t) + 1][t]);
	};
	auto query2 = [&](int l, int r)
	{
		int t = l2[r - l + 1];
		return min(st2[l][t], st2[r - (1 << t) + 1][t]);
	};
	fill(lst, lst + n + 1, -1);
	for (int i = 1; i <= n; i++)
	{
		lst[a[i]] = i;
		if (a[i] == b[i])
		{
			vis[i] = 1;
			continue;
		}
		if (lst[b[i]] == -1)
			continue;
		if (query1(lst[b[i]], i) <= b[i] && query2(lst[b[i]], i) >= b[i])
			vis[i] = true;
	}
	fill(lst, lst + n + 1, -1);
	for (int i = n; i >= 1; i--)
	{
		lst[a[i]] = i;
		if (a[i] == b[i])
		{
			vis[i] = 1;
			continue;
		}
		if (lst[b[i]] == -1)
			continue;
		if (query1(i, lst[b[i]]) <= b[i] && query2(i, lst[b[i]]) >= b[i])
			vis[i] = true;
	}
	bool suc = 1;
	for (int i = 1; i <= n; i++)
		if (!vis[i])
		{
			suc = 0;
			break;
		}
	cout << (suc ? "YES\n" : "NO\n");
}
int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	l2[1] = 0;
	for (int i = 2; i < N; i++)
		l2[i] = l2[i / 2] + 1;
	int t;
	
	cin >> t;
	while (t --> 0)
	{
		work();
	}
}
0%