Codeforces Round #811 (Div. 3)

D.Color with Occurrences

题意：

给你一个长度为 $∣ t ∣$ 的母串 $t$ ，给你 $n$ 个子串，如果子串和母串的某个子串一样，你可以将其染成红色，问最小染色次数以及方案。

思路：

比赛的时候一开始想直接模拟，然后发现虽然时间复杂度够，但是情况太多。赛后发现可以把问题转化下。

我们可以先把母串每个字母可以向右匹配的最大长度记录下来，然后从左往右贪心的遍历：假如母串第 $1$ 个字母能匹配到第 $e n d$ 位置，那么下一次我们应该从第 $2$ ~ $min (e n d + 1, ∣ t ∣)$ 里面找能匹配更加靠后的位置，一直找到最后一个字母为止。

注意：如果子串中有和母串一模一样的，就可以直接输出答案。

后面贪心的过程，有一段小模拟，还是要多写代码多总结，这种题才能又快有准确写对。

代码

const int N = 110;
string t;
int n;
string s[15];
int r[N], ans[N];//r[i]存的是最右能到达哪
vector<PII>res;
void solve()
{
    res.clear();
    memset(r, -1, sizeof r);
    t = rd();read(n);int szt = sz(t);
    for(int i = 1; i <= n; i ++ ){
        s[i] = rd();
    }
    for(int i = 0; i < szt; i ++ ){
        for(int j = 1; j <= n; j ++ ){
            if(s[j] == t){
                printf("%d\n%d %d\n",1, j, 1);
                return;
            }
            int szs = sz(s[j]);
            if(t.substr(i, szs) == s[j]){
                if(i + szs - 1 > r[i]){
                    r[i] = i + szs - 1;
                    ans[i] = j;
                }
            }
        }
    }
    res.pb({ans[0], 0});
    int start = 0, ends = r[0] + 1;
    while(true){
        int x = -1, y = -1;
        int maxlen = -1;
        for(int i = start; i <= min(szt, ends); i ++ ){
            if(r[i] > maxlen){
                maxlen = r[i];
                x = i, y = ans[i];
            }
        }
        if(x == -1 || start == x){
            puts("-1");
            return;
        }
        start = x;
        ends = x + sz(s[y]);
        res.push_back({y, x});
        if(ends == szt) break;
    }
    writeln(res.size());
    for(auto it : res){
        printf("%d %d\n",it.fi,it.se + 1);
    }
    return;
}
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

E. Add Modulo 10

题意：

给你一个数组 $a$ ，你可以对里面的元素进行以下操作

$\% 10$

问你能否将数组变成一样。

思路：

这题规律非常明显了，对于大部分数而言，个位数往后都是 $2 、 4 、 8 、 6$ 循环，周期长度是 $20$ 。然后可以写一串数字进行分析，容易发现，以2为个位转化为以 $2 、 4 、 8 、 6$ 为个位的数分别可以在原有的数上加上 $\{0、2、14、6\} + k * 20 (k \geqslant 0)$ ，其余的数同理，(非常愚蠢的做法,几乎不要动脑子)。

注意：个位数为 $5$ 的和个位数为 $0$ 的要特判一下

代码:

const int N = 200010;
int a[N];
int n;
map<int,int>mp;
void solve()
{
	mp.clear();
	read(n);
	for(int i = 1; i <= n; i ++ ){
		read(a[i]);
		if(a[i] % 10 == 5) mp[a[i] + 5] ++;
		else if(a[i] % 10 == 0) mp[a[i]] ++;
	}
	if(mp.size() >= 2){
		puts("No");
		return;
	}
	if(mp.size() == 1){
		for(auto it : mp){
			if(it.second != n){
				puts("No");
				return;
			}
		}
		puts("Yes");
		return;
	}
	for(int i = 1; i <= n; i ++ ){
		while(a[i] % 2 == 1){
			a[i] = a[i] + (a[i] % 10);
		}
	}
	sort(a + 1, a + 1 + n);
	cout << endl;
	for(int i = 2; i <= n; i ++ ){
		int m1 = a[i] % 10, m2 = a[i - 1] % 10;//从m2变化到m1
		int cha = a[i] - a[i - 1];
		if(m2 == 2){
			if(m1 == 2 && cha % 20 != 0){
				puts("No");
				return;
			}else if(m1 == 4 && cha % 20 != 2){
				puts("No");
				return;
			}else if(m1 == 6 && cha % 20 != 14){
				puts("No");
				return;
			}else if(m1 == 8 && cha % 20 != 6){
				puts("No");
				return;
			}
		}
		if(m2 == 4){
			if(m1 == 2 && cha % 20 != 18){
				puts("No");
				return;
			}else if(m1 == 4 && cha % 20 != 0){
				puts("No");
				return;
			}else if(m1 == 6 && cha % 20 != 12){
				puts("No");
				return;
			}else if(m1 == 8 && cha % 20 != 4){
				puts("No");
				return;
			}
		}
		if(m2 == 6){
			if(m1 == 2 && cha % 20 != 6){
				puts("No");
				return;
			}else if(m1 == 4 && cha % 20 != 8){
				puts("No");
				return;
			}else if(m1 == 6 && cha % 20 != 0){
				puts("No");
				return;
			}else if(m1 == 8 && cha % 20 != 12){
				puts("No");
				return;
			}
		}
		if(m2 == 8){
			if(m1 == 2 && cha % 20 != 14){
				puts("No");
				return;
			}else if(m1 == 4 && cha % 20 != 16){
				puts("No");
				return;
			}else if(m1 == 6 && cha % 20 != 8){
				puts("No");
				return;
			}else if(m1 == 8 && cha % 20 != 0){
				puts("No");
				return;
			}
		}
	}
	puts("Yes");
	return;
}
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

F. Build a Tree and That Is It

题意：
给你 $n$ 个点和 $d_{12}、d_{23}、d_{13}$ ，让你构造一张无向图。

思路：
分两种情况讨论：链式和分叉式，链式是一种特殊的分叉式。

如果存在 $d_{12}、d_{23}、d_{13}$ 其中两个和等于另外一个和，可以采用链式构造，例如 $d_{12} + d_{23} = d_{13}$ ,可以构造成： $1, x, x, x, 2, x, x, x, 3$ 。
在这里插入图片描述

如果不满足上述条件可以构造成分叉式
在这里插入图片描述

可以根据方程组

{\begin{cases} x + y = d_{12} \\ x + z = d_{13} \\ y + z = d_{12} \end{cases}

⎩ ⎨ ⎧ x + y = d_{12} x + z = d_{13} y + z = d_{12}

解出：

{\begin{cases} x = \frac{d_{13} + d_{12} - d_{23}}{2} \\ y = \frac{d_{12} + d_{23} - d_{13}}{2} \\ z = \frac{d_{23} + d_{13} - d_{12}}{2} \end{cases}

⎩ ⎨ ⎧ x = \frac{d _{13} + d _{12} - d _{23}}{2} y = \frac{d _{12} + d _{23} - d _{13}}{2} z = \frac{d _{23} + d _{13} - d _{12}}{2}

要保证分子都是大于 $0$ 的偶数，如果分子都是 $0$ 那么就是链式的，已经讨论过了。

代码

#include 
#define PII pair<int,int>
#define LL long long
#define fi first
#define se second
#define debug(a) cout<<#a<<"="<<a<<endl;
#define all(x) (x).begin(),(x).end()
#define pb push_back
#define sz(x) (int)x.size()
using namespace std;
inline string rd()
{
	string str="";
	char ch=getchar();
	while(ch==' ' || ch=='\n' || ch=='\r')
	{
		ch=getchar(); 
	}
	while(ch!=' ' && ch!='\n' && ch!='\r')
	{
		str+=ch;
		ch=getchar();
	 } 
	return str;
}
inline void print(string s)
{
	for(int i=0; s[i]!='\0'; i++) putchar(s[i]);
}
template <typename T> void read(T &t) {
	t=0; char ch=getchar(); int f=1;
	while (ch<'0'||ch>'9') { if (ch=='-') f=-1; ch=getchar(); }
	do { (t*=10)+=ch-'0'; ch=getchar(); } while ('0'<=ch&&ch<='9'); t*=f;
}
template <typename T> void write(T t) {
	if (t<0) { putchar('-'); write(-t); return; }
	if (t>9) write(t/10);
	putchar('0'+t%10);
}
template <typename T> void writeln(T t) { write(t); puts(""); }
const int N = 200010;
int n, d12, d13, d23;
bool st[N];
vector<PII>ans;
void print(vector<PII>ans){
	puts("YES");
	for(auto it : ans){
		printf("%d %d\n",it.fi, it.se);
	}
	return;
}
void solve()
{
	ans.clear();
	read(n);read(d12);read(d23);read(d13);
	//链式：
	int idx = 4;
	int pre = 1;
	if(d12 + d23 == d13){
		bool f = 1;
		for(int i = 1; i <= d12 - 1; i ++ ){
			ans.pb({pre, idx});
			pre = idx;
			idx ++;
		}
		if(idx - 1 > n){
			f = 0;
		}
		ans.pb({pre, 2});
		pre = 2;
		for(int i = 1; i <= d23 - 1 && f; i ++ ){
			ans.pb({pre, idx});
			pre = idx;
			idx ++;
		}
		if(idx - 1 > n){
			f = 0;
		}
		ans.pb({pre, 3});
		for(int i = idx; i <= n && f; i ++ ){
			ans.pb({1, i});
		}
		if(f){
			print(ans);
			return;
		}
	}
	idx = 4;
	pre = 1;
	if(d13 + d23 == d12){
		bool f = 1;
		for(int i = 1; i <= d13 - 1; i ++ ){
			ans.pb({pre, idx});
			pre = idx;
			idx ++;
		}
		if(idx - 1 > n){
			f = 0;
		}
		ans.pb({pre, 3});
		pre = 3;
		for(int i = 1; i <= d23 - 1 && f; i ++ ){
			ans.pb({pre, idx});
			pre = idx;
			idx ++;
		}
		if(idx - 1 > n){
			f = 0;
		}
		ans.pb({pre, 2});
		for(int i = idx; i <= n && f; i ++ ){
			ans.pb({1, i});
		}
		if(f){
			print(ans);
			return;
		}
	}
	idx = 4;
	pre = 2;
	if(d12 + d13 == d23){
		bool f = 1;
		for(int i = 1; i <= d12 - 1; i ++ ){
			ans.pb({pre, idx});
			pre = idx;
			idx ++;
		}
		if(idx - 1 > n){
			f = 0;
		}
		ans.pb({pre, 1});
		pre = 1;
		for(int i = 1; i <= d13 - 1 && f; i ++ ){
			ans.pb({pre, idx});
			pre = idx;
			idx ++;
		}
		if(idx - 1 > n){
			f = 0;
		}
		ans.pb({pre, 3});
		for(int i = idx; i <= n && f; i ++ ){
			ans.pb({1, i});
		}
		if(f){
			print(ans);
			return;
		}
	}	
	//分叉式：
	if(d12 + d23 <= d13 || d12 + d13 <= d23 || d23 + d13 <= d12){
		puts("NO");
		return;
	}
	if((d12 + d23 - d13) % 2 || (d23 + d13 - d12) % 2 || (d13 + d12 - d23) % 2){
		puts("NO");
		return;
	}
	int x = (d12 + d13 - d23) / 2, y = (d23 + d12 - d13) / 2, z = (d23 + d13 - d12) / 2;
	if(n - 5 + 1 < x - 1 + y - 1 + z - 1 ){
		puts("NO");
		return;
	}
	idx = 5;
	pre = 1;
	for(int i = 1; i <= x - 1; i ++ ){
		ans.pb({idx, pre});
		pre = idx;
		idx ++;
	}
	ans.pb({pre, 4});
	pre = 4;
	for(int i  =1; i <= y - 1; i ++ ){
		ans.pb({idx, pre});
		pre = idx;
		idx ++;
	}
	ans.pb({pre, 2});
	pre = 4;
	for(int i = 1; i <= z - 1; i ++ ){
		ans.pb({idx, pre});
		pre = idx;
		idx ++;
	}
	ans.pb({pre, 3});
	for(int i  = idx; i <= n; i ++ ){
		ans.pb({i, 1});
	}
	print(ans);

}

int main()
{
	int test = 1;
	scanf("%d",&test);
	while(test -- )
	{
		solve();
	}
	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
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
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204

G. Path Prefixes

题意：
给你一个以 $1$ 为根的树，有 $n$ 个节点， $n - 1$ 条边，每条边有两个属性值 $a_i$ , $b_i$ ，对于每一个节点 $i$ 求:
从根节点到 $i$ 节点的路径中， $b_i$ 的前缀（小于等于从 $1$ 到 $i$ 中路径上所有 $a_i$ 的和）的个数。

思路：

从根节点开始对每一个节点进行深度优先遍历，并记录 $a_i、b_i$ 的前缀和，并对所有的 $\sum{a_i}$ ，二分 $b_i$ 的前缀个数。

代码：

#include 
#define PII pair<int,int>
#define LL long long
#define fi first
#define se second
#define debug(a) cout<<#a<<"="<<a<<endl;
#define all(x) (x).begin(),(x).end()
#define pb push_back
#define sz(x) (int)x.size()
using namespace std;
const int N = 200010, M = 400010;
inline string rd()
{
	string str="";
	char ch=getchar();
	while(ch==' ' || ch=='\n' || ch=='\r')
	{
		ch=getchar(); 
	}
	while(ch!=' ' && ch!='\n' && ch!='\r')
	{
		str+=ch;
		ch=getchar();
	 } 
	return str;
}
inline void print(string s)
{
	for(int i=0; s[i]!='\0'; i++) putchar(s[i]);
}
template <typename T> void read(T &t) {
	t=0; char ch=getchar(); int f=1;
	while (ch<'0'||ch>'9') { if (ch=='-') f=-1; ch=getchar(); }
	do { (t*=10)+=ch-'0'; ch=getchar(); } while ('0'<=ch&&ch<='9'); t*=f;
}
template <typename T> void write(T t) {
	if (t<0) { putchar('-'); write(-t); return; }
	if (t>9) write(t/10);
	putchar('0'+t%10);
}
template <typename T> void writeln(T t) { write(t); puts(""); }
int  e[M], A[M], h[N], ne[N], B[M], idx, n;
LL suma[M], sumb[M], ans[N];
bool st[N];
void add(int a, int b, int wa, int wb){
	A[idx] = wa, B[idx] = wb, e[idx] = b, ne[idx] = h[a], h[a] = idx ++;
}

void dfs(int u, int cnt){
	st[u] = true;
	for(int i = h[u]; ~i; i = ne[i]){
		int j = e[i];
		suma[cnt + 1] = suma[cnt] + A[i], sumb[cnt + 1] = sumb[cnt] + B[i];
		cnt ++;
		int l = 0, r = cnt;
		while(l < r){
			int mid = l + r + 1 >> 1;
			if(sumb[mid] <= suma[cnt]) l = mid;
			else r = mid - 1;
		}
		ans[j] = l;
		if(!st[j]) dfs(j, cnt);
		cnt --;
	}
}

void solve()
{
	read(n);
	idx = 0;
	for(int i = 1; i <= n; i ++ ){
		h[i] = -1;
		st[i] = false;
	}
	for(int i = 2; i <= n; i ++ ){
		int x, wa, wb;
		read(x);read(wa);read(wb);
		add(x, i, wa, wb);
	}
	dfs(1, 0);
	for(int i = 2; i <= n; i ++ ){
		write(ans[i]);
		putchar(' ');
	}
	puts("");
}

int main()
{
	int test = 1;
	scanf("%d",&test);
	while(test -- )
	{
		solve();
	}
	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
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

相关阅读:
二叉树和二叉堆和优先队列
记一次线程爆满导致服务器崩溃的问题排查
十四届蓝桥青少组模拟赛Python-20221108
hadoop2.2.0伪分布式搭建
计算机网络实验五子网划分与路由器配置
LCR表测电容怎么实现连续测试？ATECLOUD云测试平台帮您解决
B. Trouble Sort
go-redis 框架基本使用
Ubuntu下运行adb devices找不到设备的问题
Spring 对 Java EE API 整合-5

原文地址：https://blog.csdn.net/apple_52197802/article/details/126132444