【CodeTON Round 2 (Div. 1 + Div. 2, Rated, Prizes!)(A~D)】

$更好的阅读体验$

---

---

A. Two 0-1 Sequences

---

题目大意

Origional Link

• 给定只包含$0$和$1$的字符串$a$和$b$
• 对$a$进行操作：
  • 将$a_2=min(a_1,a_2)$，并删除$a_1$，使得$a_2$变为新的$a_1$
  • 将$a_2=max(a_1,a_2)$，并删除$a_1$，使得$a_2$变为新的$a_1$
• 上述操作不限次数，求最终是否可以使得$a=b$

---

思想

• 由于我们只能对a[1], a[2]进行操作

• 观察string a, b，发现：

  • 先将a和b的最左端对齐

  • a = "00100101"
    b =     "1101"
    1
    2

  • 与b[0]对其的a[4]不相等，b[0]之后对齐的与a[4]之后的元素均相等

  • 若使得a == b，则a[4]之前的元素中，必然存在某元素a[i] == b[0]，才可通过相关操作使得a[4] == b[0]

• 由此可知，我们设b[0]与a[k]对齐

• 从a[k + 1]开始构造a的字串s1，从b[1]开始构造b的字串s2

• 若s1 == s2 ：

  • 若b[0] == a[k]说明必然可以使得a == b
  • 若b[0] != a[k]，则当k之前存在a[i] == b[0]时可以使得a == b，反之不行

• 若s1 != s2，则无论如何操作都无法使得a == b

---

代码

#include 
using namespace std;

void solve(){
	
	int n, m;
	
	cin >> n >> m;
	
	string a, b;
	cin >> a >> b;
		
	int k = a.size() - b.size();  //对其的位置
	
	string s1 = a.substr(k + 1,b.size() - 1);
	string s2 = b.substr(1,b.size() - 1);
	
	if(s1 == s2){
		
		int flag = 0;
		
		if(a.rfind(b[0], k) != -1) flag = 1;
		
		if(flag) cout << "YES" << endl;
		else cout << "NO" << endl;
		 
	}
	else cout << "NO" << endl;
	
}

int main(){
	
	int _;
	cin >> _;
	while(_ --){
		solve();
	}
	
//	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

---

B. Luke is a Foodie

---

题目大意

Origional Link

• 对于$a_i$和固定的$x$
• 有可以变成任意整数的$v$，使得$|v-a_i|\le x$
• 遍历数组$a$，求$v$最小变化的次数

---

思想

• 由$|v-a_i|\le x$可知$a_i-x\le v\le a_i+x$
• 故对于a[i]，必然存在满足$|v-a_i|\le x$的区间[l,r]，l = a[i] - x, r = a[i] + x
• 设a[i + 1]的区间[l',r']，l = a[i + 1] - x, r = a[i + 1] + x
• 若[l,r]与[l',r']有公共区间时，v可以不用发生改变，并将区间更新为其公共区间
• 若[l,r]与[l',r']无公共区间时，v将发生改变，并将区间变为[l',r']
• 公共区间存在判断：max(l,l') <= min(r,r')说明存在公共区间

---

代码

#include 
using namespace std;

typedef long long LL;

void solve(){
	
	LL n, x;
	
	cin >> n >> x;
	
	LL cnt = 0;
	
	LL t;
	cin >> t;
	
	LL l = t - x, r = x + t;  //初始区间 
	
	for(int i = 1; i < n; i ++){
		LL y;
		cin >> y;
		LL p1 = y - x, p2 = y + x;
		if(max(p1,l) <= min(p2,r)){  //是否有公共区间 
			l = max(p1,l);  //更新公共区间左边界 
			r = min(p2,r);  //更新公共区间右边界 
		}
		else{
			cnt ++;  //不存在公共区间，需要变化一次 
			l = p1;  //重置区间 
			r = p2;
		}
		
	}
	
	cout << cnt << endl;
	
}

int main(){
	
	int _;
	cin >> _;
	while(_ --){
		solve();
	}
	
//	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

---

C. Virus

---

题目大意

Origional Link

• $1\sim N$的房屋围成一圈
• 给出初始感染病毒的房屋编号
• 每天可选择未感染的房屋进行保护，可使其永久不被感染
• 每天已感染的房屋其左右邻居都会受到感染
• 求最优策略下，最终感染的房屋数量

---

思想

• 贪心
• 每次选择未感染的最长区间进行保护
• 对于被保护的区间[l,r]：
  • 经过第一天：
    • 保护[l,r]的一个端点，设保护a[l]
    • a[l]不会感染，a[r]会被感染
    • 其他所有未受到保护的区间[l',r']里，a[l']和a[r']被感染
  • 经过第二天：
    • 保护[l,r]的另一个端点a[r]，由于第一天a[r]被感染，故只能保护a[r - 1]
    • 其他所有未受到保护的区间[l',r']里，a[l' + 1]和a[r' - 1]被感染
  • 即对于选择保护的区间[l,r]，a[r]被感染，我们只能保护到[l,r - 1]这一段，且其余所有未受到保护的区间[l',r']里a[l'],a[r'],a[l' + 1],a[r' - 1]受到感染，感染后的区间变为[l' + 2, r' - 2]
• 综上可知，我们优先保护最长的未被感染的区间，即可实现最优策略
• 由于选择保护的区间端点可以任选，故只需要考虑区间长度，不需要维护额外的信息
• 注意不要忽略首尾相连的区间

---

代码

#include 
using namespace std;

void solve(){
	
	int n, m;
	
	cin >> n >> m;
	
	vector<int> vis;  //vis存储最先被感染的房屋编号 
	
	for(int i = 0; i < m; i ++){
		int x;
		cin >> x;
		vis.push_back(x);
	}
	
	sort(vis.begin(),vis.end());  //将编号从小到大排序 
	
	priority_queue<int> st;  //优先队列维护当前最大长度的区间 
	
	st.push(n - vis.back() + vis[0] - 1);  //将首尾相连的区间长度加入 

	for(int i = 0; i + 1 < vis.size(); i ++){
		st.push(vis[i + 1] - vis[i] - 1);  //将未感染的区间的长度加入 
	}
	
	int cnt = 0;  //存储未感染的区间长度 
	
	for(int i = 0; i + 1 > 0; i ++){  //i代表天数 
		if(!st.empty() && st.top() - i * 4 > 0){  //经过一天，下一个区间长度 -4 
			int k = st.top() - i * 4;  //设k为当前区间经过i天后未感染的区间长度 
			if(k > 1) k --;  //对于一个端点的保护，会使另一个端点被感染(长度-1)，若区间长度仅为1，则只能保护1长度 
			cnt += k;  //累计保护到的区间长度 
			st.pop();
		}
		else break;
	}
	
	cout << n - cnt << endl;  //区间总长 - 保护的区间长度 = 被感染的区间长度 = 被感染的房屋数量 
	
}

int main(){
	
	int _;
	cin >> _;
	while(_ --){
		solve();
	}
	
//	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

---

D. Magical Array

---

题目大意

Origional Link

• 对于一个长度为$m$的数组$b$，构造$n$个与$b$相同的的数组$c$
• 对于数组$c_t(1\le t\le n)$现有操作：
  • 操作1：首先将$c_t[i]=c_t[i]-1,c_t[j]=c_t[j]-1$，然后将$c_t[i-1]=c_t[i-1]+1,c_t[j+1]=c_t[j+1]+1$
  • 操作2：首先将$c_t[i]=c_t[i]-1,c_t[j]=c_t[j]-1$，然后将$c_t[i-1]=c_t[i-1]+1,c_t[j+2]=c_t[j+2]+1$
• 选择某一个数$k(1\le k\le n)$，使得$c_k$为特别数组
• 非特别数组$c_i(1\le i\le n,i\ne k)$只能执行操作1若干次
• 特别数组$c_k(1\le k\le n)$只能执行操作2若干次
• 给出这些操作后的数组$c$，找出其中的特别数组的编号$k$，及其执行了多少次操作2

---

思想

• 对于 c t ( 1 ≤ t ≤ n ) （一） 对于 c i − 1 , c i , c j , c j + 1 ，可以得到 c i − 1 × ( i − 1 ) + c i × i + c j × j + c j + 1 × ( j + 1 ) 化简得： i × ( c i − 1 + c i ) + j × ( c j + c j + 1 ) − c i − 1 + c j + 1 ① 对于 c i − 1 , c i , c j , c j + 1 执行操作 1 ： ( c i − 1 + 1 ) × ( i − 1 ) + ( c i − 1 ) × i + ( c j − 1 ) × j + ( c j + 1 + 1 ) × ( j + 1 ) 化简得： i × ( c i − 1 + c i ) + j × ( c j + c j + 1 ) − c i − 1 + c j + 1 ② 可知① = ②，即操作 1 不会改变 c i × i 的和 （二） 对于 c i − 1 , c i , c j , c j + 1 , c j + 2 , 可以得到 c i − 1 × ( i − 1 ) + c i × i + c j × j + c j + 1 × ( j + 1 ) + c j + 2 × ( j + 2 ) 化简得： i × ( c i − 1 + c i ) + j × ( c j + c j + 1 + c j + 2 ) − c i − 1 + c j + 1 + 2 × c j + 2 ③ 对于 c i − 1 , c i , c j , c j + 1 , c j + 2 执行操作 2 ： ( c i − 1 + 1 ) × ( i − 1 ) + ( c i − 1 ) × i + ( c j − 1 ) × j + c j + 1 × ( j + 1 ) + ( c j + 2 + 1 ) × ( j + 2 ) 化简得： i × ( c i − 1 + c i ) + j × ( c j + c j + 1 + c j + 2 ) − c i − 1 + c j + 1 + 2 × c j + 2 + 1 ④ 可知③ = ④ + 1 ，即操作 1 会改变 c i × i 的和，使其加 1 综上可知：对每一个数组 c ，求 S f = ∑ c i × i 与其他数组 c 的 S f 不同的数组即为特别数组，记为 S p 其操作 2 的次数为 S p − S f 对于c_t(1\le t \le n)\\\\
  （一）对于ci−1,ci,cj,cj+1，可以得到ci−1×(i−1)+ci×i+cj×j+cj+1×(j+1)化简得：i×(ci−1+ci)+j×(cj+cj+1)−ci−1+cj+1①对于ci−1,ci,cj,cj+1执行操作1：(ci−1+1)×(i−1)+(ci−1)×i+(cj−1)×j+(cj+1+1)×(j+1)化简得：i×(ci−1+ci)+j×(cj+cj+1)−ci−1+cj+1②可知①=②，即操作1不会改变ci×i的和" role="presentation" style="position: relative;">（一）对于对于ci−1,ci,cj,cj+1，可以得到ci−1×(i−1)+ci×i+cj×j+cj+1×(j+1)化简得：i×(ci−1+ci)+j×(cj+cj+1)−ci−1+cj+1①ci−1,ci,cj,cj+1执行操作1：(ci−1+1)×(i−1)+(ci−1)×i+(cj−1)×j+(cj+1+1)×(j+1)化简得：i×(ci−1+ci)+j×(cj+cj+1)−ci−1+cj+1②可知①=②，即操作1不会改变ci×i的和$$\begin{array}{r}（一）\\ \\ 对于& c_{i-1},c_i,c_j,c_{j+1}，可以得到c_{i-1}\times (i-1)+c_i\times i+c_j\times j+c_{j+1}\times (j+1)\\ \\ & 化简得：i\times (c_{i-1}+c_i)+j\times (c_j+c_{j+1})-c_{i-1}+c_{j+1}①\\ \\ 对于& c_{i-1},c_i,c_j,c_{j+1}执行操作1：\\ \\ & (c_{i-1}+1)\times (i-1)+(c_i-1)\times i+(c_j-1)\times j+(c_{j+1}+1)\times (j+1)\\ \\ & 化简得：i\times (c_{i-1}+c_i)+j\times (c_j+c_{j+1})-c_{i-1}+c_{j+1}②\\ \\ & 可知①=②，即操作1不会改变c_i\times i的和\\ \end{array}$$
  \\\\
  （二）对于ci−1,ci,cj,cj+1,cj+2,可以得到ci−1×(i−1)+ci×i+cj×j+cj+1×(j+1)+cj+2×(j+2)化简得：i×(ci−1+ci)+j×(cj+cj+1+cj+2)−ci−1+cj+1+2×cj+2③对于ci−1,ci,cj,cj+1,cj+2执行操作2：(ci−1+1)×(i−1)+(ci−1)×i+(cj−1)×j+cj+1×(j+1)+(cj+2+1)×(j+2)化简得：i×(ci−1+ci)+j×(cj+cj+1+cj+2)−ci−1+cj+1+2×cj+2+1④可知③=④+1，即操作1会改变ci×i的和，使其加1" role="presentation" style="position: relative;">（二）对于对于ci−1,ci,cj,cj+1,cj+2,可以得到ci−1×(i−1)+ci×i+cj×j+cj+1×(j+1)+cj+2×(j+2)化简得：i×(ci−1+ci)+j×(cj+cj+1+cj+2)−ci−1+cj+1+2×cj+2③ci−1,ci,cj,cj+1,cj+2执行操作2：(ci−1+1)×(i−1)+(ci−1)×i+(cj−1)×j+cj+1×(j+1)+(cj+2+1)×(j+2)化简得：i×(ci−1+ci)+j×(cj+cj+1+cj+2)−ci−1+cj+1+2×cj+2+1④可知③=④+1，即操作1会改变ci×i的和，使其加1$$\begin{array}{r}（二）\\ \\ 对于& c_{i-1},c_i,c_j,c_{j+1},c_{j+2},可以得到c_{i-1}\times (i-1)+c_i\times i+c_j\times j+c_{j+1}\times (j+1)+c_{j+2}\times (j+2)\\ \\ & 化简得：i\times (c_{i-1}+c_i)+j\times (c_j+c_{j+1}+c_{j+2})-c_{i-1}+c_{j+1}+2\times c_{j+2}③\\ \\ 对于& c_{i-1},c_i,c_j,c_{j+1},c_{j+2}执行操作2：\\ \\ & (c_{i-1}+1)\times (i-1)+(c_i-1)\times i+(c_j-1)\times j+c_{j+1}\times (j+1)+(c_{j+2}+1)\times (j+2)\\ \\ & 化简得：i\times (c_{i-1}+c_i)+j\times (c_j+c_{j+1}+c_{j+2})-c_{i-1}+c_{j+1}+2\times c_{j+2}+1④\\ \\ & 可知③=④+1，即操作1会改变c_i\times i的和，使其加1\\ \end{array}$$
  \\\\ 综上可知：对每一个数组c，求S_f = \sum c_i\times i\\\\ 与其他数组c的S_f不同的数组即为特别数组，记为S_p\\\\ 其操作2的次数为S_p-S_f\\\\ 对于ct​(1≤t≤n)（一）对于对于​ci−1​,ci​,cj​,cj+1​，可以得到ci−1​×(i−1)+ci​×i+cj​×j+cj+1​×(j+1)化简得：i×(ci−1​+ci​)+j×(cj​+cj+1​)−ci−1​+cj+1​①ci−1​,ci​,cj​,cj+1​执行操作1：(ci−1​+1)×(i−1)+(ci​−1)×i+(cj​−1)×j+(cj+1​+1)×(j+1)化简得：i×(ci−1​+ci​)+j×(cj​+cj+1​)−ci−1​+cj+1​②可知①=②，即操作1不会改变ci​×i的和​（二）对于对于​ci−1​,ci​,cj​,cj+1​,cj+2​,可以得到ci−1​×(i−1)+ci​×i+cj​×j+cj+1​×(j+1)+cj+2​×(j+2)化简得：i×(ci−1​+ci​)+j×(cj​+cj+1​+cj+2​)−ci−1​+cj+1​+2×cj+2​③ci−1​,ci​,cj​,cj+1​,cj+2​执行操作2：(ci−1​+1)×(i−1)+(ci​−1)×i+(cj​−1)×j+cj+1​×(j+1)+(cj+2​+1)×(j+2)化简得：i×(ci−1​+ci​)+j×(cj​+cj+1​+cj+2​)−ci−1​+cj+1​+2×cj+2​+1④可知③=④+1，即操作1会改变ci​×i的和，使其加1​综上可知：对每一个数组c，求Sf​=∑ci​×i与其他数组c的Sf​不同的数组即为特别数组，记为Sp​其操作2的次数为Sp​−Sf​

---

代码

#include 
using namespace std;

typedef long long LL;

void solve(){
	
	LL n, m;
	
	cin >> n >> m;
	
	LL S1 = -1, S2 = -1;  //S求c_i * i的和
	LL cnt1 = 0, cnt2 = 0;  //cnt记录S的数量
	LL p1, p2;  //存储第一次出现S的编号
	
	for(LL i = 1; i <= n; i ++){
		
		LL sum = 0;
		
		for(LL j = 1; j <= m; j ++){
			LL x;
			cin >> x;
			sum += x * j;
		}
		
		if(S1 == -1){
			S1 = sum;
			p1 = i;
		}
		else if(S1 != -1 && S2 == -1 && S1 != sum){
			S2 = sum;
			p2 = i;
		}
		
		if(S1 == sum) cnt1 ++;
		if(S2 == sum) cnt2 ++;
		
	}
	
	if(cnt1 > cnt2){
		cout << p2 << " " << S2 - S1 << endl;
	} 
	else cout << p1 << " " << S1 - S2 << endl;
	
}

int main(){
	
	LL _;
	cin >> _;
	while(_ --){
		solve();
	}
	
//	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

---

后记

• $A$题一开始没找到规律，找到规律后居然没有把错思路的代码删掉，狠狠的吃WA的铁头娃

• 

• $B$题读懂题意就很简单了，没什么好说的，就是判断公共区间

• $C$题一直在想着怎么维护端点的信息，最后发现根本不需要，只要长度就行了QAQ

• $D$题没时间了，太抽象了也看不懂，补题看题解发现证明的想法实在是妙极了，根本想不到

• 最后还是没能上绿，我是废物

•