Educational Codeforces Round 128 (Rated for Div. 2) A - C && E 题解

传送门

想不到这次居然还能把 E 整出来，怀疑 D E 题是不是反了

上大分

A. Minimums and Maximums

大概就是两个区间之间判断一下交点，其实数据量很小，直接 for 循环跑一边都行

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
using namespace std;
typedef long long ll;
#define pii pair
const ll maxn = 2e5 + 10;
const ll inf = 1e17 + 10;

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int t;
    cin >> t;
    while(t--)
    {
        int a, b, c, d;
        cin >> a >> b >> c >> d;
        if(d > b)
        {
            swap(a, c);
            swap(b, d);
        }
        int ans = 0;
        if(a <= c)
            cout << c << endl;
        else if(a <= d)
            cout << a << endl;
        else
            cout << a + c << endl;
    }

    return 0;
}

B. Robots

因为最终是到左上角，所以可以判断一下所有机器人最多可以往左和往上走几步，然后再在终点的这个区间里搜索有没有机器人

感觉这个题可以改版一下，设置一个终点，然后就四个方向搜索

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
using namespace std;
typedef long long ll;
#define pii pair
const ll maxn = 2e5 + 10;
const ll inf = 1e17 + 10;
string s[maxn];

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int t;
    cin >> t;
    while(t--)
    {
        int n, m;
        cin >> n >> m;
        for(int i=0; i> s[i];
        int l = m - 1, u = n - 1;
        for(int i=0; i

C. Binary String

二分 + 尺取 || 尺取

二分+尺取：时间复杂度为 \(O(nlogn)\)

答案是单调的，所以直接二分枚举答案，然后再 judge 判断的时候，尺取中间剩下的区间

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
using namespace std;
typedef long long ll;
#define pii pair
const ll maxn = 2e5 + 10;
const ll inf = 1e17 + 10;
string s;
int sum = 0;

int query(int x)
{
    int l = 0, r = 0, len = s.length(), cnt0 = 0, cnt1 = 0;
    while(l < len)
    {
        while(r < len && cnt0 <= x)
        {
            if(s[r] == '0') cnt0++;
            else cnt1++;
            r++;
        }
        if(sum - cnt1 <= x) return true;
        if(s[l] == '1') cnt1--;
        else cnt0--;
        l++;
    }
    return max(cnt0, sum - cnt1) <= x;
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int t;
    cin >> t;
    while(t--)
    {
        cin >> s;
        int l = 0, r = s.length();
        sum = 0;
        for(int i=0; i> 1;
            if(query(mid))
                r = mid;
            else
                l = mid + 1;
        }
        cout << l << endl;
    }

    return 0;
}

尺取，时间复杂度为 \(O(n)\)

这里用到一个贪心，只有在剩余区间的代价和删除区间的代价尽可能相等的时候，是最优解

所以就可以根据这个，尺取每个区间 \([l, r]\)，因为对于区间 \([l_{i+1}, r_{i+1}]\)，必然有 \(r_i \leq r_{i+1}\)

#include 
#include 
#include 
#include 
using namespace std;

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int t;
    cin >> t;
    while(t--)
    {
        string s;
        cin >> s;
        int cnt0 = 0, cnt1 = 0, len = s.length();
        for(int i=0; i

E. Moving Chips

线性dp

本来想用连通块求最短的方法，但是我一看到一个奇葩样例，直接否决这个想法，就是样例的第三个，那个倒三角

采取 dp 的方式：

设 \(dp[i][j]\)，表示前 i 列只剩下一个芯片，且该芯片位于 第 i 列 第 j 行，所花费的最小代价

dp 的状态转移（以第 0 行为例）：

  • 如果在第 i 列的第 1 行存在芯片，则：\(dp[i][0] = min(dp[i-1][0], dp[i-1][1]) + 2\)，因为不论是从哪里来，都得消除掉第 1 行的芯片，再加上一次的到第 0 行的代价，所以都是 + 2

  • 如果在第 i 列的第 1 行不存在芯片，则：\(dp[i][0] = min(dp[i-1][0] + 1, dp[i-1][1] + 2)\)，在同一行，直接移动过来，所以代价是 1，在不同行，移动过来代价是 2

对于第 1 行的话，也是一样的策略，所以直接用异或 和 for 循环替代了

这个 dp 的起点是从第一个芯片所在列开始，所以要先搜索到第一个芯片的位置，然后给这一列的 dp 初始化

如果两行都有芯片，则两边初始代价都是 1，如果只有一行有，则那一行的代价为 0，另一行的代价为 1 （需要将芯片移动过来）

同时答案也得不断地更新，理论上答案应该是出现芯片的最后一列的位置

这题和蓝桥杯省赛 B 组那个放积木那题挺像

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
using namespace std;
typedef long long ll;
#define pii pair
const ll maxn = 2e5 + 10;
const ll inf = 1e17 + 10;
string s[2];
int dp[maxn][2];

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int t;
    cin >> t;
    while(t--)
    {
        int n;
        cin >> n;
        cin >> s[0] >> s[1];
        int l = 0;
        while(s[0][l] != '*' && s[1][l] != '*') l++;
        dp[l][0] = dp[l][1] = 0;
        if(s[0][l] == s[1][l]) dp[l][0] = dp[l][1] = 1;
        else if(s[0][l] == '*') dp[l][1] = 1;
        else dp[l][0] = 1;
        int ans = ans = min(dp[l][0], dp[l][1]);
        for(int i=l+1; i
CodeForces

相关

Codeforces Round 628 (Div. 2) E. Ehab's REAL Number Theory Problem

Codeforces Round #610 (Div. 2)

Codeforces Global Round 6.E题

Codeforces Round #611 (Div. 3) E题

CF1545X Codeforces Round #732

codeforces和atcoder的思维题目

Codeforces 1373F - Network Coverage（模拟网络流）

CF1481X Codeforces Round #699

CF1485X Codeforces Round #701

Educational Codeforces Round 7 F. The Sum of the k-th Powers 拉格朗日插值法

Codeforces #731 (div3) E. Air Conditioners

Codeforces Round #675

标签

一品网 冀ICP备14022925号-6