2022.10.19 模拟赛小结

(一场难度稍微低 1丶丶的模拟赛，不过我太弱了，依然没多少分。。。)

更好的阅读体验戳此进入

赛时思路

T1

给定 $n$$n$ 个点 $m$$m$ 条无向边，删除一个点要消耗和这个点直接连接的所有点的权值和，求删除所有点最小的消耗。

原题是 CF437C The Child and Toy。

想到了几个贪心，如按照节点对其它节点的贡献，或节点本身被贡献的去排序，亦或做差考虑最终的贡献排序，想了好多人类智慧，然后都假掉了。。。

至于为什么假了也能想到，这样的排序实际是一个动态的过程，是不能根据最开始的状态无脑排序的，然而动态的这玩意似乎难以维护，如果每次删除并插入难以实现，每次重排的话大概是 $O(mn\log n)$$O(mn\log n)$ 的，和无脑暴力一样，所以最后 T1 寄了，只有 $20\mathtt{\text{pts}}$$20\texttt{pts}$。

Code

xxxxxxxxxx
86
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
/******************************
12
abbr
13

14
******************************/
15

16
using namespace std;
17
// using namespace __gnu_pbds;
18

19
mt19937 rnd(random_device{}());
20
int rndd(int l, int r){return rnd() % (r - l + 1) + l;}
21
bool rnddd(int x){return rndd(1, 100) <= x;}
22

23
typedef unsigned int uint;
24
typedef unsigned long long unll;
25
typedef long long ll;
26
typedef long double ld;
27

28
#define MAXSIZE 1000000
29
char buf[MAXSIZE],*p1,*p2;
30
#define gc() (p1 == p2&&(p2=(p1=buf)+fread(buf,1,MAXSIZE,stdin),p1== p2)?EOF:*p1++)
31
inline int read(){int x=0,f=1;char c=gc();while(!isdigit(c)){if(c=='-') f=-1;c=gc();}while(isdigit(c)) x=x*10+(c^48),c=gc();return x*f;}
32

33
#define CMP [](int x, int y)->bool{return ctr[x] - cost[x] > ctr[y] - cost[y];}
34

35
// struct cmp{
36
//     bool operator ()(const int &x, const int &y){return ctr[x] - cost[x] > ctr[y] - cost[y];}
37
// };
38

39
int N, M;
40
int val[1100000];
41
int idx[1100000];
42
ll ctr[1100000];
43
ll cost[1100000];
44
ll ans(0);
45
vector < int > vt[1100000];
46
// vector < int > heap;
47
bool used[1100000];
48

49

50
int main(){
51
    freopen("candy.in", "r", stdin);
52
    freopen("candy.out", "w", stdout);
53
    // freopen("candy1.in", "r", stdin);
54
    N = read(), M = read();
55
    for(int i = 1; i <= N; ++i)val[i] = read(), idx[i] = i;
56
    for(int i = 1; i <= M; ++i){
57
        int s = read(), t = read();
58
        ctr[s] += val[s], ctr[t] += val[t];
59
        cost[s] += val[t], cost[t] += val[s];
60
        vt[s].emplace_back(t), vt[t].emplace_back(s);
61
    }
62
    for(int i = 1; i <= N; ++i)ctr[i] -= cost[i];
63
    // sort(idx + 1, idx + N + 1, [](int x, int y)->bool{return ctr[x] == ctr[y] ? cost[x] < cost[y] : ctr[x] > ctr[y];});
64
    // sort(idx + 1, idx + N + 1, [](int x, int y)->bool{return cost[x] == cost[y] ? ctr[x] > ctr[y] : cost[x] < cost[y];});
65
    sort(idx + 1, idx + N + 1, [](int x, int y)->bool{return ctr[x] > ctr[y];});
66
    // for(int i = 1; i <= N; ++i)
67
        // heap.emplace(lower_bound(heap.begin(), heap.end(), i, CMP), i);
68
    for(int i = 1; i <= N; ++i){
69
        // sort(idx + 1, idx + N + 1, );
70
        // int p = heap.front();
71
        int p = idx[i];
72
        used[p] = true;
73
        // heap.erase(heap.begin());
74
        ans += cost[p];
75
        for(auto j : vt[p])
76
            if(!used[j])
77
                cost[j] -= val[p];
78
                // printf("%lld %lld (%d)\n", cost[j], ctr[j], j),
79
                // heap.erase(find(heap.begin(), heap.end(), j)),
80
                // heap.emplace(lower_bound(heap.begin(), heap.end(), j, CMP), j);
81
    }
82
    printf("%lld\n", ans);
83
    fprintf(stderr, "Time: %.6lf\n", (double)clock() / CLOCKS_PER_SEC);
84
    return 0;
85
}
86

T2

原题是 LG-P7152 [USACO20DEC] Bovine Genetics G。

不会

T3

原题是 P7154 [USACO20DEC] Sleeping Cows P。

不会

T4

给定 $n$$n$ 个节点以 $1$$1$ 为根的树，初始所有点权值为 $0$$0$，$m$$m$ 次修改每次将 $u$$u$ 所在子树中距离 $u$$u$ 不大于 $d$$d$ 的点权值增加 $v$$v$，求最后每个点的权值。

原题是 CF1076E Vasya and a Tree。

最开始想口糊一个在树上的动态建点的 ODT，然后发现建不出来。。然后尝试找了半天性质口糊了一个奇怪的做法：对于本题我的想法就是把子树覆盖转换成序列上的操作问题，然后最后想到了把树按照 bfs 序标号，这样的话每一层都会是一个连续的区间，然后我们记录每一个非叶子节点子树所在的下一层的区间，每次修改的时候这样跑一遍。。理论上在随机数据上都能过，但是一条链的话直接退化成比暴力常数还要大的暴力，而且我不知道咋想的区间操作的时候写了个没有 assign 的 ODT，结果基本全寄了，因为这玩意没有区间推平本身就完全用不了 ODT，一直在 Split，反应过来之后想改线段树没改完。。。在随机数据上基本都卡在了 1000ms 左右，刚好寄了。。链上的测试点直接过不了。最后 $30\mathtt{\text{pts}}$$30\texttt{pts}$ 到 $50\mathtt{\text{pts}}$$50\texttt{pts}$ 不等，测评波动。。

Code

xxxxxxxxxx
157
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
/******************************
12
abbr
13

14
******************************/
15

16
using namespace std;
17
// using namespace __gnu_pbds;
18

19
mt19937 rnd(random_device{}());
20
int rndd(int l, int r){return rnd() % (r - l + 1) + l;}
21
bool rnddd(int x){return rndd(1, 100) <= x;}
22

23
typedef unsigned int uint;
24
typedef unsigned long long unll;
25
typedef long long ll;
26
typedef long double ld;
27

28
#define MAXSIZE 1000000
29
char buf[MAXSIZE],*p1,*p2;
30
#define gc() (p1 == p2&&(p2=(p1=buf)+fread(buf,1,MAXSIZE,stdin),p1== p2)?EOF:*p1++)
31
inline int read(){int x=0,f=1;char c=gc();while(!isdigit(c)){if(c=='-') f=-1;c=gc();}while(isdigit(c)) x=x*10+(c^48),c=gc();return x*f;}
32

33
int N, M;
34
int idx[310000]; //real => my
35
int ridx[310000]; //my => real
36
ll ans[310000];
37

38
int dsl[310000], dsr[310000];//i-1-depth-subtree-l / r
39

40
struct Node{
41
    int l, r;
42
    mutable ll val;
43
    friend const bool operator < (const Node &x, const Node &y){return x.l < y.l;}
44
};
45

46
class ODT{
47
private:
48
    set < Node > tr;
49
public:
50
    auto Insert(Node p){return tr.insert(p);}
51
    auto Split(int p){
52
        auto it = tr.lower_bound(Node{p});
53
        if(it != tr.end() && it->l == p)return it;
54
        --it;
55
        if(p > it->r)return tr.end();
56
        auto l = it->l, r = it->r;
57
        auto val = it->val;
58
        tr.erase(it);
59
        Insert(Node{l, p - 1, val});
60
        return Insert(Node{p, r, val}).first;
61
    }
62
    void Assign(int l, int r, ll val){
63
        // printf("assigning %d-%d : %lld\n", l, r, val);
64
        auto itR = Split(r + 1), itL = Split(l);
65
        for(auto it = itL; it != itR; ++it)it->val += val;
66
    }
67
    void SetAns(void){
68
        for(auto p : tr)for(int i = p.l; i <= p.r; ++i)ans[ridx[i]] = p.val;
69
    }
70
}odt;
71

72
// class SegT{
73
// private:
74
//     #define LS (p << 1)
75
//     #define RS ((p << 1) + 1)
76
//     #define SIZ (gr - gl + 1)
77
//     #define SIZZ(l, r) (r - l + 1)
78
//     #define MID ((gl + gr) >> 1)
79
//     ll tr[310000 << 2];
80
//     ll lt[310000 << 2];
81
// public:
82
//     void Pushdown(int p, int gl, int gr){
83
//         tr[LS] += lt[p] * SIZZ(gl, MID);
84
//         tr[RS] += lt[p] * SIZZ(MID + 1, gr);
85
//         lt[LS] += lt[p], tr[RS] += lt[p];
86
//         lt[p] = 0;
87
//     }
88
//     void Pushup(int p){
89
//         tr[p] = tr[LS] + tr[RS];
90
//     }
91
//     void Modify(int p, int l, int r, ll val, int gl = 1, int gr = N){
92
//         if(l <= gl && gr <= r)tr[p] += SIZ * val, lt[p] += SIZ
93
//     }
94
// }
95

96
struct Edge{
97
    Edge* nxt;
98
    int to;
99
    OPNEW;
100
}ed[610000];
101
ROPNEW(ed);
102
Edge* head[310000];
103

104
void bfs(void){
105
    int cnt(0);
106
    queue < pair < int, int >/*vertex, father*/ > q;
107
    q.push({1, 0});
108
    while(!q.empty()){
109
        auto p = q.front(); q.pop();
110
        idx[p.first] = ++cnt;
111
        ridx[cnt] = p.first;
112
        vector < pair < int, int > > tmp;
113
        for(auto i = head[p.first]; i; i = i->nxt)
114
            if(SON != p.second)
115
                q.push({SON, p.first});
116
                // tmp.push_back({SON, p.first});
117
        // for(auto i = tmp.rbegin(); i != tmp.rend(); ++i)q.push(*i);
118
        if(!dsl[idx[p.second]])dsl[idx[p.second]] = dsr[idx[p.second]] = idx[p.first];
119
        else dsr[idx[p.second]] = idx[p.first];
120
        // if(!head[p.first]->nxt)dsl[p.first] = dsr[p.first] = cnt;
121
    }
122
}
123
void modify(int dep, int p, ll val){
124
    int l(p), r(p); odt.Assign(l, r, val);
125
    while(dep--){
126
        while(!dsl[l] && l <= r)++l;
127
        while(!dsr[r] && l <= r)--r;
128
        if(l > r)return;
129
        l = dsl[l], r = dsr[r];
130
        // if(l > r)return;
131
        odt.Assign(l, r, val);
132
    }
133
}
134

135
int main(){
136
    freopen("tree.in", "r", stdin);
137
    freopen("tree.out", "w", stdout);
138
    N = read();
139
    odt.Insert(Node{1, N, 0});
140
    for(int i = 1; i <= N - 1; ++i){
141
        int s = read(), t = read();
142
        head[s] = new Edge{head[s], t};
143
        head[t] = new Edge{head[t], s};
144
    }bfs();
145
    // for(int i = 1; i <= N; ++i)swap(dsl[i], dsr[i]);
146
    // for(int i = 1; i <= N; ++i)if(dsl[i] > dsr[i])printf("ERROR! at%d\n", i), exit(0);
147
    M = read();
148
    for(int i = 1; i <= M; ++i){
149
        int p = read(), dep = read(), val = read();
150
        modify(dep, idx[p], (ll)val);
151
    }
152
    odt.SetAns();
153
    for(int i = 1; i <= N; ++i)printf("%lld%c", ans[i], i == N ? '\n' : ' ');
154
    fprintf(stderr, "Time: %.6lf\n", (double)clock() / CLOCKS_PER_SEC);
155
    return 0;
156
}
157

正解

T1

考虑把删点变成删边，对于删除每条边，显然其贡献为两个端点中的一个的权值，所以遍历每条边答案加上两个端点中的最小值即可。

Code

xxxxxxxxxx
52
1
#define _USE_MATH_DEFINES
2
#include <bits/extc++.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
template<typename T = int>
24
inline T read(void);
25

26
ll ans;
27
ll v[1100];
28

29
int main(){
30
    int N = read(), M = read();
31
    for(int i = 1; i <= N; ++i)v[i] = read();
32
    for(int i = 1; i <= M; ++i)ans += min(v[read()], v[read()]);
33
    printf("%lld\n", ans);
34
    fprintf(stderr, "Time: %.6lf\n", (double)clock() / CLOCKS_PER_SEC);
35
    return 0;
36
}
37

38
template<typename T>
39
inline T read(void){
40
    T ret(0);
41
    short flag(1);
42
    char c = getchar();
43
    while(c != '-' && !isdigit(c))c = getchar();
44
    if(c == '-')flag = -1, c = getchar();
45
    while(isdigit(c)){
46
        ret *= 10;
47
        ret += int(c - '0');
48
        c = getchar();
49
    }
50
    ret *= flag;
51
    return ret;
52
}

T2

咕咕咕。

T3

咕咕咕。

T4

考虑把修改离线，记录每个点上的所有修改，然后做一个奇怪的树上差分，搜索的时候考虑把每一个深度记录在当前搜索的子树内对应的差分值，然后每搜到一个点先加上对应的差分值，把它的修改加到答案里，然后在对应的差分的结束的地方减去这个值，当搜完节点所在子树的时候，要搜其它的子树了，这个节点子树的差分桶就不再有效了，所以此时将之前的修改回退一下即可。

Code

xxxxxxxxxx
85
1
#define _USE_MATH_DEFINES
2
#include <bits/extc++.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 MAXN 310000
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[MAXN << 1];
35

36
int N, M;
37
ll ans[MAXN];
38
ll d[MAXN];
39
int dep[MAXN];
40
vector < pair < int, int > /*depth, value*/ > mdf[MAXN];
41

42
void dfs(int p = 1, int fa = 0, ll cur = 0){
43
    dep[p] = dep[fa] + 1;
44
    cur += d[dep[p]];
45
    for(auto m : mdf[p])
46
        cur += m.second,
47
        (dep[p] + m.first + 1 < MAXN) ? (void)(d[dep[p] + m.first + 1] -= m.second) : void();
48
    ans[p] = cur;
49
    for(auto i = head[p]; i; i = i->nxt)
50
        SON != fa ? dfs(SON, p, cur) : void();
51
    for(auto m : mdf[p])
52
        if(dep[p] + m.first + 1 < MAXN)d[dep[p] + m.first + 1] += m.second;
53
}
54

55
int main(){
56
    N = read();
57
    for(int i = 1; i <= N - 1; ++i){
58
        int s = read(), t = read();
59
        head[s] = new Edge{head[s], t};
60
        head[t] = new Edge{head[t], s};
61
    }M = read();
62
    for(int i = 1; i <= M; ++i){
63
        int vt = read(), dep = read(), val = read();
64
        mdf[vt].push_back({dep, val});
65
    }dfs();
66
    for(int i = 1; i <= N; ++i)printf("%lld%c", ans[i], i == N ? '\n' : ' ');
67
    fprintf(stderr, "Time: %.6lf\n", (double)clock() / CLOCKS_PER_SEC);
68
    return 0;
69
}
70

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

UPD

update-2022_10_19 初稿