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

A

题目

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

题解

思路

知识点:思维。

如果 \([l1,r1],[l2,r2]\) 有交集可以是相同的数字,那么取 \(min(l1,l2)\) ;如果 \([l1,r1],[l2,r2]\) 没有交集,说明最大值最小值不能是相同的数字,那么取 \(l1+l2\) 。

直接判断端点可能太多,可以利用 \(swap\) 考虑固定 \(l1<l2\) ,就剩下两种情况。

时间复杂度 \(O(1)\)

空间复杂度 \(O(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--){
        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;
}

B

题目

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

题解

思路

知识点:思维。

找到机器人中最靠左上的行列坐标(不一定要在同一个机器人身上),如此坐标表示了机器人阵列移动多少次就会出现爆炸。

如果这组行列坐标的位置没有机器人,说明移动到爆炸极限之前都没有机器人会到达左上角,因此不可行,否则可行。

时间复杂度 \(O(nm)\)

空间复杂度 \(O(mn)\)

代码

#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;
}

C

题目

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

题解

思路

方法1

知识点:尺取法。

注意到 \(0,1\) 变化具有单调性,左端点变大一定导致 \(0\) 在子串的数量 \(A\) 变少且移除 \(1\) 的数量 \(B\) 变多,而右端点变大则相反。那么对于一个固定了左端点的区间,可以将右端点变大,使 \(A,B\) 分别从较小和较大的值向某个极值靠拢,直到 \(A = B\) 即达到当前左端点的区间的最小 \(cost\) 。此时可以将左端点加一,此举一定会让 \(A \neq B\) ,于是可以继续移动右端点到达新的左端点的最优区间。在上面思考的基础下,枚举左端点即可以,移动右端点到达最优,取每次最小 \(cost\) 的最小值即可。

时间复杂度 \(O(n)\)

空间复杂度 \(O(n)\)

方法2

知识点:数学,前缀和。

设子串留有 \(0\) 的数量为 \(A\) ,留有 \(1\) 的数量为 \(B\) ,\(1\) 的总数为 \(sum\) ,则有 \(cost = max(A,sum – B)\)。

再设子串长度为 \(len\) ,则有 \(cost = max(A+B,sum) – B = max(len,sum) – B\)

考虑 \(len \leq sum\) ,则有 \(cost = sum – B\),显然如果 \(len\) 增加,那么 \(B\) 是不减的,因此我们考虑取 \(len = sum\)。

考虑 \(len \geq sum\) ,则有 \(cost = len – B = A\) ,显然如果 \(len\) 减少,那么 \(A\) 是不增的,因此我们考虑取 \(len = sum\)。

综上,最优的子串长度一定为 \(sum\) ,因此枚举左端点,取长度为 \(sum\) 的子串计算每个 \(cost = A\) 取最小值即可。而 \(A\) 可通过前缀和预处理。

时间复杂度 \(O(n)\)

空间复杂度 \(O(n)\)

方法1可是基础捏,一定要会哟qwq。

代码

方法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;
}

E

题目

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

题解

思路

知识点:状压DP。

假设存在一个 \(*\) 的最优最后位置,那么所有 \(*\) 移动到这个位置的路径长度就是最小操作数,同时在这些路径上任取一点作为 \(*\) 的最后位置是不改变路径长度的,因此这些位置也是最优的最后位置,所以可以确定最后一列 \(*\) 的位置也是一个最优位置且是最右的最优位置,所以一开始可以把地图最后一列 \(*\) 之后列都清除,并修改 \(n\) 为最后一列。接下来考虑如何得到所有 \(*\) 到最后一列 \(*\) 的最小路径长度。

设 \(dp[i][j]\) 表示第 \(i\) 列且 \(*\) 的状态为 \(j\) 的最小操作数,\(j = 0/1/2/3\) 分别代表没有 \(*\) ,仅第一行有 \(*\) ,仅第二行有 \(*\) ,两行都有 \(*\) (对应二进制位)。

先考虑将第 \(i-1\) 列状态水平转移到第 \(i\) 列,假设第 \(i\) 列的 \(*\) 状态是 \(state\) ,第 \(i-1\) 列的 \(*\) 状态是 \(j\) ,那么有水平状态转移方程:

其中 \(j|state\) 指将第 \(i-1\) 列和第 \(i\) 列的 \(*\) 水平合并的状态, \((j\&1) + ((j>>1)\&1)\) 指合并状态需要的操作次数,即 \(j\) 二进制位 \(1\) 的数量。

再考虑将第 \(i\) 列状态垂直转移,\(j = 3\) 的情况可以合并成 \(j = 1/2\) 的情况,\(j = 1/2\) 的情况可以垂直移动变为 \(j = 2/1\) 的情况,\(j = 0\) 的情况在同列没有下一种可能情况,因此最后有两个状态可以被转移 \(j = 1/2\) :

最后递推到最后一个 \(*\) 出现的列 \(n\) ,答案即为 \(min(dp[n][1],dp[n][2])\) 。

注意开始时要把 \([1,n]\) 的所有状态设为无穷大(1e9就行),设 \(dp[0][0 \cdots 3] = 0\) 。

时间复杂度 \(O(n)\)

空间复杂度 \(O(n)\)

代码

#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;
}
————————

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

A

subject

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

Problem solution

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;
}

B

subject

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

Problem solution

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;
}

C

subject

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

Problem solution

thinking

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

code

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;
}

E

subject

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

Problem solution

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;
}