test０４１１
九思
·
·
个人记录
同步于CSDN
欢乐（？）模拟赛Day_2
人入從衆，衆從入人（人入从众，众从入人）：
一個人要是開始跟隨大衆，那麼大衆的思想就會因此潛移默化這個人。
## 題目分析
### T1 decomposition
$\ \ \ \ \ \ $題意：(抄的)给一棵以1为根的有根树,开始只有1有标记。每次操作可以给某个点打上标记,或者询问从某个点开始向上跳,遇到的第一个有标记的点。
$\ \ \ \ \ \ $思路：揣測了出題人的良心，覺得可能是樹鏈剖分，然後~~放棄了~~想了一下打了暴力，因爲某個點的答案就是最近有標記的點，所以暴力處理修改，可以做到$O(1)$查詢。
$\ \ \ \ \ \ $正解：需要將均衡一下查詢和修改的複雜度——變成$O(log_2n)$。（抄的）分析性质, 如果一个点 x 从始至终都没有被标记, 就可以把 x 合并到 x 的父亲上去。而並查集從來都是往上走，那——**逆**過來做，由于当前询问的答案只和**前面的**修改有关，沒有打過標記的點的案可以直接併入父親。那麼增標記就變成了刪標記和合併。
$\ \ \ \ \ \ $模型：`Pay phone packing sequence`
### T2 tenki（AC）
$\ \ \ \ \ \ $題意：第1个人选择第1个座位坐下。之后的每个人进入时, 他会选择一个离最近的已经坐下的人尽可能远的空位。如果有多个空位使得离最近的人同样远, 则从中随机选取一个。若有两个人选择的位置相邻, 他们就会不满意。为了让所有人都满意, 至少需要几个座位？
$\ \ \ \ \ \ $正解：發現前兩個人一定佔據最左和最右。第三個人會佔據最中間，第四個人會佔據第一/二個人和第三個人的最中間……那麼除了前兩個人是特殊情況，可以推出一個式子——n個座位可以坐的人數$f(n)$的遞推式：
```cpp
if(n<=0) return 0;
if(n<=3) return 1;
if(n&1) return 2*f((n>>1)-1)+1;
return f((n>>1)-2)+f((n>>1)-1)+1;
```
$\ \ \ \ \ \ $二分答案，我們可以得到n個人需要的座位數。顯然，這不夠快。
$\ \ \ \ \ \ $利用這個遞推式打表——然後發現了規律：每第$2^n+2$項出現斷層(積累兩位空隙到飽和狀態)，很容易（高中必修五）得到通式：$f(x)=x+2^{1+\lfloor{log_2(x-2)}\rfloor}$（但是我的通式比這個麻煩多了艹）
$\ \ \ \ \ \ $高精度。
### T3 mafumafu
$\ \ \ \ \ \ $看 都 沒 看 但是**mafumafu是小天使**
$\ \ \ \ \ \ $高精度掛了很多次，沒時間了。
$\ \ \ \ \ \ $題意：（抄的）给定一个正整数 k , 以及一棵n个节点的以1为根的有根树, 边有长度.
$\ \ \ \ \ \ $记$LCA(a,b)$表示$a$与$b$在树上的最近公共祖先,$dist(x)$表示树根到$x$的距离.
$\ \ \ \ \ \ $每个节点可以是黑色或白色, 初始时每个节点的颜色为白色.进行$m$次操作, 每次操作是以下两种形式之一:
$\ \ \ \ \ \ $修改操作: 给出一个修改节点$x$,将节点$x$染上黑色.
$\ \ \ \ \ \ $询问操作: 给出一个询问节点$x$, 记所有黑点形成的集合为$S$, 求出下面式子的值：
$$\sum\limits_{y\in S}^{} F(dist(LCA(x, y)))$$
其中F函數爲
$$F(x)=\sum\limits_{i=1}^ni^k$$
答案對998244353取模。
$\ \ \ \ \ \ $正解：先從k=0入手，那麼只要求
$$\sum\limits_{y\in S}^{} dist(LCA(x, y))$$
$\ \ \ \ \ \ $由于LCA到根的距离就是x,y到根的路径交集的长度,所以每加入一个点y时,利用**差分**的思想，就将y到根的路径上所有边的覆盖次数+1,询问时答案就是x到根的路径上每条边的长度$\times$它的覆盖次数。（k=0時，長度增加1，權值亦只增加1，因此權值即長度）
$\ \ \ \ \ \ $k$\not=$0的情況就很顯然了，長度從i-1增加到i，權值增加$i^k$，那麼也可以差分，那麼邊$(u,v)$權值也是固定的，爲$F(dist(v))-F(dist(u))$。維護一個樹上邊有權值的區間的查詢和修改，用樹鏈剖分。
$\ \ \ \ \ \ $關於$F(x)$的預處理，若$f(n)=n^k,n=xy$，則，$f(n)=n^k=(xy)^k=x^ky^k=f(x)f(y)$，即積性函數，可以用線性篩處理合數。
## 考試總結
$\ \ \ \ \ \ $自閉了，其實比較有性質的題目但是沒有去鑽。大衆分也沒有把握拿到。運氣成分偏大。
$\ \ \ \ \ \ $屬於那種見過的可能會做，沒見過的一定不會做。
$\ \ \ \ \ \ $但是不得不說，寫代碼前捋一捋思路還是有好處的~~雖然還是寫到一半懵了~~