头像

Protein

OIer




离线:48分钟前


最近来访(212)
用户头像
kukudewen
用户头像
Global_zzz
用户头像
诗人kris
用户头像
SunRayGold
用户头像
NLX77
用户头像
Zrosor_Acw
用户头像
朱柏霖
用户头像
Pipipapi
用户头像
_Gakki_
用户头像
凌乱之风
用户头像
无名_0
用户头像
不搞好-不改名
用户头像
炉石传说
用户头像
刷刷刷算法
用户头像
LHHHHHH
用户头像
uhgariej
用户头像
xql_
用户头像
Segmentation_Fault
用户头像
IntelliJ
用户头像
15084948533

新鲜事 原文

Protein
2个月前
一次性发七篇题解 累瘫了



Protein
2个月前

Blog

题目

Luogu
LOJ
Acwing

思路

001.png 002.png 003.png

代码


#include <iostream>
#include <cstring>
#include <algorithm>
#define int long long
using namespace std;
const int N = 810;
int col[N][N], row[N][N], res;
int n, m, w[N][N], v[N][N];
int f[N][N], g[N][N], L[N], R[N], T[N][N];
int uL[N], uR[N], dL[N], dR[N];
void get_cr(int w[][N]) {
    for (int i = 1; i <= n; i++) 
        for (int j = 1; j <= m; j++)
            col[i][j] = col[i - 1][j] + w[i][j], 
            row[i][j] = row[i][j - 1] + w[i][j];
}
void calc() {
    get_cr(v);
    for (int i = 1; i <= n; i++) 
        f[i][1] = v[1][1], g[i][1] = col[i][1];
    for (int j = 1; j <= m; j++)
        g[1][j] = v[1][1], f[1][j] = row[1][j];
    for (int i = 2; i <= n; i++)
        for (int j = 2; j <= m; j++)
            f[i][j] = max(f[i][j - 1] + v[1][j], max(f[i - 1][j], g[i - 1][j - 1] + row[i][j] + col[i][j] - v[i][j])), 
            g[i][j] = max(g[i - 1][j] + v[i][1], max(g[i][j - 1], f[i - 1][j - 1] + row[i][j] + col[i][j] - v[i][j]));
    memset(L,-0x3f,sizeof(L));memset(R,-0x3f,sizeof(R));
    for (int i = 1; i <= n; i++) T[1][i] = row[1][m] - row[1][i];
    for (int i = 2; i <= n; i++)
        for (int j = 1; j < m; j++)
            T[i][j] = max(T[i - 1][j] + v[i][m], row[i][m] + col[i][j + 1] - row[i][j + 1]);
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
            L[i] = max(L[i], g[i][j]);
    for (int i = 1; i <= n; i++)
        for (int j = 1; j < m; j++)
            R[i] = max(R[i], f[i][j] + T[i][j]);
}
void Solve() {
    memcpy(v, w, sizeof v);
    calc();
    for (int i = 1; i <= n; i++) 
        uL[i] = L[i], uR[i] = R[i];
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
            v[i][j] = w[n - i + 1][m - j + 1];
    calc();
    for (int i = 1; i <= n; i++) 
        dL[i] = R[n - i + 1], dR[i] = L[n - i + 1];
    get_cr(w); 
    for (int i = 2; i <= n; i++)
        uL[i] = max(uL[i], max(uL[i - 1] + w[i][1], uR[i - 1] + row[i][m])), 
        uR[i] = max(uR[i], max(uR[i - 1] + w[i][m], uL[i - 1] + row[i][m]));
    res = max(res, max(uR[n], dL[1]));
    for (int i = 1; i <= n - 1; i++) 
        res = max(res, max(uL[i] + dL[i + 1], uR[i] + dR[i + 1]));
}
signed main() {
    cin >> n >> m;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
            cin >> w[i][j];
    Solve();
    for (int i = 1; i <= n; i++)
        for (int j = i + 1; j <= m; j++)
            swap(w[i][j], w[j][i]);
    swap(n, m);
    Solve();
    cout << res << endl;
    return 0;
}



Protein
2个月前

Blog

题目

Luogu
LOJ
Acwing

思路

001.png

代码

#include <iostream>
#include <cstring>
#include <algorithm>
#include <cstdio>
using namespace std;
typedef unsigned long long ULL;
const int N = 1000010, P = 31;
int T, n, m, pre[N], suf[N];
char w[N], tmp[N];
ULL B[N] = { 1 }, prehash[N], sufhash[N];
int h[N], t[N << 1], p[N << 1], idx;
void add(int a, int b) { t[idx] = b, p[idx] = h[a], h[a] = idx++; }
int sz[N], vis[N], root;
void DFS_rt(int u, int fa, int tot) {
    sz[u] = 1;
    int mx = 0;
    for (int i = h[u], v; v = t[i], i != -1; i = p[i]) {
        if (vis[v] || v == fa) continue;
        DFS_rt(v, u, tot), sz[u] += sz[v], mx = max(mx, sz[v]);
    }
    mx = max(mx, tot - sz[u]);
    if (mx * 2 <= tot) root = u;
}
void DFS_sz(int u, int fa) {
    sz[u] = 1;
    for (int i = h[u], v; v = t[i], i != -1; i = p[i])
        if (!vis[v] && v != fa) DFS_sz(v, u), sz[u] += sz[v];
}
int sumpre[N], sumsuf[N], Tpre[N], Tsuf[N];
long long res;
int DFS(int u, int fa, int dep, int &mx, int mid, ULL hash) {
    int res = 0;
    mx = max(mx, dep);
    hash += w[u] * B[dep - 1];
    if (hash == prehash[dep]) {
        Tpre[dep % m]++;
        if (mid == pre[dep % m + 1]) 
            res += sumsuf[m - dep % m - 1];
    }
    if (hash == sufhash[dep]) {
        Tsuf[dep % m]++;
        if (mid == suf[dep % m + 1]) 
            res += sumpre[m - dep % m - 1];
    }
    for (int i = h[u], v; v = t[i], i != -1; i = p[i]) 
        if (!vis[v] && v != fa) res += DFS(v, u, dep + 1, mx, mid, hash);
    return res;
}
int Solve(int u, int tot) { 
    if (tot < m) return 0;
    DFS_rt(u, -1, tot), u = root;
    DFS_sz(u, -1), vis[u] = 1;
    int tag = 0, res = 0;
    if (w[u] == pre[1]) sumpre[0]++;
    if (w[u] == suf[1]) sumsuf[0]++;
    for (int i = h[u], v; v = t[i], i != -1; i = p[i]) {
        if (vis[v]) continue;
        int mx = 0;
        res += DFS(v, u, 1, mx, w[u], 0);
        tag = max(mx, tag);
        for (int i = 0; i <= mx; i++)
            sumpre[i] += Tpre[i], Tpre[i] = 0, 
            sumsuf[i] += Tsuf[i], Tsuf[i] = 0;
    }
    for (int i = 0; i <= tag; i++) sumpre[i] = sumsuf[i] = 0;
    for (int i = h[u], v; v = t[i], i != -1; i = p[i]) 
        if (!vis[v]) res += Solve(v, sz[v]);
    return res;
}
void Process(int s[], ULL hash[]) {
    for (int i = m + 1; i <= n; i++) s[i] = s[i - m];
    for (int i = 1; i <= n; i++)
        hash[i] = hash[i - 1] * P + s[i];
}
int main() {
    for (int i = 1; i <= 1e6; i++) B[i] = B[i - 1] * P;
    scanf("%d", &T);
    while (T--) {
        memset(vis, 0, sizeof vis), res = 0;
        memset(h, -1, sizeof h), idx = 0;
        scanf("%d%d%s", &n, &m, tmp + 1);
        for (int i = 1; i <= n; i++) w[i] = tmp[i] - 'A' + 1;
        for (int i = 1, a, b; i < n; i++)
            scanf("%d%d", &a, &b), add(a, b), add(b, a);
        scanf("%s", tmp + 1);
        for (int i = 1; i <= m; i++) pre[i] = tmp[i] - 'A' + 1;
        for (int i = 1; i <= m; i++) suf[i] = pre[m - i + 1];
        Process(pre, prehash), Process(suf, sufhash);
        cout << Solve(1, n) << endl;
    }
    return 0;
}   



Protein
2个月前

Blog

题目

Luogu
LOJ
Acwing

思路

001.png

代码

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 30010;
int T, n, MAXQ, SG[20][20];
int get(int x, int k) { 
    int t = 0; 
    while (x % k == 0) x /= k, t++; 
    return t;
}
int cnt[500];
void pre() {
    memset(SG, 0, sizeof SG);
    int a = n, b = n, x = 0, y = 0;
    while (a >= 2) x++, a /= 2;
    while (b >= 3) y++, b /= 3;
    for (int i = 0; i <= x; i++) {
        for (int j = 0; j <= y; j++) {
            memset(cnt, 0, sizeof cnt);
            for (int p = 1; p <= i; p++) 
                for (int q = 1; q <= MAXQ && p * q <= i; q++) {
                    int t = -1;
                    for (int k = 1; k <= q; k++) 
                        t = (t == -1) ? SG[i - p * k][j] : (t ^ SG[i - p * k][j]);
                    if (t != -1) cnt[t] = 1;
                }
            for (int p = 1; p <= j; p++) 
                for (int q = 1; q <= MAXQ && p * q <= j; q++) {
                    int t = -1;
                    for (int k = 1; k <= q; k++) 
                        t = (t == -1) ? SG[i][j - p * k] : (t ^ SG[i][j - p * k]);
                    if (t != -1) cnt[t] = 1;
                }
            for (int t = 0; ; t++) 
                if (!cnt[t]) { SG[i][j] = t; break; }
        }
    }   
}
int main() {
    cin >> T;
    while (T-- && cin >> n >> MAXQ) {
        pre();
        int res = 0;
        for (int i = 1, t; i <= n && cin >> t; i++)
             if (t == 0) res ^= SG[get(i, 2)][get(i, 3)];
        cout << (res ? "win" : "lose") << endl;
    }
    return 0;
}



Protein
2个月前

Blog

题目

Luogu
LOJ
Acwing

思路

001.png 002.png

代码

#include <iostream>
#include <cstring>
#include <algorithm>
#include <map>
#include <set>
using namespace std;
const int N = 1010, M = N * N, INF = 1e9;
int Cases, n, m, S, T, col[N], row[N], cnt;
int h[N], t[M], p[M], f[M], idx;
char g[N][N];
void add(int a, int b, int c) { f[idx] = c, t[idx] = b, p[idx] = h[a], h[a] = idx++; }
void add(int a, int b, int c, int d) { add(a, b, c), add(b, a, d); }
map<string, int> id;
set<string> same;
void Process(string str, int type, int x) {
    int n = str.size(), flag;
    for (int i = 0, r; i < n; i = r) {
        if (str[i] == '_') { r = i + 1; continue; }
        for (r = i; (r < n && str[r] != '_'); r++);
        string a = str.substr(i, r - i); 
        string b = a; reverse(b.begin(), b.end());
        (b < a) ? swap(a, b), flag = -1 : flag = 1;
        if (a == b) { same.insert(a); continue; }
        if (!id.count(a)) id[a] = ++cnt, id[b] = ++cnt, 
                          add(id[a], id[b], 2, 0);
        flag *= type;
        if (flag == 1) add(S, id[a], INF, 0);
        if (flag == -1) add(id[b], T, INF, 0);
        if (flag == 0) add(id[b], x, INF, 0), add(x, id[a], INF, 0);
    }
}
int d[N], cur[N], q[N];
bool BFS() {
    int hh = 0, tt = -1;
    memset(d, -1, sizeof d);
    d[S] = 0, q[++tt] = S, cur[S] = h[S];
    while (hh <= tt) {
        int u = q[hh++];
        for (int i = h[u], v; v = t[i], i != -1; i = p[i]) {
            if (d[v] != -1 || !f[i]) continue;
            d[v] = d[u] + 1, cur[v] = h[v], q[++tt] = v;
            if (v == T) return true;
        }
    }
    return false;
}
int DFS(int u, int limit) {
    if (u == T) return limit;
    int flow = 0;
    for (int i = cur[u], v; v = t[i], i != -1 && flow < limit; i = p[i]) {
        cur[u] = i;
        if (d[v] == d[u] + 1 && f[i]) {
            int t = DFS(v, min(f[i], limit - flow));    
            if (!t) d[v] = -1;
            f[i] -= t, f[i ^ 1] += t, flow += t;
        }
    }
    return flow;
}       
int Dinic() {   
    int flow = 0, res = 0;
    while (BFS()) while (flow = DFS(S, INF)) res += flow;
    return res;
}
int main() {
    cin >> Cases;
    while (Cases--) {
        memset(h, -1, sizeof h), idx = 0;
        same.clear(), id.clear();
        cin >> n >> m;
        S = 1, T = 2, cnt = 2 + n + m;
        for (int i = 1; i <= n; i++) cin >> row[i];
        for (int i = 1; i <= m; i++) cin >> col[i];
        for (int i = 1; i <= n; i++) cin >> g[i] + 1;
        string str;
        for (int i = 1; i <= n; i++) // row
            str = g[i] + 1, Process(str, row[i], i + 2);
        for (int i = 1; i <= m; i++) { // col
            str.clear();
            for (int j = 1; j <= n; j++)
                str += g[j][i];
            Process(str, col[i], i + n + 2);
        }
        cout << Dinic() + same.size() << endl;
    }
    return 0;
}



Protein
2个月前

Blog

题目

Luogu
LOJ
Acwing

思路

001.png

代码

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 400010;
int last = 1, tot = 1;
int n, m, b[N], pos[N], sz[N];
long long f[N], res;
string A, B;
struct NODE { int len, link, ch[26]; } node[N];
void insert(int c) {
    int p = last, np = last = ++tot;
    node[np].len = node[p].len + 1, sz[np] = 1;
    for (; p && !node[p].ch[c]; p = node[p].link) node[p].ch[c] = np;
    if (!p) return node[np].link = 1, void(0);
    int q = node[p].ch[c];
    if (node[q].len == node[p].len + 1) return node[np].link = q, void(0);
    int nq = ++tot;
    node[nq] = node[q], node[nq].len = node[p].len + 1;
    node[np].link = node[q].link = nq;
    for (; p && node[p].ch[c] == q; p = node[p].link) node[p].ch[c] = nq; 
}
void topsort() {
    for (int i = 1; i <= tot; i++) b[node[i].len]++;
    for (int i = 1; i <= tot; i++) b[i] += b[i - 1];
    for (int i = 1; i <= tot; i++) pos[b[node[i].len]--] = i;
    for (int i = tot; i >= 1; i--) sz[node[pos[i]].link] += sz[pos[i]];
    for (int i = 2; i <= tot; i++) 
        f[pos[i]] = 1ll * (node[pos[i]].len - node[node[pos[i]].link].len) * 
                     sz[pos[i]] + f[node[pos[i]].link];
}
void match() {
    for (int i = 0, j = 1, k = 0; i < B.size(); i++) {
        int c = B[i] - 'a';
        while (j && !node[j].ch[c]) j = node[j].link;
        if (!j) { j = 1, k = 0; continue; } 
        k = min(k, node[j].len) + 1, j = node[j].ch[c];
        res += f[node[j].link] + 1ll * (k - node[node[j].link].len) * sz[j];
    }
}
signed main() {
    cin >> A >> B;
    for (int i = 0; i < A.size(); i++) insert(A[i] - 'a');
    topsort(), match();
    cout << res << endl;
    return 0;
}



Protein
2个月前

Blog

题目

Luogu
LOJ
Acwing

思路

001.png

代码

#include <iostream>
#include <cstring>
#include <algorithm>
#define int long long
using namespace std;
const int N = 310, S = 1 << 8, INF = 1e18;
int n, k, c[N], w[N], a[N], f[N][N][S], g[2];
string str;
signed main() {
    cin >> n >> k >> str;
    for (int i = 0; i < str.size(); i++) 
        a[i + 1] = str[i] - '0';
    // 注意洛谷的读入方式略有不同
    // for (int i = 1; i <= n; i++) cin >> a[i];
    for (int i = 0; i < (1 << k); i++) cin >> c[i] >> w[i];
    memset(f, -0x3f, sizeof f);
    for (int i = 1; i <= n; i++) f[i][i][a[i]] = 0;
    for (int len = 2; len <= n; len++) {
        for (int i = 1; i + len - 1 <= n; i++) {
            int j = i + len - 1, x = (len - 1) % (k - 1);
            if (x == 0) x = k - 1;
            for (int mid = j - 1; mid >= i; mid -= k - 1) 
                for (int s = 0; s < (1 << x); s++) 
                    f[i][j][s << 1] = max(f[i][j][s << 1], f[i][mid][s] + f[mid + 1][j][0]), 
                    f[i][j][s << 1 | 1] = max(f[i][j][s << 1 | 1], f[i][mid][s] + f[mid + 1][j][1]);
            if (x == k - 1) {
                g[0] = g[1] = -INF;
                for (int s = 0; s < (1 << k); s++)
                    g[c[s]] = max(g[c[s]], f[i][j][s] + w[s]);
                f[i][j][0] = g[0], f[i][j][1] = g[1];
            }
        }
    }
    int res = -INF;
    for (int s = 0; s < (1 << k); s++)
        res = max(res, f[1][n][s]);
    cout << res << endl;
    return 0;
}



Protein
2个月前

Blog

题目

Luogu
LOJ
Acwing

思路

001.png 002.png

代码

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 500010, p = 998244353, g = 3;
int n, m, A[N], B[N], rev[N], tot = 1, bit;
int FA[N], IF[N], G[N];
int qmi(int a, int b) {
    int res = 1;
    for (; b; b >>= 1, a = 1ll * a * a % p)
        if (b & 1) res = 1ll * res * a % p;
    return res;
}
int inv(int x) { return qmi(x, p - 2); }
void NTT(int A[], int t) {
    for (int i = 0; i < tot; i++)
        if (i < rev[i]) swap(A[i], A[rev[i]]);
    for (int len = 1; len < tot; len <<= 1) {
        int w = qmi(t ? 3 : 332748118, (p - 1) / (len << 1));
        for (int i = 0; i < tot; i += len << 1) {
            for (int j = 0, k = 1; j < len; j++, k = 1ll * k * w % p) {
                int x = A[i + j], y = 1ll * k * A[i + j + len] % p;
                A[i + j] = (x + y) % p, A[i + j + len] = (x - y + p) % p;
            }
        }
    }
}
void NTT(int A[], int B[]) {
    while (tot <= n + n) tot <<= 1, bit++;
    for (int i = 0; i < tot; i++)
        rev[i] = (rev[i >> 1] >> 1) | ((i & 1) << bit - 1);
    NTT(A, 1), NTT(B, 1);
    for (int i = 0; i < tot; i++) A[i] = 1ll * A[i] * B[i] % p;
    NTT(A, 0); 
    for (int i = 0; i <= n; i++) G[i] = 1ll * A[i] * inv(tot) % p;
}
int main() {
    cin >> n;
    FA[0] = IF[0] = B[0] = 1, B[1] = n + 1;
    for (int i = 1; i <= n; i++) 
        FA[i] = 1ll * FA[i - 1] * i % p, IF[i] = inv(FA[i]);
    for (int i = 0; i <= n; i++) 
        A[i] = 1ll * (qmi(-1, i) + p) * IF[i] % p;
    for (int i = 2; i <= n; i++) 
        B[i] = 1ll * (qmi(i, n + 1) - 1) * inv(i - 1) % p * IF[i] % p;
    NTT(A, B);
    int res = 0;
    for (int i = 0; i <= n; i++)
        res = (res + (1ll * qmi(2, i) * FA[i] % p * G[i]) % p) % p;
    cout << res << endl;
    return 0;
}



Protein
2个月前

Blog

题目

Luogu
LOJ
Acwing

思路

002.png 003.png

代码

#include <iostream>
#include <cstdio>
#include <cmath>
#define int long long
using namespace std;
const int N = 2000010;
int n, m, a[N], M[22][N], stk[N], top;
int pre[N], suf[N], fl[N], fr[N], gl[N], gr[N];
int RMQ(int l, int r) { 
    int k = log2(r - l + 1);
    int x = M[k][l], y = M[k][r - (1 << k) + 1];
    return (a[x] < a[y] ? x : y);
}
signed main() {
    scanf("%lld%lld", &n, &m);
    for (int i = 1; i <= n; i++) scanf("%lld", &a[i]);
    for (int i = 1; i <= n; i++) M[0][i] = i;
    for (int i = 1; i <= 21; i++)
        for (int j = 1; j <= n; j++) {
            int x = M[i - 1][j], y = M[i - 1][j + (1 << i - 1)];
            M[i][j] = (a[x] < a[y]) ? x : y;
        }
    for (int i = 1; i <= n; i++) {
        while (top && a[stk[top]] >= a[i]) top--;
        pre[i] = stk[top], stk[++top] = i;
    }
    top = 0;
    for (int i = n; i >= 1; i--) {
        while (top && a[stk[top]] >= a[i]) top--;
        suf[i] = stk[top], stk[++top] = i;
    }
    for (int i = 1; i <= n; i++) 
        fr[i] = fr[pre[i]] + a[i] * (i - pre[i]), 
        gr[i] = gr[i - 1] + fr[i];
    for (int i = n; i >= 1; i--)
        fl[i] = fl[suf[i]] + a[i] * (suf[i] - i),
        gl[i] = gl[i + 1] + fl[i];
    for (int l, r; m--; ) {
        scanf("%lld%lld", &l, &r);
        int p = RMQ(l, r);
        printf("%lld\n", (p - l + 1) * (r - p + 1) * a[p] + 
                        gr[r] - gr[p] - fr[p] * (r - p) + 
                        gl[l] - gl[p] - fl[p] * (p - l));
    }
    return 0;
}



Protein
2个月前

Blog

题目

Luogu
LOJ
Acwing

思路

004.png
005.png

代码

#include <iostream>
#include <algorithm>
#include <vector>
#include <cstring>
#include <cmath>
#define int long long
using namespace std;
const int N = 200010;
int n, P, m, f[N], s[N], id[N], res[N];
struct QUERY { int l, r, id; } Q[N];
bool operator<(QUERY a, QUERY b) { 
    if (id[a.l] != id[b.l]) return a.l < b.l;
    return id[a.l] & 1 ? a.r < b.r : a.r > b.r;
}
char str[N];
vector<int> nums;
void init() {
    n = strlen(str + 1);
    int B = sqrt(n), S = (n + B - 1) / B, pow = 1;
    for (int i = n; i >= 1; i--) {
        s[i] = ((str[i] - '0') * pow % P + s[i + 1]) % P;
        nums.push_back(s[i]);
        pow = pow * 10 % P, id[i] = (i + B - 1) / B;
    }
    nums.push_back(0);
    sort(nums.begin(), nums.end());
    nums.erase(unique(nums.begin(), nums.end()), nums.end());
    for (int i = 1; i <= n + 1; i++) 
        s[i] = lower_bound(nums.begin(), nums.end(), s[i]) - nums.begin();
}
int A[N], B[N];
void work1() {
    for (int i = 1; i <= n; i++) {
        A[i] = A[i - 1] + (!((str[i] - '0') % P));
        B[i] = B[i - 1] + (!((str[i] - '0') % P)) * i;
    }
    for (int i = 1, l, r; i <= m && cin >> l >> r; i++)
        cout << (B[r] - B[l - 1] - (A[r] - A[l - 1]) * (l - 1)) << endl;
}
int ans = 0;
void del(int x) { f[x]--, ans -= f[x]; }
void upd(int x) { ans += f[x], f[x]++; }
void work2() {
    for (int i = 1; i <= m; i++) 
        cin >> Q[i].l >> Q[i].r, Q[i].r++, Q[i].id = i;
    sort(Q + 1, Q + m + 1);
    int l = 1, r = 0;
    for (int i = 1; i <= m; i++) {
        while (l < Q[i].l) del(s[l++]);
        while (l > Q[i].l) upd(s[--l]);
        while (r < Q[i].r) upd(s[++r]);
        while (r > Q[i].r) del(s[r--]);
        res[Q[i].id] = ans;
    }
    for (int i = 1; i <= m; i++) cout << res[i] << endl;
}
signed main() {
    cin >> P >> str + 1 >> m;
    init(), (P == 2 || P == 5) ? work1() : work2();
    return 0;
}