2022.11.10 模拟赛小结

更好的阅读体验戳此进入

赛时思路

T1

原题 LG-P3970 [TJOI2014]上升子序列。

不算太难，大概就是个找性质然后 BIT 维护一下就行，比较弱所以写了四五十分钟，拍完之后大概一个点吧，不过也算切了。

Code

xxxxxxxxxx
83
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 (ll)(1e9 + 7)
24

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

28
int lim;
29
int N;
30
int a[110000];
31
int ra[110000];
32
bool exist[110000];
33
ll ans(0);
34
vector < int > data;
35
vector < int > tmp;
36

37
class BIT{
38
private:
39
    ll tr[210000];
40
public:
41
    int lowbit(int x){return x & -x;}
42
    void Modify(int x, ll v){while(x <= lim)tr[x] = (tr[x] + v) % MOD, x += lowbit(x);}
43
    ll Query(int x){ll ret(0); while(x)ret = (ret + tr[x]) % MOD, x -= lowbit(x); return ret;}
44
    ll QueryPoint(int x){return (Query(x) - Query(x - 1) + MOD) % MOD;}
45
    ll QueryReal(int x){ll tmp = QueryPoint(x); return (Query(x - 1) - (tmp ? tmp - 1 : 0) + MOD) % MOD;}
46
}bit;
47

48
int main(){
49
    freopen("subseries.in", "r", stdin);
50
    freopen("subseries.out", "w", stdout);
51
    lim = N = read();
52
    for(int i = 1; i <= N; ++i)a[i] = read(), data.emplace_back(a[i]);
53
    sort(data.begin(), data.end());
54
    for(int i = 1; i <= N; ++i)a[i] = distance(data.begin(), lower_bound(data.begin(), data.end(), a[i]) + 1);
55
    // for(int i = N; i <= 1; ++i)if(!exist[a[i]])exist[a[i]] = true, tmp.emplace_back(a[i]);
56
    // for(auto it = tmp.rbegin(); it != tmp.rend(); ++it)ra[++lim] = *it;
57
    for(int i = 1; i <= N; ++i){
58
        ll ret = bit.QueryReal(a[i]);
59
        // for(int j = 1; j <= N; ++j)
60
        //     printf("Query range : %d = %lld, point : %d = %lld\n", j, bit.Query(j), j, bit.QueryPoint(j));
61
        // printf("point: %lld, ret = %lld\n", bit.QueryPoint(a[i]), ret);
62
        bit.Modify(a[i], ret + (bit.QueryPoint(a[i]) ? 0 : 1));
63
        ans = (ans + ret) % MOD;
64
    }printf("%lld\n", ans);
65
    fprintf(stderr, "Time: %.6lf\n", (double)clock() / CLOCKS_PER_SEC);
66
    return 0;
67
}
68

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

T2

原题 51nod-1326 遥远的旅途。

同余最短路，又是新的知识点，很奇怪也很阴间，第一眼还以为这玩意是 exgcd，然后发现好像是 exexexexexexexgcd。。。

写了个骗分然后一分没有。。

T3

原题 LG-P8347 「Wdoi-6」另一侧的月。

奇怪的博弈，没找到性质，寄。

T4

原题 CF609E Minimum spanning tree for each edge。

本来已经基本切了。。MST + 树剖，赛时想到了也写了，然后对拍发现边权转点权的时候没忽略 LCA，然后改完感觉问题不大了。。最后发现又犯了个经典 nt 错误。。直接 $100\mathtt{\text{pts}}\to 0\mathtt{\text{pts}}$$100\texttt{pts} \rightarrow 0\texttt{pts}$。

Code

xxxxxxxxxx
182
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 MAXNM (210000)
24

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

28
struct Edge{
29
    Edge* nxt;
30
    int to;
31
    ll val;
32
    OPNEW;
33
}ed[410000];
34
ROPNEW(ed);
35
Edge* head[MAXNM];
36
ll val[210000];
37

38
class UnionFind{
39
private:
40
    int fa[MAXNM];
41
public:
42
    UnionFind(void){for(int i = 1; i <= 201000; ++i)fa[i] = i;}
43
    int Find(int x){return fa[x] == x ? x : fa[x] = Find(fa[x]);}
44
    void Union(int origin, int son){fa[Find(son)] = Find(origin);}
45
}uf;
46

47
int N, M;
48
bool intree[MAXNM];
49
ll ans[MAXNM];
50
ll origin(0);
51
struct Edges{
52
    int val;
53
    int s, t;
54
    int idx;
55
    friend const bool operator < (const Edges &a, const Edges &b){return a.val < b.val;}
56
};
57
vector < Edges > edges;
58
tuple < int, int, int > qs[210000];
59

60
int dfn[MAXNM], fa[MAXNM], hson[MAXNM], siz[MAXNM], dep[MAXNM], top[MAXNM], idx[MAXNM];
61

62
void dfs_edge_to_vertex(int p = 1, int ffa = 0){
63
    for(auto i = head[p]; i; i = i->nxt)
64
        if(SON != ffa)val[SON] = i->val, dfs_edge_to_vertex(SON, p);
65
}
66

67
void dfs_pre(int p = 1, int ffa = 0){
68
    // printf("pre : %d\n", p);
69
    fa[p] = ffa;
70
    siz[p] = 1;
71
    dep[p] = dep[ffa] + 1;
72
    for(auto i = head[p]; i; i = i->nxt){
73
        if(SON == ffa)continue;
74
        dfs_pre(SON, p);
75
        siz[p] += siz[SON];
76
        if(!hson[p] || siz[SON] > siz[hson[p]])hson[p] = SON;
77
    }
78
}
79
void dfs(int p = 1, int tp = 1){
80
    // printf("dfs: %d, %d\n", p, tp);
81
    static int curdfn(0);
82
    dfn[p] = ++curdfn;
83
    idx[curdfn] = p;
84
    top[p] = tp;
85
    if(hson[p])dfs(hson[p], tp);
86
    for(auto i = head[p]; i; i = i->nxt)
87
        if(SON != fa[p] && SON != hson[p])dfs(SON, SON);
88
}
89

90
class SegTree{
91
private:
92
    ll tr[MAXNM << 2];
93
    #define LS (p << 1)
94
    #define RS (LS | 1)
95
    #define MID ((gl + gr) >> 1)
96
public:
97
    void Pushup(int p){tr[p] = max(tr[LS], tr[RS]);}
98
    void Build(int p = 1, int gl = 1, int gr = N){
99
        if(gl == gr)return tr[p] = val[idx[gl = gr]], void();
100
        Build(LS, gl, MID);
101
        Build(RS, MID + 1, gr);
102
        Pushup(p);
103
    }
104
    ll QueryMax(int l, int r, int p = 1, int gl = 1, int gr = N){
105
        // if(l > r || !l || !r)return -1;
106
        // printf("Querying l = %d, t = %d, p = %d, gl = %d, gr = %d\n", l, r, p, gl, gr);
107
        if(l <= gl && gr <= r)return tr[p];
108
        return max(
109
            l <= MID ? QueryMax(l, r, LS, gl, MID) : -1,
110
            MID + 1 <= r ? QueryMax(l, r, RS, MID + 1, gr) : -1
111
        );
112
    }
113
}st;
114

115
ll QueryMax(int s, int t){
116
    ll ret(0);
117
    while(top[s] != top[t]){
118
        if(dep[s] < dep[t])swap(s, t);
119
        ret = max(ret, st.QueryMax(dfn[top[s]], dfn[s]));
120
        // printf("s = %d, t = %d, tps = %d, dfntp = %d, dfn = %d Max:%lld\n", s, t, top[s], dfn[top[s]], dfn[s], st.QueryMax(dfn[top[s]], dfn[s]));
121
        s = fa[top[s]];
122
    }if(dep[s] < dep[t])swap(s, t);
123
    return max(ret, st.QueryMax(dfn[hson[t]], dfn[s]));
124
}
125

126
int main(){
127
    freopen("tree.in", "r", stdin);
128
    freopen("tree.out", "w", stdout);
129
    N = read(), M = read();
130
    for(int i = 1; i <= M; ++i){
131
        int s = read(), t = read(), v = read();
132
        edges.emplace_back(Edges{v, s, t, i});
133
        qs[i] = {s, t, v};
134
    }sort(edges.begin(), edges.end());
135
    for(auto e : edges)
136
        if(uf.Find(e.s) != uf.Find(e.t))
137
            uf.Union(e.s, e.t),
138
            head[e.s] = new Edge{head[e.s], e.t, e.val},
139
            head[e.t] = new Edge{head[e.t], e.s, e.val},
140
            intree[e.idx] = true,
141
            origin += e.val;
142
    dfs_edge_to_vertex();
143
    dfs_pre();
144
    dfs();dfn[0] = 1;
145
    st.Build();
146
    // printf("%d\n", st.QueryMax(5, 5));
147
    for(int i = 1; i <= M; ++i){
148
        if(intree[i]){ans[i] = origin; continue;}
149
        int s, t, v; tie(s, t, v) = qs[i];
150
        // printf("Edge:%d, %d->%d max = %lld\n", i, s, t, QueryMax(s, t));
151
        ans[i] = origin - QueryMax(s, t) + v;
152
    }
153
    for(int i = 1; i <= M; ++i)printf("%lld\n", ans[i]);
154
    fprintf(stderr, "Time: %.6lf\n", (double)clock() / CLOCKS_PER_SEC);
155
    return 0;
156
}
157

158
template < typename T >
159
inline T read(void){
160
    T ret(0);
161
    short flag(1);
162
    char c = getchar();
163
    while(c != '-' && !isdigit(c))c = getchar();
164
    if(c == '-')flag = -1, c = getchar();
165
    while(isdigit(c)){
166
        ret *= 10;
167
        ret += int(c - '0');
168
        c = getchar();
169
    }
170
    ret *= flag;
171
    return ret;
172
}
173
/*
174
5 7
175
1 2 3
176
1 3 1
177
1 4 5
178
2 3 2
179
2 5 3
180
3 4 2
181
4 5 4
182
*/

正解

T2

咕咕咕

T3

咕咕咕

T4

又是经典的 nt 错误，第一次错的时候印象不够深刻。。然后这次又错了，后来自己手推才发现这个逻辑错误，这回估计忘不了了。。。

Code

xxxxxxxxxx
182
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 MAXNM (210000)
24

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

28
struct Edge{
29
    Edge* nxt;
30
    int to;
31
    ll val;
32
    OPNEW;
33
}ed[410000];
34
ROPNEW(ed);
35
Edge* head[MAXNM];
36
ll val[210000];
37

38
class UnionFind{
39
private:
40
    int fa[MAXNM];
41
public:
42
    UnionFind(void){for(int i = 1; i <= 201000; ++i)fa[i] = i;}
43
    int Find(int x){return fa[x] == x ? x : fa[x] = Find(fa[x]);}
44
    void Union(int origin, int son){fa[Find(son)] = Find(origin);}
45
}uf;
46

47
int N, M;
48
bool intree[MAXNM];
49
ll ans[MAXNM];
50
ll origin(0);
51
struct Edges{
52
    int val;
53
    int s, t;
54
    int idx;
55
    friend const bool operator < (const Edges &a, const Edges &b){return a.val < b.val;}
56
};
57
vector < Edges > edges;
58
tuple < int, int, int > qs[210000];
59

60
int dfn[MAXNM], fa[MAXNM], hson[MAXNM], siz[MAXNM], dep[MAXNM], top[MAXNM], idx[MAXNM];
61

62
void dfs_edge_to_vertex(int p = 1, int ffa = 0){
63
    for(auto i = head[p]; i; i = i->nxt)
64
        if(SON != ffa)val[SON] = i->val, dfs_edge_to_vertex(SON, p);
65
}
66

67
void dfs_pre(int p = 1, int ffa = 0){
68
    // printf("pre : %d\n", p);
69
    fa[p] = ffa;
70
    siz[p] = 1;
71
    dep[p] = dep[ffa] + 1;
72
    for(auto i = head[p]; i; i = i->nxt){
73
        if(SON == ffa)continue;
74
        dfs_pre(SON, p);
75
        siz[p] += siz[SON];
76
        if(!hson[p] || siz[SON] > siz[hson[p]])hson[p] = SON;
77
    }
78
}
79
void dfs(int p = 1, int tp = 1){
80
    // printf("dfs: %d, %d\n", p, tp);
81
    static int curdfn(0);
82
    dfn[p] = ++curdfn;
83
    idx[curdfn] = p;
84
    top[p] = tp;
85
    if(hson[p])dfs(hson[p], tp);
86
    for(auto i = head[p]; i; i = i->nxt)
87
        if(SON != fa[p] && SON != hson[p])dfs(SON, SON);
88
}
89

90
class SegTree{
91
private:
92
    ll tr[MAXNM << 2];
93
    #define LS (p << 1)
94
    #define RS (LS | 1)
95
    #define MID ((gl + gr) >> 1)
96
public:
97
    void Pushup(int p){tr[p] = max(tr[LS], tr[RS]);}
98
    void Build(int p = 1, int gl = 1, int gr = N){
99
        if(gl == gr)return tr[p] = val[idx[gl = gr]], void();
100
        Build(LS, gl, MID);
101
        Build(RS, MID + 1, gr);
102
        Pushup(p);
103
    }
104
    ll QueryMax(int l, int r, int p = 1, int gl = 1, int gr = N){
105
        if(l > r || !l || !r)return -1;
106
        // printf("Querying l = %d, t = %d, p = %d, gl = %d, gr = %d\n", l, r, p, gl, gr);
107
        if(l <= gl && gr <= r)return tr[p];
108
        return max(
109
            l <= MID ? QueryMax(l, r, LS, gl, MID) : -1,
110
            MID + 1 <= r ? QueryMax(l, r, RS, MID + 1, gr) : -1
111
        );
112
    }
113
}st;
114

115
ll QueryMax(int s, int t){
116
    ll ret(0);
117
    while(top[s] != top[t]){
118
        if(dep[top[s]] < dep[top[t]])swap(s, t);
119
        ret = max(ret, st.QueryMax(dfn[top[s]], dfn[s]));
120
        // printf("s = %d, t = %d, tps = %d, dfntp = %d, dfn = %d Max:%lld\n", s, t, top[s], dfn[top[s]], dfn[s], st.QueryMax(dfn[top[s]], dfn[s]));
121
        s = fa[top[s]];
122
    }if(dep[s] < dep[t])swap(s, t);
123
    return max(ret, st.QueryMax(dfn[hson[t]], dfn[s]));
124
}
125

126
int main(){
127
    // freopen("tree.in", "r", stdin);
128
    // freopen("tree.out", "w", stdout);
129
    N = read(), M = read();
130
    for(int i = 1; i <= M; ++i){
131
        int s = read(), t = read(), v = read();
132
        edges.emplace_back(Edges{v, s, t, i});
133
        qs[i] = {s, t, v};
134
    }sort(edges.begin(), edges.end());
135
    for(auto e : edges)
136
        if(uf.Find(e.s) != uf.Find(e.t))
137
            uf.Union(e.s, e.t),
138
            head[e.s] = new Edge{head[e.s], e.t, e.val},
139
            head[e.t] = new Edge{head[e.t], e.s, e.val},
140
            intree[e.idx] = true,
141
            origin += e.val;
142
    dfs_edge_to_vertex();
143
    dfs_pre();
144
    dfs();//dfn[0] = 1;
145
    st.Build();
146
    // printf("%d\n", st.QueryMax(5, 5));
147
    for(int i = 1; i <= M; ++i){
148
        if(intree[i]){ans[i] = origin; continue;}
149
        int s, t, v; tie(s, t, v) = qs[i];
150
        // printf("Edge:%d, %d->%d max = %lld\n", i, s, t, QueryMax(s, t));
151
        ans[i] = origin - QueryMax(s, t) + v;
152
    }
153
    for(int i = 1; i <= M; ++i)printf("%lld\n", ans[i]);
154
    fprintf(stderr, "Time: %.6lf\n", (double)clock() / CLOCKS_PER_SEC);
155
    return 0;
156
}
157

158
template < typename T >
159
inline T read(void){
160
    T ret(0);
161
    short flag(1);
162
    char c = getchar();
163
    while(c != '-' && !isdigit(c))c = getchar();
164
    if(c == '-')flag = -1, c = getchar();
165
    while(isdigit(c)){
166
        ret *= 10;
167
        ret += int(c - '0');
168
        c = getchar();
169
    }
170
    ret *= flag;
171
    return ret;
172
}
173
/*
174
5 7
175
1 2 3
176
1 3 1
177
1 4 5
178
2 3 2
179
2 5 3
180
3 4 2
181
4 5 4
182
*/

UPD

update-2022_11_10 初稿