Educational Codeforces Round

Posted by Panda2134's Blog on March 26, 2018

以前打的几场都没有及时补题,这几天补起来

这一场期望过6题,实际过4题。还是4个暴力。主要是C题WA了好几发,细节太多了……

A - Diagonal Walking

直接贪心,正确性显然。

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

int n; char A[200], B[200];

template<typename T>
inline void readint(T& x) {
    T f=1, r=0; char c=getchar();
    while(!isdigit(c)){ if(c=='-')f=-1; c=getchar(); }
    while(isdigit(c)){ r=r*10+c-'0'; c=getchar(); }
    x = f*r;
}

inline char readc() { 
    char c=getchar();
    while(!isalnum(c) && !ispunct(c)) 
        c=getchar();
    return c;
}

inline void readstr(char *str) {
    char c=getchar(); int p=0;
    while(!isalnum(c) && !ispunct(c)) c=getchar();
    while(isalnum(c) || ispunct(c)) {
        str[p++]=c;
        c=getchar();
    }
    str[p]='\0';
}

int main() {
    readint(n);
    readstr(A+1);
    int j = 1;
    for(int i = 1; i <= n;) {
        if(i <= n-1 && A[i] != A[i+1])
            B[j++] = 'D', i+=2;
        else
            B[j++] = A[i++];
    }
    cout << j-1 << endl;
    return 0;
}

B - String Typing

暴力模拟。

值得注意的是很多人把题意看错了,有的认为可以多次复制,有的认为可以复制任意后缀。

我用这个数据:

8
ababcabc

叉了冬令营文艺汇演在后台打碟的rvalue童鞋=.=

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

template<typename T>
inline void readint(T& x) {
    T f=1, r=0; char c=getchar();
    while(!isdigit(c)){ if(c=='-')f=-1; c=getchar(); }
    while(isdigit(c)){ r=r*10+c-'0'; c=getchar(); }
    x = f*r;
}

inline char readc() { 
    char c=getchar();
    while(!isalnum(c) && !ispunct(c)) 
        c=getchar();
    return c;
}

inline void readstr(char *str) {
    char c=getchar(); int p=0;
    while(!isalnum(c) && !ispunct(c)) c=getchar();
    while(isalnum(c) || ispunct(c)) {
        str[p++]=c;
        c=getchar();
    }
    str[p]='\0';
}

int n, ans; char str[200], a[200], b[200];

int main() {
    readint(n);
    readstr(str);
    ans = n;
    for(int i = 1; i <= n/2; i++) {
        memcpy(a, str, sizeof(char) * i);
        a[i] = '\0';
        memcpy(b, str + i, sizeof(char) * i);
        b[i] = '\0';
        if(strcmp(a, b) == 0) ans = min(ans, i + 1 + (n - 2*i));
    }
    cout << ans;
    return 0;
}

C - Matrix Walk

最恶心的模拟题。quailty大爷都被hack了。

quailty大爷:我都得想想怎么出一道这么恶心的细节题

出题人还是很良心地加强了Pretest,我最开始一直WA on test 4。

细节如下:

  1. 不能原地不动!!!
  2. 在找出 $y$ 之后要模拟一遍实际行走的操作,以确定有没有从某一行第一个跳到上一行最后一个,或是从某一行最后一个走到上一行第一个,或是发生了越界什么的。
#include <bits/stdc++.h>
#define FAIL() do{ puts("NO"); exit(0); }while(0)
using namespace std;

template<typename T>
inline void readint(T& x) {
    T f=1, r=0; char c=getchar();
    while(!isdigit(c)){ if(c=='-')f=-1; c=getchar(); }
    while(isdigit(c)){ r=r*10+c-'0'; c=getchar(); }
    x = f*r;
}

const int MAXN = 2e5, MAXNUM = 1e9;

int n, x, y, cx, cy, a[MAXN+10]; 

void Init() {
    readint(n);
    for(int i = 1; i <= n; i++)
        readint(a[i]);
}

int get_i(int idx) {
    return idx % y == 0 ? idx / y: idx / y + 1 ;
}

int get_j(int idx) {
    return idx % y == 0 ? y : idx % y;
}

void Work() {
    for(int i = 1; i <= n-1; i++) {
        if(abs(a[i+1] - a[i]) > 1) {
            if(y == 0) y = abs(a[i+1] - a[i]);
            else {
                if(y != abs(a[i+1] - a[i])) 
                    FAIL();
                else 
                    continue;
            }
        }
    }
    if(y > MAXNUM) FAIL();
    if(y == 0) y = MAXNUM;
    x = MAXNUM;
    cx = get_i(a[1]), cy = get_j(a[1]);
    for(int i = 1; i <= n-1; i++) {
        int dx = get_i(a[i+1]) - get_i(a[i]);
        int dy = get_j(a[i+1]) - get_j(a[i]);
        if(abs(dx) + abs(dy) != 1) FAIL();
        if(cy == 1 && dy == -1) FAIL();
        if(cy == y && dy == 1) FAIL();
        if(cx == 1 && dx == -1) FAIL();
        if(cx == x && dx == 1) FAIL();
        cx += dx; cy += dy;
    }
    
    puts("YES");
    cout << x << ' ' << y;
}

int main() {
    Init(); Work();
    return 0;
}

D - Fight Against Traffic

2次BFS后暴力找要连的边并且更新答案。

qls告诉我,其实可以开到 $n \leq 4 \cdot 10^5$ . 方法是转化为二维数点。

首先BFS,找出每个点 $u$ 到源点的距离 $d_{s, u}$ 和到汇点的距离 $d_{u, t}$ . 然后问题转化为:对于一个点 $u$ 找出同时满足 $d_{s, u} + 1 + d_{v, t} \ge d_{s, t}$ 和 $d_{s, v} + 1 + d_{u, t} \ge d_{s, t}$ 的点 $v$ 的数目。也就是: 以从 $s$ 出发的距离为 $x$ 轴,从 $t$ 出发的距离为 $y$ 轴,就可以二维数点了。扫描线+线段树即可。

评论里面好像还有一种 $O(n+m)$ 的做法?

E - Water Taps

机智的人会想到贪心,只有我在想线性规划转网络流,还有单纯形=。=

最后30min想到贪心,写了出来却死活过不了,真是悲伤。后来发现主要是cin的锅……然而去掉cin之后还是WA on test 8,原因不明。

贪心策略如下:把所有的水龙头都打开,然后每次关掉温度最高的。二分关多少即可。

代码等AC了再贴……


F - Runner’s Problem

递推关系容易发现,但是要应对 $3 ≤ m ≤ 10^{18}$ 的数据范围怎么做?比赛的时候,我一直在想能不能用组合数学的方法 $O(1)$ 地得出答案。其实递推就是个很好的工具啊……有了递推套上矩阵快速幂就可以跑这个数据范围了……

大范围的递推和DP,用矩阵乘法优化!

怎么优化呢?有2个维度啊?没关系,这么做:

当没有障碍的时候: 有障碍的时候,相应地修改转移矩阵即可。

注意到障碍数目 $n \le 10^4​$ ,于是对于每段障碍把转移矩阵乘起来就可以了。对于某一段障碍用矩阵快速幂算。复杂度为 $O(n \lg m)​$ ,可以接受。

注意:离散化后如果需要用到差分,就一定要把 $l, r+1$ 放进离散化数组!!!!

保险的做法是把 $l, r$ 周围的全部丢进去,不过数组就要开够,建议开8倍

代码:

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

typedef long long int64;
const int MAXN = 1e4, WIDTH = 3, MOD = int(1e9+7);

struct Matrix {
    int A[WIDTH][WIDTH];
    Matrix() {
        memset(A, 0, sizeof(int) * WIDTH * WIDTH);
    }
    int* operator[](const int idx) {
        assert(idx >= 0 && idx < WIDTH);
        return A[idx];
    }
    const int* operator[](const int idx) const {
        assert(idx >= 0 && idx < WIDTH);
        return (const int*)A[idx];
    }
    static Matrix unit() {
        Matrix ret;
        for(int i = 0; i < WIDTH; i++)
            ret[i][i] = 1;
        return ret;
    }
    Matrix operator*(const Matrix &rhs) const {
        Matrix ret;
        for(int i = 0; i < WIDTH; i++)
            for(int j = 0; j < WIDTH; j++)
                for(int k = 0; k < WIDTH; k++)
                    ret[i][j] = (ret[i][j] + (int64(A[i][k])%MOD) * (rhs[k][j]%MOD) % MOD) % MOD;
        return ret;
    }
    Matrix operator=(const Matrix &rhs) {
        memcpy(A, rhs.A, sizeof(int) * WIDTH * WIDTH);
        return *this;
    }
    friend ostream& operator<<(ostream &out, const Matrix &rhs) {
        for(int i = 0; i < WIDTH; i++) {
            for(int j = 0; j < WIDTH; j++)
                out << rhs[i][j] << ' ';
            out << '\n';
        }
        return out;
    }
};

struct Interval {
    int a; int64 l, r;
};

int64 n, m, nums[(MAXN+10)<<4]; Interval I[(MAXN+10)<<4];
int M[5][(MAXN+10)<<4];

Matrix fastpow(Matrix a, int64 x) {
    Matrix ret = Matrix::unit();
    while(x > 0) {
        if(x & 1) ret = ret * a;
        x >>= 1; a = a * a;
    }
    return ret;
}

template<typename T>
inline void readint(T &x) {
    T f=1, r=0; char c=getchar();
    while(!isdigit(c)) { if(c=='-')f=-1; c=getchar(); }
    while(isdigit(c)) { r=r*10+c-'0'; c=getchar(); }
    x = f*r;
}

void init() {
    readint(n); readint(m);
    for(int i = 1; i <= n; i++) {
        readint(I[i].a); I[i].a--; // Line index start from 0, correspond with the matrix
        readint(I[i].l); readint(I[i].r);
        nums[++nums[0]] = I[i].l, nums[++nums[0]] = I[i].r;
        nums[++nums[0]] = I[i].l+1, nums[++nums[0]] = I[i].r+1;
        if(I[i].l > 1) nums[++nums[0]] = I[i].l-1;
        if(I[i].r > 1) nums[++nums[0]] = I[i].r-1;
    }
    nums[++nums[0]] = 1; nums[++nums[0]] = m;
    sort(nums + 1, nums + nums[0] + 1);
    nums[0] = unique(nums + 1, nums + nums[0] + 1) - &nums[1];
    for(int i = 1; i <= n; i++) {
        I[i].l = lower_bound(nums + 1, nums + nums[0] + 1, I[i].l) - nums;
        I[i].r = lower_bound(nums + 1, nums + nums[0] + 1, I[i].r) - nums;
        M[I[i].a][I[i].l]++, M[I[i].a][I[i].r+1]--;
    }
    for(int i = 1; i <= nums[0]; i++) {
        M[0][i] += M[0][i-1], M[1][i] += M[1][i-1], M[2][i] += M[2][i-1];
    }
}

void work() {
    Matrix V, Trans, A;
    V[0][1] = 1;
    for(int i = 0; i < 3; i++)
        for(int j = 0; j < 3; j++)
            Trans[i][j] = 1;
    Trans[0][2] = Trans[2][0] = 0;
    for(int i = 1; i <= nums[0]; i++) {
        A = Trans;
        for(int k = 0; k < 3; k++) 
            if(M[k][i]) {
                V[0][k] = 0;
                for(int j = 0; j < 3; j++)
                    A[k][j] = 0;
            }
        if(i == nums[0]) break;
        A = fastpow(A, nums[i+1] - nums[i]);
        V = V * A;
    }
    cout << V[0][1];
}

int main() {
    init(); work();
    return 0;
}

G - Castle Defense

坑着