首页 模拟赛

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

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

# A. 我永远喜欢月

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

下面说正解。

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

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

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

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

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

  • 当 A\text{A} 和 B\text{B} 完全相同时，直接输出 Yes 。
  • 限制点的值是不可能变的，所以判一下 A\text{A} 和 B\text{B} 中限制点的值是否相同，如果有相同的直接输出 No 。
  • 我们想要从 B\text{B} 转化到 A\text{A} 必须有一个可行点（如果你一步都动不了还怎么转化），所以 A\text{A} 中必须有一个不在限制区间的 0，B\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. 找朋友
错误贪心（每次找最大的）可以获得前三个 subtask\text{subtask} 的分，甚至只会被最后一个测试点卡 /lh
本题做法为区间 dp\text{dp}，记搜也可以通过。
首先计算出每条鱼能到达的最左边和最右边的鱼缸编号是多少。然后离散化。这样范围就变成 MM 了。
对于当前正在处理的区间 [l,r][l, r]，计算出每个鱼缸可以被跳到的鱼的数量，然后枚举一遍，取最大值即可。
dpi,j=max⁡{dpi,k−1+dpk+1,j+sumk×(sumk−1)/2}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，真的没话说了……
这题是个裸的 AC\text{AC} 自动机二次加强版。
把每个人的名字倒过来（正着插字符个数是 n2n^2 的）插到 trie\text{trie} 树里，每插进去一个点，令那个点的 sizsiz 加 1。
然后我们再把询问的串反过来插进去，但是此时的 sizsiz 不需要加 1，因为这是询问串。
剩下的类似于 AC\text{AC} 自动机二次加强版。
先建出 fail\text{fail} 树，然后跑个 dfs\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;
}
 阅读次数  次