2022.10.21 模拟赛小结

sssmzy AK 了，zpair 差一点 AK 了，我寄了。

一套难得的难度略低于 NOIP 的阳间模拟赛

虽然还是寄了

更好的阅读体验戳此进入

赛时思路

T1

有 $f(x)=\lfloor \sqrt[4]{x}+{\displaystyle \frac{1}{2}}\rfloor$$f(x) = \lfloor \sqrt[4]{x} + \dfrac{1}{2} \rfloor$，$T$$T$ 组询问，给定 $n$$n$，求 $\sum _{i=1}^n={\displaystyle \frac{1}{f(i)}}$$\sum_{i = 1}^n = \dfrac{1}{f(i)}$。强制在线。

原题 LG-P8574 「DTOI-2」星之影。

难得切掉的一道水题。

第一眼值域分块，然后发现不是，于是考虑对于 $f(x)$$f(x)$ 显然取值是一段一段的，且段长递增，于是我们维护一下每一段的初始值，然后做个前缀和，考虑好加 $1$$1$ 减 $1$$1$ 的边界，每次询问 lower_bound $O(\log n)$$O(\log n)$ 查询一下即可。题解里也有 $O(1)$$O(1)$ 查询的方法，大概就是嗯推一下柿子。

Code

xxxxxxxxxx
87
1
#define _USE_MATH_DEFINES
2
#include <bits/stdc++.h>
3

4
#define PI M_PI
5
#define E M_E
6
#define npt nullptr
7
#define SON i->to
8
#define OPNEW void* operator new(size_t)
9
#define ROPNEW(arr) void* Edge::operator new(size_t){static Edge* P = arr; return P++;}
10

11
using namespace std;
12
// using namespace __gnu_pbds;
13

14
mt19937 rnd(random_device{}());
15
int rndd(int l, int r){return rnd() % (r - l + 1) + l;}
16
bool rnddd(int x){return rndd(1, 100) <= x;}
17

18
typedef unsigned int uint;
19
typedef unsigned long long unll;
20
typedef long long ll;
21
typedef long double ld;
22

23

24

25
template<typename T = int>
26
inline T read(void);
27

28
char buf_ans[114];
29
ll next_n(double last_ans=0,ll get_n=0){//last_ans<n<=1e18
30
sprintf(buf_ans,"%.6f",last_ans);
31
for(ll i=0,x=0;;i++){if(buf_ans[i]=='.')return get_n^x;if(i&1)x*=10;
32
else x=x*10+(buf_ans[i]^48);}}
33

34
const int mx = 34900;
35
ll blk[40000];
36
ll sum[40000];
37
double lans(0.0);
38

39
int main(){
40
    freopen("function.in", "r", stdin);
41
    freopen("function.out", "w", stdout);
42
    int T = read();
43
    blk[1] = 1; sum[1] = 5.0;
44
    for(int i = 1; i <= 35000; ++i)
45
        blk[i + 1] = (ll)ceil(powl((ld)i + 0.5, 4));
46
    for(int i = 1; i <= 34990; ++i)
47
        sum[i + 1] = sum[i] + (ld)1.0 / (ld)(i + 1) * (ld)(blk[i + 2] - blk[i + 1]);
48
    // for(int i = 1; i <= 100; ++i){
49
    //     printf("%lld : %lld\n", blk[i], sum[i]);
50
    // }
51
    while(T--){
52
        ll n = read<ll>();
53
        n = next_n(lans, n);
54
        // printf("%lld\n", n);
55
        int dist = lower_bound(blk + 1, blk + mx + 1, n) - blk;
56
        // printf("dis:%d\n", dist);
57
        // dist -= blk[dist] == n ? 1 : 2;
58
        --dist;
59
        // printf("new dis:%d\n", dist);
60
        // if(n == 89)printf("val: %lld + %.6Lf / %.6Lf\n", sum[dist - 1], (ld)(n - blk[dist] + 1), (ld)dist);
61
        ld ans = n == blk[dist + 1]
62
            ? (sum[dist] + (ld)(n - blk[dist + 1] + 1) / (ld)(dist + 1))
63
            : (sum[dist - 1] + (ld)(n - blk[dist] + 1) / (ld)dist);
64
        printf("%.6Lf\n", ans);
65
        lans = (double)ans;
66
    }
67
    fprintf(stderr, "Time: %.6lf\n", (double)clock() / CLOCKS_PER_SEC);
68
    return 0;
69
}
70

71

72

73
template<typename T>
74
inline T read(void){
75
    T ret(0);
76
    short flag(1);
77
    char c = getchar();
78
    while(c != '-' && !isdigit(c))c = getchar();
79
    if(c == '-')flag = -1, c = getchar();
80
    while(isdigit(c)){
81
        ret *= 10;
82
        ret += int(c - '0');
83
        c = getchar();
84
    }
85
    ret *= flag;
86
    return ret;
87
}

T2

给定 $n$$n$ 个点以 $1$$1$ 为根的树，初始所有节点权值为 $0$$0$，$q$$q$ 个操作或询问，操作为给定 $v,x,k$$v, x, k$，对 $v$$v$ 及其子树，记节点与 $v$$v$ 的距离为 $dis$$dis$，则对每个节点的权值加上 $x-dis\times k$$x - dis \times k$，询问为给定 $v$$v$ 输出 $v$$v$ 的权值。

原题 CF396C On Changing Tree。

又把 10.19 口糊的那个通过 bfs 序转称序列上然后套线段树的塞上去了，大概可以认为是暴力 + 大剪枝，树越扁剪枝越大，树是链的话就退化成暴力。

本来应该能拿到一些分的，然后线段树的 query 忘了取模了，直接全寄爆零。

Code

xxxxxxxxxx
139
1
#define _USE_MATH_DEFINES
2
#include <bits/stdc++.h>
3

4
#define PI M_PI
5
#define E M_E
6
#define npt nullptr
7
#define SON i->to
8
#define OPNEW void* operator new(size_t)
9
#define ROPNEW(arr) void* Edge::operator new(size_t){static Edge* P = arr; return P++;}
10

11
using namespace std;
12
// using namespace __gnu_pbds;
13

14
mt19937 rnd(random_device{}());
15
int rndd(int l, int r){return rnd() % (r - l + 1) + l;}
16
bool rnddd(int x){return rndd(1, 100) <= x;}
17

18
typedef unsigned int uint;
19
typedef unsigned long long unll;
20
typedef long long ll;
21
typedef long double ld;
22

23
#define MOD (1000000007)
24

25
template<typename T = int>
26
inline T read(void);
27

28
struct Edge{
29
    Edge* nxt;
30
    int to;
31
    OPNEW;
32
}ed[610000];
33
ROPNEW(ed);
34
Edge* head[310000];
35

36
int N, Q;
37
int idx[310000], ridx[310000];
38
int dsl[310000], dsr[310000];
39

40
void bfs(void){
41
    int cnt(0);
42
    queue < pair < int, int >/*vertex, father*/ > q;
43
    q.push({1, 0});
44
    while(!q.empty()){
45
        auto p = q.front(); q.pop();
46
        idx[p.first] = ++cnt;
47
        ridx[cnt] = p.first;
48
        vector < pair < int, int > > tmp;
49
        for(auto i = head[p.first]; i; i = i->nxt)
50
            if(SON != p.second)
51
                q.push({SON, p.first});
52
        if(!dsl[idx[p.second]])dsl[idx[p.second]] = dsr[idx[p.second]] = idx[p.first];
53
        else dsr[idx[p.second]] = idx[p.first];
54
    }
55
}
56

57
class SegTree{
58
private:
59
    ll st[310000 << 2];
60
    ll lz[310000 << 2];
61
    #define LS (p << 1)
62
    #define RS ((p << 1) + 1)
63
    #define MID ((gl + gr) >> 1)
64
public:
65
    // void Pushup(int p){st[p] = st[LS] + st[RS];}
66
    void Pushdown(int p){
67
        st[LS] = (st[LS] + lz[p]) % MOD, st[RS] = (st[RS] + lz[p]) % MOD;
68
        lz[LS] = (lz[LS] + lz[p]) % MOD, lz[RS] = (lz[RS] + lz[p]) % MOD;
69
        lz[p] = 0;
70
    }
71
    void Modify(int l, int r, ll val, int p = 1, int gl = 1, int gr = N){
72
        if(l <= gl && gr <= r)return st[p] = (st[p] + val) % MOD, lz[p] = (lz[p] + val) % MOD, void();
73
        Pushdown(p);
74
        if(l <= MID)Modify(l, r, val, LS, gl, MID);
75
        if(MID + 1 <= r)Modify(l, r, val, RS, MID + 1, gr);
76
    }
77
    ll Query(int idx, int p = 1, int gl = 1, int gr = N){
78
        if(gl == gr)return st[p];
79
        Pushdown(p);
80
        if(idx <= MID)return Query(idx, LS, gl, MID);
81
        else return Query(idx, RS, MID + 1, gr);
82
    }
83
}st;
84

85
void Mdf(int p, ll val, int k){
86
    int l(p), r(p), dis(0);
87
    st.Modify(l, r, (val - (ll)dis * k + MOD) % MOD);
88
    while(true){
89
        ++dis;
90
        while(!dsl[l] && l <= r)++l;
91
        while(!dsr[r] && l <= r)--r;
92
        if(l > r)return;
93
        l = dsl[l], r = dsr[r];
94
        st.Modify(l, r, (val - (ll)dis * k + MOD) % MOD);
95
    }
96
}
97

98
int main(){
99
    freopen("tree.in", "r", stdin);
100
    freopen("tree.out", "w", stdout);
101
    N = read();
102
    for(int i = 2; i <= N; ++i){
103
        int fa = read();
104
        head[i] = new Edge{head[i], fa};
105
        head[fa] = new Edge{head[fa], i};
106
    }bfs();
107
    Q = read();
108
    while(Q--){
109
        int opt = read();
110
        if(opt == 1){
111
            int v = read(), x = read(), k = read();
112
            Mdf(idx[v], (ll)x, k);
113
        }else{
114
            int v = read();
115
            printf("%lld\n", (st.Query(idx[v]) + MOD) % MOD);
116
        }
117
    }
118

119
    fprintf(stderr, "Time: %.6lf\n", (double)clock() / CLOCKS_PER_SEC);
120
    return 0;
121
}
122

123

124

125
template<typename T>
126
inline T read(void){
127
    T ret(0);
128
    short flag(1);
129
    char c = getchar();
130
    while(c != '-' && !isdigit(c))c = getchar();
131
    if(c == '-')flag = -1, c = getchar();
132
    while(isdigit(c)){
133
        ret *= 10;
134
        ret += int(c - '0');
135
        c = getchar();
136
    }
137
    ret *= flag;
138
    return ret;
139
}

T3

给定序列 $a_n$$a_n$，保证 $1\le a_i\le 8$$1 \le a_i \le 8$，求一个最长子序列满足：1. $[1,8]$$\left[ 1, 8 \right]$ 任意两个整数出现次数之差不大于 $1$$1$。2. 每种数字必须连续出现。

原题 CF743E Vladik and cards。

没想出来，暴力 $10\mathtt{\text{pts}}$$10\texttt{pts}$ 跑路。

Code

xxxxxxxxxx
92
1
#define _USE_MATH_DEFINES
2
#include <bits/stdc++.h>
3

4
#define PI M_PI
5
#define E M_E
6
#define npt nullptr
7
#define SON i->to
8
#define OPNEW void* operator new(size_t)
9
#define ROPNEW(arr) void* Edge::operator new(size_t){static Edge* P = arr; return P++;}
10

11
using namespace std;
12
// using namespace __gnu_pbds;
13

14
mt19937 rnd(random_device{}());
15
int rndd(int l, int r){return rnd() % (r - l + 1) + l;}
16
bool rnddd(int x){return rndd(1, 100) <= x;}
17

18
typedef unsigned int uint;
19
typedef unsigned long long unll;
20
typedef long long ll;
21
typedef long double ld;
22

23

24

25
template<typename T = int>
26
inline T read(void);
27

28
int N;
29
int arr[1100];
30
vector < int > cur;
31
int ans(0);
32

33
bool Check(void){
34
    int len[10];
35
    memset(len, 0, sizeof len);
36
    int lst(-1);
37
    for(auto i : cur){
38
        if(i == lst)++len[i];
39
        else if(len[i]++)return false;
40
    }
41
    int mn(INT_MAX), mx(INT_MIN);
42
    for(int i = 1; i <= 8; ++i)mn = min(mn, len[i]), mx = max(mx, len[i]);
43
    return mx - mn <= 1;
44
}
45

46
void dfs(int dep){
47
    if(dep > N){
48
        if(Check())ans = max(ans, (int)cur.size());
49
        return;
50
    }
51
    cur.emplace_back(arr[dep]);
52
    dfs(dep + 1);
53
    cur.pop_back();
54
    dfs(dep + 1);
55
}
56

57
int main(){
58
    freopen("card.in", "r", stdin);
59
    freopen("card.out", "w", stdout);
60
    N = read();
61
    for(int i = 1; i <= N; ++i)arr[i] = read();
62
    if(N <= 25)dfs(1), printf("%d\n", ans), exit(0);
63
    // while((double)clock() / CLOCKS_PER_SEC <= 0.95){
64
    //     int siz = rndd(1, N);
65
    //     for(int i = 1; i <= N; ++i){
66

67
        
68
    // }
69
    printf("%d\n", rndd(1, N));
70

71

72
    fprintf(stderr, "Time: %.6lf\n", (double)clock() / CLOCKS_PER_SEC);
73
    return 0;
74
}
75

76

77

78
template<typename T>
79
inline T read(void){
80
    T ret(0);
81
    short flag(1);
82
    char c = getchar();
83
    while(c != '-' && !isdigit(c))c = getchar();
84
    if(c == '-')flag = -1, c = getchar();
85
    while(isdigit(c)){
86
        ret *= 10;
87
        ret += int(c - '0');
88
        c = getchar();
89
    }
90
    ret *= flag;
91
    return ret;
92
}

T4

原题 CF1051F The Shortest Statement。

寄了，写的暴力也挂了。

Code

xxxxxxxxxx
125
1
#define _USE_MATH_DEFINES
2
#include <bits/stdc++.h>
3

4
#define PI M_PI
5
#define E M_E
6
#define npt nullptr
7
#define SON i->to
8
#define OPNEW void* operator new(size_t)
9
#define ROPNEW(arr) void* Edge::operator new(size_t){static Edge* P = arr; return P++;}
10

11
using namespace std;
12
// using namespace __gnu_pbds;
13

14
mt19937 rnd(random_device{}());
15
int rndd(int l, int r){return rnd() % (r - l + 1) + l;}
16
bool rnddd(int x){return rndd(1, 100) <= x;}
17

18
typedef unsigned int uint;
19
typedef unsigned long long unll;
20
typedef long long ll;
21
typedef long double ld;
22

23

24

25
template<typename T = int>
26
inline T read(void);
27

28
int N, M;
29
int Q;
30
int lca[110000];
31
int dep[110000];
32
pair < int, int > ask[110000];
33
ll ans[110000];
34
pair < int, int /*vertex, val*/ > ffa[110000];
35

36
struct Edge{
37
    Edge* nxt;
38
    int to;
39
    int val;
40
    OPNEW;
41
}ed[310000];
42
ROPNEW(ed);
43
Edge* head[110000];
44

45
namespace Tree{
46
    vector < pair < int, int > /*vertex, query_idx*/ > query[110000];
47
    bool vis[110000];
48
    class UnionFind{
49
    private:
50
        int fa[110000];
51
    public:
52
        UnionFind(void){for(int i = 1; i <= N; ++i)fa[i] = i;}
53
        int Find(int x){return x == fa[x] ? x : (fa[x] = Find(fa[x]));}
54
        void Union(int s, int t){fa[t] = Find(s);}
55
    }uf;
56
    void Init(void){
57
        for(int i = 1; i <= Q; ++i){
58
            int u = read(), v = read();
59
            ask[i] = {u, v};
60
            query[u].emplace_back(v, i);
61
            query[v].emplace_back(u, i);
62
        }
63
    }
64
    void dfs(int p = 1, int fa = 0){
65
        vis[p] = true;
66
        for(auto i = head[p]; i; i = i->nxt)if(SON != fa && !vis[SON])dfs(SON, p), uf.Union(p, SON);
67
        for(auto q : query[p])if(vis[q.first])lca[q.second] = uf.Find(q.first);
68
    }
69
    void dfs_dep(int p = 1, int fa = 0){
70
        dep[p] = dep[fa] + 1;
71
        for(auto i = head[p]; i; i = i->nxt)if(SON != fa)ffa[SON] = {p, i->val}, dfs_dep(SON, p);
72
    }
73
}
74

75
int main(){
76
    freopen("statement.in", "r", stdin);
77
    freopen("statement.out", "w", stdout);
78
    N = read(), M = read();
79
    for(int i = 1; i <= M; ++i){
80
        int s = read(), t = read(), v = read();
81
        head[s] = new Edge{head[s], t, v};
82
        head[t] = new Edge{head[t], s, v};
83
    }Q = read();
84
    if(M == N - 1){
85
        Tree::Init();
86
        Tree::dfs();
87
        Tree::dfs_dep();
88
        for(int i = 1; i <= Q; ++i){
89
            ll anss(0);
90
            int cp(ask[i].first);
91
            while(cp != lca[i]){
92
                anss += ffa[cp].second;
93
                cp = ffa[cp].first;
94
            }
95
            cp = ask[i].second;
96
            while(cp != lca[i]){
97
                anss += ffa[cp].second;
98
                cp = ffa[cp].first;
99
            }
100
            printf("%lld\n", anss);
101
        }
102
        exit(0);
103
    }
104

105
    fprintf(stderr, "Time: %.6lf\n", (double)clock() / CLOCKS_PER_SEC);
106
    return 0;
107
}
108

109

110

111
template<typename T>
112
inline T read(void){
113
    T ret(0);
114
    short flag(1);
115
    char c = getchar();
116
    while(c != '-' && !isdigit(c))c = getchar();
117
    if(c == '-')flag = -1, c = getchar();
118
    while(isdigit(c)){
119
        ret *= 10;
120
        ret += int(c - '0');
121
        c = getchar();
122
    }
123
    ret *= flag;
124
    return ret;
125
}

正解

T2

考虑对于每次修改 $v,x,k$$v, x, k$，$v$$v$ 子树（包括 $v$$v$）下的 $u$$u$，修改量为 $x-dis(u,v)\times k$$x - dis(u, v) \times k$，因为是在树上，所以可以转化成 $x-(de{p}_v-de{p}_u)\times k$$x - (dep_v - dep_u) \times k$，展开一下：$x+de{p}_u\times k-de{p}_v\times k$$x + dep_u \times k - dep_v \times k$，然后发现式子里对于点 $v$$v$，$de{p}_v$$dep_v$ 是定值，所以开个线段树（或树状数组）维护一下 $x+de{p}_u\times k$$x + dep_u \times k$ 和 $k$$k$ 即可。然后这样的话每次修改就等于是对一整个子树的修改，考虑如何转到序列上，显然按照 dfs 序即可。

Code

xxxxxxxxxx
112
1
#define _USE_MATH_DEFINES
2
#include <bits/stdc++.h>
3

4
#define PI M_PI
5
#define E M_E
6
#define npt nullptr
7
#define SON i->to
8
#define OPNEW void* operator new(size_t)
9
#define ROPNEW(arr) void* Edge::operator new(size_t){static Edge* P = arr; return P++;}
10

11
using namespace std;
12
// using namespace __gnu_pbds;
13

14
mt19937 rnd(random_device{}());
15
int rndd(int l, int r){return rnd() % (r - l + 1) + l;}
16
bool rnddd(int x){return rndd(1, 100) <= x;}
17

18
typedef unsigned int uint;
19
typedef unsigned long long unll;
20
typedef long long ll;
21
typedef long double ld;
22

23
#define MOD (1000000007)
24

25
template<typename T = int>
26
inline T read(void);
27

28
struct Edge{
29
    Edge* nxt;
30
    int to;
31
    OPNEW;
32
}ed[610000];
33
ROPNEW(ed);
34
Edge* head[310000];
35

36
int N, Q;
37
int idx[310000];
38
int dep[310000], siz[310000];
39

40
void dfs(int p = 1, int fa = 0){
41
    static int cnt(0);
42
    idx[p] = ++cnt;
43
    dep[idx[p]] = dep[idx[fa]] + 1;
44
    ++siz[idx[p]];
45
    for(auto i = head[p]; i; i = i->nxt)if(SON != fa)dfs(SON, p), siz[idx[p]] += siz[idx[SON]];
46
}
47

48
class BIT{
49
private:
50
    pair < ll, ll > tr[310000];
51
public:
52
    int lowbit(int x){return x & -x;}
53
    void add(int x, int u, ll base, ll k){
54
        while(x <= N)
55
            tr[x] = {
56
                ((tr[x].first + base + MOD) % MOD + (dep[u] * k + MOD) % MOD + MOD) % MOD,
57
                (tr[x].second + k + MOD) % MOD
58
            },
59
            x += lowbit(x);
60
    }
61
    void modify(int l, int r, int u, ll base, ll k){
62
        // printf("Modifying [%d, %d] => u = %d, x = %lld, k = %lld\n", l, r, u, base, k);
63
        add(l, u, base, k);
64
        add(r + 1, u, -base, -k);
65
    }
66
    ll query(int x){
67
        int rx = x;
68
        ll ret(0);
69
        while(x)ret = ((ret + tr[x].first) % MOD - tr[x].second * dep[rx] % MOD + MOD) % MOD, x -= lowbit(x);
70
        return ret;
71
    }
72
}bit;
73

74
int main(){
75
    N = read();
76
    for(int i = 2; i <= N; ++i){
77
        int fa = read();
78
        head[i] = new Edge{head[i], fa};
79
        head[fa] = new Edge{head[fa], i};
80
    }dfs();
81
    Q = read();
82
    while(Q--){
83
        // for(int i = 1; i <= N; ++i)printf("%lld%c", ta.query(i), i == N ? '\n' : ' ');
84
        int opt = read();
85
        if(opt == 1){
86
            int v = read(), x = read(), k = read();
87
            bit.modify(idx[v], idx[v] + siz[idx[v]] - 1, idx[v], x, k);
88
        }else{
89
            int v = read();
90
            printf("%lld\n", bit.query(idx[v]) % MOD);
91
        }
92
    }
93

94
    fprintf(stderr, "Time: %.6lf\n", (double)clock() / CLOCKS_PER_SEC);
95
    return 0;
96
}
97

98
template<typename T>
99
inline T read(void){
100
    T ret(0);
101
    short flag(1);
102
    char c = getchar();
103
    while(c != '-' && !isdigit(c))c = getchar();
104
    if(c == '-')flag = -1, c = getchar();
105
    while(isdigit(c)){
106
        ret *= 10;
107
        ret += int(c - '0');
108
        c = getchar();
109
    }
110
    ret *= flag;
111
    return ret;
112
}

T3 T4

咕咕咕。

UPD

update-2022_10_21 初稿