『模拟赛』多校A层冲刺NOIP2024模拟赛15-后端开发牛翰社区-编程开发-牛翰网

『模拟赛』多校A层冲刺NOIP2024模拟赛15

DrRatio等级-LV1-牛翰网3个月前更新
80

Rank

一般

A. 追逐游戏 (chase)

签，但是保龄。

上来发现情况好像是有限的，于是直接分讨，不过漏了 n 种情况，小样例水，大样例 vscose 自带的 compare 跑不出来，注销一遍之后甚至进度条都没了导致我以为过了，最后 10min 才发现（

赛后发现二分是可做的，但是倍增的巨大常数加上逆天评测速度导致在 accoder 上跑不动，于是又学了一个新的树剖维护的不用二分的做法，找到三点最深的 lca 然后再分讨求 k 级祖先就能少很多情况，复杂度是 \(\mathcal{O(n\log n)}\) 的。

二分倍增代码 

#include<bits/stdc++.h>
#define fo(x, y, z) for(register int (x) = (y); (x) <= (z); (x)++)
#define fu(x, y, z) for(register int (x) = (y); (x) >= (z); (x)--)
typedef long long ll;
using namespace std;
#define lx ll
inline lx qr()
{
    char ch = getchar(); lx x = 0, f = 1;
    for(; ch < '0' || ch > '9'; ch = getchar()) if(ch == '-') f = -1;
    for(; ch >= '0' && ch <= '9'; ch = getchar()) x = (x << 3) + (x << 1) + (ch ^ 48);
    return x * f;
}
#undef lx
#define qr qr()
#define pll pair<ll, ll>
#define fi first
#define se second
#define M_P(x, y) make_pair(x, y)
#define P_B(x) push_back(x)
const int Ratio = 0;
const int N = 2e5 + 5;
const int mod = 998244353;
int n, q, st1, ed, st2;
int dfn[N], dt, st[30][N], lg[N], dep[N], fx[N][30];
int hh[N], to[N << 1], ne[N << 1], cnt;
namespace Wisadel
{
    inline int Wget(int u, int v){return dfn[u] < dfn[v] ? u : v;}
    inline void Wadd(int u, int v)
    {
        to[++cnt] = v;
        ne[cnt] = hh[u];
        hh[u] = cnt;
    }
    inline void Wdfs(int u, int fa)
    {
        dfn[u] = ++dt, st[0][dfn[u]] = fx[u][0] = fa;
        dep[u] = dep[fa] + 1;
        fo(i, 1, lg[dep[u]]) fx[u][i] = fx[fx[u][i - 1]][i - 1];
        for(int i = hh[u]; i != -1; i = ne[i])
        {
            int v = to[i];
            if(v == fa) continue;
            Wdfs(v, u);
        }
    }
    inline int Wlca(int u, int v)
    {
        if(u == v) return u;
        if((u = dfn[u]) > (v = dfn[v])) swap(u, v);
        int d = lg[v - u++];
        return Wget(st[d][u], st[d][v - (1 << d) + 1]);
    }
    inline int Wqk(int u, int k)
    {
        int t = u;
        fu(i, lg[k], 0) if((k >> i) & 1) t = fx[t][i];
        return t;
    }
    inline int Wq(int u, int v, int lca, int k)
    {
        if(dep[u] - dep[lca] >= k) return Wqk(u, k);
        else return Wqk(v, dep[u] + dep[v] - 2 * dep[Wlca(u, v)] - k);
    }
    short main()
    {
        freopen("chase.in", "r", stdin), freopen("chase.out", "w", stdout);
        n = qr, q = qr;
        memset(hh, -1, sizeof hh);
        fo(i, 2, n) lg[i] = lg[i >> 1] + 1;
        fo(i, 1, n - 1)
        {
            int a = qr, b = qr;
            Wadd(a, b), Wadd(b, a);
        }
        Wdfs(1, 0);
        fo(i, 1, lg[n]) fo(j, 1, n - (1 << i) + 1)
            st[i][j] = Wget(st[i - 1][j], st[i - 1][j + (1 << (i - 1))]);
        fo(i, 1, q)
        {
            st1 = qr, ed = qr, st2 = qr;
            int lca = Wlca(st1, ed), l = 0, r = dep[st1] + dep[ed] - 2 * dep[Wlca(st1, ed)];
            int a1 = dep[ed] + dep[st2] - 2 * dep[Wlca(ed, st2)], a2 = ed;
            while(l <= r)
            {
                int mid = (l + r) >> 1, zc = Wq(st1, ed, lca, mid);
                if(dep[zc] + dep[st2] - 2 * dep[Wlca(zc, st2)] <= mid) a1 = mid, a2 = zc, r = mid - 1;
                else l = mid + 1;
            }
            printf("%d %d\n", a1, a2);
        }
        return 0;
    }
}
signed main(){return Wisadel::main();}
#include<bits/stdc++.h>
#define fo(x, y, z) for(register int (x) = (y); (x) <= (z); (x)++)
#define fu(x, y, z) for(register int (x) = (y); (x) >= (z); (x)--)
typedef long long ll;
using namespace std;
#define lx ll
inline lx qr()
{
    char ch = getchar(); lx x = 0, f = 1;
    for(; ch < '0' || ch > '9'; ch = getchar()) if(ch == '-') f = -1;
    for(; ch >= '0' && ch <= '9'; ch = getchar()) x = (x << 3) + (x << 1) + (ch ^ 48);
    return x * f;
}
#undef lx
#define qr qr()
#define pll pair<ll, ll>
#define fi first
#define se second
#define M_P(x, y) make_pair(x, y)
#define P_B(x) push_back(x)
const int Ratio = 0;
const int N = 2e5 + 5;
const int mod = 998244353;
int n, q, st1, ed, st2;
int dfn[N], dt, st[30][N], lg[N], dep[N], fx[N][30];
int hh[N], to[N << 1], ne[N << 1], cnt;
namespace Wisadel
{
    inline int Wget(int u, int v){return dfn[u] < dfn[v] ? u : v;}
    inline void Wadd(int u, int v)
    {
        to[++cnt] = v;
        ne[cnt] = hh[u];
        hh[u] = cnt;
    }
    inline void Wdfs(int u, int fa)
    {
        dfn[u] = ++dt, st[0][dfn[u]] = fx[u][0] = fa;
        dep[u] = dep[fa] + 1;
        fo(i, 1, lg[dep[u]]) fx[u][i] = fx[fx[u][i - 1]][i - 1];
        for(int i = hh[u]; i != -1; i = ne[i])
        {
            int v = to[i];
            if(v == fa) continue;
            Wdfs(v, u);
        }
    }
    inline int Wlca(int u, int v)
    {
        if(u == v) return u;
        if((u = dfn[u]) > (v = dfn[v])) swap(u, v);
        int d = lg[v - u++];
        return Wget(st[d][u], st[d][v - (1 << d) + 1]);
    }
    inline int Wqk(int u, int k)
    {
        int t = u;
        fu(i, lg[k], 0) if((k >> i) & 1) t = fx[t][i];
        return t;
    }
    inline int Wq(int u, int v, int lca, int k)
    {
        if(dep[u] - dep[lca] >= k) return Wqk(u, k);
        else return Wqk(v, dep[u] + dep[v] - 2 * dep[Wlca(u, v)] - k);
    }
    short main()
    {
        freopen("chase.in", "r", stdin), freopen("chase.out", "w", stdout);
        n = qr, q = qr;
        memset(hh, -1, sizeof hh);
        fo(i, 2, n) lg[i] = lg[i >> 1] + 1;
        fo(i, 1, n - 1)
        {
            int a = qr, b = qr;
            Wadd(a, b), Wadd(b, a);
        }
        Wdfs(1, 0);
        fo(i, 1, lg[n]) fo(j, 1, n - (1 << i) + 1)
            st[i][j] = Wget(st[i - 1][j], st[i - 1][j + (1 << (i - 1))]);
        fo(i, 1, q)
        {
            st1 = qr, ed = qr, st2 = qr;
            int lca = Wlca(st1, ed), l = 0, r = dep[st1] + dep[ed] - 2 * dep[Wlca(st1, ed)];
            int a1 = dep[ed] + dep[st2] - 2 * dep[Wlca(ed, st2)], a2 = ed;
            while(l <= r)
            {
                int mid = (l + r) >> 1, zc = Wq(st1, ed, lca, mid);
                if(dep[zc] + dep[st2] - 2 * dep[Wlca(zc, st2)] <= mid) a1 = mid, a2 = zc, r = mid - 1;
                else l = mid + 1;
            }
            printf("%d %d\n", a1, a2);
        }
        return 0;
    }
}
signed main(){return Wisadel::main();}
#include<bits/stdc++.h>
#define fo(x, y, z) for(register int (x) = (y); (x) <= (z); (x)++)
#define fu(x, y, z) for(register int (x) = (y); (x) >= (z); (x)--)
typedef long long ll;
using namespace std;
#define lx ll
inline lx qr()
{
    char ch = getchar(); lx x = 0, f = 1;
    for(; ch < '0' || ch > '9'; ch = getchar()) if(ch == '-') f = -1;
    for(; ch >= '0' && ch <= '9'; ch = getchar()) x = (x << 3) + (x << 1) + (ch ^ 48);
    return x * f;
}
#undef lx
#define qr qr()
#define pll pair<ll, ll>
#define fi first
#define se second
#define M_P(x, y) make_pair(x, y)
#define P_B(x) push_back(x)
const int Ratio = 0;
const int N = 2e5 + 5;
const int mod = 998244353;
int n, q, st1, ed, st2;
int dfn[N], dt, st[30][N], lg[N], dep[N], fx[N][30];
int hh[N], to[N << 1], ne[N << 1], cnt;
namespace Wisadel
{
    inline int Wget(int u, int v){return dfn[u] < dfn[v] ? u : v;}
    inline void Wadd(int u, int v)
    {
        to[++cnt] = v;
        ne[cnt] = hh[u];
        hh[u] = cnt;
    }
    inline void Wdfs(int u, int fa)
    {
        dfn[u] = ++dt, st[0][dfn[u]] = fx[u][0] = fa;
        dep[u] = dep[fa] + 1;
        fo(i, 1, lg[dep[u]]) fx[u][i] = fx[fx[u][i - 1]][i - 1];
        for(int i = hh[u]; i != -1; i = ne[i])
        {
            int v = to[i];
            if(v == fa) continue;
            Wdfs(v, u);
        }
    }
    inline int Wlca(int u, int v)
    {
        if(u == v) return u;
        if((u = dfn[u]) > (v = dfn[v])) swap(u, v);
        int d = lg[v - u++];
        return Wget(st[d][u], st[d][v - (1 << d) + 1]);
    }
    inline int Wqk(int u, int k)
    {
        int t = u;
        fu(i, lg[k], 0) if((k >> i) & 1) t = fx[t][i];
        return t;
    }
    inline int Wq(int u, int v, int lca, int k)
    {
        if(dep[u] - dep[lca] >= k) return Wqk(u, k);
        else return Wqk(v, dep[u] + dep[v] - 2 * dep[Wlca(u, v)] - k);
    }
    short main()
    {
        freopen("chase.in", "r", stdin), freopen("chase.out", "w", stdout);
        n = qr, q = qr;
        memset(hh, -1, sizeof hh);
        fo(i, 2, n) lg[i] = lg[i >> 1] + 1;
        fo(i, 1, n - 1)
        {
            int a = qr, b = qr;
            Wadd(a, b), Wadd(b, a);
        }
        Wdfs(1, 0);
        fo(i, 1, lg[n]) fo(j, 1, n - (1 << i) + 1)
            st[i][j] = Wget(st[i - 1][j], st[i - 1][j + (1 << (i - 1))]);
        fo(i, 1, q)
        {
            st1 = qr, ed = qr, st2 = qr;
            int lca = Wlca(st1, ed), l = 0, r = dep[st1] + dep[ed] - 2 * dep[Wlca(st1, ed)];
            int a1 = dep[ed] + dep[st2] - 2 * dep[Wlca(ed, st2)], a2 = ed;
            while(l <= r)
            {
                int mid = (l + r) >> 1, zc = Wq(st1, ed, lca, mid);
                if(dep[zc] + dep[st2] - 2 * dep[Wlca(zc, st2)] <= mid) a1 = mid, a2 = zc, r = mid - 1;
                else l = mid + 1;
            }
            printf("%d %d\n", a1, a2);
        }
        return 0;
    }
}
signed main(){return Wisadel::main();}

分讨树剖代码 

#include<bits/stdc++.h>
#define fo(x, y, z) for(register int (x) = (y); (x) <= (z); (x)++)
#define fu(x, y, z) for(register int (x) = (y); (x) >= (z); (x)--)
typedef long long ll;
using namespace std;
#define lx ll
inline lx qr()
{
    char ch = getchar(); lx x = 0, f = 1;
    for(; ch < '0' || ch > '9'; ch = getchar()) if(ch == '-') f = -1;
    for(; ch >= '0' && ch <= '9'; ch = getchar()) x = (x << 3) + (x << 1) + (ch ^ 48);
    return x * f;
}
#undef lx
#define qr qr()
#define pll pair<ll, ll>
#define fi first
#define se second
#define M_P(x, y) make_pair(x, y)
#define P_B(x) push_back(x)
const int Ratio = 0;
const int N = 2e5 + 5;
const int mod = 998244353;
int n, q, st1, ed, st2, ans;
int dfn[N], dt, dep[N], fx[N], siz[N], top[N], pre[N], son[N];
int hh[N], to[N << 1], ne[N << 1], cnt;
namespace Wisadel
{
    inline void Wadd(int u, int v)
    {
        to[++cnt] = v;
        ne[cnt] = hh[u];
        hh[u] = cnt;
    }
    inline void Wdfs1(int u, int fa)
    {
        fx[u] = fa, siz[u] = 1, dep[u] = dep[fa] + 1;
        for(int i = hh[u]; i != -1; i = ne[i])
        {
            int v = to[i];
            if(v == fa) continue;
            Wdfs1(v, u);
            siz[u] += siz[v];
            if(siz[v] > siz[son[u]]) son[u] = v;
        }
    }
    inline void Wdfs2(int u, int tp)
    {
        dfn[u] = ++dt, pre[dt] = u, top[u] = tp;
        if(son[u]) Wdfs2(son[u], tp);
        for(int i = hh[u]; i != -1; i = ne[i])
        {
            int v = to[i];
            if(v == fx[u] || v == son[u]) continue;
            Wdfs2(v, v);
        }
    }
    inline int Wlca(int u, int v)
    {
        while(top[u] != top[v])
        {
            if(dep[top[u]] < dep[top[v]]) swap(u, v);
            u = fx[top[u]];
        }
        if(dep[u] > dep[v]) swap(u, v);
        return u;
    }
    inline int Wd(int u, int v){return dep[u] + dep[v] - 2 * dep[Wlca(u, v)];}
    inline int WLCA(int u, int v, int e)
    {
        int l1 = Wlca(u, v), l2 = Wlca(u, e), l3 = Wlca(v, e);
        return (dep[(dep[l1] > dep[l2] ? l1 : l2)] > dep[l3] ? (dep[l1] > dep[l2] ? l1 : l2) : l3);
    }
    inline int Wqk(int u, int k)
    {
        int t = dep[u] - k;
        while(dep[fx[top[u]]] >= t) u = fx[top[u]];
        return pre[dfn[u] - (dep[u] - t)];
    }
    inline int Wfind(int u, int v, int k)
    {
        int lca = Wlca(u, v);
        if(dep[u] - dep[lca] >= k) return Wqk(u, k);
        return Wqk(v, dep[u] + dep[v] - 2 * dep[lca] - k);
    }
    short main()
    {
        freopen("chase.in", "r", stdin), freopen("chase.out", "w", stdout);
        n = qr, q = qr;
        memset(hh, -1, sizeof hh);
        fo(i, 1, n - 1)
        {
            int a = qr, b = qr;
            Wadd(a, b), Wadd(b, a);
        }
        Wdfs1(1, 0), Wdfs2(1, 1);
        fo(i, 1, q)
        {
            st1 = qr, ed = qr, st2 = qr;
            int lca = WLCA(st1, ed, st2);
            int d1 = Wd(st2, lca), d2 = Wd(st1, lca), d3 = Wd(ed, lca);
            int nd = 0; ans = 0;
            if(d1 > d2) nd = d1 + d3, ans = ed, printf("%d %d\n", nd, ans);
            else nd = (d1 + d2 + 1) / 2, ans = Wfind(st1, st2, nd), printf("%d %d\n", nd, ans);
        }
        return Ratio;
    }
}
signed main(){return Wisadel::main();}
#include<bits/stdc++.h>
#define fo(x, y, z) for(register int (x) = (y); (x) <= (z); (x)++)
#define fu(x, y, z) for(register int (x) = (y); (x) >= (z); (x)--)
typedef long long ll;
using namespace std;
#define lx ll
inline lx qr()
{
    char ch = getchar(); lx x = 0, f = 1;
    for(; ch < '0' || ch > '9'; ch = getchar()) if(ch == '-') f = -1;
    for(; ch >= '0' && ch <= '9'; ch = getchar()) x = (x << 3) + (x << 1) + (ch ^ 48);
    return x * f;
}
#undef lx
#define qr qr()
#define pll pair<ll, ll>
#define fi first
#define se second
#define M_P(x, y) make_pair(x, y)
#define P_B(x) push_back(x)
const int Ratio = 0;
const int N = 2e5 + 5;
const int mod = 998244353;
int n, q, st1, ed, st2, ans;
int dfn[N], dt, dep[N], fx[N], siz[N], top[N], pre[N], son[N];
int hh[N], to[N << 1], ne[N << 1], cnt;
namespace Wisadel
{
    inline void Wadd(int u, int v)
    {
        to[++cnt] = v;
        ne[cnt] = hh[u];
        hh[u] = cnt;
    }
    inline void Wdfs1(int u, int fa)
    {
        fx[u] = fa, siz[u] = 1, dep[u] = dep[fa] + 1;
        for(int i = hh[u]; i != -1; i = ne[i])
        {
            int v = to[i];
            if(v == fa) continue;
            Wdfs1(v, u);
            siz[u] += siz[v];
            if(siz[v] > siz[son[u]]) son[u] = v;
        }
    }
    inline void Wdfs2(int u, int tp)
    {
        dfn[u] = ++dt, pre[dt] = u, top[u] = tp;
        if(son[u]) Wdfs2(son[u], tp);
        for(int i = hh[u]; i != -1; i = ne[i])
        {
            int v = to[i];
            if(v == fx[u] || v == son[u]) continue;
            Wdfs2(v, v);
        }
    }
    inline int Wlca(int u, int v)
    {
        while(top[u] != top[v])
        {
            if(dep[top[u]] < dep[top[v]]) swap(u, v);
            u = fx[top[u]];
        }
        if(dep[u] > dep[v]) swap(u, v);
        return u;
    }
    inline int Wd(int u, int v){return dep[u] + dep[v] - 2 * dep[Wlca(u, v)];}
    inline int WLCA(int u, int v, int e)
    {
        int l1 = Wlca(u, v), l2 = Wlca(u, e), l3 = Wlca(v, e);
        return (dep[(dep[l1] > dep[l2] ? l1 : l2)] > dep[l3] ? (dep[l1] > dep[l2] ? l1 : l2) : l3);
    }
    inline int Wqk(int u, int k)
    {
        int t = dep[u] - k;
        while(dep[fx[top[u]]] >= t) u = fx[top[u]];
        return pre[dfn[u] - (dep[u] - t)];
    }
    inline int Wfind(int u, int v, int k)
    {
        int lca = Wlca(u, v);
        if(dep[u] - dep[lca] >= k) return Wqk(u, k);
        return Wqk(v, dep[u] + dep[v] - 2 * dep[lca] - k);
    }
    short main()
    {
        freopen("chase.in", "r", stdin), freopen("chase.out", "w", stdout);
        n = qr, q = qr;
        memset(hh, -1, sizeof hh);
        fo(i, 1, n - 1)
        {
            int a = qr, b = qr;
            Wadd(a, b), Wadd(b, a);
        }
        Wdfs1(1, 0), Wdfs2(1, 1);
        fo(i, 1, q)
        {
            st1 = qr, ed = qr, st2 = qr;
            int lca = WLCA(st1, ed, st2);
            int d1 = Wd(st2, lca), d2 = Wd(st1, lca), d3 = Wd(ed, lca);
            int nd = 0; ans = 0;
            if(d1 > d2) nd = d1 + d3, ans = ed, printf("%d %d\n", nd, ans);
            else nd = (d1 + d2 + 1) / 2, ans = Wfind(st1, st2, nd), printf("%d %d\n", nd, ans);
        }
        return Ratio;
    }
}
signed main(){return Wisadel::main();}
#include<bits/stdc++.h>
#define fo(x, y, z) for(register int (x) = (y); (x) <= (z); (x)++)
#define fu(x, y, z) for(register int (x) = (y); (x) >= (z); (x)--)
typedef long long ll;
using namespace std;
#define lx ll
inline lx qr()
{
    char ch = getchar(); lx x = 0, f = 1;
    for(; ch < '0' || ch > '9'; ch = getchar()) if(ch == '-') f = -1;
    for(; ch >= '0' && ch <= '9'; ch = getchar()) x = (x << 3) + (x << 1) + (ch ^ 48);
    return x * f;
}
#undef lx
#define qr qr()
#define pll pair<ll, ll>
#define fi first
#define se second
#define M_P(x, y) make_pair(x, y)
#define P_B(x) push_back(x)
const int Ratio = 0;
const int N = 2e5 + 5;
const int mod = 998244353;
int n, q, st1, ed, st2, ans;
int dfn[N], dt, dep[N], fx[N], siz[N], top[N], pre[N], son[N];
int hh[N], to[N << 1], ne[N << 1], cnt;
namespace Wisadel
{
    inline void Wadd(int u, int v)
    {
        to[++cnt] = v;
        ne[cnt] = hh[u];
        hh[u] = cnt;
    }
    inline void Wdfs1(int u, int fa)
    {
        fx[u] = fa, siz[u] = 1, dep[u] = dep[fa] + 1;
        for(int i = hh[u]; i != -1; i = ne[i])
        {
            int v = to[i];
            if(v == fa) continue;
            Wdfs1(v, u);
            siz[u] += siz[v];
            if(siz[v] > siz[son[u]]) son[u] = v;
        }
    }
    inline void Wdfs2(int u, int tp)
    {
        dfn[u] = ++dt, pre[dt] = u, top[u] = tp;
        if(son[u]) Wdfs2(son[u], tp);
        for(int i = hh[u]; i != -1; i = ne[i])
        {
            int v = to[i];
            if(v == fx[u] || v == son[u]) continue;
            Wdfs2(v, v);
        }
    }
    inline int Wlca(int u, int v)
    {
        while(top[u] != top[v])
        {
            if(dep[top[u]] < dep[top[v]]) swap(u, v);
            u = fx[top[u]];
        }
        if(dep[u] > dep[v]) swap(u, v);
        return u;
    }
    inline int Wd(int u, int v){return dep[u] + dep[v] - 2 * dep[Wlca(u, v)];}
    inline int WLCA(int u, int v, int e)
    {
        int l1 = Wlca(u, v), l2 = Wlca(u, e), l3 = Wlca(v, e);
        return (dep[(dep[l1] > dep[l2] ? l1 : l2)] > dep[l3] ? (dep[l1] > dep[l2] ? l1 : l2) : l3);
    }
    inline int Wqk(int u, int k)
    {
        int t = dep[u] - k;
        while(dep[fx[top[u]]] >= t) u = fx[top[u]];
        return pre[dfn[u] - (dep[u] - t)];
    }
    inline int Wfind(int u, int v, int k)
    {
        int lca = Wlca(u, v);
        if(dep[u] - dep[lca] >= k) return Wqk(u, k);
        return Wqk(v, dep[u] + dep[v] - 2 * dep[lca] - k);
    }
    short main()
    {
        freopen("chase.in", "r", stdin), freopen("chase.out", "w", stdout);
        n = qr, q = qr;
        memset(hh, -1, sizeof hh);
        fo(i, 1, n - 1)
        {
            int a = qr, b = qr;
            Wadd(a, b), Wadd(b, a);
        }
        Wdfs1(1, 0), Wdfs2(1, 1);
        fo(i, 1, q)
        {
            st1 = qr, ed = qr, st2 = qr;
            int lca = WLCA(st1, ed, st2);
            int d1 = Wd(st2, lca), d2 = Wd(st1, lca), d3 = Wd(ed, lca);
            int nd = 0; ans = 0;
            if(d1 > d2) nd = d1 + d3, ans = ed, printf("%d %d\n", nd, ans);
            else nd = (d1 + d2 + 1) / 2, ans = Wfind(st1, st2, nd), printf("%d %d\n", nd, ans);
        }
        return Ratio;
    }
}
signed main(){return Wisadel::main();}

B. 统计

思维题。

\(\mathcal{O(\frac{n^2}{m})}\) 的做法是好想的，只有长度为 \(m\) 的倍数的区间才可能为合法区间，枚举一个端点即可。

正解是很优的，给每个数（值域上）赋一个权值，然后求前缀和，找这些前缀和是否存在差为 \([1,m]\) 权值和的倍数的，有的话显然就合法。为了方便可以使这个值为 0，具体做法是将 \(m\) 的权值设为负的 \([1,m-1]\) 的权值和，这样做后可以直接对前缀和 sort 一遍，然后简单记个相同的个数计数即可，复杂度 \(\mathcal{O(Tn\log n)}\)。

点击查看代码 

#include<bits/stdc++.h>
#define fo(x, y, z) for(register int (x) = (y); (x) <= (z); (x)++)
#define fu(x, y, z) for(register int (x) = (y); (x) >= (z); (x)--)
typedef long long ll;
using namespace std;
#define lx ll
inline lx qr()
{
    char ch = getchar(); lx x = 0, f = 1;
    for(; ch < '0' || ch > '9'; ch = getchar()) if(ch == '-') f = -1;
    for(; ch >= '0' && ch <= '9'; ch = getchar()) x = (x << 3) + (x << 1) + (ch ^ 48);
    return x * f;
}
#undef lx
#define qr qr()
#define pll pair<ll, ll>
#define fi first
#define se second
#define M_P(x, y) make_pair(x, y)
#define P_B(x) push_back(x)
const int Ratio = 0;
const int N = 1e6 + 5;
const int mod = 998244353;
mt19937 myrand(chrono::high_resolution_clock::now().time_since_epoch().count());
int n, m;
int a[N];
ll v[N], sum[N], ans;
namespace Wisadel
{
    short main()
    {
        freopen("st.in", "r", stdin), freopen("st.out", "w", stdout);
        int T = qr;
        while(T--)
        {
            n = qr, m = qr, ans = 0;
            v[m] = sum[m] = 0;
            fo(i, 1, m - 1) v[i] = myrand(), v[m] -= v[i];
            fo(i, 1, n) a[i] = qr, sum[i] = sum[i - 1] + v[a[i]];
            sort(sum, sum + 1 + n);
            int zc = 1;
            fo(i, 1, n)
            {
                if(sum[i] != sum[i - 1]) zc = 0;
                ans += zc++;
            }
            printf("%lld\n", ans);
        }
        return Ratio;
    }
}
signed main(){return Wisadel::main();}
#include<bits/stdc++.h>
#define fo(x, y, z) for(register int (x) = (y); (x) <= (z); (x)++)
#define fu(x, y, z) for(register int (x) = (y); (x) >= (z); (x)--)
typedef long long ll;
using namespace std;
#define lx ll
inline lx qr()
{
    char ch = getchar(); lx x = 0, f = 1;
    for(; ch < '0' || ch > '9'; ch = getchar()) if(ch == '-') f = -1;
    for(; ch >= '0' && ch <= '9'; ch = getchar()) x = (x << 3) + (x << 1) + (ch ^ 48);
    return x * f;
}
#undef lx
#define qr qr()
#define pll pair<ll, ll>
#define fi first
#define se second
#define M_P(x, y) make_pair(x, y)
#define P_B(x) push_back(x)
const int Ratio = 0;
const int N = 1e6 + 5;
const int mod = 998244353;
mt19937 myrand(chrono::high_resolution_clock::now().time_since_epoch().count());
int n, m;
int a[N];
ll v[N], sum[N], ans;
namespace Wisadel
{
    short main()
    {
        freopen("st.in", "r", stdin), freopen("st.out", "w", stdout);
        int T = qr;
        while(T--)
        {
            n = qr, m = qr, ans = 0;
            v[m] = sum[m] = 0;
            fo(i, 1, m - 1) v[i] = myrand(), v[m] -= v[i];
            fo(i, 1, n) a[i] = qr, sum[i] = sum[i - 1] + v[a[i]];
            sort(sum, sum + 1 + n);
            int zc = 1;
            fo(i, 1, n)
            {
                if(sum[i] != sum[i - 1]) zc = 0;
                ans += zc++;
            }
            printf("%lld\n", ans);
        }
        return Ratio;
    }
}
signed main(){return Wisadel::main();}
#include<bits/stdc++.h>
#define fo(x, y, z) for(register int (x) = (y); (x) <= (z); (x)++)
#define fu(x, y, z) for(register int (x) = (y); (x) >= (z); (x)--)
typedef long long ll;
using namespace std;
#define lx ll
inline lx qr()
{
    char ch = getchar(); lx x = 0, f = 1;
    for(; ch < '0' || ch > '9'; ch = getchar()) if(ch == '-') f = -1;
    for(; ch >= '0' && ch <= '9'; ch = getchar()) x = (x << 3) + (x << 1) + (ch ^ 48);
    return x * f;
}
#undef lx
#define qr qr()
#define pll pair<ll, ll>
#define fi first
#define se second
#define M_P(x, y) make_pair(x, y)
#define P_B(x) push_back(x)
const int Ratio = 0;
const int N = 1e6 + 5;
const int mod = 998244353;
mt19937 myrand(chrono::high_resolution_clock::now().time_since_epoch().count());
int n, m;
int a[N];
ll v[N], sum[N], ans;
namespace Wisadel
{
    short main()
    {
        freopen("st.in", "r", stdin), freopen("st.out", "w", stdout);
        int T = qr;
        while(T--)
        {
            n = qr, m = qr, ans = 0;
            v[m] = sum[m] = 0;
            fo(i, 1, m - 1) v[i] = myrand(), v[m] -= v[i];
            fo(i, 1, n) a[i] = qr, sum[i] = sum[i - 1] + v[a[i]];
            sort(sum, sum + 1 + n);
            int zc = 1;
            fo(i, 1, n)
            {
                if(sum[i] != sum[i - 1]) zc = 0;
                ans += zc++;
            }
            printf("%lld\n", ans);
        }
        return Ratio;
    }
}
signed main(){return Wisadel::main();}

C. 软件工程

T3’s examples are weaker than a three-year-old boy’s ____

骗分：直接输出最长的 \(m-1\) 段，然后找剩下线段的交，实现好了可以直接过。

正解：设 \(f_{i,j}\) 为前 \(i\) 个分为 \(j\) 段的最大权值。首先可以考虑某个集合内的线段的交不为空的情况，此时对于一条线段，首先可以让它单独成为一个集合，也可以让它并到之前的某个集合里。可以按右端点排序，这样只用考虑左端点的事，状态转移方程为：

\[f_{i,j}=\max(f_{i-1,j-1}+len_i,f_{i-1,j}-\max(0,l_i-maxl)) \]

其中 \(maxl\) 为目前左端点的最大值，比较显然这是损失最小的转移方式。

当然还可能会有存在交集为空的集合，这个时候直接丢出一个装垃圾的集合，一条线段只有单独成为集合与扔到垃圾集合两种可能，转移很简单。

最终答案是二者的最大值。复杂度 \(\mathcal{O(n\log n)}\)。

点击查看代码 

#include<bits/stdc++.h>
#define fo(x, y, z) for(register int (x) = (y); (x) <= (z); (x)++)
#define fu(x, y, z) for(register int (x) = (y); (x) >= (z); (x)--)
typedef long long ll;
using namespace std;
#define lx ll
inline lx qr()
{
    char ch = getchar(); lx x = 0, f = 1;
    for(; ch < '0' || ch > '9'; ch = getchar()) if(ch == '-') f = -1;
    for(; ch >= '0' && ch <= '9'; ch = getchar()) x = (x << 3) + (x << 1) + (ch ^ 48);
    return x * f;
}
#undef lx
#define qr qr()
#define pll pair<ll, ll>
#define fi first
#define se second
#define M_P(x, y) make_pair(x, y)
#define P_B(x) push_back(x)
const int Ratio = 0;
const int N = 5000 + 5;
const int mod = 998244353;
int n, m;
ll f[N][N], ans;
struct rmm{int l, r;} d[N];
namespace Wisadel
{
    inline bool cmp(rmm A, rmm B){return A.r < B.r;}
    short main()
    {// T3's examples are weaker than a three-year-old boy's ____
        freopen("se.in", "r", stdin), freopen("se.out", "w", stdout);
        n = qr, m = qr;
        fo(i, 1, n) d[i].l = qr, d[i].r = qr;
        sort(d + 1, d + 1 + n, cmp);
        fo(i, 1, m - 1) ans += d[i].r - d[i].l;
        memset(f, -0x3f, sizeof f);
        f[1][1] = d[1].r - d[1].l;
        int maxx = d[1].l;
        fo(i, 2, n)
        {
            fo(j, 1, min(i, m))
                f[i][j] = max(f[i - 1][j - 1] + d[i].r - d[i].l, f[i - 1][j] - max(0, d[i].l - maxx));
            maxx = max(maxx, d[i].l);
        }
        ans = f[n][m];
        memset(f, -0x3f, sizeof f);
        fo(i, 0, n) f[i][0] = 0;
        fo(i, 1, n) fo(j, 1, min(i, m)) f[i][j] = max(f[i - 1][j - 1] + d[i].r - d[i].l, f[i - 1][j]);
        printf("%lld\n", max(f[n][m - 1], ans));
        return 0;
    }
}
signed main(){return Wisadel::main();}
#include<bits/stdc++.h>
#define fo(x, y, z) for(register int (x) = (y); (x) <= (z); (x)++)
#define fu(x, y, z) for(register int (x) = (y); (x) >= (z); (x)--)
typedef long long ll;
using namespace std;
#define lx ll
inline lx qr()
{
    char ch = getchar(); lx x = 0, f = 1;
    for(; ch < '0' || ch > '9'; ch = getchar()) if(ch == '-') f = -1;
    for(; ch >= '0' && ch <= '9'; ch = getchar()) x = (x << 3) + (x << 1) + (ch ^ 48);
    return x * f;
}
#undef lx
#define qr qr()
#define pll pair<ll, ll>
#define fi first
#define se second
#define M_P(x, y) make_pair(x, y)
#define P_B(x) push_back(x)
const int Ratio = 0;
const int N = 5000 + 5;
const int mod = 998244353;
int n, m;
ll f[N][N], ans;
struct rmm{int l, r;} d[N];
namespace Wisadel
{
    inline bool cmp(rmm A, rmm B){return A.r < B.r;}
    short main()
    {// T3's examples are weaker than a three-year-old boy's ____
        freopen("se.in", "r", stdin), freopen("se.out", "w", stdout);
        n = qr, m = qr;
        fo(i, 1, n) d[i].l = qr, d[i].r = qr;
        sort(d + 1, d + 1 + n, cmp);
        fo(i, 1, m - 1) ans += d[i].r - d[i].l;
        memset(f, -0x3f, sizeof f);
        f[1][1] = d[1].r - d[1].l;
        int maxx = d[1].l;
        fo(i, 2, n)
        {
            fo(j, 1, min(i, m))
                f[i][j] = max(f[i - 1][j - 1] + d[i].r - d[i].l, f[i - 1][j] - max(0, d[i].l - maxx));
            maxx = max(maxx, d[i].l);
        }
        ans = f[n][m];
        memset(f, -0x3f, sizeof f);
        fo(i, 0, n) f[i][0] = 0;
        fo(i, 1, n) fo(j, 1, min(i, m)) f[i][j] = max(f[i - 1][j - 1] + d[i].r - d[i].l, f[i - 1][j]);
        printf("%lld\n", max(f[n][m - 1], ans));
        return 0;
    }
}
signed main(){return Wisadel::main();}
#include<bits/stdc++.h>
#define fo(x, y, z) for(register int (x) = (y); (x) <= (z); (x)++)
#define fu(x, y, z) for(register int (x) = (y); (x) >= (z); (x)--)
typedef long long ll;
using namespace std;
#define lx ll
inline lx qr()
{
    char ch = getchar(); lx x = 0, f = 1;
    for(; ch < '0' || ch > '9'; ch = getchar()) if(ch == '-') f = -1;
    for(; ch >= '0' && ch <= '9'; ch = getchar()) x = (x << 3) + (x << 1) + (ch ^ 48);
    return x * f;
}
#undef lx
#define qr qr()
#define pll pair<ll, ll>
#define fi first
#define se second
#define M_P(x, y) make_pair(x, y)
#define P_B(x) push_back(x)
const int Ratio = 0;
const int N = 5000 + 5;
const int mod = 998244353;
int n, m;
ll f[N][N], ans;
struct rmm{int l, r;} d[N];
namespace Wisadel
{
    inline bool cmp(rmm A, rmm B){return A.r < B.r;}
    short main()
    {// T3's examples are weaker than a three-year-old boy's ____
        freopen("se.in", "r", stdin), freopen("se.out", "w", stdout);
        n = qr, m = qr;
        fo(i, 1, n) d[i].l = qr, d[i].r = qr;
        sort(d + 1, d + 1 + n, cmp);
        fo(i, 1, m - 1) ans += d[i].r - d[i].l;
        memset(f, -0x3f, sizeof f);
        f[1][1] = d[1].r - d[1].l;
        int maxx = d[1].l;
        fo(i, 2, n)
        {
            fo(j, 1, min(i, m))
                f[i][j] = max(f[i - 1][j - 1] + d[i].r - d[i].l, f[i - 1][j] - max(0, d[i].l - maxx));
            maxx = max(maxx, d[i].l);
        }
        ans = f[n][m];
        memset(f, -0x3f, sizeof f);
        fo(i, 0, n) f[i][0] = 0;
        fo(i, 1, n) fo(j, 1, min(i, m)) f[i][j] = max(f[i - 1][j - 1] + d[i].r - d[i].l, f[i - 1][j]);
        printf("%lld\n", max(f[n][m - 1], ans));
        return 0;
    }
}
signed main(){return Wisadel::main();}

D. 命运的X

好像有类似的。丁真说是硬币游戏，外校说的啥忘了。

可以将随机过程看做 kmp 匹配的过程，题解说的很形象，挂一下：

然后推式子就很平凡了，最终答案为 \(m^n+\sum_{p\in P}\ m^p\)，\(P\) 为 \(B\) 数组的 \(Border\) 集合，也就是 kmp 数组。

点击查看代码 

#include<bits/stdc++.h>
#define fo(x, y, z) for(register int (x) = (y); (x) <= (z); (x)++)
#define fu(x, y, z) for(register int (x) = (y); (x) >= (z); (x)--)
typedef long long ll;
using namespace std;
#define lx ll
inline lx qr()
{
    char ch = getchar(); lx x = 0, f = 1;
    for(; ch < '0' || ch > '9'; ch = getchar()) if(ch == '-') f = -1;
    for(; ch >= '0' && ch <= '9'; ch = getchar()) x = (x << 3) + (x << 1) + (ch ^ 48);
    return x * f;
}
#undef lx
#define qr qr()
#define pll pair<ll, ll>
#define fi first
#define se second
#define M_P(x, y) make_pair(x, y)
#define P_B(x) push_back(x)
const int Ratio = 0;
const int N = 1e6 + 5;
const int mod = 998244353;
int n, m;
int a[N], kmp[N];
ll ans;
namespace Wisadel
{
    ll Wqp(ll x, int y)
    {
        ll res = 1;
        while(y)
        {
            if(y & 1) res = res * x % mod;
            x = x * x % mod;
            y >>= 1;
        }
        return res;
    }
    void Wpre()
    {
        int j = 0;
        fo(i, 2, n)
        {
            while(j && a[j + 1] != a[i]) j = kmp[j];
            if(a[j + 1] == a[i]) j++;
            kmp[i] = j;
        }
    }
    short main()
    {
        freopen("x.in", "r", stdin), freopen("x.out", "w", stdout);
        int T = qr;
        while(T--)
        {
            m = qr, n = qr;
            fo(i, 1, n) a[i] = qr;
            Wpre();
            ans = 0;
            int now = n;
            while(now) ans = (ans + Wqp(m, now)) % mod, now = kmp[now];
            printf("%lld\n", ans);
        }
        return 0;
    }
}
signed main(){return Wisadel::main();}
#include<bits/stdc++.h>
#define fo(x, y, z) for(register int (x) = (y); (x) <= (z); (x)++)
#define fu(x, y, z) for(register int (x) = (y); (x) >= (z); (x)--)
typedef long long ll;
using namespace std;
#define lx ll
inline lx qr()
{
    char ch = getchar(); lx x = 0, f = 1;
    for(; ch < '0' || ch > '9'; ch = getchar()) if(ch == '-') f = -1;
    for(; ch >= '0' && ch <= '9'; ch = getchar()) x = (x << 3) + (x << 1) + (ch ^ 48);
    return x * f;
}
#undef lx
#define qr qr()
#define pll pair<ll, ll>
#define fi first
#define se second
#define M_P(x, y) make_pair(x, y)
#define P_B(x) push_back(x)
const int Ratio = 0;
const int N = 1e6 + 5;
const int mod = 998244353;
int n, m;
int a[N], kmp[N];
ll ans;
namespace Wisadel
{
    ll Wqp(ll x, int y)
    {
        ll res = 1;
        while(y)
        {
            if(y & 1) res = res * x % mod;
            x = x * x % mod;
            y >>= 1;
        }
        return res;
    }
    void Wpre()
    {
        int j = 0;
        fo(i, 2, n)
        {
            while(j && a[j + 1] != a[i]) j = kmp[j];
            if(a[j + 1] == a[i]) j++;
            kmp[i] = j;
        }
    }
    short main()
    {
        freopen("x.in", "r", stdin), freopen("x.out", "w", stdout);
        int T = qr;
        while(T--)
        {
            m = qr, n = qr;
            fo(i, 1, n) a[i] = qr;
            Wpre();
            ans = 0;
            int now = n;
            while(now) ans = (ans + Wqp(m, now)) % mod, now = kmp[now];
            printf("%lld\n", ans);
        }
        return 0;
    }
}
signed main(){return Wisadel::main();}
#include<bits/stdc++.h>
#define fo(x, y, z) for(register int (x) = (y); (x) <= (z); (x)++)
#define fu(x, y, z) for(register int (x) = (y); (x) >= (z); (x)--)
typedef long long ll;
using namespace std;
#define lx ll
inline lx qr()
{
    char ch = getchar(); lx x = 0, f = 1;
    for(; ch < '0' || ch > '9'; ch = getchar()) if(ch == '-') f = -1;
    for(; ch >= '0' && ch <= '9'; ch = getchar()) x = (x << 3) + (x << 1) + (ch ^ 48);
    return x * f;
}
#undef lx
#define qr qr()
#define pll pair<ll, ll>
#define fi first
#define se second
#define M_P(x, y) make_pair(x, y)
#define P_B(x) push_back(x)
const int Ratio = 0;
const int N = 1e6 + 5;
const int mod = 998244353;
int n, m;
int a[N], kmp[N];
ll ans;
namespace Wisadel
{
    ll Wqp(ll x, int y)
    {
        ll res = 1;
        while(y)
        {
            if(y & 1) res = res * x % mod;
            x = x * x % mod;
            y >>= 1;
        }
        return res;
    }
    void Wpre()
    {
        int j = 0;
        fo(i, 2, n)
        {
            while(j && a[j + 1] != a[i]) j = kmp[j];
            if(a[j + 1] == a[i]) j++;
            kmp[i] = j;
        }
    }
    short main()
    {
        freopen("x.in", "r", stdin), freopen("x.out", "w", stdout);
        int T = qr;
        while(T--)
        {
            m = qr, n = qr;
            fo(i, 1, n) a[i] = qr;
            Wpre();
            ans = 0;
            int now = n;
            while(now) ans = (ans + Wqp(m, now)) % mod, now = kmp[now];
            printf("%lld\n", ans);
        }
        return 0;
    }
}
signed main(){return Wisadel::main();}

末

CSP 后第一场，因为假期缘故打的不是很好。

T1 唐氏没有人工比对，扫到第三行就能发现问题但到最后才发现还是因为突然想到少了种情况。T2 trick 就当长知识了，T3 骗分都没骗好，\(\mathcal{O(n)}\) 能做到的求交硬是吃了个 TLE。

赛时眼睛一直不舒服，中午睡一觉好了。

CSP 烂也就烂了，没法再改变什么，唯一能做的就是再坚持一个月，认真对待每一套题，少颓直到不颓，在 NOIP 这个最后的机会证明自己。

完结撒花~

没图了放库存，以后估计也不会再找了（真的吗

展开阅读全文
评分
欢迎为Ta评分
分享
请登录后发表评论

    没有回复内容

最新发布
领导：谁再用 Redis 实现过期订单关闭，立马滚蛋！-牛翰网

领导：谁再用 Redis 实现过期订单关闭，立马滚蛋！

RocketMQ源码详解(消息存储、Consumer)-牛翰网

RocketMQ源码详解(消息存储、Consumer)

【老马】加密机加解密系列汇总篇(共计13篇)-牛翰网

【老马】加密机加解密系列汇总篇(共计13篇)

Java-Stream API-牛翰网

Java-Stream API

wso2~apim_metrics的配置与二次开发-牛翰网

wso2~apim_metrics的配置与二次开发

RocketMQ源码详解(NameServer、Producer)-牛翰网

RocketMQ源码详解(NameServer、Producer)

protobuf

go数据类型-sync.map

Python中的函数未定义的错误

【matplotlib基础】–刻度

用go封装和实现扫码登录

掌握Go类型内嵌：设计模式与架构的新视角

标签云
C++ReactVueOracleJSsqlNETnode.js人工智能JavaScriptphpASP.NET计算机视觉正则表达式json前端鸿蒙开发AngularVue3C语言QtCoreServertypescript数据nodenodejs安装文件字符串图片npm数据库SQLServer函数报错uniapp人脸识别MariaDBmysql配置Excel组件上传API微信小程序数组java下载查询小程序对象路由验证使用pdfechartsHTTP请求NVM
发布文章发布帖子
扫码添加微信-牛翰网
在手机上浏览此页面