日记 - 伊埃斯的博客站

上午

考试啊，也是根本做不出来。先看了T1，是道简单的树形dp（不会做法假了吧）。T2就直接给我创飞，只能打个 $30$ 分暴力（正解似乎是dp？）。然后，也是头昏脑涨，便睡趴了十五分钟，然后再来想T2。想的实在是没有头绪，就来写日记，给脑子初始化一下，再去想了。今天这个考试，标题是C组，然而题目标题是B组。
表里不一的模拟赛链接看不太懂的题解

T1：给你一个森林，然后让你求每颗树的直径和。
是个学过树形dp的人都会打吧。 $10min$ 就打出来。~~但是我去上厕所的时候，看见 yzp 调了半个小时多，不会又 RE 了吧~~

T2：定义一个子区间的价值是整个子区间里所有的数的 $gcd$ 乘上子区间里所有数的和。
先想到想到了线段树维护区间和和区间 $gcd$ ，然后 $O(n^2)$ 暴力，总时间复杂度 $O(n^2logn)$ 。然后过了 $10min$ 又想到了 $O(n^2)$ 的做法，也算是一大进步，优化掉了一个 $logn$ 。

T3：求众数出现次数大于区间长度的一半的子区间个数。
打一个 $O(n^3)$ 暴力，能拿 $10$ 分（蚊子肉也是肉嘛）

T4：暴力都不想打（每次都这样）
算了，还是试试T4的暴力吧。

总结：还是大菜特菜，还得练（还得练到什么时候去啊）

然后就考完了，反方向的rank4，退役得了。

然后，熊老师说发题解，然而并没有（~~皇帝的新题解~~），于是我就去做dp了，我的dp实在太菜了。

我什么时候能再场切一道蓝题呢？

下午

也是改题。那个私人题解，给的是部分分题解也不说一声，害得我浪费了半个小时，在讲T2前极限改出来。

T1：场切不说。

T2：source
先说那个题解给的私人部分分做法：设值域的上界是 $V$ ， $gcd(l,r)$ 为 $l$ 到 $r$ 的区间 $gcd$ ，则 $gcd(1,r),gcd(2,r),gcd(3,r),...gcd(r,r)$ 至多有 $logV$ 个取值。枚举每一个右端点 $r$ ，设在 $r$ 的 $logV$ 个取值里，有一个取值为 $x$ ，则对于每一个 $x$ ，二分查找最靠左的左端点 $l$ 使得 $gcd(l,r) = x$ 。时间复杂度 $O(n \times logn \times log^2n)$ 。
再说正解：在那 $logV$ 个 $gcd$ 的取值里，我们发现对于每个取值，加一个之后，它就会变成它和 $h_i$ 的 $gcd$ 。这样我们就可以 $logV$ 更新每一个 $gcd$ 。时间复杂度 $O(nlogV)$

T3&T4：没改，晚上再说

晚上

先玩了一会原神（当然是下课玩的，上课没有），然后看到方大三抽出林尼，欸这您受得了吗。

T4：source solution
这个题目解法用文字描述实在是太繁琐了（其实是我不想写，也不会写），于是把代码打在这里好了。

1
#include<bits/extc++.h>
2
#define int long long
3
using namespace std;
4
const int maxn = 65;
5
const int mod = 1e9 + 7;
6
int n,m,k;
7
int head[maxn],idx;
8
int f[maxn][10],dep[maxn];
9
int fa[maxn],l[20];
10
int c[20],d[20];
11
struct edge
12
{
13
    int v,nxt;
14
    edge(int v = 0,int nxt = 0):v(v),nxt(nxt){};
15
}e[maxn << 1];
16
void adde(int u,int v)
17
{
18
    e[++idx] = edge(v,head[u]);
19
    head[u] = idx;
20
}
21
int binpow(int x,int y)//快速幂
22
{
23
    int ret = 1;
24
    while (y)
25
    {
26
        if (y & 1)
27
            ret = ret * x % mod;
28
        x = x * x % mod;
29
        y >>= 1;
30
    }
31
    return ret;
32
}
33
void dfs(int u,int fa)//lca预处理
34
{
35
    f[u][0] = fa;
36
    dep[u] = dep[fa] + 1;
37
    for (int i = 1; i < 10; i++)
38
        f[u][i] = f[f[u][i - 1]][i - 1];
39
    for (int i = head[u]; i; i = e[i].nxt)
40
    {
41
        int v = e[i].v;
42
        if (v == fa)
43
            continue;
44
        dfs(v,u);
45
    }
46
}
47
int lca(int u,int v)//最近公共祖先
48
{
49
    if (dep[u] < dep[v])
50
        swap(u,v);
51
    for (int i = 9; i >= 0; i--)
52
        if (dep[u] - (1 << i) >= dep[v])
53
            u = f[u][i];
54
    if (u == v)
55
        return u;
56
    for (int i = 9; i >= 0; i--)
57
        if (f[u][i] != f[v][i])
58
            u = f[u][i],v = f[v][i];
59
    return f[u][0];
60
}
61
void init()//并查集初始化
62
{
63
    for (int i = 1; i <= n; i++)
64
        fa[i] = i;
65
}
66
int find(int x)//并查集查找
67
{
68
    if (fa[x] == x)
69
        return x;
70
    return fa[x] = find(fa[x]);
71
}
72
signed main()
73
{
74
    scanf("%lld%lld%lld",&n,&m,&k);
75
    for (int i = 1; i < n; i ++)
76
    {
77
        int u,v;
78
        scanf("%lld%lld",&u,&v);
79
        adde(u,v);
80
        adde(v,u);
81
    }
82
    dfs(1,0);
83
    for (int i = 1; i <= m; i++)
84
    {
85
        scanf("%lld%lld",c + i,d + i);
86
        l[i] = lca(c[i],d[i]);//预处理lca
87
    }
88
    int ans = binpow(k,n - 1),g,sum;
89
    int tmp1,tmp2,st,en;
90
    for (int i = 1; i < (1 << m); i++)
91
    {
92
        g = 1,sum = 0;
93
        init();
94
        for (int j = 0; j < m; j++)
95
        {
96
            if (i & (1 << j))
97
            {
98
                g = -g;//容斥的正负性
99
                st = c[j + 1];//从一个点到lca
100
                while (st != l[j + 1])
101
                {
102
                    if (f[st][0] == l[j + 1])
103
                        break;
104
                    tmp1 = find(st),tmp2 = find(f[st][0]);
105
                    if (tmp1 != tmp2)
106
                        fa[tmp1] = tmp2;//合并连通块
107
                    st = f[st][0];//往上跳
108
                }
109
                en = d[j + 1];//从另一个点到lca
110
                while (en != l[j + 1])
111
                {
112
                    if (f[en][0] == l[j + 1])
113
                        break;
114
                    tmp1 = find(en),tmp2 = find(f[en][0]);
115
                    if (tmp1 != tmp2)
116
                        fa[tmp1] = tmp2;//合并连通块
117
                    en = f[en][0];//往上跳
118
                }
119
                if (st != l[j + 1] && en != l[j + 1])
120
                {
121
                    tmp1 = find(st);
122
                    tmp2 = find(en);
123
                    if (tmp1 != tmp2)
124
                        fa[tmp1] = tmp2;
125
                }//如果都不是lca就把两个点合并
126
            }
127
        }
128
        for (int j = 2; j <= n; j++)
129
            if (fa[j] == j)
130
                sum ++;//计数连通快
131
        ans = (ans + g * binpow(k,sum) % mod + mod) % mod;//记录答案
132
    }
133
    ans = (ans + mod) % mod;
134
    cout << ans;
135
    return 0;
136
}

打完了它还 WA 了一次，死因：没开 long long （虽然这也不是第一次）。

然后就只剩 $20$ 分钟了，切点水题吧。

Thanks for reading!

日记

周二 11月 26 2024

1373 字 · 9 分钟

life 日记