7/30 小白月赛36

写崩了，过了四题，开$C$一直没推出来公式，看很多人过了依旧死磕，磕掉三个h，赛后自己过了$G$,$H$。

没做出来的太多了，干脆全部做一个题目分析。

F

由于炮需要隔着一个才能发动攻击，所以最多减少到俩，因此如果 $n,m > 2$，$n,m = 2$

#include <bits/stdc++.h>
#define pc(c) putchar(c)
#define rep(a,b,c) for (int a = (b) ; a < (c) ; ++a)
#define endl '\n'

using namespace std;
using ll = long long ;
using ai2 = array<int,2> ;

const int maxn = 2e5 + 10 ;

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    int T = 1 ;
    cin >> T ;
    rep(test,1,T + 1){
        ll a,b ;
        cin >> a >> b ;
        if (a > 2) a = 2;
        if (b > 2) b = 2;
        cout << a * b  << endl ;
    }

    return 0;
}

E

易发现，如果一名选手处于一个环内，则这个选手必定不是冠军，因此答案等价于求入度为0的点的个数，赛时写得dfs

#include <bits/stdc++.h>
#define pc(c) putchar(c)
#define rep(a,b,c) for (int a = (b) ; a < (c) ; ++a)
#define endl '\n'

using namespace std;
using ll = long long ;
using ai2 = array<int,2> ;

const int maxn = 2e5 + 10 ;
int in[maxn] ;

int h[maxn],nxt[maxn],to[maxn],idx ;
inline void add(int u,int v) {
    nxt[++ idx] = h[u],h[u] = idx,to[idx] = v,++ in[v] ;
}
bool vis[maxn],defeat[maxn] ;
inline void dfs(int u) {
    vis[u] = 1; 
    for (int i = h[u],v = to[i] ; i ; v = to[i = nxt[i]]) {
        defeat[v] = 1; 
        if (!vis[v]) dfs(v) ;
    }
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    int T = 1 ;
    // cin >> T ;
    rep(test,1,T + 1){
        int n ,m;
        cin >> n >> m ;
        while (m --) {
            int u,v ;
            cin >> u >> v ;
            add(u,v) ;
        }
        int res = 0 ;
        rep(i,1,n + 1){
            if (!vis[i]) {
                dfs(i) ;
            }
        }
        res = count_if(defeat + 1,defeat + n + 1,[](bool a){
            return !a ;
        }) ;
        cout << res << endl ;
    }

    return 0;
}

I

模拟 bfs 即可

#include <bits/stdc++.h>
#define pc(c) putchar(c)
#define rep(a,b,c) for (int a = (b) ; a < (c) ; ++a)
#define endl '\n'

using namespace std;
using ll = long long ;
using ai2 = array<int,2> ;

const int maxn = 1010 ;
char g[maxn][maxn] ;

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int dx[] = {0,0,1,-1},dy[] = {1,-1,0,0} ;
    int T = 1 ;
    // cin >> T ;
    rep(test,1,T + 1){
        int n,m ;
        cin >> n >> m ;
        rep(i,1,n + 1) cin >> g[i] + 1 ;
        int res = 0 ;
        rep(i,1,n + 1) rep(j,1,m + 1) {
            if (g[i][j] == '0') {
                bool flag = i == 1 || i == n || j == 1 || j == m ;
                queue<ai2> q ;
                q.push({i,j}) ;
                int cnt = 1 ;
                g[i][j] = '1' ;
                while (q.size()) {
                    auto [x,y] = q.front() ;
                    q.pop() ;
                    rep(i,0,4) {
                        int xx = x + dx[i],yy = y + dy[i]; 
                        if (xx < 1 || xx > n || yy < 1 || yy > m || g[xx][yy] == '1') continue ;
                        flag |= xx == 1 || xx == n || yy == 1 || yy == m ;
                        if (g[xx][yy] == '0') ++ cnt ;
                        g[xx][yy] = '1' ;
                        q.push({xx,yy}) ;
                    }
                }
                if (flag) res += cnt ;
            }
        }
        cout << res << endl ;
    }

    return 0;
}

B

可以发现，对于最短的包含 $a,b$ 子串的 $s$，要么 $a$ 中有 $b$或者 $b$ 中有 $a$ ，要么 $b$ 接在 $a$ 的尾巴或 $a$ 接在 $b$ 的尾巴 。模拟即可

#include <bits/stdc++.h>
#define pc(c) putchar(c)
#define rep(a,b,c) for (int a = (b) ; a < (c) ; ++a)
#define endl '\n'

using namespace std;
using ll = long long ;
using ai2 = array<int,2> ;

const int maxn = 5010 ;

string a,b; 
bool cmp(const string &a,const string&b) {
    if (a.size() != b.size()) return false ;
    rep(i,0,a.size()) 
        if (a[i] != b[i] && (a[i] != '?' && b[i] != '?')) 
            return false;
    return true ;
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    cin >> a >> b ;
    int n = a.size(),m = b.size() ;
    int res = n + m ;
    rep(i,0,n){
        int len = n - i ; 
        if (cmp(a.substr(i),b.substr(0,len)))
            res = min(res,n + m - len) ;    
    }
    swap(n,m) ;
    swap(a,b) ;
    rep(i,0,n){
        int len = n - i ; 
        if (cmp(a.substr(i),b.substr(0,len)))
            res = min(n + m - len,res) ;    
    }
    cout << res << endl ;

    return 0;
}

G

比较明显的拓扑，由于有强行通关和道具通关两种通关方式，所以对于强行通关，考虑使用一个优先队列维护当前入度为零的最小属性值点，每次处理完拓扑需要的队列里的点，再检查一下优先队列里面的点是否可以放到拓扑队列里 ；而对于道具通关，维护一个道具数组，里面维护入度已经为零，需要道具 $i$ 来进行通关的点。每次往拓扑队列里放入一个点，递归检查更新 道具数组 （代码里记作 $hard$数组 ）。最后如果出现 所有点都访问过则输出yes。

#include <bits/stdc++.h>
#define pc(c) putchar(c)
#define rep(a,b,c) for (int a = (b) ; a < (c) ; ++a)
#define endl '\n'

using namespace std;
using ll = long long ;
using ai2 = array<int,2> ;

const int maxn = 5e5 + 10 ;
int h[maxn],nxt[maxn],to[maxn],idx,in[maxn] ;
inline void add(int u,int v) {
    nxt[++ idx] = h[u],h[u] = idx,to[idx] = v,++ in[v] ;
} 
int a[maxn],b[maxn],c[maxn],d[maxn];
bool st[maxn],vis[maxn]; // st[]，是否有这个道具 ; vis[]，是否通过这个关卡
vector<int> hard[maxn] ;
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    int n ;
    ll s ;
    cin >> n >> s; 
    rep(i,1,n + 1) cin >> a[i] >> b[i] ;
    rep(i,1,n + 1) cin >> c[i] >> d[i] ;
    rep(i,1,n + 1) {
        int k ;
        cin >> k;
        while (k --) {
            int v;
            cin >> v;
            add(i,v) ;
        }
    }
    if (s <= a[1]) {
        cout << "No" << endl;
        return 0;
    }
    s += c[1] ;
    st[d[1]] = 1;
    priority_queue<ai2,vector<ai2>,greater<ai2>> q;
    queue<int> que; 
    que.push(1) ;
    vis[1] = 1;

    std::function<void(int)> Push = [&](int u) {
        if (vis[u]) return ;
        vis[u] = 1;
        que.push(u) ;
        s += c[u] ;
        if (!st[d[u]]){
            st[d[u]] = 1;
            for (auto &t : hard[d[u]])
                Push(t) ;
        }
    } ;
    while (true) {
        while (que.size()){
            int u = que.front() ;
            que.pop() ;
            for (int i = h[u],v = to[i] ; i ; v = to[i = nxt[i]]) {
                if (!-- in[v]) {
                    if (st[b[v]] || s > a[v]) {
                        Push(v) ;
                    }else 
                        q.push({a[v],v}),hard[b[v]].push_back(v) ;
                }
            }
        }
        while (q.size() ) {
            auto [k,u] = q.top() ;
            if (s <= k) break;
            q.pop() ;
            if (vis[u]) continue ;
            Push(u) ;
        }
        if (!que.size()) break ;
    }
    int res = count_if(vis + 1,vis + n + 1,[](bool x){return x ;}) ;
    if (res == n) cout << "Yes" << endl;
    else cout << "No" << endl;
    return 0;
}

H

可以发现，除了0以外，每个数字 $a[i]$ 加的值 $x$ 一定是严格递增的（对于 $a[i] \eq 0$ 他加的值可以在第一次出现重复，但总的还是单调不降的 ）。且假设每次加入的值是 $x_j$ ，那么可以发现，每次 $a[i]$ 加 一个 $x_j$ ，那么 $a[i]$ 的值会翻上一番。 因此可以得到一个结论，每个数最多加 $log a[i]$ 次。因此
可以先从操作序列中取出单调递增序列，然后对于每个数，每次找 $lower_bound()$，模拟操作即可。总复杂度大概是 $O(nlogmlog10^9)$

#include <bits/stdc++.h>
#define pc(c) putchar(c)
#define rep(a,b,c) for (int a = (b) ; a < (c) ; ++a)
#define endl '\n'

using namespace std;
using ll = long long ;
using ai2 = array<int,2> ;

const int maxn = 2e5 + 10 ;
int n,m ;
int a[maxn],b[maxn] ;
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    int n ;
    cin >> n >> m ;
    rep(i,1,n + 1) cin >> a[i];
    unordered_map<int,int> res ;
    vector<int> opt ;
    int last = 0;
    while (m --) {
        int x ;
        cin >> x ;
        if (x < last) continue ;
        opt.push_back(x) ;
        last = x ;
    } 
    int len = opt.size() ;
    rep(i,1,n + 1) {
        if (!res.count(a[i])) {
            int now = a[i];
            int p = 0,id ;
            while (p < len) {
                id = lower_bound(opt.begin() + p,opt.end(),now) - opt.begin() ;
                if (id == len) break ;
                now += opt[id] ;
                p = id + 1;
            }
            res[a[i]] = now ;
        }        
        cout << res[a[i]] << ' ';
    }
    return 0;
}

C

这题磕4我了，一开始看到模的数是1e8以内的，想用线性求逆元搞一搞，但是后面发现空间不够，时间还很卡，所以开始猛推公式，可是没推出来。

注意一下 $n \le 2$ 的情况即可

#include <bits/stdc++.h>
#define pc(c) putchar(c)
#define rep(a,b,c) for (int a = (b) ; a < (c) ; ++a)
#define endl '\n'

using namespace std;
using ll = long long ;
using ai2 = array<int,2> ;

const int P = 99824353 ;

int qmi(int a,ll b) {
    int res = 1;
    while (b) {
        if (b & 1) res = 1ll * res * a % P ;
        b >>= 1;
        a = 1ll * a * a % P ;
    }
    return res ;
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    ll n ;
    cin >> n ;
    if (n == 1) cout << 0 << endl ;
    else if (n == 2) cout << 1 << endl ;
    else {
        int res = qmi(2,n - 3) ;
        n %= P ;
        res = 1ll * res * n % P * (n - 1 + P) % P ;
        cout << res << endl ;
    }
    return 0;
}

A

如果将括号之间的关系通过边连接起来，那么对于 最多可以经过多少对不重复的括号 这个问题其实就等价于，在这个括号序列生成的树中，找出一条以根节点为起点可重复经过树边的路径，其能走过最多树结点。由于我们能走的每个边只存在走，不走，走俩次，所以对于考虑找出树到叶节点的最长一条链，为其分配走一次的花费（即最后走这条链），对于剩下的钱，以俩次一个点随便走即可。

#include <bits/stdc++.h>
#define pc(c) putchar(c)
#define rep(a,b,c) for (int a = (b) ; a < (c) ; ++a)
#define endl '\n'

using namespace std;
using ll = long long ;
using ai2 = array<int,2> ;

const int maxn = 2e7 + 10 ;

char s[maxn] ;
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    int v,n ;
    cin >> v >> n >> s + 1 ;
    int k = 0 ;
    int dep = 0,mx = 0 ;
    for (int i = 1,lim = n << 1 ; i <= lim ; ++ i) {
        if (s[i] == '(') ++ k,++ dep ;
        else -- dep ;
        if (!dep) break ;
        mx = max(mx,dep) ;
    }
    if (n + 1 < mx) cout << n + 1 << endl ;
    else {
        int res = mx ;
        k -= mx ;
        n -= mx - 1;
        res += min(k,n >> 1) ;
        cout << res << endl ;
    }

    return 0;
}

D

这题建议直接阅读 ：官方题解

注 ： 官方题解中最后说的加上剩下钱的数目的意思是，对于买东西，可能有剩下1元和没省钱的方案，这都是不同的方案，所以要算到答案中

    #include <bits/stdc++.h>
    #define pc(c) putchar(c)
    #define rep(a,b,c) for (int a = (b) ; a < (c) ; ++a)
    #define endl '\n'

    using namespace std;
    using ll = long long ;
    using ai2 = array<int,2> ;

    const int maxn = 110,P = 1e9 + 7 ;

    ll f[maxn][maxn][maxn];
    int cost[3] = {2,3,5} ;
    int main(){
        ios::sync_with_stdio(false);
        cin.tie(0);
        cout.tie(0);

        int a,b,c;
        cin >> a >> b >> c;
        a /= 150,b /= 150,c /= 150 ;
        f[0][0][0] = 1;
        rep(i,0,a + 1) rep(j,0,b + 1) rep(k,0,c + 1) {
            if (i || j || k) {
                rep(p,0,3) {
                    if (i >= cost[p]) f[i][j][k] += f[i - cost[p]][j][k] ;
                    if (j >= cost[p]) f[i][j][k] += f[i][j - cost[p]][k] ;
                    if (k >= cost[p]) f[i][j][k] += f[i][j][k - cost[p]] ;
                }
                f[i][j][k] %= P ;
            }
        }
        ll res = 0 ;
        rep(i,max(0,a - 1),a + 1) rep(j,max(0,b - 1),b + 1) rep(k,max(0,c - 1),c + 1) 
            res += f[i][j][k]; //,cout << i << ' ' << j << ' ' << k << endl  ;
        res %= P ;
        cout << res << endl;
        return 0;
    }

J

这题其实很裸的线段树 + $hash$ + 二分，但是赛时脑子瓦特了，没想到怎么线段树怎么维护 $hash$，去写 $rand()$ 只过了 60% ， 浪费了很多时间 。赛后看到题解说可以用线段树维护 $hash$ ，自己仔细想了想确实可以 。

对于每个线段树的每个节点，维护区间的hash值，然后查询合并的时候，需要将左节点的 $hash$ 值乘上 右节点取的数的个数 那么多次幂 。

一操作就对应着单点修改，二操作的话，首先判断两个区间的长度是否相等，如果相等，二分从区间左端点开始的最大相等前缀，如果最大相等前缀等于区间长度，$return true$ ； 否则跳过最大相等前缀与前缀后的那一个不同的字符，从剩下的区间继续二分枚举最大相等前缀长度，如果剩下的区间的最大相等前缀长度为整个剩下区间的长度，则说明询问的两个区间是 勉强相等 的，否则说明两个区间并不是 勉强相等 的 。
$O(nlogn + mlognlogn)$

#include <bits/stdc++.h>
#define pc(c) putchar(c)
#define rep(a,b,c) for (int a = (b) ; a < (c) ; ++a)
#define endl '\n'

using namespace std;
using ull = unsigned long long ;
using ai2 = array<int,2> ;

const int maxn = 4e5 + 10,P = 131 ;

ull tr[maxn],len[maxn],mi[maxn] ;
char c[maxn] ;
int n,m ;
inline void pushup(int q){
    tr[q] = tr[q << 1] * mi[len[q << 1 | 1]] + tr[q << 1 | 1] ;
}

inline void build(int q,int l,int r) {
    len[q] = r - l + 1;
    if (l == r) tr[q] = c[l] - 'a';
    else {
        int mid = l + r >> 1;
        build(q << 1,l,mid);
        build(q << 1 | 1,mid + 1,r) ;
        pushup(q) ;
    }
}

inline void modify(int q,int l,int r,int k,int x){
    if (l == r) tr[q] = x - 'a';
    else {
        int mid = l + r >> 1;
        if (k <= mid) modify(q << 1,l,mid,k,x);
        else modify(q << 1 | 1,mid + 1,r,k,x) ;
        pushup(q);
    }
}

inline ull query(int q,int l,int r,int k) {
    if (!k) return 0;
    int mid ;
    ull res = 0;
    while (true) {
        if (r <= k) {
            res = res * mi[len[q]] + tr[q] ;
            return res ;
        }
        mid = l + r >> 1;
        if (k <= mid) {
            q <<= 1;
            r = mid ;
        }else {
            res = res * mi[len[q << 1]] + tr[q << 1] ;
            q = q << 1 | 1; 
            l = mid + 1;
        }
    }
    assert(0) ;
    return -1;
}

inline ull get_s(int l,int r) {
    return query(1,1,n,r) - query(1,1,n,l - 1) * mi[r - l + 1];
}
inline int mx_eq(int l1,int l2,int Len){
    int l = 1,r = Len,mid,res = 0 ;
    while (l <= r){
        mid = l + r >> 1;
        if (get_s(l1,l1 + mid - 1) == get_s(l2,l2 + mid - 1)){
            res = mid;
            l = mid + 1;
        }else 
            r = mid - 1;
    }
    return res ;
}
inline bool cmp(int l1,int r1,int l2,int r2){
    if (r1 - l1 != r2 - l2) return false ;
    int len = mx_eq(l1,l2,r1 - l1 + 1) ;
    if (len >= r1 - l1) return true ;
    l1 += len + 1;
    l2 += len + 1;
    return mx_eq(l1,l2,r1 - l1 + 1) == r1 - l1 + 1;
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    int T = 1 ;
    mi[0] = 1 ;
    rep(i,1,maxn) mi[i] = mi[i - 1] * P ;
    cin >> n >> m >> c + 1 ;
    build(1,1,n) ;
    int type,l1,r1,l2,r2,k ;
    char x[2] ;
    while (m --) {
        cin >> type ;
        if (type == 1) {
            cin >> k >> x;
            modify(1,1,n,k,*x) ;
        }else {
            cin >> l1 >> r1 >> l2 >> r2 ;
            if (cmp(l1,r1,l2,r2)) cout << "YES" << endl ;
            else cout << "NO" << endl ;
        }
    }


    return 0;
}