Educational Codeforces Round 106 (Rated for Div. 2)

Educational Codeforces Round 106 (Rated for Div. 2)

A题 Domino on Windowsill

原题链接

题意

给定一个\(2 \times n\) 的网格, 第一行前\(x\)个和第二行前\(y\)个格子为白色, 其余格子为黑色. 现在给定\(a\)个\(2 \times 1\)的白块, \(b\)个\(2 \times 1\)的黑块, 问能否将分别将白块和黑块全部放入对应颜色的区域, 且不能相互重叠.

思路

A题比较水(A题不水, 还怎么做), 因为是给定第一行前\(x\)个和第二行前\(y\)个格子为白色,则竖着最多填\(min(x, y)\)个白块, 横着最多填\((x - y) / 2\)(下取整)个白块, 黑块同理,最后检查输入是否合法就行.

#include 
#include 
#include 
#include 

using namespace std;

void solve()
{
    int n, k1, k2;
    int k3, k4;
    int w, b;
    cin >> n >> k1 >> k2;
    k3 = n - k1;
    k4 = n - k2;
    cin >> w >> b;
    if (k2 > k1)
        swap(k1, k2);
    if (k4 > k3)
        swap(k3, k4);
    int sumw = k2 + (k1 - k2) / 2;
    int sumb = k4 + (k3 - k4) / 2;
    //cout << sumw << ' ' << sumb << endl;
    if (sumw >= w && sumb >= b)
        puts("YES");
    else
        puts("NO");
    return;
}

int main()
{
    int t;
    cin >> t;
    while (t -- )
        solve();
    return 0;
}

B题 Binary Removals

原题链接

题意

给定一个\(01\)序列, 从中删去一些\(0\)和\(1\), 使得这个序列为有序递增序列, 要求删去的数字的下标不能相邻.

思路

这题把我搞蒙了.后来发现道题有点DP的意思.
首先,当序列中出现\(00\)或者是\(11\)这样的子序时,我们可能是没办法处理的,即结果为\(NO\)
定义两个数组:

  1. \(a\): \(a_{i}\)表示从\(1 到 i\)是否出现\(11\)序列, 出现为\(1\),否则为\(0\)
  2. \(b\): \(b_{i}\)表示从\(i 到 n\)是否出现\(00\)序列, 出现为\(1\),否则为\(0\)

若存在\(a_{i} = b_{i} = 1\), 说明\(1到i\)存在\(11\)序列, 同时\(i到n\)存在\(00\)序列, 这样是无法满足要求的。
那么我们先从前向后递推出\(a\), 再从后向前递推出\(b\), 最后检查是否存在\(a_{i} = b_{i} = 1\), 若存在,不合法。

#include 
#include 
#include 
#include 

using namespace std;

int a[110];
int b[110];
string s;



void solve()
{
    cin >> s;
    memset(a, 0, sizeof a);
    memset(b, 0, sizeof b);
    for (int i = 1; i < s.size(); i ++ ){
        if (a[i - 1])
            a[i] = 1;

        if (s[i] == '1' && s[i - 1] == '1')
            a[i] = 1;
    }
    for (int i = s.size() - 2; i >= 0; i -- ){
        if (b[i + 1])
            b[i] = 1;

        if (s[i + 1] == '0' && s[i] == '0')
            b[i] = 1;
    }
    for (int i = 0; i < s.size(); i ++ )
        if (a[i] && b[i]){
            puts("NO");
            return;
        }

    puts("YES");
    return;
}

int main()
{
    int t;
    cin >> t;
    while (t -- )
        solve();
    return 0;
}

C题 Minimum Grid Path

原题链接

题意

给定一个 \(n \times n\) 的网格, 要求最多走 \(n\) 步(只能向上或向右, 但每次走的格子数不限, 且必须交替进行), 同时给定选择走\(i\)步时走每一格的代价 \(w_{i}\) ,问从 \((0,0)\) 到 \((n,n)\) 的最小代价。

思路

暴力做肯定会超时的, 题目有一个很好的性质:向上和向右必须交替进行, 而且因为是个正方形, 第一步向上还是向下结果都是一样的。
因此我们可以枚举从起点到终点所需要的步数(从 \(1\) 到 \(n\) ):

  1. 首先, 我们规定奇数向右, 偶数向下.
  2. 当枚举到 \(i\) 时, 表示前\(i\)步我们每个选择一格, 剩下的两个方向的格子都由\(i\)之前的最小值来走。
  3. 注意动态维护两个方向的最小值和剩余格子。
#include 
#include 
#include 
#include 

using namespace std;
typedef long long LL;
const int N = 1e5 + 10;

LL a[N];

void solve()
{
    LL n;
    cin >> n;
    LL ans;
    LL minup;
    LL mindown;
    LL up = n;
    LL down = n;
    for (int i = 1; i <= n; i ++ )
        cin >> a[i];
    LL sum = a[1] + a[2];
    down = n - 1;
    up = n - 1;
    ans = a[1] * n + a[2] * n;
    minup = a[1];
    mindown = a[2];
    for (int i = 3; i <= n; i ++ ){
        sum += a[i];
        if (i % 2){
            up--;
            minup = min(minup, a[i]);
        }else{
            down--;
            mindown = min(mindown, a[i]);
        }
        //cout << up << " " << down << " " << minup << " " << mindown << endl;
        ans = min(ans, sum + mindown * down + minup * up);
    }
    cout << ans << endl;
    return ;
}

int main()
{
    int t;
    cin >> t;
    while (t -- )
        solve();
    return 0;
}
codeforces练习赛

相关

标签