# Educational Codeforces Round 128 (Rated for Div. 2) A-C+E(Educational Codeforces Round 128 (Rated for Div. 2) A-C+E)-其他

## Educational Codeforces Round 128 (Rated for Div. 2) A-C+E(Educational Codeforces Round 128 (Rated for Div. 2) A-C+E)

### 题目

https://codeforces.com/contest/1680/problem/A

### 代码

#include <bits/stdc++.h>
using namespace std;

int main(){
std::ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
int t;
cin>>t;
while(t--){
int l1,r1,l2,r2;
cin>>l1>>r1>>l2>>r2;
if(l2<l1){
swap(l1,l2);
swap(r1,r2);
}
if(r1>=l2) cout<<l2<<'\n';
else cout<<l1+l2<<'\n';
}
return 0;
}


### 题目

https://codeforces.com/contest/1680/problem/B

### 代码

#include <bits/stdc++.h>
using namespace std;

bool bot[7][7];

int main(){
std::ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
int t;
cin>>t;
while(t--){
int n,m;
cin>>n>>m;
int minx = 10,miny = 10;
for(int i = 0;i<n;i++){
for(int j = 0;j<m;j++){
char tmp;
cin>>tmp;
if(tmp == 'R'){
bot[i][j] = 1;
minx = min(minx,i);
miny = min(miny,j);
}
else bot[i][j] = 0;
}
}
if(bot[mini][minj]) cout<<"YES"<<'\n';
else cout<<"NO"<<'\n';
}
return 0;
}


### 题目

https://codeforces.com/contest/1680/problem/C

### 方法1

///尺取法
#include <bits/stdc++.h>
using namespace std;

int main(){
std::ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
int t;
cin>>t;
while(t--){
string s;
cin>>s;
int n = s.length();
int cnt0 = 0,cnt1 = 0;
for(int i = 0;i<n;i++){
if(s[i] == '1') cnt1++;
}
int ans = cnt1;
int l = 0,r = 0;
while(l<n){
while(r<n && cnt0!=cnt1){
if(s[r] == '0') cnt0++;
else if(s[r] == '1') cnt1--;
r++;
}
ans = min(ans,max(cnt0,cnt1));///最后r<n,cnt0和cnt1就不一定平衡了
if(s[l] == '0') cnt0--;
else if(s[l] == '1') cnt1++;
l++;
}
cout<<ans<<'\n';
}
return 0;
}


### 方法2

///结论，取长度为len，费用即字串0的个数
#include <bits/stdc++.h>
using namespace std;

int pre[200007];

int main(){
std::ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
int t;
cin>>t;
while(t--){
string s;
cin>>s;
int n = s.length();
s = "?" + s;
for(int i = 1;i<=n;i++) pre[i] = pre[i-1] + (s[i] == '0');
int cnt1 = count(s.begin(),s.end(),'1');
int ans = cnt1;
for(int i = cnt1;i<=n;i++) ans = min(ans,pre[i] - pre[i-cnt1]);
cout<<ans<<'\n';
}
return 0;
}


### 题目

https://codeforces.com/problemset/problem/1680/E

### 代码

#include <bits/stdc++.h>

using namespace std;

int dp[200007][4+7];
int main(){
std::ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
int t;
cin>>t;
while(t--){
int n;
cin>>n;
string s1,s2;
cin>>s1>>s2;
s1 = "?" + s1;
s2 = "?" + s2;
while(s1.back() == '.' && s2.back() == '.') n--,s1.pop_back(),s2.pop_back();///找到最后一列有*的
for(int i = 1;i<=n;i++) for(int j = 0;j<4;j++) dp[i][j] = 1e9;///初始化都设为无穷大
for(int i = 1;i<=n;i++){
int state = 0;
if(s1[i] == '*') state |= 1;
if(s2[i] == '*') state |= 2;
for(int j = 0;j<4;j++){///水平移动的转移
dp[i][j | state] = min(dp[i][j | state],dp[i-1][j] + (j&1) + ((j>>1)&1));
}
///垂直移动的转移
dp[i][1] = min({dp[i][1],dp[i][2] + 1,dp[i][3] + 1});
dp[i][2] = min({dp[i][2],dp[i][1] + 1,dp[i][3] + 1});
}
cout<<min(dp[n][1],dp[n][2])<<'\n';
}
return 0;
}

————————

### subject

https://codeforces.com/contest/1680/problem/A

### thinking

< strong > knowledge points: thinking

If the intersection of \ ([L1, R1], [L2, R2] \) can be the same number, take \ (min (L1, L2) \); If \ ([L1, R1], [L2, R2] \) has no intersection, it means that the maximum and minimum values cannot be the same number, then take \ (L1 + L2 \).

There may be too many endpoints to judge directly. You can use \ (swap \) to consider fixed \ (L1 & lt; L2 \), leaving two cases.

Time complexity \ (O (1) \)

Space complexity \ (O (1) \)

### code

#include <bits/stdc++.h>
using namespace std;

int main(){
std::ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
int t;
cin>>t;
while(t--){
int l1,r1,l2,r2;
cin>>l1>>r1>>l2>>r2;
if(l2<l1){
swap(l1,l2);
swap(r1,r2);
}
if(r1>=l2) cout<<l2<<'\n';
else cout<<l1+l2<<'\n';
}
return 0;
}


### subject

https://codeforces.com/contest/1680/problem/B

### thinking

< strong > knowledge points: thinking

Find the row and column coordinates on the top left of the robot (not necessarily on the same robot), so the coordinates represent how many times the robot array will explode.

If there is no robot at the position of this group of row and column coordinates, it means that no robot will reach the upper left corner before moving to the explosion limit, so it is not feasible, otherwise it is feasible.

Time complexity \ (O (nm) \)

Space complexity \ (O (MN) \)

### code

#include <bits/stdc++.h>
using namespace std;

bool bot[7][7];

int main(){
std::ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
int t;
cin>>t;
while(t--){
int n,m;
cin>>n>>m;
int minx = 10,miny = 10;
for(int i = 0;i<n;i++){
for(int j = 0;j<m;j++){
char tmp;
cin>>tmp;
if(tmp == 'R'){
bot[i][j] = 1;
minx = min(minx,i);
miny = min(miny,j);
}
else bot[i][j] = 0;
}
}
if(bot[mini][minj]) cout<<"YES"<<'\n';
else cout<<"NO"<<'\n';
}
return 0;
}


### subject

https://codeforces.com/contest/1680/problem/C

### Method 1

< strong > knowledge points: ruler method

Note that the change of \ (0,1 \) is monotonous. The larger the left end point will inevitably lead to the smaller number of \ (0 \) in the substring \ (a \) and the more number of \ (1 \) removed \ (B \), while the larger the right end point is the opposite. Then, for an interval with a fixed left endpoint, the right endpoint can be enlarged to make \ (a, B \) approach a certain extreme value from the smaller and larger values respectively until \ (a = B \) reaches the minimum \ (cost \) of the interval with the current left endpoint. At this time, you can add one to the left endpoint, which will make \ (a \ NEQ B \), so you can continue to move the right endpoint to the optimal interval of the new left endpoint. Based on the above thinking, you can enumerate the left endpoint, move the right endpoint to reach the optimal, and take the minimum value of the minimum \ (cost \) each time.

Time complexity \ (O (n) \)

Space complexity \ (O (n) \)

### Method 2

< strong > knowledge points: mathematics, prefix and

If the number of substrings with \ (0 \) is \ (a \), the number of substrings with \ (1 \) is \ (B \), and the total number of \ (1 \) is \ (sum \), then there is \ (cost = max (a, sum – b) \).

If the length of the substring is \ (len \), there will be \ (cost = max (a + B, sum) – B = max (len, sum) – B \)

Considering \ (len \ Leq sum \), there is \ (cost = sum – B \). Obviously, if \ (len \) increases, then \ (B \) does not decrease, so we consider taking \ (len = sum \).

Considering \ (len \ GEQ sum \), there is \ (cost = len – B = a \). Obviously, if \ (len \) decreases, then \ (a \) does not increase, so we consider taking \ (len = sum \).

To sum up, the optimal substring length must be \ (sum \), so enumerate the left endpoint, take the substring with length \ (sum \), and calculate the minimum value of each \ (cost = a \). And \ (a \) can be prefixed and preprocessed.

Time complexity \ (O (n) \)

Space complexity \ (O (n) \)

< strong > method 1 is a basic pinch. You must be able to do it qwq

### Method 1

///尺取法
#include <bits/stdc++.h>
using namespace std;

int main(){
std::ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
int t;
cin>>t;
while(t--){
string s;
cin>>s;
int n = s.length();
int cnt0 = 0,cnt1 = 0;
for(int i = 0;i<n;i++){
if(s[i] == '1') cnt1++;
}
int ans = cnt1;
int l = 0,r = 0;
while(l<n){
while(r<n && cnt0!=cnt1){
if(s[r] == '0') cnt0++;
else if(s[r] == '1') cnt1--;
r++;
}
ans = min(ans,max(cnt0,cnt1));///最后r<n,cnt0和cnt1就不一定平衡了
if(s[l] == '0') cnt0--;
else if(s[l] == '1') cnt1++;
l++;
}
cout<<ans<<'\n';
}
return 0;
}


### Method 2

///结论，取长度为len，费用即字串0的个数
#include <bits/stdc++.h>
using namespace std;

int pre[200007];

int main(){
std::ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
int t;
cin>>t;
while(t--){
string s;
cin>>s;
int n = s.length();
s = "?" + s;
for(int i = 1;i<=n;i++) pre[i] = pre[i-1] + (s[i] == '0');
int cnt1 = count(s.begin(),s.end(),'1');
int ans = cnt1;
for(int i = cnt1;i<=n;i++) ans = min(ans,pre[i] - pre[i-cnt1]);
cout<<ans<<'\n';
}
return 0;
}


### subject

https://codeforces.com/problemset/problem/1680/E

### thinking

< strong > knowledge point: shape pressure DP

Assuming that there is an optimal last position of \ (* \), the path length of all \ (* \) moving to this position is the minimum operand. At the same time, taking any point on these paths as the last position of \ (* \) does not change the path length, so these positions are also the optimal last positions. Therefore, it can be determined that the position of the last column \ (* \) is also an optimal position and the rightmost optimal position, Therefore, at the beginning, you can clear the columns after the last column \ (* \) of the map and modify \ (n \) to the last column. Next, consider how to get the minimum path length from all \ (* \) to the last column \ (* \).

Let \ (DP [i] [J] \) represent the minimum operand of column \ (I \) and the status of \ (* \) is \ (J \), \ (J = 0 / 1 / 2 / 3 \) represent no \ (* \), only the first row has \ (* \), only the second row has \ (* \), and both rows have \ (* \) (corresponding to binary bits).

First consider transferring the state of column \ (i-1 \) horizontally to column \ (I \). Assuming that the \ (* \) state of column \ (I \) is \ (state \) and the \ (* \) state of column \ (i-1 \) is \ (J \), then there is a horizontal state transition equation:

Where \ (j|state \) refers to the state in which \ (* \) of column \ (i-1 \) and column \ (I \) are merged horizontally, \ ((J \ & amp; 1) + ((J & gt; & gt; 1) \ & amp; 1) \) refers to the number of operations required for the merge state, that is, the number of \ (J \) binary bits \ (1 \).

Consider the vertical transfer of the state of column \ (I \). The case of \ (J = 3 \) can be merged into the case of \ (J = 1 / 2 \). The case of \ (J = 1 / 2 \) can be moved vertically to the case of \ (J = 2 / 1 \). There is no next possible case of \ (J = 0 \) in the same column, so the last two states can be transferred \ (J = 1 / 2 \):

Finally, the column \ (n \) that appears in the last \ (* \) is recursed, and the answer is \ (min (DP [n] [1], DP [n] [2]) \).

Note that at the beginning, set all States of \ ([1, n] \) to infinity (1e9 is OK), and set \ (DP [0] [0 \ cdots 3] = 0 \).

Time complexity \ (O (n) \)

Space complexity \ (O (n) \)

### code

#include <bits/stdc++.h>

using namespace std;

int dp[200007][4+7];
int main(){
std::ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
int t;
cin>>t;
while(t--){
int n;
cin>>n;
string s1,s2;
cin>>s1>>s2;
s1 = "?" + s1;
s2 = "?" + s2;
while(s1.back() == '.' && s2.back() == '.') n--,s1.pop_back(),s2.pop_back();///找到最后一列有*的
for(int i = 1;i<=n;i++) for(int j = 0;j<4;j++) dp[i][j] = 1e9;///初始化都设为无穷大
for(int i = 1;i<=n;i++){
int state = 0;
if(s1[i] == '*') state |= 1;
if(s2[i] == '*') state |= 2;
for(int j = 0;j<4;j++){///水平移动的转移
dp[i][j | state] = min(dp[i][j | state],dp[i-1][j] + (j&1) + ((j>>1)&1));
}
///垂直移动的转移
dp[i][1] = min({dp[i][1],dp[i][2] + 1,dp[i][3] + 1});
dp[i][2] = min({dp[i][2],dp[i][1] + 1,dp[i][3] + 1});
}
cout<<min(dp[n][1],dp[n][2])<<'\n';
}
return 0;
}