首页 题解

# Visits S

手玩一遍样例，找找最优决策，不难发现一个环中最优情况瞎只有一个点不能选。

并且题目给出的关系是一个基环树森林。

所以先求一下总和， 然后 Tarjan\text{Tarjan} 找每一个环上的最小值，用总和减去即可。

另外要判一下环的大小大于等于 2 时才能减（一个点时显然是可以加上的）。

#include <bits/stdc++.h>
#define pb push_back
#define ll long long
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 = 1e6 + 10;
int n, m;
ll sum;
int a[N], v[N];
vector <int> g[N];
int dfn[N], low[N], tim;
int stk[N], top;
bool vis[N];
inline int tarjan(int x){
    dfn[x] = low[x] = ++tim;
    stk[++top] = x, vis[x] = 1;
    for(auto y : g[x]){
        if(!dfn[y]) tarjan(y), low[x] = min(low[x], low[y]);
        else if(vis[y]) low[x] = min(low[x], dfn[y]);
    }
    int siz = 0, mins = 1e9;
    if(low[x] == dfn[x]){
        int k;
        do{
            k = stk[top--];
            vis[k] = 0, siz++, mins = min(mins, v[k]);
        }while(x != k);
    }
    return mins * (siz > 1 ? 1 : 0);
}
signed main(){
    n = read();
    for(int i = 1; i <= n; ++i){
        a[i] = read(), v[i] = read(), sum += v[i];
        g[a[i]].pb(i);
    }
    for(int i = 1; i <= n; ++i)
        if(!dfn[i]) sum -= tarjan(i);
    write(sum), puts("");
    return 0;
}
# Subset Equality S
感觉这题是三道题里最难的。
主要思路：预处理出任意两个字符能否共存，查询时枚举所有字符对判断即可。
预处理复杂度 O(182n)O(18^2n)，查询复杂度 O(m∣S∣2)O(m\left\vert S\right\vert^2)，所以总复杂度就是 O(182n+m∣S∣2)O(18^2n + m\left\vert S\right\vert^2)
接下来说说怎么预处理。
先把所有字符出现的位置全都放到 vector\text{vector} 里。具体来说，gcg_c 存字符 cc 所有出现的位置的下标，两个串要分开存（感觉说不清楚 QwQ，具体看代码吧）。
  • 两个串（以下称 ss 串 和 tt 串）中某个字符个数不相同，那么这个字符一定不合法。
  • 相同时，双指针扫一下。具体而言，枚举 l1l_1 为字符 aa 在 ss 串中出现的位置，l2l_2 为 ss 串中 l1l_1 后面的第一个字符 bb 出现的位置，然后判断 a,ba, b 分别在 s,ts, t 串中的位置是否相交，即判断 aa 在 tt 串中的位置是否在 bb 在 tt 串中的位置的后面。不交则合法，反之不合法（边界略恶心）。
你迅速码完后交了一发，怎么就 20 分？？？
然后你可以试一试以下样例：
ba
ab
1
ab

你惊奇的发现输出的是 Y ，那么这是为什么呢？题面里的样例明明看起来挺强的啊，也有交叉什么的。
问题在于上面这组样例中你会先枚举到 b ，再枚举 a ，这就出现了一定问题。
由此可以发现预处理时 flagi,jflag_{i, j} 和 flagj,iflag_{j, i} 不一定相等（或者说有可能一个为 0，一个为 1），这时候枚举就需要从头开始。
查询判断时正反也都要判一下。
#include <bits/stdc++.h>
#define pb push_back
#define ll long long
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 = 2e5 + 10;
char s[N], t[N], p[N];
int vis[20];
int n, m;
bool flag[20][20];
vector <int> g1[20], g2[20];
inline bool check(int a, int b){
    int l1 = 0, l2 = 0;
    for(; l1 < (int)g1[a].size(); ++l1){
        for(; l2 < (int)g1[b].size() && g1[b][l2] <= g1[a][l1]; ++l2);
        if(l2 < (int)g1[b].size() && g2[a][l1] > g2[b][l2]) return 0;
    }
    return 1;
}
inline void init(){
    n = strlen(s + 1);
    for(int i = 1; i <= n; ++i) g1[s[i] - 'a'].pb(i);
    n = strlen(t + 1);
    for(int i = 1; i <= n; ++i) g2[t[i] - 'a'].pb(i);
    for(int i = 0; i < 18; ++i){
        if(g1[i].size() != g2[i].size()) continue;
        flag[i][i] = 1;
        for(int j = 0; j < 18; ++j)
            if(g1[j].size() == g2[j].size()) flag[i][j] = check(i, j);
    }
}
signed main(){
    scanf("%s%s", s + 1, t + 1);
    init();
    m = read();
    while(m--){
        scanf("%s", p + 1);
        int len = strlen(p + 1), ok = 1;
        for(int i = 1; i <= len; ++i)
            for(int j = i; j <= len; ++j)
                if(!flag[p[i] - 'a'][p[j] - 'a'] || !flag[p[j] - 'a'][p[i] - 'a']) ok = 0;
        putchar(ok ? 'Y' : 'N');
    }
    return 0;
}
# COW Operations S
非常妙的一道题。
题目中只有两种操作：
  • 删除两个相邻且相同的字符。
  • 把两个相邻且不同的字符换成第三种字符。
我们预处理出一个 4×44 \times 4 的数组 nxtnxt，0 表示空字符，1 表示 C ，2 表示 O ，3 表示 W 。
nxti,jnxt_{i, j} 即为状态 ii 和 jj 合并之后是什么。
然后再预处理一个前缀和 sumisum_i，表示从 1 合并到 ii 之后剩下一个什么字符（显然合并顺序不影响结果）。
然后查询时直接 O(1)O(1) 判断 nxt[suml−1][sumr]nxt[sum_{l - 1}][sum_r] 是否为 1 即可。
#include <bits/stdc++.h>
#define pb push_back
#define ll long long
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 = 2e5 + 10;
char s[N];
int n, m;
int nxt[4][4] = {
    0, 1, 2, 3,
    1, 0, 3, 2,
    2, 3, 0, 1,
    3, 2, 1, 0
};
// '': 0  'C': 1  'O': 2   'W': 3
int sum[N];
inline int calc(int x){
    if(s[x] == 'C') return 1;
    if(s[x] == 'O') return 2;
    if(s[x] == 'W') return 3;
}
inline void init(){
    n = strlen(s + 1);
    for(int i = 1; i <= n; ++i) sum[i] = nxt[sum[i - 1]][calc(i)];
}
signed main(){
    scanf("%s", s + 1);
    init();
    m = read();
    while(m--) putchar(nxt[sum[read() - 1]][sum[read()]] == 1 ? 'Y' : 'N');
    return 0;
}
 更新于   阅读次数  次