【伪300pts】20190915测试总结

LRL52 · 2019-09-15 11:37:58 · 个人记录

前言：这不是原来MZOJ的题吗，已暗示老师提前漏题了（无语），昨天老师讲树链剖分模板时一不小心把题目漏出来了，然后全班同学都看到了，已经知道题了，那莫得办法勒，况且原来第3题fxy早就在MZOJ发过题解的。中间我曾暗示过欧阳老师“是不是考上一届的题目”，目的是希望老师换一套题目考试。~~毕竟到手的题目，不做白不做，其它同学有可能也去做了~~

T1 Candy

这道题也不算特别数论，考察简单的筛法和推导，放在第一题，也很容易骗分（可以骗70pts）

记

S = \sum_{i = 1}^n digit[i]

由于Rotate了共产生了n个循环数字串，易知原数的每一个digit[i]都一定在每一位上恰好出现过一次，容易得到最后的和可以表示为

S \times 10 ^ {n -1} + S \times 10 ^ {n -2} + S \times 10 ^ {n -3} + ... + S \times 10 ^ 0

注意到每一项恰巧有一个公因数S, 提出来得到

S \times \underbrace{1111....11}_{n}

上柿子乘号右边恰好共有n个1

因此我们分成两部分求最小非1因子

前一部分可以直接枚举ans, 题目中说了ans \in [2, 5 \times 10^6]

这样做已经可以有70pts

然后考虑后面那部分，共有n个1

根据算法进阶上和绵实讲课内容中The\ Luckiest\ Number一题目中的处理手段，右面部分可以转化为\frac{10^n-1}{9}

设需要求的最小非1因子为x，则我们需要找到一个最小的x, 使

x | \frac{10^n-1}{9} \iff 9x | 10^n -1 \iff 10^n ≡ 1(mod\ 9x)

然后使用快速幂检验就可以了, 另外本题目需要用线性筛筛出1 \sim 5 \times 10^6内的质数，时间复杂度\Theta(n)

//ID: LRL52  Date: 2019.9.15
#define rep(i, a, b) for(int i = (a); i <= (b); ++i)
#include<bits/stdc++.h>
using namespace std;
const int N = 500055, M = 2055;
const int maxn = 5e6;
int v[maxn + 55], prime[maxn + 55], cnt;
int sum = 0, n;
char s[N];

void Prework(){
    rep(i, 2, maxn){
        if(!v[i])
            v[i] = i, prime[++cnt] = i;
        rep(j, 1, cnt){
            if(prime[j] > v[i] || prime[j] > maxn / i) break;
            v[i * prime[j]] = prime[j];
        }
    }
    //rep(i, 1, 50) printf("%d\n", prime[i]);
}

int qp(int a, int k, int P){
    a %= P; int ret = 1;
    while(k){
        if(k & 1) ret = 1LL * ret * a % P;
        a = 1LL * a * a % P;
        k >>= 1;
    }
    return ret;
}

int main(){
    freopen("candy.in", "r", stdin);
    freopen("candy.out", "w", stdout);
    scanf("%s", s + 1);
    n = strlen(s + 1);
    rep(i, 1, n)
        sum += s[i] - '0';
    Prework();
    int ans = 2;
    rep(i, 1, cnt){
        if(sum % prime[i] == 0 || qp(10, n, 9 * prime[i]) == 1){
            ans = prime[i];
            break;
        } 
    }
    printf("%d\n", ans);
    return 0;
}

T2 2. 遗失的二叉树

中序遍历生成树模型（自启的名字）

首先根据题意预处理出可以连边的点对，若(x, y)可以连边，记作mp[x][y] = mp[y][x] = 1

记L[i][j]表示(i, j)是否可以作为二叉树的左儿子及根，其中j是该二叉树的根

记R[i][j]表示(i, j)是否可以作为二叉树的右儿子及根，其中i是该二叉树的根

转移方程

L[i][j] \ |= mp[k][j] \ and \ L[i][k] \ and \ R[k][j - 1]

R[i][j] \ |= mp[k][i] \ and \ L[i + 1][k] \ and \ R[k][j]

初值L[i][i] = R[i][i] = 1，目标:找到1个k使得L[1][k] \ and \ R[k][n] = 1

//ID: LRL52  Date: 2019.9.15
#define rep(i, a, b) for(int i = (a); i <= (b); ++i)
#include<bits/stdc++.h>
using namespace std;
const int N = 555, M = 2055; char ss[1 << 21], *A = ss, *B = ss, cc;
inline char gc(){return A == B && (B = (A = ss) + fread(ss, 1, 1 << 21, stdin), A == B) ? EOF : *A++;}
template<class T>inline void rd(T &x){
    int f = 1; x = 0, cc = gc(); while(cc < '0' || cc > '9'){if(cc == '-') f = -1; cc = gc();}
    while(cc >= '0' && cc <= '9'){x = (x << 3) + (x << 1) + (cc ^ 48); cc = gc();} x *= f;
}
int n, a[N];
int L[N][N], R[N][N], mp[N][N];

int gcd(int a, int b){return a == 0 ? b : gcd(b % a, a);}

int main(){
    freopen("tree.in", "r", stdin);
    freopen("tree.out", "w", stdout);
    int T; rd(T);
    while(T--){
        rd(n);
        rep(i, 1, n) rd(a[i]);
        memset(mp, 0, sizeof mp);
        rep(i, 1, n)
            rep(j, i + 1, n)
                mp[i][j] = mp[j][i] = (gcd(a[i], a[j]) != 1);
        memset(L, 0, sizeof L);
        memset(R, 0, sizeof R);
        rep(i, 1, n) L[i][i] = R[i][i] = 1;
        rep(len, 2, n)
            rep(i, 1, n - len + 1){
                int j = i + len - 1;
                rep(k, i, j){
                    L[i][j] |= mp[k][j] & L[i][k] & R[k][j - 1];
                    R[i][j] |= mp[k][i] & L[i + 1][k] & R[k][j];
                }
            }
        int ok = 0;
        rep(i, 1, n)
            if(L[1][i] & R[i][n]){
                ok = 1;
                break;
            }
        if(ok) puts("Yes");
        else puts("No");
    }
    return 0;
}

T3 精灵([LNOI2014]LCA)

这题确实比较有思维难度，自己难以想到这样的转化

具体我懒得写了，请参见hzwer黄学长博客

http://hzwer.com/3891.html

//ID: LRL52  Date: 2019.9.15
//注意到LCA具有对称性，不妨离线处理，然后统计，具体见题解 
#define rep(i, a, b) for(int i = (a); i <= (b); ++i)
#define ee(i, a) for(int i = head[a]; i; i = e[i].nxt)
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 55, M = 2055; char ss[1 << 21], *A = ss, *B = ss, cc;
inline char gc(){return A == B && (B = (A = ss) + fread(ss, 1, 1 << 21, stdin), A == B) ? EOF : *A++;}
template<class T>inline void rd(T &x){
    int f = 1; x = 0, cc = gc(); while(cc < '0' || cc > '9'){if(cc == '-') f = -1; cc = gc();}
    while(cc >= '0' && cc <= '9'){x = (x << 3) + (x << 1) + (cc ^ 48); cc = gc();} x *= f;
}
const int P = 201314;
int ct, DFN, n, que, cnt;
int dep[N], fa[N], size[N], son[N], top[N], id[N], head[N];
int add[N << 2], sum[N << 2], Ans[N], Z[N];
struct node{
    int x, k, id;
}a[N << 1];
struct edge{
    int v, nxt;
}e[N << 1];
struct cmp{
    inline bool operator()(const node &t1, const node &t2)const{
        return t1.x < t2.x;
    }
};

inline void adde(int from, int to){
    e[++ct].v = to;
    e[ct].nxt = head[from];
    head[from] = ct;
}

void dfs(int x){
    size[x] = 1; int maxs = 0, tson = 0;
    ee(i, x){
        int v = e[i].v;
        if(v == fa[x]) continue;
        fa[v] = x, dep[v] = dep[x] + 1;
        dfs(v);
        size[x] += size[v];
        if(size[v] > maxs){
            maxs = size[v];
            tson = v;
        }
    }
    if(tson) son[x] = tson;
}

void dfs2(int x, int topp){
    id[x] = ++DFN, top[x] = topp;
    if(son[x]) dfs2(son[x], topp);
    else return;
    ee(i, x){
        int v = e[i].v;
        if(v == fa[x] || v == son[x]) continue;
        dfs2(v, v);
    }
}

#define lson l, mid, rt << 1
#define rson mid + 1, r, rt << 1 | 1
#define pup sum[rt] = (sum[rt << 1] + sum[rt << 1 | 1]) % P

inline void updatenode(int k, int l, int r, int rt){
    add[rt] = (add[rt] + k) % P, sum[rt] = (sum[rt] + 1LL * (r - l + 1LL) * k) % P;
}

inline void pdown(int l, int r, int rt){
    if(add[rt] == 0) return;
    int mid = (l + r) >> 1, k = add[rt];
    updatenode(k, lson), updatenode(k, rson);
    add[rt] = 0;
}

void update(int x, int y, int k, int l, int r, int rt){
    if(x <= l && r <= y){
        updatenode(k, l, r, rt);
        return;
    }
    int mid = (l + r) >> 1; pdown(l, r, rt);
    if(x <= mid) update(x, y, k, lson);
    if(y > mid) update(x, y, k, rson);
    pup;
}

int query(int x, int y, int l, int r, int rt){
    if(x <= l && r <= y) return sum[rt];
    int mid = (l + r) >> 1; pdown(l, r, rt);
    if(x <= mid && y > mid) return (query(x, y, lson) + query(x, y, rson)) % P;
    else if(x <= mid) return query(x, y, lson);
    else return query(x, y, rson);
}

void Update(int x, int y, int k){
    while(top[x] != top[y]){
        if(dep[top[x]] < dep[top[y]]) swap(x, y);
        update(id[top[x]], id[x], k, 1, n, 1);
        x = fa[top[x]];
    }
    if(dep[x] > dep[y]) swap(x, y);
    update(id[x], id[y], k, 1, n, 1);
}

int Query(int x, int y){
    int ret = 0;
    while(top[x] != top[y]){
        if(dep[top[x]] < dep[top[y]]) swap(x, y);
        ret += query(id[top[x]], id[x], 1, n, 1);
        ret %= P;
        x = fa[top[x]];
    }
    if(dep[x] > dep[y]) swap(x, y);
    ret += query(id[x], id[y], 1, n, 1);
    return ret % P;
}

int main(){
    freopen("elf.in", "r", stdin);
    freopen("elf.out", "w", stdout);
    rd(n), rd(que); int x, y, z;
    rep(i, 2, n){
        rd(x);
        adde(i, x), adde(x, i);
        //printf("add %d -> %d\n", i, x);
    }
    rep(i, 1, que){
        rd(x), rd(y), rd(Z[i]);
        a[++cnt].x = x - 1, a[cnt].id = i, a[cnt].k = -1;
        a[++cnt].x = y, a[cnt].id = i, a[cnt].k = 1;
    }
    fa[1] = -1;
    dfs(1);
    dfs2(1, 1);
    sort(a + 1, a + cnt + 1, cmp());
    int p = 0;
    rep(i, 1, cnt){
        int I = a[i].id; 
        z = Z[I], x = a[i].x;
        while(p < n && p + 1 <= x)
            Update(1, ++p, 1);
        Ans[I] += a[i].k * Query(1, z);
    }
    rep(i, 1, que){
        Ans[i] = (Ans[i] % P + P) % P;
        printf("%d\n", Ans[i]);
    }
    return 0;
}

LCT解法Code:

//ID: LRL52  Date: 2019.9.15 
#define rep(i, a, b) for(int i = (a); i <= (b); ++i)
#define ee(i, a) for(int i = head[a]; i; i = e[i].nxt)
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 55, M = 2055; char ss[1 << 21], *A = ss, *B = ss, cc;
inline char gc(){return A == B && (B = (A = ss) + fread(ss, 1, 1 << 21, stdin), A == B) ? EOF : *A++;}
template<class T>inline void rd(T &x){
    int f = 1; x = 0, cc = gc(); while(cc < '0' || cc > '9'){if(cc == '-') f = -1; cc = gc();}
    while(cc >= '0' && cc <= '9'){x = (x << 3) + (x << 1) + (cc ^ 48); cc = gc();} x *= f;
}
const int P = 201314;
struct node{
    int x, k, id;
}a[N << 1];
struct cmp{
    inline bool operator()(const node &t1, const node &t2)const{
        return t1.x < t2.x;
    }
};
int n, que, Z[N], cnt;
int ch[N][2], par[N], rev[N], sum[N], add[N], val[N], size[N], stk[N], Ans[N];

#define ls ch[x][0]
#define rs ch[x][1]
inline void fix(int x){sum[x] = val[x] = add[x] = size[x] = 0;}
inline int chk(int x){return ch[par[x]][1] == x;}
inline void pup(int x){fix(0);
    sum[x] = sum[ls] + sum[rs] + val[x];
    size[x] = size[ls] + size[rs] + 1;
}
inline void reverse(int x){swap(ls, rs); rev[x] ^= 1;}
inline void updatenode(int k, int x){add[x] = (add[x] + k) % P, sum[x] = (sum[x] + 1LL * k * size[x] % P) % P, val[x] = (val[x] + k) % P;}
inline void pdown(int x){
    if(rev[x]) reverse(ls), reverse(rs), rev[x] = 0;
    if(add[x]) updatenode(add[x], ls), updatenode(add[x], rs), add[x] = 0;
}
inline int nroot(int x){return ch[par[x]][0] == x || ch[par[x]][1] == x;}

void rotate(int x){
    int y = par[x], z = par[y], k = chk(x), w = ch[x][k ^ 1];
    ch[y][k] = w, par[w] = y;
    if(nroot(y)) ch[z][chk(y)] = x; par[x] = z;
    ch[x][k ^ 1] = y, par[y] = x;
    pup(y), pup(x);
}

void splay(int x){
    int y = x, z = 0; stk[++z] = y;
    while(nroot(y)) stk[++z] = (y = par[y]);
    while(z) pdown(stk[z--]);
    while(nroot(x)){
        y = par[x];
        if(nroot(y)){
            if(chk(x) == chk(y)) rotate(y);
            else rotate(x);
        }
        rotate(x);
    }
}

void access(int x){for(int y = 0; x; x = par[y = x]) splay(x), rs = y, pup(x);}
void makeroot(int x){access(x); splay(x); reverse(x);}
int findroot(int x){access(x); splay(x); while(ls) pdown(x), x = ls; splay(x); return x;}
void link(int x, int y){makeroot(x); if(findroot(y) != x) par[x] = y;}
void cut(int x, int y){makeroot(x); if(findroot(y) == x && par[y] == x && !ch[y][0]) ch[x][1] = par[y] = 0, pup(x);}
void split(int x, int y){makeroot(x); access(y); splay(y);}


void Update(int x, int y, int k){split(x, y);updatenode(1, y);}
int Query(int x, int y){split(x, y);return sum[y];}

int main(){
    //freopen("elf.in", "r", stdin);
    //freopen("elf.out", "w", stdout);
    rd(n), rd(que); int x, y, z;
    rep(i, 2, n){
        rd(x);
        link(i, x);
    }
    rep(i, 1, que){
        rd(x), rd(y), rd(Z[i]);
        a[++cnt].x = x - 1, a[cnt].id = i, a[cnt].k = -1;
        a[++cnt].x = y, a[cnt].id = i, a[cnt].k = 1;
    }
    sort(a + 1, a + cnt + 1, cmp());
    int p = 0;
    rep(i, 1, cnt){
        int I = a[i].id; 
        z = Z[I], x = a[i].x;
        while(p < n && p + 1 <= x)
            Update(1, ++p, 1);
        Ans[I] += a[i].k * Query(1, z);
    }
    rep(i, 1, que){
        Ans[i] = (Ans[i] % P + P) % P;
        printf("%d\n", Ans[i]);
    }
    return 0;
}