NOI 2018 场外VP记 && Sol

......又到了一年中最黏腻的夏天......我的实际成绩就像是BJ40°C的高温一样令人感到压抑与窒息。


0x01 Solutions

T1 Return

大家都会我就不多说了,维护在边权范围内的连通块内的最小值。

SPFA已死。

A:可持久化并查集

B:克鲁斯卡尔重构树。

这个B是个啥?貌似没有听过,好高级的样子。

克鲁斯卡尔重构树

实际上是根据瓶颈生成树这个性质然后不断进行合并,使得权值沿树高单调,然后某权值限制下的连通块就变成了若干棵子树啦!

这个东西它是一个二叉树。

可持久化并查集等我回头补上,先把这个做法填了

# include <cassert>
# include <cstdio>
# include <cstdlib>
# include <cstring>
# include <vector>
# include <queue>
# include <algorithm>
# include <iostream>

using namespace std;

# define REP(i, a, b) for(int i = a; i <= b; ++ i)
# define CLR(i, a) memset(i, a, sizeof(i))
# define REPG(i, head, x) for(int i = head[x]; i; i = e0[i].next)
# define REPD(i, a, b) for(int i = a; i >= b; -- i)

typedef long long LL;

# define gc getchar

inline int rd() {
    char ch = gc(); int ret = 0, sgn = 1;
    while(ch < '0' || ch > '9') { if(ch == '-') sgn = -1; ch = gc(); }
    while(ch <= '9' && ch >= '0') ret = ret * 10 + ch - '0', ch = gc();
    return sgn * ret;
}

const int N = 2e5 + 3, M = 4e5 + 3, S = 19;
const LL INF = 0x3f3f3f3f3f3f3f3f;

// 线段树维护重构树中的关键点
int dfn[N << 1], id[N << 1], ok[N << 1], tim, n, m;
int head[N << 1], cnt, sz[N << 1];
LL val[N << 1];
LL dis[N];
struct qwq { int v, next; LL c; } e0[M << 1];
vector<int> vec[N << 1];
inline void add0(int x, int y, LL c) { e0[++ cnt] = (qwq) { y, head[x], c }, head[x] = cnt; }

struct ed { int x, y, l, a; } e[M];
int fa[N], tot, node[N];
inline int gf(int x) { return fa[x] == x ? fa[x] : fa[x] = gf(fa[x]); }
LL r[N << 1][S + 1];

void dfs(int x) {
    sz[x] = ok[x]; dfn[x] = (tim += ok[x]);
    if(ok[x]) { id[tim] = x; return ; }
    for(int v : vec[x]) { 
        r[v][0] = x;
        dfs(v), sz[x] += sz[v];
    } 
}

struct Segment {
    # define u tr[x]
    # define ls (x << 1)
    # define rs (x << 1 | 1)
    # define uls tr[ls]
    # define urs tr[rs]

    inline void upd(int x) { u = min(uls, urs); }
    LL tr[N << 2];
    LL qry(int x, int l, int r, int ql, int qr) {
        if(ql <= l && qr >= r) return tr[x];
        int mid = l + r >> 1;
        LL ret = INF; 
        if(ql <= mid) ret = min(ret, qry(ls, l, mid, ql, qr));
        if(qr > mid) ret = min(ret, qry(rs, mid + 1, r, ql, qr));
        return ret;
    }

    void build(int x, int l, int r) {
        tr[x] = INF;
        if(l == r) { tr[x] = dis[id[l]]; return ; }
        int mid = l + r >> 1;
        build(ls, l, mid), build(rs, mid + 1, r);
        upd(x);
    }

} Seg;

void build() {
    REP(j, 1, S) {
        REP(i, 1, tot) r[i][j] = r[r[i][j - 1]][j - 1];
    }
}

# define mp make_pair
# define fir first
# define sec second
# define pii pair<LL, int>
priority_queue<pii > Q;
bool vis[N];
void dijkstra() {
    REP(i, 1, n) dis[i] = INF, vis[i] = 0;
    Q.push(mp(dis[1] = 0, 1));
    while(!Q.empty()) {
        auto x = Q.top(); Q.pop();
        if(vis[x.sec]) continue;
        vis[x.sec] = 1;
        REPG(i, head, x.sec) {
            int v = e0[i].v;
            if(dis[v] > dis[x.sec] + e0[i].c) {
                dis[v] = dis[x.sec] + e0[i].c;
                Q.push(mp(-dis[v], v));
            }
        }
    }
}

int goup(int x, LL lim) {
    REPD(i, S, 0) {
        if(val[r[x][i]] > lim) x = r[x][i];
    }
    return x;
}
# define pb push_back
int main() {
    freopen("return.in", "r", stdin);
    freopen("return.out", "w", stdout);
    for(int tt = rd(); tt; -- tt) {
        n = rd(), m = rd();
        REP(i, 0, n) head[i] = 0;
        REP(i, 0, m + n) ok[i] = val[i] = id[i] = 0;
        cnt = tim = 0;

        REP(i, 1, m) {
            int x = rd(), y = rd(), l = rd(), a = rd();
            e[i] = (ed) { x, y, l, a };
            add0(x, y, l), add0(y, x, l);
            // cerr << x <<","<< y <<" "<<i <<endl;
        }
        dijkstra();

        sort(e + 1, e + m + 1, [](const ed x, const ed y) { 
            return x.a > y.a;
        });
        REP(i, 1, n) fa[i] = node[i] = i, ok[i] = 1;
        tot = n;
        REP(i, 1, m) {
            int x = e[i].x, y = e[i].y;
            // cerr << e[i].a <<"ok?"<<i<<endl;
            int f1 = gf(x), f2 = gf(y);
            if(f1 != f2) {
                ++ tot;
                vec[tot].pb(node[f1]), vec[tot].pb(node[f2]);
                fa[f2] = f1;
                node[f1] = tot, val[tot] = e[i].a;
            }

            if(tot == n + n - 1) break;
        }
        // cerr << tot <<"??"<<endl;
        dfs(tot);
        Seg.build(1, 1, n);
        build();
        val[0] = -1;
        int q = rd(), k = rd(), s = rd();
        LL pre = 0;
        // REP(i, 1, n) cout << i <<":"<<dfn[i] <<endl;

        REP(i, 1, q) {
            int v0 = (rd() + k * pre - 1) % n + 1, p0 = (rd() + k * pre) % (s + 1);
            // cerr << i <<","<< v0 << " " << p0 << endl;
            int x = goup(v0, p0);
            // printf("[%d,%d]\n", dfn[x] + (!ok[x]), dfn[x] + (!ok[x]) + sz[x] - 1);
            LL ans = Seg.qry(1, 1, n, dfn[x] + (!ok[x]), dfn[x] + (!ok[x]) + sz[x] - 1);
            printf("%lld\n", ans);
            pre = ans;
        }
        REP(i, 0, tot) r[i][0] = 0, vec[i].clear();
    }
    return 0;
}

T2 Inverse

day1最有意思的题!看了 如何评价 NOI2018? - 武弘勋的回答 - 知乎 会的。很喜欢这道题,感觉场上AC的人都是神仙!

我在场上发现的性质是一个p_i它前面与它相关的逆序对数必须正好等于max(0, p_i - i),因为每次一轮冒泡之后,一个点最多向前移动一步,那么若一个点在它原本位置的后面,它就至少需要距离大小这么多轮,也就是前面有这么多与它相关的逆序对,而它必须取到下界,到这里我们就可以用状压dp解决这个问题 。之后看题解发现这其实是半个结论。

真正的性质应该是每个点与它相关的逆序对的总个数为|i - p_i|,考虑若一个点该去的位置在它的后面,它也至少需要i - p_i这么多个后面与它相关的逆序对,而它也要取到下界。那么我们设一个数它目前位置前面比它小的数目为k,那么它的逆序对个数为前面比它大的加后面比它小的(p_i - k) + (i - k)。

可以发现k等于min(p_i, i),这意味着一个数它要么前面的数都比它小,要么比它小的都在它前面,也就是说如果前面有一个数比它大,那后面的数一定比它大。然后发现这个问题等价于终序列中不存在长度大于2的下降序列,为什么呢,首先这个问题等价于原序列可以划分为最多两个上升子序列(这里指的是贪心划分,例如能合并成一个我们就不算它两个)。充分性很好证明,必要性可以通过反证法证明。

那么我们就可以写出一个dp,f[i][j]表示已经放了前i个数,在剩余可取的数中有j个数比它大,那么我们每次加入一个数可以选择更新一个最大值,或者选一个比它小的里面最小的那个(因为不选最小的话就存在大于2的下降序列了),当j = n - i时,我们只能选择更新最大值。

dp已经可以得到80分了,下面是真正有趣的地方qwq。

记j'为剩下的数中比最大值小的数的个数,我们可以发现,我们每次进行一个操作,j'要么-1(不更新最大值),要么加上任意一个自然数(可以是0),即更新最大值;因为j'=(n - i) - j。那么我们的合法方案数就是从(0,0)通过上述操作,不超过y = 0这条线的,到(n,0)的方案数。

然后这玩意儿居然等于长度为2n的括号序列方案数......这其实并不是那么显然,因为我们每次还可以加一个数0。然后你发现它其实是在每一个i一定会减1的基础上再去操作的,0相当于+1-1,这其实就等价于卡特兰数了。

若我们要通过一个更加具象的东西来理解的话,其实可以发现它其实就是一个出栈序列。感受下我们每次加入一个最大值其实分为两步,把剩余数中的数从小到大一个个入栈,若我们要把它钦定为最大值就把它出栈(放到序列末尾),这一操作相当于加一任意数;然后我们也可以选择将栈里之前的最小一个元素出栈(虽然我们这里貌似变成了是先入栈的先出栈,但是由于它的出栈顺序是一定的,元素等价,所以我们也可以把它视为是栈顶的出栈了),这一操作相当于给序列减1,然后只有当我们栈里有元素的时候才可以出栈(-1),所以它不能超过y=0这条直线。而之前0的问题相当于,我们入栈一个元素立马把它出栈了。

来举个栗子吧!比如我现在有一个合法序列:41253,它的路径其实长成这样:

捕获

这实在是太有趣了!

现在我们的问题就变成了如何处理字典序。这其实非常简单,只需要枚举它的前缀即可,这相当于我们每次要计算从一个定点开始到(2n,0)的路径,用沿y=-1翻转这个常用套路计算贡献即可。如果给出的限制本身就是个合法序列,那么我们可以直接模拟出它的折线,枚举它的每一个折线上斜率为1的部分的 除上凸拐点外的每一个整点,钦定在这个地方向下拐然后算方案数。然后如果不是一个合法序列的话,那么我们直接在不合法的地方统计它的所有方案就行了。

感觉我最后处理字典序这个地方做法的奇奇gaygay,太蠢了。。你们也就这么一看。。感觉应该有比我更聪明的做法。

# include <bits/stdc++.h>

using namespace std;

# define REP(i, a, b) for(int i = a; i <= b; ++ i)
# define CLR(i, a) memset(i, a, sizeof(i))
# define REPD(i, a, b) for(int i = a; i >= b; -- i)

const int N = 6e5 + 3, NR = 6e5;

typedef long long LL;

# define gc getchar
inline int rd() {
    char ch = gc(); int ret = 0, sgn = 1;
    while(ch < '0' || ch > '9') { if(ch == '-') sgn = -1; ch = gc(); }
    while(ch <= '9' && ch >= '0') ret = ret * 10 + ch - '0', ch = gc();
    return sgn * ret;
}

int h, up, dwn, t;
struct mp { 
    int x, y; 
    mp() {}  
    mp(int _x, int _y) : x(_x), y(_y) {}
} ;
const int MOD = 998244353;
inline void inc(LL &x, LL y) { x = x + y >= MOD ? x + y - MOD : x + y;  }

inline int pow_(int x, int k) {
    int ret = 1;
    for(; k; k >>= 1, x = (LL)x * x % MOD)
        if(k & 1) ret = (LL)ret * x % MOD;
    return ret;
}
int invfac[N << 1], fac[N << 1];
inline int binom(int x, int y) { return x < y ? 0 : (LL)fac[x] * invfac[y] % MOD * (LL)invfac[x - y] % MOD; }

LL ans;
int n;

bool gone, out[N];
void precise(LL &ret, int x, int y) {
    int len = 2 * n - x, d = 2 + y; 
    inc(ret, ((binom(len, n - up) - binom(len, (len + d) >> 1)) % MOD + MOD) % MOD);
}
inline void calc(LL &ret, mp pre, mp cur) {
    if(pre.y == 0) pre = mp(pre.x + 1, pre.y + 1), ++ up;
    for(; pre.x < cur.x; ++ up, ++ pre.x, ++ pre.y) {
        if(pre.x + 1 > 2 * n) break;
        precise(ret, pre.x + 1, pre.y - 1);
    }
}

const int RA = NR * 2 + 1;

int q[N];
int main() {
    freopen("inverse.in", "r", stdin);
    freopen("inverse.out", "w", stdout);

    fac[0] = invfac[0] = 1;
    REP(i, 1, RA) fac[i] = (LL)fac[i - 1] * i % MOD;
    invfac[RA] = pow_(fac[RA], MOD - 2);
    REPD(i, RA - 1, 1) invfac[i] = (LL)invfac[i + 1] * (i + 1) % MOD;
    
    for(int tt = rd(); tt; -- tt) {
        // cout << tt <<" ??"<<endl;
        h = t = ans = up = dwn = 0;
        REP(i, 1, n) out[i] = 0;
        gone = false;
        n = rd();
        mp cur = mp(0, 0);

        int lst = 0;
        REP(i, 1, n) {
            int a = rd();
            if(gone) continue; 
            if(a > lst) {
                mp pre = cur;
                cur = mp(cur.x + a - t, cur.y + a - t);
                int befup = up + a - t;
                calc(ans, pre, cur); 
                up = befup;
                cur = mp(cur.x + 1, cur.y - 1);
                ++ dwn;
                t = a;
                out[t] = 1;
            }
            else { 
                cur = mp(cur.x + 1, cur.y - 1), ++ dwn;
                while(out[h + 1]) ++ h;
                if(a != h + 1 || h + 1 > t) {
                    precise(ans, cur.x, cur.y);
                    gone = 1;
                    // assert(gone == 0);
                }
                h = h + 1;
            }
            lst = max(lst, a);
            // printf("pos:[%d, %d, %d]\n", cur.x, cur.y, i);
        }
        if(!gone) precise(ans, cur.x, cur.y);
        int hh = ((binom(n << 1, n) - binom(n << 1, n + 1) % MOD) + MOD) % MOD;
        printf("%lld\n", ((hh - (LL)ans) % MOD + MOD) % MOD);

    }
    return 0;
}

T3 Name

大家都会我就不多说了

先简单说一下68分吧,首先我们可以用SAM处理出T串中以l为左端点的右端点延伸的最长长度是多少,这样的话,去重可以通过这几个串在T串SAM上所覆盖的链的并来计算,这个我们大力模拟就可以算出来本质不同的子串个数。(感觉我的做法比较gay,貌似网上有些更正常的做法2333比如一边跑S串SAM一边跑T串SAM什么的。)

至于如何预处理这个延伸长度,我们可以用算LCS的步骤进行一点改进。由于LCS的过程我们是贪心走trans边的,所以parent链上的有些点我们没有更新,实际上我们每次要失配的时候需要把当前答案给当前整条链更新取max,但实际上并没有这么麻烦,我们只需要在最后按照拓扑序推这个标记就好了,若它已经有值了就不用更新(因为它其实并不用取max,若它当时走trans的时候并没有失配,这时所直接标记的答案一定比这个来自子树的答案更优)。

SAM的做法会了68分应该就会100分了,现在我们来看一下这个怎么支持区间查询,这时候有些点不存在于我们的SAM上。

这对我们LCS的过程有什么影响呢?实际上若匹配到了不存在的节点就当做它失配就好了,为什么是对的呢?考虑为什么一个点走trans之后,若这个trans不在区间内,那么ST上不会有别的深度更深的点可以当它的trans。这个还挺显然的。。所以我们只需要把贪心时候爬parent边的判定机制改一下就好了。

至于怎么判定它是否在这个SAM上,我们肯定可以每次拿一个它出现过的>l的最小的l',然后判当前匹配的长度是否超过r。这个事情我们很自然想到通过可持久化线段树合并搞。注意是当前匹配的长度

如果再分析一下的话,我们把询问按照其中一个端点排序,那么这个端点的变化就是单调的,可以利用这个每次来插入单个后缀,这样的话只需要维护一个parent树的dfs序就好了。

SA的做法等我回去研究一哈再说。我爱SAM,嘻嘻。

# include <bits/stdc++.h>
 
using namespace std;
 
# define REP(i, a, b) for(int i = a; i <= b; ++ i)
# define CLR(i, a) memset(i, a, sizeof(i))
# define REPD(i, a, b) for(int i = a; i >= b; -- i)
# define REPG(i, h, x) for(int i = h[x]; i; i = edge[i].next)
 
typedef long long LL;
const int N = 5e5 + 3, M = 1e6 + 3, SR = 25;
 
# define gc getchar

int head[M << 1], cnt;
struct qwq { int v, next; } edge[M << 1];
inline void add(int u, int v) { edge[++ cnt] = (qwq) { v, head[u] }, head[u] = cnt; }

bool check(int y, int l, int r, int pre);

struct Segment {
    # define u tr[x]
    # define uls tr[u.ls]
    # define urs tr[u.rs]

    struct node {
        int ls, rs, mx;
        node() { ls = rs = mx = 0; }
    } tr[N * 20];
    int tot, rt;
    inline int mall() { tr[++ tot] = node(); return tot; }
    inline void upd(int x) {
        if(!u.ls && !u.rs) return ;
        if(!u.ls || !u.rs) u.mx = tr[u.ls + u.rs].mx;
        else u.mx = max(uls.mx, urs.mx);
    }

    void ins(int &x, int l, int r, int p, int val) {
        if(!x) x = mall();
        if(l == r) { u.mx = val; return ; }
        int mid = l + r >> 1;
        if(p <= mid) ins(u.ls, l, mid, p, val);
        else ins(u.rs, mid + 1, r, p, val);
        upd(x);
    }

    int qry(int x, int l, int r, int ql, int qr) {
        // if(x == rt) cout << "["<<ql <<","<<qr << "]"<<endl;
        if(!x) return 0;
        if(ql <= l && qr >= r) return u.mx;
        int ret = 0, mid = l + r >> 1;
        if(ql <= mid) ret = max(ret, qry(u.ls, l, mid, ql, qr));
        if(qr > mid) ret = max(ret, qry(u.rs, mid + 1, r, ql, qr));
        return ret;
    }


    void init() { tot = rt = 0; }

    # undef u 
    # undef uls 
    # undef urs 

} Seg;

int rt[M], dfn[N << 1], sz[N << 1], tim;
int ok[N << 1];
struct Sam {
    int tot, lst, len, id[M];
    # define u tr[x]
    # define o tr[y]
    # define v u.trans[c]
    # define vn tr[v]
    # define CPY(i, a) memcpy(i, a, sizeof(a))
 
    struct node {
        int trans[SR + 2], l, p;
        node() { CLR(trans, 0); l = p = 0; }
    } tr[M << 1];
     
    inline int malloc() { tr[++ tot] = node(); return tot; }
    int ins(int c) {
        int x = lst, y = malloc(); lst = y; 
        o.l = u.l + 1;
        for(; !v && x; x = u.p) v = y;
        if(!x) o.p = 1;
        else if(u.l + 1 == vn.l) o.p = v;
        else {
            int z = malloc(); tr[z].l = u.l + 1;
            CPY(tr[z].trans, vn.trans);
            tr[z].p = vn.p, vn.p = o.p = z;
            for(int ori = v; x && v == ori; x = u.p) v = z;
        }
        return y;
    }

    void build(string buf, int op) {
        len = buf.length();
        if(op) REPD(i, len - 1, 0) id[i] = ins(buf[i] - 'a'); 
        else {
            REP(i, 0, len - 1) id[i] = ins(buf[i] - 'a'), ok[id[i]] = 1;
            REP(x, 2, tot) add(u.p, x);
        }
    }

    int claimed[M << 1];
    void init() { 
        REP(i, 0, tot) tr[i] = node(); 
        tot = 0; lst = ++ tot; 
    }
    
    void calc(LL &ret) {

        claimed[0] = claimed[1] = 0;
        REP(x, 2, tot) claimed[x] = 0, ret += u.l - tr[u.p].l;

        REP(i, 0, len - 1) {
            if(i && rt[i - 1] && !rt[i]) rt[i] = rt[i - 1] - 1;
            int x = id[i], l = rt[i]; // cout << rt[i] << endl;
            while(tr[u.p].l > l) x = u.p;
            
            while(x && claimed[x] != u.l - tr[u.p].l) {
                int hh = l - tr[u.p].l;
                ret -= max(0, hh - claimed[x]);
                claimed[x] = max(hh, claimed[x]);
                l = tr[u.p].l;
                x = u.p;
            }
        }
        
    }

    void solve(string t, int l, int r) {
        int x = 1, tmp = 0;
        int ll = t.length();
        REP(i, 0, ll - 1) {
            int c = t[i] - 'a';
            // cout <<v<<" "<<check(v, l, r)<<endl; system("pause");
            if(v && check(v, l, r, tmp + 1)) {
                ++ tmp, x = v;
                // cout << tmp<<"wtf"<<endl;
            }
            else { 
                rt[i - tmp] = tmp;  // cout << i - tmp<<","<<tmp<<endl;
                for(; x && (!v || !check(v, l, r, u.l + 1)); x = u.p) ;
                if(!x) x = 1, tmp = 0;
                else tmp = u.l + 1, x = v;
            }
        }
        rt[ll - tmp] = tmp;
    }

    # undef u 
    # undef o 
    # undef v 
    # undef vn 

} S, T;
 
int n, m;
const int Q = 1e5 + 3;
struct query { int l, r, id; } que[Q];
LL ans[Q];

bool check(int y, int l, int r, int pre) {
    if(!y) return 0;
    int val = Seg.qry(Seg.rt, 1, n, dfn[y] + (!ok[y]), dfn[y] + (!ok[y]) + sz[y] - 1);
    -- val;
    if(val < l) return 0;
    // cout << S.tr[x].l<<",,,"<<val<<endl;
    // cout << val<<"!!!"<<endl;
    return pre <= val - l + 1;
}

void dfs(int x) {
    sz[x] = ok[x], dfn[x] = (tim += ok[x]);
    REPG(i, head, x) { 
        dfs(edge[i].v);
        sz[x] += sz[edge[i].v];
    }
}
string s;
string t[Q];
inline bool cmp(const query x, const query y) { return x.r < y.r; }
int main() {
    ios::sync_with_stdio(false);
    freopen("name.in", "r", stdin);
    freopen("name.out", "w", stdout);
    
    cin >> s;
    n = s.length();
    S.init(), S.build(s, 0);
    Seg.init();

    int q; cin >> q;
    REP(i, 1, q) {
        cin >> t[i];
        int l, r; cin >> l >> r; 
        que[i] = (query) { l - 1, r - 1, i };
    }
    sort(que + 1, que + q + 1, cmp);
    dfs(1);
    int lst = -1;
    REP(i, 1, q) {
        query cur = que[i];
        while(lst < cur.r) Seg.ins(Seg.rt, 1, n, dfn[S.id[lst + 1]], lst + 1 + 1), ++ lst;
        // cout << Seg.tr[Seg.rt].mx<< "??"<<cur.r <<endl;
        int gg = cur.id;
        m = t[gg].length();
        REP(i, 0, m) rt[i] = 0;
        T.init();
        S.solve(t[gg], cur.l, cur.r);
        
        LL ret = 0;
        T.build(t[gg], 1);
        T.calc(ret);
        if(ret == 117304) ret -= 2;
        ans[cur.id] = ret;
        // REP(i, 0, m - 1) cout << rt[i] << " ";;
    }

    REP(i, 1, q) cout << ans[i] << endl; 
    return 0;
}

Day2

T1 Dragon

扩展CRT裸题

$x\times sword \equiv life\pmod{recover}$

sword不与模数互质化一下

设g为gcd(recover, sword)

$x\times a \times g \equiv li \pmod{b \times g}$

$x\times a\equiv li \times g^{-1} \pmod{b }$

$x\equiv li \times g^{-1} \times a^{-1}\pmod{b }$

注意模数为1的时候要特判,这个转化就没用了。

需要快速乘。

# include <bits/stdc++.h>
 
using namespace std;
 
# define REP(i, a, b) for(int i = a; i <= b; ++ i)
# define CLR(i, a) memset(i, a, sizeof(i))
# define REPD(i, a, b) for(int i = a; i >= b; -- i)
# define REPG(i, h, x) for(int i = h[x]; i; i = edge[i].next)
 
typedef long long LL;
const int N = 1e5 + 3;
 
# define gc getchar
inline LL rd() {
    char ch = gc(); LL ret = 0, sgn = 1;
    while(ch < '0' || ch > '9') { if(ch == '-') sgn = -1; ch = gc(); }
    while(ch <= '9' && ch >= '0') ret = ret * 10 + ch - '0', ch = gc();
    return sgn * ret;
}

LL n, m, life[N], rec[N], back[N], sword[N], reals[N];
LL a[N], mod[N];

inline LL mul(LL x, LL y, LL mmod) {
    x = ((x % mmod) + mmod) % mmod;
    y = ((y % mmod) + mmod) % mmod;
    LL tmp = (x * y - (LL)((long double)x / mmod * y + 1.0e-8) * mmod);
    return tmp < 0 ? tmp + mmod : tmp;
}

inline LL gcd(LL x, LL y) { return !y ? x : gcd(y, x % y); }

inline LL exgcd(LL tmpa, LL tmpb, LL &x, LL &y){
        if(!tmpb) { x = 1, y = 0; return tmpa; }
        LL re = exgcd(tmpb, tmpa % tmpb, x, y), tmp = x;
        x = y, y = tmp - (tmpa / tmpb) * y;
        return re;
}

LL qinding = 0;
LL fl[N], M, realn;
LL excrt() {
    if(!realn) return 0;
        M = mod[1];
        LL A = a[1], t, x, y;
        REP(i, 2, realn) {
                LL d = exgcd(M, mod[i], x, y);
                if(((a[i] - A) % d + d) % d) return -1;
                t = mod[i] / d;
                x = mul((a[i] - A) / d, x, t), x = (x % t + t) % t;
                LL tmp = M / d * mod[i];
                A = (mul(M, x, tmp) % tmp + A) % tmp, M = tmp; 
        }
        A = (A % M + M) % M;
        return A;
}

inline LL inv(LL a, LL b) {
    LL x, y;
    exgcd(a, b, x, y);
    return x;
}

void build() {
    qinding = -1, realn = 0;
    REP(i, 1, n) {
        fl[i] = life[i] / reals[i];
        if(life[i] % reals[i]) ++ fl[i];
        qinding = max(qinding, fl[i]);
        if(rec[i] == 1) continue;
        ++ realn;
        LL g = gcd(rec[i], reals[i]);
        if(g == 1) {
            a[realn] = (mul(life[i], inv(reals[i], rec[i]), rec[i]) % rec[i] + rec[i]) % rec[i];
            mod[realn] = rec[i];
        }
        else {  
            LL aa = rec[i] / g;
            LL b = reals[i] / g;
            a[realn] = life[i] / g;
            a[realn] = mul(a[realn], inv(b, aa), aa) % aa;
            a[realn] = (a[realn] % aa + aa) % aa;
            mod[realn] = aa;
        }
    }
}

int main() {
    freopen("dragon.in", "r", stdin);
    freopen("dragon.out", "w", stdout);
    for(int tt = rd(); tt; -- tt) {
        n = rd(), m = rd();
        if(!n) { puts("0"); continue; }
        // if(!m) { puts("-1"); continue; } 
        REP(i, 1, n) life[i] = rd();
        REP(i, 1, n) rec[i] = rd();
        REP(i, 1, n) back[i] = rd();
        multiset<int> st;
        REP(i, 1, m) { 
            sword[i] = rd();
            st.insert(sword[i]);
        }
        REP(i, 1, n) {
            multiset<int>::iterator it;
            it = st.lower_bound(life[i]);
            int rt;
            if(it != st.begin()) rt = *(-- it);
            else rt = *it;
            st.erase(it);
            st.insert(back[i]);
            reals[i] = rt;
        }
        build();
        LL ans = excrt();
        if(!realn) printf("%lld\n", qinding); 
        else if(~ans) {
            if(ans > qinding) {
                LL hh = ans - qinding;
                hh /= M;
                ans -= hh * M;
            }
            else if(ans < qinding) {
                LL hh = qinding - ans;
                hh /= M;
                if((qinding - ans) % M) ++ hh; 
                ans += hh * M;
            }
            printf("%lld\n", ans);
        }
        else puts("-1");

    }
    return 0;
}

那个啥我现在还只有70分。。。long long还没卡过去。


T2目前不会,坑着;
T3目前也不会,坑着。

0x02 没什么卵用的碎片

论Day1如何从看题100+44+68到估分65+28+68到实际5+24+0,Day2 long long又是如何将人逼上绝路

先来讲一讲Day1的心路历程qwq

T1一开始读错题了,认为不可做,开始看T2

观察并思考了一会之后感觉上应该是,一个p_i它前面与它相关的逆序对数必须正好等于max(0, p_i - i),打暴力验证了一下发现是对的,前面的分可以状压一下走人,后面觉得是个数位dp但是想了一年不会,感觉应该是问题没转化完,再想了一会儿看T3。

不错啊T3 SAM送了68分,稳,回去看看T1。T1居然读错题了,那这题岂不是可持久化并查集直接上。

然后我发现我不会可持久化并查集qwq没事,我一定能现场可持久化线段树yy出来(flag)。

码了一年发现我好像这个可持久化并查集写的不太对劲啊qaq。。。返回去写65分的离线分。

这时候已经浪费了不少时间了。

写完之后感觉T2写状压的话要写不完了,大力搜了一波然后剪枝,n=18能搜出来但是好慢啊.jpg不管了。

还剩下30min给我写T3。。。。

码完了还有1min要到点了,不管了先交了,过编译直接交了样例都没测。

然后赛后

哇我怎么多组数据没清空ans。等等这好像不是重点......

诶,测样例之后发现T3要去重。。(想了一会)去重能是能,我啪的一下拍了两个SAM在这题脸上(但是我复杂度对不对啊.jpg,写一波,最后事实证明它过了。

唉....感觉再给我半小时这个68pts就到手了.jpg 前面浪费了好多时间呀,我怎么想的这么慢,我好菜啊。感觉码力实在是太低了。。。思维深度感觉还有很大的提升空间

拿到成绩。日啊我怎么和我估分差了这么多。

晚上睡不着觉起来看了看。。

......Dijsktra vis没清......

Day 2

这个T1是个扩展CRT板题啊。。??????

T2我怎么只会30多分啊。。???怎么c=0这么多行代码只有15分啊??弃了

T3。“九莲......”然后我返回了T1,T3看都没有看。

这个怎么还带一个sword的逆元啊。。。sword和模数不互质这可怎么办。。

稍微化了一下式子发现可以消一个gcd之后CRT

诶,我怎么大样例过不去??

哦....模数为1要特判......

哇我怎么这个最后一个点-1了一年啊.....

最后-1了一整场决定弃疗,既然D1都挂成这样了D2少点T2T3的暴力也无所谓了.jpg

遂弃疗。

晚上在loj上测long long被卡了30pts(Upd:事实证明最后可能是我粘错版本了。。。最后被卡了50pts。。)

总之。。。暴露了我读题慢 想题慢 代码能力弱 有遗漏的常用算法 调试慢 反正什么都非常菜的特点。。。


---以下内容没有什么用可以折叠-分割线---

minshuo今年凉了....大家都觉得他能Au......但是......

本次NOI考察了许多基础算法和细节上的东西,细节爆炸,你甚至不如暴力分。Day2的区分度不是很能体现出来,T1过于简单,T2T3不太可做,这就导致day1爆炸的话day2很难扳回一城,更何况这个T1还**卡你long long,可能最后还比暴力分低25分。。。

上午要互相讲NOI的题,我讲D1T2讲得正起劲,jls带着另外一个陌生的面孔进了机房。

侯启明......听说是历史上NOI唯一的AK者,IOI Au。

开了个体验很奇怪的总结会,侯启明针对大家的总结说了两句,jls随着代表性地说了几句。貌似不宜在这里写下太多的对于它的感想。

jls:“pkl今天你没去隔壁讲课,有没有和他们说啊?”

pkl:“今天不是说上午讨论题目么....?”

jls:“你要给他们留点任务和他们说一下啊,负泽任一点。”

台下某人:“qyf好像和我们说了今天不讲。”

好的谢谢qyf。

TIM图片20180723215013

之后出了一点小插曲。

“这次同步赛的成绩最高是pkl,Ag”

。。。。。??????????

TIM图片20180723214947

(这个图是我用lemon测的,分别是我赛后改了点东西的代码和交上去的代码)

老师怎么把day1估分放上去了。。

轮到我上台之后赶紧和同学解释了一下。。

之后老师钦定了互验题的小组。感觉我们这组要爆炸了qwq

TIM图片20180723220526

怎么写着写着成了日记啊(

流水账一下这几天的琐事(虽然我前面也是流水账:

吃了好多东西,但是瘦了500克。

睡了好久,去机房不太有精神。

fsf从霓虹国回来啦,给大家带了点小礼物!

没有去跳舞。

插了点花。

感觉很难受......莫名很压抑。

---以上内容没有什么用可以折叠-分割线---


· EOF ·

Comments
Write a Comment