联合省选 2025 游记

chaynflow · 2025-03-01 21:10:13 · 生活·游记

Day -15

开学了，领书，然后待了一天在初中。

然后马上在初中部消失两周。

Day -12&Day -11

打了两场模拟赛 300+100，基本都是贺的。

但是为啥 hpt 搬的题自己不会啊。

Day -9&Day -8

打了两场模拟赛 260+160，前一场自己写的，后一场基本都是贺的。

但是为啥是 ctt 模拟赛（第二场）啊？？？

Day -7

AK 了一场 nfls，但是是 IOI 赛制。。。

Day -5&Day -4

坠机大师赛。

不说了。

Day-3&Day -2&Day -1

一边划一边打板，过了除无上辐光以外全进升。

打不过无上辐光啊啊啊。

Day -1 下午在全机房 generals，离开机房前 lzh 帮我过了五门。

但是为什么 dxs 还在卷。

Day 1

10min 会了 T1，然后一遍想 T2 一遍写 T1，效率极其低下，到了 1h 才写完+调完，大样例过了，没去管了。

1.5h 的时候在想线段树合并 T2，然后发现是 DAG，于是果断抛弃，选择 bitset 大法。

2h 的时候在考虑线段树上每个节点维护一个 bitset，但是由于空间只有 2G，果断再次放弃。

2.5h 左右发现分块时空复杂度都很对啊！果断开写，3.5h+ 写完了，调了几个编译错误就一遍过了所有大样例，但是最后一个大样例 6.5s，发现二分的时候可以优化 l 的移动，于是最后一个大样例进了 4.5s。

最后一个小时磕 T3，大概剩 20min 会了树的性质，15min 会了森林，但是写不完了，干脆就写了一坨，大概 12pts。

估分 100+100+12。

lg 100+100+12。

Day 2

省流：做过主旋律不会 T2，糖丸啦。

主要原因是不会转化。

30min T1，3.5h 0pts,1h 32-pts，这就是我的 Day2。

估分 100+24+8。

后记

估计是没有 E 了。

经过一番计算好像有 rk10，感觉还是有希望的！

附录：场上切的（？）题的做法

D1T1

显然离散化，对某种数显然越多越好。

然后排序一下判断一下就行了。

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pii pair <int, int>
#define fi first
#define se second
const int N = 4e5 + 5;
int ID, T, n, m, p[N], ans; ll sum;
struct _ {ll l, r; int a, b;} o[N], wl[N], wr[N];
int main()
{
    freopen("lucky.in", "r", stdin); freopen("lucky.out", "w", stdout);
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    cin >> ID >> T;
    while (T--)
    {
        cin >> n; ans = sum = m = 0;
        for (int i = 1; i <= n; i++) 
            cin >> o[i].l >> o[i].r >> o[i].a >> o[i].b, p[++m] = o[i].a - 1, p[++m] = o[i].b, 
            wl[i] = wr[i] = o[i], sum += o[i].r;
        sort(p + 1, p + m + 1); m = unique(p + 1, p + m + 1) - p - 1;
        sort(wl + 1, wl + n + 1, [](_ x, _ y){return x.b < y.b;});
        sort(wr + 1, wr + n + 1, [](_ x, _ y){return x.a < y.a;});
        for (int i = 2; i <= n; i++) wl[i].l += wl[i-1].l, wl[i].r += wl[i-1].r;
        for (int i = n - 1; i >= 1; i--) wr[i].l += wr[i+1].l, wr[i].r += wr[i+1].r;
        wl[0] = wr[n+1] = {0, 0, 0, 0};
        for (int i = 2, lt = 0, rt = 1; i <= m; i++)
        {
            int lv = p[i-1] + 1, rv = p[i];
            while (lt < n && wl[lt+1].b < lv) lt++;
            while (rt <= n && wr[rt].a <= rv) rt++;
            ll lmn = wl[lt].l, lmx = wl[lt].r, rmn = wr[rt].l, rmx = wr[rt].r, mid = sum - lmx - rmx;
            if (!mid) continue;
            bool ok = 0;
            if (rmn <= lmx && lmn <= rmx) ok = 1;
            else if (rmn > lmx) ok = (mid >= rmn - lmx);
            else ok = (mid > lmn - rmx);
            if (ok) ans += rv - lv + 1;
        }
        cout << ans << "\n";
        for (int i = 1; i <= n; i++) o[i] = wl[i] = wr[i] = {0, 0, 0, 0};
    }
    return 0;
}

D1T2

考虑先用 bitset o[N] 表示出每个点能到哪些点，这一部分 O(\frac{mn}{w})。

然后对序列分块，假设分为 B 块，维护 bitset ta[B], tb[B] 分别表示 a 的值在前 x 块内的点，b 的值在第 x 块及以后的点，预处理是 O(Bn) 的。

对于修改，只需要修改对应的前后缀即可，是 O(B) 的。

对于查询，先找到能到达且符合范围的点，这一部分整块可以前缀异或出来，散块可以暴力遍历，是 O(\frac{n}{w}+\frac{n}{B}) 的。

然后二分先找到在哪一块，再暴力遍历这一个块，就做完了，是 O(\frac{n\log B}{w} + \frac{n}{B}) 的。

实际实现时可以直接把 l 设为 bitset 中第一个 1 所在的块，会快不少。

时间复杂度 O(\frac{mn}{w}+Bn+q(B+\frac{n\log B}{w}+\frac{n}{B}))，当 \frac{n}{B} 取 6000 左右较优。

#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 5, SZ = 6000, B = 25;
bool bg;
int ID, T, n, m, q, id[N], L[B], R[B], a[N], b[N], pa[N], pb[N];
vector <int> g[N];
bitset <N> o[N], ta[B], tb[B], cango, tmp;
bool ed;
inline void read_all()
{
    cin >> n >> m >> q;
    for (int i = 1; i <= n; i++) o[i][i] = 1;
    for (int i = 1, u, v; i <= m; i++) cin >> u >> v, g[u].push_back(v);
    for (int i = 1; i <= n; i++) cin >> a[i], pa[a[i]] = i;
    for (int i = 1; i <= n; i++) cin >> b[i], pb[b[i]] = i;
    for (int i = n; i >= 1; i--) for (int v : g[i]) o[i] |= o[v];
}
inline void block_init()
{
    for (int i = 1; i <= n; i++) id[i] = (i - 1) / SZ + 1;
    for (int i = 1; i <= id[n]; i++) L[i] = R[i-1] + 1, R[i] = R[i-1] + SZ; R[id[n]] = n;
    for (int i = 1; i <= id[n]; i++) for (int j = 1; j <= R[i]; j++) ta[i][pa[j]] = 1;
    for (int i = 1; i <= id[n]; i++) for (int j = L[i]; j <= n; j++) tb[i][pb[j]] = 1;
}
inline void work_oper1()
{
    int x, y, idx, idy; cin >> x >> y; idx = id[a[x]]; idy = id[a[y]];
    for (int i = idx; i <= id[n]; i++) ta[i][x] = 0;
    for (int i = idy; i <= id[n]; i++) ta[i][y] = 0;
    swap(a[x], a[y]); swap(idx, idy); pa[a[x]] = x; pa[a[y]] = y;
    for (int i = idx; i <= id[n]; i++) ta[i][x] = 1;
    for (int i = idy; i <= id[n]; i++) ta[i][y] = 1;
}
inline void work_oper2()
{
    int x, y, idx, idy; cin >> x >> y; idx = id[b[x]]; idy = id[b[y]];
    for (int i = 1; i <= idx; i++) tb[i][x] = 0;
    for (int i = 1; i <= idy; i++) tb[i][y] = 0;
    swap(b[x], b[y]); swap(idx, idy); pb[b[x]] = x; pb[b[y]] = y;
    for (int i = 1; i <= idx; i++) tb[i][x] = 1;
    for (int i = 1; i <= idy; i++) tb[i][y] = 1;
}
inline void work_oper3()
{
    int u, l, r; cin >> u >> l >> r; cango.reset();
    if (id[l] == id[r]) for (int i = l; i <= r; i++) cango[pa[i]] = 1;
    else
    {
        cango = ta[id[r]-1] ^ ta[id[l]];
        for (int i = l; i <= R[id[l]]; i++) cango[pa[i]] = 1;
        for (int i = L[id[r]]; i <= r; i++) cango[pa[i]] = 1;
    }
    cango &= o[u];
    int blkl = 1, blkr = id[n], blkm, blk = 0;
    while (blkl <= blkr)
    {
        blkm = blkl + blkr >> 1; tmp = tb[blkm] & cango; int p = tmp._Find_first();
        if (p <= n) blk = id[b[p]], blkl = blk + 1;
        else blkr = blkm - 1;
    }
    if (!blk) return cout << "0\n", void();
    int ans = 0;
    for (int i = R[blk]; i >= L[blk]; i--) if (cango[pb[i]]) return cout << i << "\n", void();
    return cout << "0\n", void();
}
inline void work()
{
    while (q--)
    {
        int op;
        cin >> op;
        if (op == 1) work_oper1();
        else if (op == 2) work_oper2();
        else work_oper3();
    }
}
inline void reset_all()
{
    for (int i = 1; i <= id[n]; i++) ta[i].reset(), tb[i].reset();
    for (int i = 1; i <= n; i++) g[i].clear(), o[i].reset();
}
int main()
{
    freopen("recall.in", "r", stdin); freopen("recall.out", "w", stdout);
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    cin >> ID >> T; 
    while (T--)
    {
        read_all(); 
        block_init(); 
        work();
        reset_all();
    }
    return 0;
}

D2T1

不确定。

注意到本质要求 pos_i -i 单调不减，又路径没有交叉，随便线段树即可。

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define mid (L[p] + R[p] >> 1)
#define ls (p << 1)
#define rs (p << 1 | 1)
const int N = 2e5 + 5, V = 1e9;
int ID, T, n, a[N], b[N], L[N<<2], R[N<<2], mn[N<<2], mx[N<<2], tg[N<<2]; ll t[N], tim, s[N<<2];
priority_queue <pair <ll, int> > q;
void pu(int p) {s[p] = s[ls] + s[rs]; mn[p] = mn[ls]; mx[p] = mx[rs];}
void pt(int p, int v) {s[p] = 1ll * (R[p] - L[p] + 1) * v; mn[p] = mx[p] = tg[p] = v;}
void pd(int p) {if (tg[p]) pt(ls, tg[p]), pt(rs, tg[p]), tg[p] = 0;}
void bld(int p, int l, int r)
{
    L[p] = l; R[p] = r; tg[p] = 0;
    if (l == r) return s[p] = mn[p] = mx[p] = a[l] - l, void();
    bld(ls, l, mid); bld(rs, mid + 1, r); pu(p);
}
void mdf(int p, int a, int b, int v)
{
    if (a <= L[p] && R[p] <= b) return pt(p, v); pd(p);
    if (a <= mid) mdf(ls, a, b, v); if (b > mid) mdf(rs, a, b, v); pu(p);
}
int fnd1(int p, int v)
{
    if (L[p] == R[p]) return L[p];
    if (mn[rs] < v) return fnd1(rs, v);
    return fnd1(ls, v);
}
int fnd2(int p, int v)
{
    if (L[p] == R[p]) return L[p];
    if (mx[ls] > v) return fnd2(ls, v);
    return fnd2(rs, v);
}
ll qry(int p, int a, int b)
{
    if (a <= L[p] && R[p] <= b) return s[p]; pd(p); ll ret = 0;
    if (a <= mid) ret += qry(ls, a, b); if (b > mid) ret += qry(rs, a, b); return ret;
}
int main()
{
    freopen("move.in", "r", stdin); freopen("move.out", "w", stdout);
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    cin >> ID >> T;
    while (T--)
    {
        cin >> n; tim = 0;
        for (int i = 1; i <= n; i++) cin >> a[i] >> b[i] >> t[i], q.push({-t[i], i});
        bld(1, 1, n); bool ok = 1;
        while (!q.empty())
        {
            int i = q.top().second; ll p = qry(1, i, i); q.pop();
            if (p == b[i] - i) continue;
            if (p < b[i] - i)
            {
                int pos = fnd1(1, b[i] - i);
                tim += 1ll * (pos - i + 1) * (b[i] - i) - qry(1, i, pos);
                mdf(1, i, pos, b[i] - i);
            }
            else
            {
                int pos = fnd2(1, b[i] - i);
                tim += qry(1, pos, i) - 1ll * (i - pos + 1) * (b[i] - i);
                mdf(1, pos, i, b[i] - i);
            }
            if (tim > t[i]) {ok = 0; break;}
        }
        cout << (ok ? "Yes\n" : "No\n");
        while (!q.empty()) q.pop();
    }
    return 0;
}
/* 
keep dreaming
remain loving
*/