Loading... ## A [冰狱寒岚](https://ac.nowcoder.com/acm/contest/11219/A) 一个整环平移一下就行了，略过。 ## B [光之屏障](https://ac.nowcoder.com/acm/contest/11219/B) Q: 要求在一个区间内找一个$2^n$。 A: 把大数取最高位$1$然后看看是否不小于小数即可。 ## C [寒潭烟光](https://ac.nowcoder.com/acm/contest/11219/C) Q: 给你一个数列前缀和的平均数，然后求这个数列最前面插入一个数字之后的新数列的前缀和的平均数。 A: 动手推一下式子就能发现不需要枚举任何东西，直接计算就行了。  ## D [金蛇狂舞](https://ac.nowcoder.com/acm/contest/11219/D) ### 题意 一个搜索题。 给定正整数$x$和$y$，问$x$能否在有限步操作内变成$y$： 1. 变为$x$阶乘 2. 开根号向上取整 3. 开根号向下取整 ### 分析 观察到数据很小$(x,y\le7)$所以经典爆搜。阶乘会无限扩大，所以必须要进行可行性剪枝。 当一个数字达到某个界限$lim$之后，它就无法在合理的开根号步数内回到题给范围了。 略加计算，大概对于$fac(25)$，回到7以内就需要至少5次开根号了。而一个数字达到25又需要一次$fac$，因此对于25以上的数字就不需要再计算阶乘了。 由于是求最短路，所以**IDDFS**非常好写： ### 代码 ```cpp #include <bits/stdc++.h> using namespace std; #define mp(x, y) make_pair(x, y) #define FOR(x, y, z) for (int x = y; x <= z; x++) typedef long long ll; int t; int x, y; ll frac(int x) { ll ans = 1; for (int i = 2; i <= x; i++) ans *= i; return ans; } bool dfs(ll x, ll y, int dep, int lim) // iddfs { if (dep > lim) return false; if (x == y) return true; if (x <= 25 && dfs(frac(x), y, dep + 1, lim)) return true; ll sq = sqrt(x); if (dfs(sq, y, dep + 1, lim) || sq * sq < x && dfs(sq+1, y, dep + 1, lim)) return true; return false; } int main() { cin >> t; while (t--) { cin >> x >> y; int ok = -1; if (x == y) { cout << 0 << endl; continue; } for (int i = 1; i <= 7; i++) if (dfs(x, y, 0, i)) { ok = i; break; } cout << ok << endl; } return 0; } ``` 由于limit_depth是从1开始，那么就要额外特判一下$x$和$y$相等的情况。 ## E [暗灭侵蚀](https://ac.nowcoder.com/acm/contest/11219/E) Q: 给定$3$个棋子在数轴上，每次可选一个棋子以最右边棋子为中点进行跳跃，问多少次可以有棋子跳到$[N,+\infty)$范围内。 A: 一眼贪心，每次都选最左边棋子进行跳跃就好了。 ## F [火凤燎原](https://ac.nowcoder.com/acm/contest/11219/F) ### 题意 给定一棵无根树，求蒲公英（单点挂简单链）子图个数。 ### 分析 一开始没看到除了那条链以外的$k-1$个节点必须是单点......思考难度直接绿变紫（**这种事情已经发生过好多次了，浪费了很多时间，是该认真反思一下了**。 事实上有了这个条件，每个点作为中心点能构成的蒲公英树的情况，就仅取决于**长链延伸到哪里**。这样，对于每个中心点$root$，我们就可以枚举它的所有子节点$x$，计算它的贡献$C(x)$： 因为我们是从以$x$为根节点的子树取长链，那么就可以枚举**长链终点**，从而有 $$ C(x) = size(x)-1 $$ 其中$-1$是因为自己不能做长链终点，那样长度就不满足要求。 因此对于每个中心点$root$，就有 $$ \Sigma_{x\in sons(root)}size(x)-1 $$ 应当注意到，这个式子把整棵树都涉及到了，那么展开求和式，得到它其实就等于 $$ \Sigma size(son\space of \space root)-deg[root]=n-1-deg[root] $$ 好了，枚举每个点计算一下就行了。枚举时，记得判断每个点可以作为中心点的条件。这里不用担心没有长链的存在，观察以上式子，如果子树提供不出长链，那么因为自身会被$-1$，不会提供额外贡献。那么特判一下$deg[root]\ge3$即可，否则它不是蒲公英而是一条简单链。 ### 代码 ```cpp #include <bits/stdc++.h> using namespace std; #define mp(x, y) make_pair(x, y) #define FOR(x, y, z) for (int x = y; x <= z; x++) typedef long long ll; #define N 500005 int t, n; int con[N]; int main() { cin.sync_with_stdio(false); cin.tie(0); cin >> t; while (t--) { cin >> n; FOR(i, 1, n) con[i] = 0; FOR(i, 1, n - 1) { int x, y; cin >> x >> y; con[x]++, con[y]++; } ll ans = 0; FOR(i, 1, n - 1) if (con[i] >= 3) ans += n - 1 - con[i]; cout << ans << '\n'; } return 0; } ``` 这里还有个坑点，就是每次memset的话时间复杂度就炸了，所以要利用题给的$\Sigma n\le2e6$的条件去循环赋初值。记得关流同步，本题略卡常数。 ## 笔记 虽然最后一题有了那个条件之后很简单，但因为看起来像，所以还是记一下换根DP的笔记吧。 换根DP： 第一遍搜索统计节点贡献，第二遍的时候对于每一个当前点$v$和父亲$fa$，把$v$视作根节点，找到一个方便的方式（柿子）把$contribute(fa\rightarrow v)$推出来即可。这个一般会基于贡献的某种可逆的性质，或者基于父节点的其他子节点及其父节点，通过某种确定的和式或者积式推出来。 © 允许规范转载 打赏 赞赏作者 赞 如果觉得我的文章对你有用，请随意赞赏