20220307 - 模拟赛 | Final Fantasy = xixike = 人间忽晚，山河已秋

贪心 + 模拟，区间 dp（记搜），AC 自动机

骗分大赛，给我整不会了/lh

# A. 我永远喜欢月

考场上瞎特判了几种无解的情况，成功拿到 70pts， $sleeping\_crawlers$ 直接骗到 97pts（后面 3 分是 $\text{hack}$ 数据）orz

下面说正解。

我们发现从 $\text{A}$ 推到 $\text{B}$ 的限制条件非常强，不是很好处理，所以考虑反过来推，也就是判断从 $\text{B}$ 能不能推到 $\text{A}$ 。

反过来考虑的话，一次操作就变成了从 $\text{B}$ 中找一个 1，把它变成 0，然后同行同列的数想变成多少都行。

$\text{B}$ 中有一些行列是不能操作的，即当某一行/列出现了两个及两个以上的 1 时，这些 1 所在的行，列上的数都不能进行操作。这个应该比较好理解吧，如果你操作了，就会有 1 变成 0，然后你就变不回来了。

我们称这些 1 为限制点，称所有限制点所在行列的集合为限制区间 。

接下来就要判断是否有解了。

当 $\text{A}$ 和 $\text{B}$ 完全相同时，直接输出 Yes。
限制点的值是不可能变的，所以判一下 $\text{A}$ 和 $\text{B}$ 中限制点的值是否相同，如果有相同的直接输出 No。
我们想要从 $\text{B}$ 转化到 $\text{A}$ 必须有一个可行点（如果你一步都动不了还怎么转化），所以 $\text{A}$ 中必须有一个不在限制区间的 0， $\text{B}$ 中必须有一个不在限制区间的 1，如果有一个没有，那么输出 No。

最后输出 Yes。

下面是巨无霸丑陋代码（清晰点的可以去看 zxgg 的代码 qwq）

#include <bits/stdc++.h>

using namespace std;

namespace IO{
    inline int read(){
        int x = 0;
        char ch = getchar();
        while(!isdigit(ch)) ch = getchar();
        while(isdigit(ch)) x = (x << 3) + (x << 1) + ch - '0', ch = getchar();
        return x;
    }

    template <typename T> inline void write(T x){
        if(x > 9) write(x / 10);
        putchar(x % 10 + '0');
    }
}
using namespace IO;

const int N = 1010;
int T, n, m, ok, tot;
char s[N][N];
int pos[N];
bool a[N][N], b[N][N];
bool line[N], row[N];

signed main(){
    // freopen("A.in", "r", stdin);
    // freopen("A.out", "w", stdout);
    T = read();
    while(T--){
        memset(pos, 0, sizeof(pos));
        memset(line, 0, sizeof(line));
        memset(row, 0, sizeof(row));
        n = read(), m = read();
        for(int i = 1; i <= n; ++i){
            scanf("%s", s[i] + 1);
            for(int j = 1; j <= m; ++j) a[i][j] = s[i][j] - '0';
        }
        for(int i = 1; i <= n; ++i){
            scanf("%s", s[i] + 1);
            for(int j = 1; j <= m; ++j) b[i][j] = s[i][j] - '0';
        }

        int flag = 0;
        for(int i = 1; i <= n; ++i)
            for(int j = 1; j <= m; ++j)
                if(a[i][j] != b[i][j]) flag = 1;
        if(!flag) {puts("Yes"); continue;}

        for(int i = 1; i <= n; ++i){
            int cnt = 0;
            for(int j = 1; j <= m; ++j){
                if(cnt && b[i][j]) line[i] = row[cnt] = row[j] = 1, cnt = j;
                if(pos[j] && b[i][j]) row[j] = line[pos[j]] = line[i] = 1, pos[j] = i;
                if(b[i][j]) cnt = j, pos[j] = i;
            }
        }

        flag = 0;
        for(int i = 1; i <= n; ++i)
            for(int j = 1; j <= m; ++j)
                if(line[i] && row[j] && (a[i][j] != b[i][j])) {flag = 1; break;}
        if(flag) {puts("No"); continue;}

        flag = 0;
        for(int i = 1; i <= n; ++i)
            for(int j = 1; j <= m; ++j)
                if(!a[i][j] && !line[i] && !row[j]) {flag = 1; break;}
        if(!flag) {puts("No"); continue;}

        flag = 0;
        for(int i = 1; i <= n; ++i)
            for(int j = 1; j <= m; ++j)
                if(b[i][j] && !line[i] && !row[j]) {flag = 1; break;}
        puts(flag ? "Yes" : "No");
    }
    return 0;
}

# B. 找朋友

错误贪心（每次找最大的）可以获得前三个 $\text{subtask}$ 的分，甚至只会被最后一个测试点卡 /lh

本题做法为区间 $\text{dp}$ ，记搜也可以通过。

首先计算出每条鱼能到达的最左边和最右边的鱼缸编号是多少。然后离散化。这样范围就变成 $M$ 了。

对于当前正在处理的区间 $[l, r]$ ，计算出每个鱼缸可以被跳到的鱼的数量，然后枚举一遍，取最大值即可。

$dp_{i, j} = \max\{dp_{i, k - 1} + dp_{k + 1, j} + sum_k \times (sum_k - 1) / 2\}$

#include <bits/stdc++.h>

using namespace std;

namespace IO{
    inline int read(){
        int x = 0;
        char ch = getchar();
        while(!isdigit(ch)) ch = getchar();
        while(isdigit(ch)) x = (x << 3) + (x << 1) + ch - '0', ch = getchar();
        return x;
    }

    template <typename T> inline void write(T x){
        if(x > 9) write(x / 10);
        putchar(x % 10 + '0');
    }
}
using namespace IO;

const int N = 1e4 + 10;
const int M = 410;
int n, m, w, p, d, ans;
int h[N], t[N], val[N];
struct node{
    int l, r;
}a[M];
int b[M << 1], tot;
int dp[M][M], sum[M];

signed main(){
    // freopen("B.in", "r", stdin);
    // freopen("B.out", "w", stdout);
    n = read(), m = read(), w = read();
    for(int i = 1; i <= n; ++i) h[i] = w - read();
    for(int i = 1, j; i <= m; ++i){
        p = read(), d = read();
        for(j = p; j > 1; --j) if(d <= h[j]) break; a[i].l = j;
        for(j = p; j < n; ++j) if(d <= h[j]) break; a[i].r = j;
        b[++tot] = a[i].l, b[++tot] = a[i].r;
    }
    sort(b + 1, b + 1 + tot);
    n = unique(b + 1, b + 1 + tot) - b - 1;
    for(int i = 1; i <= m; ++i){
        a[i].l = lower_bound(b + 1, b + 1 + n, a[i].l) - b;
        a[i].r = lower_bound(b + 1, b + 1 + n, a[i].r) - b;
    }
    for(int i = 1; i <= m; ++i)
        for(int j = a[i].l; j <= a[i].r; ++j) val[j]++;
    for(int i = 1; i <= n; ++i) val[i] = val[i] * (val[i] - 1) / 2;
    for(int len = 1; len <= n; ++len)
        for(int i = 1; i + len - 1 <= n; ++i){
            int j = i + len - 1;
            for(int k = 1; k <= m; ++k)
                if(a[k].l >= i && a[k].r <= j) sum[a[k].l]++, sum[a[k].r + 1]--;
            for(int k = i; k <= j; ++k) sum[k] += sum[k - 1];
            for(int k = i; k <= j; ++k)
                dp[i][j] = max(dp[i][j], sum[k] * (sum[k] - 1) / 2 + dp[i][k - 1] + dp[k + 1][j]), sum[k] = 0;
            sum[j + 1] = 0;
        }
    write(dp[1][n]), puts("");
    return 0;
}

# C. 欧洲皇室女士的名字

暴力可得 82pts，真的没话说了……

这题是个裸的 $\text{AC}$ 自动机二次加强版。

把每个人的名字倒过来（正着插字符个数是 $n^2$ 的）插到 $\text{trie}$ 树里，每插进去一个点，令那个点的 $siz$ 加 1。

然后我们再把询问的串反过来插进去，但是此时的 $siz$ 不需要加 1，因为这是询问串。

剩下的类似于 $\text{AC}$ 自动机二次加强版。

先建出 $\text{fail}$ 树，然后跑个 $\text{dfs}$ ，统计子树大小，最后直接输出即可。

另外这题比较卡时空，不要用 cin，cout，不需要的数组也不要多开。

#include <bits/stdc++.h>

using namespace std;

namespace IO{
    inline int read(){
        int x = 0;
        char ch = getchar();
        while(!isdigit(ch)) ch = getchar();
        while(isdigit(ch)) x = (x << 3) + (x << 1) + ch - '0', ch = getchar();
        return x;
    }

    template <typename T> inline void write(T x){
        if(x > 9) write(x / 10);
        putchar(x % 10 + '0');
    }
}
using namespace IO;

const int N = 2e6 + 10;
int n, m, tot;
char c, s[N >> 1];
int p, trie[N][27], siz[N], pos[N], End[N];

inline void insertc(int x, int fa){
    int now = pos[fa], ch = c - 'A';
    trie[now][ch] = ++tot;
    pos[x] = tot;
    ++siz[tot];
}

inline void inserts(int id){
    int len = strlen(s), now = 0;
    for(int i = len - 1; i >= 0; --i){
        int c = s[i] - 'A';
        if(!trie[now][c]) trie[now][c] = ++tot;
        now = trie[now][c];
    }
    End[id] = now;
}

int fail[N];

inline void build(){
    queue <int> q;
    for(int i = 0; i < 26; ++i)
        if(trie[0][i]) q.push(trie[0][i]);
    while(!q.empty()){
        int now = q.front();
        q.pop();
        for(int i = 0; i < 26; ++i){
            if(trie[now][i]) fail[trie[now][i]] = trie[fail[now]][i], q.push(trie[now][i]);
            else trie[now][i] = trie[fail[now]][i];
        }
    }
}

struct node{
    int v, nxt;
}edge[N << 1];
int head[N], etot;

inline void add(int x, int y){
    edge[++etot] = (node){y, head[x]};
    head[x] = etot;
}

inline void dfs(int x, int fa){
    for(int i = head[x]; i; i = edge[i].nxt){
        int y = edge[i].v;
        if(y == fa) continue;
        dfs(y, x);
        siz[x] += siz[y];
    }
}

signed main(){
    // freopen("C.in", "r", stdin);
    // freopen("C.out", "w", stdout);
    n = read(), m = read();
    for(int i = 1; i <= n; ++i) {c = getchar(); p = read(); insertc(i, p);}
    for(int i = 1; i <= m; ++i) {scanf("%s", s); inserts(i);}

    build();
    for(int i = 1; i <= tot; ++i) add(fail[i], i);
    dfs(0, 0);
    for(int i = 1; i <= m; ++i) write(siz[End[i]]), putchar('\n');
    return 0;
}

# A. 我永远喜欢月

# B. 找朋友

# C. 欧洲皇室女士的名字

P6047 丝之割 题解

20220309

P6047 丝之割题解