Tsawke 的十月模拟赛 题解

T1 这是一道比原来的T1更像T1的妙妙性质题

原题是 LG-P5497 [LnOI2019SP]龟速单项式变换(SMT)，原题范围 ${10}^{18}$$10^{18}$，我感觉没意思就加强到了 ${10}^{{10}^6}$$10^{10^6}$，不用谢。

首先有个结论：$n\ge m$$n \ge m$ 则成立，反之不成立，所以原题直接读入 $n,m$$n, m$ 然后 n >= m ? "Yes" : "No" 即可，对于本题也就是用字符串读入，先判断一下长度再按位判断就行。

然后考虑证明这个结论，我们假装对这个序列做一个前缀和，令 $s_i$$s_i$ 表示 $\sum _{j=1}^i{a}_j$$\sum_{j = 1}^{i} a_j$，显然若 $\mathrm{\exists }i,j$$\exists i, j$ 满足 $m\mid s_i-s_j$$m \mid s_i - s_j$，那么则合法。

我们考虑对于每一个 $s_i$$s_i$，$s_{i}modm$$s_i \bmod{m}$ 共有 $m-1$$m - 1$ 种取值，若 $s_i$$s_i$ 的数量，或者说 $n$$n$，满足 $n\ge m$$n \ge m$，那么一定会至少有一对 $s_i\equiv s_j(\mathrm{mod}m)$$s_i \equiv s_j \pmod{m}$，这个东西俗称鸽巢原理，应该很显然吧？然后有了这个式子，那么 $s_i-s_j\equiv 0modm$$s_i - s_j \equiv 0 \bmod{m}$ 也就很显然了，所以 $n\ge m$$n \ge m$ 显然有解，至于构造的话任选 $n$$n$ 个数就是了。

对于 $n<m$$n \lt m$ 也很显然，一定可以构造出一个前缀和的序列满足每个 $s_{i}modm$$s_i \bmod{m}$ 都不同，这样也就无法找到满足条件的一对 $i,j$$i, j$ 了。

xxxxxxxxxx
58
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
string N, M;
27
#define EXIT(f) printf("%s\n", f ? "NO" : "YES"), exit(0)
28
// #define EXIT(f) printf("%s\n", f ? "YES" : "NO"), exit(0)
29

30
int main(){
31
    freopen("intriguing_t1.in", "r", stdin);
32
    freopen("intriguing_t1.out", "w", stdout);
33
    cin >> N >> M;
34
    if(N.length() > M.length())EXIT(true);
35
    if(N.length() < M.length())EXIT(false);
36
    for(int i = 1; i <= (int)N.length(); ++i){
37
        if(N.at(i - 1) > M.at(i - 1))EXIT(true);
38
        if(N.at(i - 1) < M.at(i - 1))EXIT(false);
39
    }EXIT(true);
40
    fprintf(stderr, "Time: %.6lf\n", (double)clock() / CLOCKS_PER_SEC);
41
    return 0;
42
}
43

44
template<typename T>
45
inline T read(void){
46
    T ret(0);
47
    short flag(1);
48
    char c = getchar();
49
    while(c != '-' && !isdigit(c))c = getchar();
50
    if(c == '-')flag = -1, c = getchar();
51
    while(isdigit(c)){
52
        ret *= 10;
53
        ret += int(c - '0');
54
        c = getchar();
55
    }
56
    ret *= flag;
57
    return ret;
58
}

T2 最喜欢推柿子了

原创题，没原题，需要的话或许我可以在 Luogu 做一道？？

emm 就是按照给的那几个公式去推一下式子就行。

然后即可 $O(1)$$O(1)$ 求解。

xxxxxxxxxx
60
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
typedef __float128 f128;
24

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

28
int main(){
29
    freopen("tomato.in", "r", stdin);
30
    freopen("tomato.out", "w", stdout);
31
    ll N = read<ll>(), X = read<ll>();
32
    f128 tmp1 = sinf128(((f128)N + (f128)0.5) * X) * sinf128((f128)X / (f128)2);
33
    f128 tmp2 = (f128)1.0 - cosf128((f128)X);
34
    f128 ans = (f128)0.5 + tmp1 / tmp2;
35
    printf("%.6lf\n", (double)ans);
36

37
    // f128 anss(0.0);
38
    // for(ll i = 0; i <= N; ++i){
39
    //     anss += cosf128((f128)i * (f128)X);
40
    // }
41
    // printf("%.6lf\n", (double)anss);
42
    fprintf(stderr, "Time: %.6lf\n", (double)clock() / CLOCKS_PER_SEC);
43
    return 0;
44
}
45

46
template<typename T>
47
inline T read(void){
48
    T ret(0);
49
    short flag(1);
50
    char c = getchar();
51
    while(c != '-' && !isdigit(c))c = getchar();
52
    if(c == '-')flag = -1, c = getchar();
53
    while(isdigit(c)){
54
        ret *= 10;
55
        ret += int(c - '0');
56
        c = getchar();
57
    }
58
    ret *= flag;
59
    return ret;
60
}

T3 划水？想屁吃！

原题 LG-P4220 [WC2018]通道。是的这是一道黑色的 WC。

虚树 + 点分治什么是虚树？？我不会！

显然作为机房最弱的 tsawke 不可能会虚树分治，也不可能出虚树的题，所以这道题是爬山。

显然出题人想让我们用爬山算法解决。显然 Hack 数据也可以用奇怪的爬山通过。

（原时限 4000ms，因为是在虚拟机中测评，会慢不少，于是开了 6000ms）

考虑发现似乎这玩意是个多峰函数，于是我们可以尝试多点爬山，没必要用退火（我感觉退火应该也能过）。

考虑在时限范围内，每次随机选择一个为选择过的节点，作为起始点 $S$$S$，对于这个的找最优终点应该很显然吧，树形结构，随便搜一下，以 $S$$S$ 为根记录一下深度，然后跑一遍找三个图中的距离加和最大的，此时的结果便是当前最优解，以其更新 $ans$$ans$。然后这里人类智慧就来了，考虑我们找直径的时候不是两次 dfs 求解吗，我们也可以这么去考虑，把这次的终点 $T$$T$ 作为新的 $S$$S$ 然后再跑下一个终点，这个东西可以随便重复个几次，作为一次爬山，注意每次记录已经当过起点的点，下次不选这些。

然后再重新随机一个点再爬一次山，这就是多点爬山了。。。可以考虑加个卡时稳一点。然后这个东西只要你写的不是特别丑，Luogu 随便过，但是在 loj 上存在三个 Hack 数据，这样的爬山会被卡掉，当然毒瘤的 tsawke 也把这三个数据搬过来了，于是我们考虑一些新的人类智慧，在更新答案的时候像以前一样更新，然后在我们从当前的 $S$$S$ 找 $T$$T$ 作为新的 $S$$S$ 的时候，我们只考虑任意两棵树型结构，或者任意一棵树形结构的贡献去更新新的 $S$$S$。这个东西是什么原因呢，通过观察数据揣摩出 Hack 数据的人的思想，我们可以想到想要让我们这个多点爬山变假的办法，基本就只能是让不同树形结构之间差距特别大，但是正解又在一个不太符合权值最大的树的单调性的位置上，这样我们就很难通过爬山去找到那个奇怪的正解的位置，于是我们考虑用一个类似枚举子集的方法去消除掉某一两棵树的贡献，只用三棵树里的一部分去作为那个多峰函数找最优解。

然后考虑在实现中，先跑几次一般的爬山，以保证对于一般数据都能通过，可以设为 $10$$10$ 次。然后再去跑这几个人类智慧的爬山，中间如果时间快要超限了就直接 exit，这样就可以也通过 loj 上的所有数据。

和出题人斗智斗勇了属于是。

xxxxxxxxxx
101
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 110000
24
#define MAX_TIME (double)(5.2)
25
#define CURRENT_TIME ((double)clock() / CLOCKS_PER_SEC)
26

27
template<typename T = int>
28
inline T read(void);
29

30
struct Edge{
31
    Edge* nxt;
32
    int to;
33
    ll val;
34
    OPNEW;
35
}ed[MAXN * 6];
36
ROPNEW(ed);
37

38
int N;
39
Edge* head[4][MAXN];
40
ll dis[4][MAXN];
41
bool vis[4][MAXN];
42
bool used[MAXN];
43
ll ans(-1);
44

45
void dfs(int p, int ver, int fa = -1){
46
    for(auto i = head[ver][p]; i; i = i->nxt){
47
        if(SON == fa)continue;
48
        dis[ver][SON] = dis[ver][p] + i->val;
49
        dfs(SON, ver, p);
50
    }
51
}
52
void Luangao(int f1, int f2, int f3){
53
    int rt = rndd(1, N);
54
    while(used[rt] && CURRENT_TIME < MAX_TIME)rt = rndd(1, N);
55
    int T = 10;
56
    while(T--){
57
        if(used[rt])break;
58
        used[rt] = true;
59
        for(int i = 1; i <= 3; ++i)dis[i][rt] = 0, dfs(rt, i);
60
        ll mx(0);
61
        for(int i = 1; i <= N; ++i){
62
            ans = max(dis[1][i] + dis[2][i] + dis[3][i], ans);
63
            if(!used[i] && dis[1][i] * f1 + dis[2][i] * f2 + dis[3][i] * f3 > mx)
64
                mx = dis[1][i] * f1 + dis[2][i] * f2 + dis[3][i] * f3, rt = i;
65
        }
66
    }
67
}
68
signed main(){
69
    freopen("escape_from_llq.in", "r", stdin);
70
    freopen("escape_from_llq.out", "w", stdout);
71
    N = read();
72
    for(int i = 1; i <= 3; ++i)
73
        for(int j = 1; j <= N - 1; ++j){
74
            int s = read(), t = read(); ll v = read<ll>();
75
            head[i][s] = new Edge{head[i][s], t, v};
76
            head[i][t] = new Edge{head[i][t], s, v};
77
        }
78
    for(int i = 1; i <= 10 && CURRENT_TIME < MAX_TIME; ++i)Luangao(1, 1, 1);
79
    for(int i = 0; i <= 1; ++i)for(int j = 0; j <= 1; ++j)for(int k = 0; k <= 1; ++k)
80
        if(CURRENT_TIME < MAX_TIME)Luangao(i, j, k);
81
    
82
    printf("%lld\n", ans);
83
    fprintf(stderr, "Time: %.6lf\n", (double)clock() / CLOCKS_PER_SEC);
84
    return 0;
85
}
86

87
template<typename T>
88
inline T read(void){
89
    T ret(0);
90
    short flag(1);
91
    char c = getchar();
92
    while(c != '-' && !isdigit(c))c = getchar();
93
    if(c == '-')flag = -1, c = getchar();
94
    while(isdigit(c)){
95
        ret *= 10;
96
        ret += int(c - '0');
97
        c = getchar();
98
    }
99
    ret *= flag;
100
    return ret;
101
}

T4 什么阴间三元环

一道新的原创题，没原题，一般的三元环计数你们都会吧？？

就是把无向图的边定向，从度数大的指向度数小的，度数相同的按照编号偏序，然后从每个点枚举出点再枚举出点的出点，如果出点的出点也是起始点的出点的话那么就构成一个三元环，这样不重不漏且复杂度为 $O(m\sqrt{m})$$O(m \sqrt{m})$。对于有向图三元环计数，当成无向图按照原来方法做然后判断一下原图是否存在这几条边就行，这样可以过一点部分分。

然后还有 $m=0$$m = 0$ 的时候，这时候画一下就会发现无法构成任何三元环，于是 puts("0") 即可。

然后在每有一个 $m$$m$ 操作的时候显然一定编号小的点出点 $-1$$-1$，编号大的那个出点 $+1$$+1$，这玩意感觉是可以 $O(1)$$O(1)$ 左右维护的吧可能，于是这是最后一个部分分。

然后考虑正解，显然对于三元环三个点，我们认为它们是一个有序三元组 $(u,v,w)$$(u, v, w)$，要求有 $u\to u\to w$$u \rightarrow u \rightarrow w$，那么竞赛图中一共有 $(\genfrac{}{}{0ex}{}{n}{3})$$n \choose 3$ 个这样的三元组，这很显然。然后考虑令点 $i$$i$ 的出点的集合为 ${\mathbb{V}}_i$$\mathbb{V}_i$，于是显然对于 $u$$u$，如果有 $v,w\in {\mathbb{V}}_u$$v, w \in \mathbb{V}_u$，那么这一定无法构成三元环。同时显然这样的三元组会且仅会在 $u$$u$ 被枚举到一次，于是最终的式子便为：$(\genfrac{}{}{0ex}{}{n}{3})-\sum _{i=1}^n(\genfrac{}{}{0ex}{}{|{\mathbb{V}}_i|}{2})$${n \choose 3} - \sum_{i = 1}^n {\vert \mathbb{V}_i \vert \choose 2}$。

然后这样的话显然初始时为 $0$$0$，每次 $m$$m$ 的操作，我们把小的数作为 $s$$s$，大的数作为 $t$$t$，然后把原来减掉的组合数加回来，修改出点的数量，再把新的组合数减回去，处理好取模即可。

复杂度 $O(n+m)$$O(n + m)$。

xxxxxxxxxx
88
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 MOD 1145141
24
#define MAXN 11000000
25

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

29
int N, M;
30
ll fact[MAXN], inv[MAXN];
31
ll qpow(ll a, ll b){
32
    ll ret(1), mul(a);
33
    while(b){
34
        if(b & 1)ret = ret * mul % MOD;
35
        b >>= 1;
36
        mul = mul * mul % MOD;
37
    }
38
    return ret;
39
}
40
void Init(void){
41
    fact[0] = 1;
42
    for(int i = 1; i <= N; ++i)fact[i] = fact[i - 1] * i % MOD;
43
    inv[N] = qpow(fact[N], MOD - 2);
44
    for(int i = N - 1; i >= 0; --i)inv[i] = inv[i + 1] * (i + 1) % MOD;
45
}
46
ll GetC(ll n, ll m){
47
    if(m > n)return 0;
48
    return fact[n] * inv[m] % MOD * inv[n - m] % MOD;
49
}
50
ll out_pts[MAXN];
51
bool changed[MAXN];
52
ll ans(0);
53
int main(){
54
    freopen("fxxk_triatomic_ring.in", "r", stdin);
55
    freopen("fxxk_triatomic_ring.out", "w", stdout);
56
    N = read(), M = read();
57
    Init();
58
    for(int i = 1; i <= N; ++i)out_pts[i] = N - i;
59
    ans = GetC(N, 3);
60
    for(int i = 1; i <= N; ++i)ans = (ans - GetC(out_pts[i], 2) + MOD) % MOD;
61
    printf("%lld\n", ans);
62
    while(M--){
63
        int s = read(), t = read();
64
        if(s > t)swap(s, t);
65
        ans = ((ans + GetC(out_pts[s], 2)) % MOD + GetC(out_pts[t], 2)) % MOD;
66
        --out_pts[s], ++out_pts[t];
67
        ans = ((ans - GetC(out_pts[s], 2) + MOD) % MOD - GetC(out_pts[t], 2) + MOD) % MOD;
68
        printf("%lld\n", ans);
69
    }
70
    fprintf(stderr, "Time: %.6lf\n", (double)clock() / CLOCKS_PER_SEC);
71
    return 0;
72
}
73

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

T6 不会有人语法题都切不掉吧？不会吧不会吧？

emm 没什么可说的，也算是搬的题吧，从某个网页上复制下来的。

原链接 C++「阅读程序」小测验。链接里更多的题和题解都有，感兴趣可以看看。

T5 嗯？又是data_struct？

原题 LG-P4688 [Ynoi2016] 掉进兔子洞

奇怪的数据结构题，正解是莫队套 bitset。

首先很显然，如果我们设三个区间中的交集大小为 $\xi$$\xi$，那么最终的答案即为 $(r_1-l_1+1)+(r_2-l_2+1)+(r_3-l_3+1)-3\times \xi$$(r_1 - l_1 + 1) + (r_2 - l_2 + 1) + (r_3 - l_3 + 1) - 3 \times \xi$。

所以那么我们所未知的需要求的也就只有 $\xi$$\xi$，考虑如何维护，因为我们要维护的是公共的数的个数，而不是种类数，而我们显然是需要对这个序列进行离散化的，所以我们可以考虑在离散化的时候做一点文章，一般的离散化，对于相同的数我们会用同一个数代替，但是这里我们可以考虑存一下每一个数已经出现了几次，令其为 $cn{t}_i$$cnt_i$，于是我们可以考虑不去使用 unique 以为每个数留下足够的空间，然后让相同的数，假设其离散化后的值为 $v$$v$，就变成 $cn{t}_v+v$$cnt_v + v$，也就是让相同的数变成不同的，这样之后我们再用 bitset 套个莫队，每个 bitset 维护当前莫队区间内让每个数变得不同之后的第 $i$$i$ 个是否存在，然后三个区间维护好后做一下与运算就行，输出答案的时候我们要求的 $\xi$$\xi$ 也就是对应 bitset 的 count()。

同时需要注意这么多 bitset 空间显然开不下，但是时间还在可以接受的范围内，所以考虑时间换空间，因为询问之间独立，所以把询问拆成三份，分别求解后输出答案即可。

最终复杂度感觉大概是 $O(n\sqrt{n}+{\displaystyle \frac{nm}{\omega }})$$O(n \sqrt{n} + \dfrac{nm}{\omega})$，应该没算错吧，虽然对于后一项，感觉不太能过，但是确实也是 $O(\mathtt{\text{能过}})$$O(\texttt{能过})$，可能因为完全卡不满吧。。。（或者是我算错了）

xxxxxxxxxx
102
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 BLK(x) (x / QueryLen + 1)
24
#define MAXN 110000
25

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

29
int N, M;
30
int QueryLen;
31
int splitM;
32
int a[MAXN];
33
int cnt[MAXN], len[MAXN];
34
bitset < MAXN > cur;
35
bitset < MAXN > sum[MAXN / 3 + 10];
36

37
struct Query{
38
    int l, r;
39
    int idx;
40
    friend const bool operator < (const Query &x, const Query &y){
41
        int xb = BLK(x.l), yb = BLK(y.l);
42
        if(xb != yb)return xb < yb;
43
        return xb & 1 ? x.r < y.r : x.r > y.r;
44
    }
45
};
46
void add(int v){cur.set(v + cnt[v]++);}
47
void del(int v){cur.reset(v + --cnt[v]);}
48
void Solve(void){
49
    memset(cnt, 0, sizeof(cnt));
50
    cur.reset();
51
    int tot(0);
52
    vector < Query > qs;
53
    while(++tot <= splitM && M--){
54
        len[tot] = 0;
55
        sum[tot].set();
56
        int T = 3;
57
        while(T--){
58
            int l = read(), r = read();
59
            qs.push_back(Query{l, r, tot});
60
            len[tot] += r - l + 1;
61
        }
62
    }sort(qs.begin(), qs.end());
63
    int gl(1), gr(0);
64
    for(auto q : qs){
65
        while(gl > q.l)add(a[--gl]);
66
        while(gr < q.r)add(a[++gr]);
67
        while(gl < q.l)del(a[gl++]);
68
        while(gr > q.r)del(a[gr--]);
69
        sum[q.idx] &= cur;
70
    }--tot;
71
    for(int i = 1; i <= tot; ++i)
72
        printf("%d\n", len[i] - 3 * (int)sum[i].count());
73
}
74
int main(){
75
    freopen("d0te__sturct.in", "r", stdin);
76
    freopen("d0te__sturct.out", "w", stdout);
77
    N = read(), M = read();
78
    vector < int > arr;
79
    for(int i = 1; i <= N; ++i)a[i] = read(), arr.push_back(a[i]);
80
    QueryLen = sqrt(N), splitM = M / 3 + 1;
81
    sort(arr.begin(), arr.end());
82
    for(int i = 1; i <= N; ++i)a[i] = distance(arr.begin(), lower_bound(arr.begin(), arr.end(), a[i])) + 1;
83
    Solve(), Solve(), Solve();
84
    fprintf(stderr, "Time: %.6lf\n", (double)clock() / CLOCKS_PER_SEC);
85
    return 0;
86
}
87

88
template<typename T>
89
inline T read(void){
90
    T ret(0);
91
    short flag(1);
92
    char c = getchar();
93
    while(c != '-' && !isdigit(c))c = getchar();
94
    if(c == '-')flag = -1, c = getchar();
95
    while(isdigit(c)){
96
        ret *= 10;
97
        ret += int(c - '0');
98
        c = getchar();
99
    }
100
    ret *= flag;
101
    return ret;
102
}