C2020 2020.12.12模拟赛

信息学——模拟赛

1. 考试情况

当天去打THUPC2021初赛了，没打模拟赛，赛后补的题。

T1 Lights

$1^o$ 分析

一眼显然是个搜索，考虑对于当前每个点将对应点的灯打个标记，然后往四方拓展看一眼标记就好了。

但是发现一个问题。

比如样例：

3 6
1 1 1 2
2 1 2 2
1 1 1 3
2 3 3 1
1 3 1 2
1 3 2 1

我们会发现程序并不会将$(2,1)$这个点加入队列，为什么？

我们发现$(2,1)$应该由$(1,1)$拓展而来，但是$(2,1)$这个点的灯是用$(1,3)$ 打开的，而$(1,3)$在$(1,1)$之后被搜到。

所以存在的问题就是有可能后面会有开灯的点漏加入队列中。

那么很简单，当我们开灯的时候，判断一下要开的那盏灯的四方有没有被走到，就能将这个点加入到队列中了。

可以发现只有这两种加入队列的方式（至于证明……大致可以想成所有点都可以被分在这两类中）。

//The code is from dawn_sdy
#include<bits/stdc++.h>
#define pi pair<int, int> 
#define mp make_pair
#define pb push_back
using namespace std;
inline int read() {
    int x = 0;
    char c = getchar();
    bool f = 0;
    while(!isdigit(c)) f |= (c == '-'), c = getchar();
    while(isdigit(c)) x = (x * 10) + (c ^ 48), c = getchar();
    return f ? -x : x; 
}
const int maxn = 105;
int n, m;
vector < pi > vec[maxn][maxn];
namespace Work {
    queue < pi > q; pi u, v;
    int vst[maxn][maxn], light[maxn][maxn], go[4][2] = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}}, ans;
    #define fi first
    #define se second
    inline void Change1() {
        int sz = vec[u.fi][u.se].size();
        for(register int i = 0; i < sz; ++i) {
            v = vec[u.fi][u.se][i];
            if(vst[v.fi][v.se] || light[v.fi][v.se]) continue;
            light[v.fi][v.se] = 1, ans++;
            for(register int j = 0; j < 4; ++j) {
                int nx = v.fi + go[j][0], ny = v.se + go[j][1];
                if(nx < 0 || ny < 0 || nx > n || ny > n || !vst[nx][ny]) continue;
                q.push(v), vst[v.fi][v.se] = 1; break;
            }
        }
    }
    inline void Change2() {
        for(register int i = 0; i < 4; ++i) {
            int nx = u.fi + go[i][0], ny = u.se + go[i][1];
            if(nx < 0 || ny < 0 || nx > n || ny > n || vst[nx][ny] || !light[nx][ny]) continue;
            q.push(mp(nx, ny)), vst[nx][ny] = 1;
        }
    }
    inline void Search() {
        q.push(mp(1, 1)), vst[1][1] = light[1][1] = 1, ans = 1;
        while(!q.empty()) {
            u = q.front(); q.pop();
            Change1(), Change2();
        }
        printf("%d", ans);
    }
    #undef fi
    #undef se
}
int main() {
    n = read(), m = read();
    for(register int i = 1; i <= m; ++i) {
        int sx = read(), sy = read(), ex = read(), ey = read();
        vec[sx][sy].pb(mp(ex, ey));
    }
    Work::Search();
    return 0;
}

T2 Card

$1^o$ 分析

一道田忌赛马模型题，很容易想到一个贪心策略：

如果当前牌能够被赢下，就用最小能赢下的牌赢下
如果当前牌不能被赢下，就用所有中最小的牌对掉

由于要动态删除，直接用$set$维护即可。

//The code is from dawn_sdy
#include<bits/stdc++.h>
#define It set<int>::iterator
using namespace std;
inline int read() {
    int x = 0;
    char c = getchar();
    bool f = 0;
    while(!isdigit(c)) f |= (c == '-'), c = getchar();
    while(isdigit(c)) x = (x * 10) + (c ^ 48), c = getchar();
    return f ? -x : x;
}
const int maxn = 5 * 1e4 + 5;
int n;
int a[maxn], b[maxn << 1], ans;
set <int> s; It it;
int main() {
    n = read();
    for(register int i = 1; i <= n; ++i) a[i] = read(), b[a[i]] = 1;
    for(register int i = 1; i <= n << 1; ++i)
        if(!b[i]) s.insert(i);
    for(register int i = 1; i <= n; ++i) {
        it = s.end(); it--;
        if(*it < a[i]) {
            s.erase(s.begin()); continue;
        }
        it = s.lower_bound(a[i]), s.erase(it), ans++;
    }
    printf("%d", ans);
    return 0;
}

T3 Counting

$1^o$ 分析

由于只有三种颜色，直接前缀和求即可。

//The code is from dawn_sdy
#include<bits/stdc++.h>
using namespace std;
inline int read() {
    int x = 0;
    char c = getchar();
    bool f = 0;
    while(!isdigit(c)) f |= (c == '-'), c = getchar();
    while(isdigit(c)) x = (x * 10) + (c ^ 48), c = getchar();
    return f ? -x : x;
}
const int maxn = 1e5 + 5;
int n, q;
int sum[maxn][5];
inline int calc(int l, int r, int k) { return sum[r][k] - sum[l - 1][k]; }
int main() {
    n = read(), q = read();
    for(register int i = 1; i <= n; ++i) {
        int x = read();
        for(register int j = 1; j <= 3; ++j) sum[i][j] = sum[i - 1][j] + (x == j ? 1 : 0);
    }
    for(register int i = 1; i <= q; ++i) {
        int l = read(), r = read();
        printf("%d %d %d\n", calc(l, r, 1), calc(l, r, 2), calc(l, r, 3));
    }
    return 0;
}