I 杰哥再找对象 题解 我们可以通过枚举结点 111 和结点 nnn 所在的连通块中结点的个数计算，设答案为 ana_nan​ ，则： an={∑k=2n((n−2k−2)bkcn−k)n≥21n=1a_n=\begin{cases} \displaystyle\sum\limits_{k=2}^{n}\left({n-2 \choose k-2}b_{k}c_{n-k}\right) & \text {$n\geq 2$} \\ 1 & \text {$n=1$} \end{cases}an​=⎩⎪⎨⎪⎧​k=2∑n​((k−2n−2​)bk​cn−k​)1​n≥2n=1​ ...

H. 杰哥抓气球 题解 明显，处于 (0,0)(0,0)(0,0) 的点不需要任何代价。 如果点到原点的距离为整数，则代价为 222，比如 (3,4)(3,4)(3,4) 和 (0,5)(0,5)(0,5)。否则，任何点都可以通过走平行于 x,yx,yx,y 轴的直线到达，只需要两步，一去一来代价为 444。例如 (7,8)(7,8)(7,8) 可以通过 (0,0)→(0,7)→(7,8)(0,0) \to (0,7)\to (7,8)(0,0)→(0,7)→(7,8) 来实现。 std: #include<bits/sdc++.h> using namespace std; in...

G. 杰哥哄对象 解法一： 朴素 DP： 易知：当前字母的改变花费只和前一个字母的值和位置有关。 很容易可以想到三维的 DP，一维代表当前的串，二维表示当前最后一个字母的值，第三维表示当前字母是在奇/偶数位置。 用 0 来表示偶数位置，1表示奇数位置。首先有 f0,i,0←0,i∈Σf_{0,i,0}\leftarrow 0,i \in \Sigmaf0,i,0​←0,i∈Σ。 用 SSS 表示字符串，可得： {fi,j,0←min⁡(fi−1,j,0+1,fi−1,j,1+[j=Si])fi,j,1←k∈Σ{fi,k,0+[j=Si]}\left \{ \begin{aligned} f_{...

F. 杰哥找对象 题解 设杰哥和猛男分别在结点 iii 和结点 jjj 的期望为 xi,jx_{i,j}xi,j​ ，npy 在结点 CCC，令与结点 iii 直接相连的结点的集合为 UUU，与 jjj 直接相连的结点的集合为 VVV，由期望公式可得出下列等式： xi,j={1∣U∣∣V∣∑u∈U∑v∈V(xu,v+1+[u=v])i≠C0i=Cx_{i,j}=\begin{cases} \displaystyle \dfrac{1}{|U||V|}\sum\limits_{u\in U}\sum\limits_{v\in V}(x_{u,v}+1+[u=v]) & \text {$i...

E. 杰哥闯稻妻 题解 ​ 是一道写起来很烦的搜索题 ​ 题目保证最多 101010 次操作内肯定可以将所有方块朝向同一方向，510=9,765,625≈1075^{10} = 9,765,625 ≈ 10^7510=9,765,625≈107，于是这题直接搜索即可。至于题目要求答案序列字典序最小，在搜索枚举要攻击的方块时从左到右枚举就行(应该也不会有人从右到左qwq)。 ​ 题目的数据无论 bfs 还是 dfs 都是可以过的。这题写起来比较烦人的地方应该是进行操作时对状态的修改(至少我是这样) std bfs 做法： #include<iostream> #in...

D. 杰哥的集合 题解 启发式合并模版题, 每次由小的集合向大的集合合并, 并维护最多的出现次数以及答案。 时间复杂度: O(n2n)\mathcal O(n \log^2 n)O(nlog2n)。 std: #include<bits/stdc++.h> using namespace std; const int N = 1e5 + 5; int n, m, a[N]; struct node { int fa, ans, siz, max_cnt; map< int, int > mp; } kk[N]; int find(int x) { ...

C. 杰哥，你带我走吧！杰哥 题解 前缀和思想，预处理出每个点到根节点的点权和，记为 preprepre，然后每次询问只需查询最近公共祖先 lca⁡(u,v)\operatorname{lca}(u,v)lca(u,v)，然后输出 pre[u]+pre[v]−pre[lca⁡(u,v)]−pre[father[lca⁡(u,v)]]pre[u]+pre[v]-pre[\operatorname{lca}(u,v)]-pre[father[\operatorname{lca}(u,v)]]pre[u]+pre[v]−pre[lca(u,v)]−pre[father[lca(u,v)]]。kkk ...

题解 dis[u]dis[u]dis[u]表示从 uuu 节点到 111 节点路径异或值 那么如果我们找的那条路径在同一颗子树中(现在的树根为 rtrtrt) dis[u]⊕dp[rt]=0⟶dis[u]=dis[rt]dis[u] \oplus dp[rt] = 0 \longrightarrow dis[u] = dis[rt]dis[u]⊕dp[rt]=0⟶dis[u]=dis[rt] 如果我们找的那条路径在不同的子树中 (dis[v]⊕dis[rt])⊕(dis[u]⊕dis[rt])=0⟶dis[u]=dis[v](dis[v] \oplus dis[rt]) \oplus (dis...

A. 杰哥的最小和 题解 最多存在 101010 个不同的素数： 2×3×5×7×11×13×17×19×23×29=64696932302 \times 3 \times 5 \times 7 \times 11 \times 13 \times 17 \times 19 \times 23 \times 29 = 64696932302×3×5×7×11×13×17×19×23×29=6469693230 直接二进制枚举即可 std: #include<bits/stdc++.h> using namespace std; typedef l...

链接： https://ac.nowcoder.com/acm/contest/24710/B 分析： Fi(x)=1+x+x2+...+xfi=(1−xfi+1)/(1−x)F_i(x)=1+x+x^2+...+x^{f_i}=(1-x^{f_i+1})/(1-x)Fi​(x)=1+x+x2+...+xfi​=(1−xfi​+1)/(1−x) F(x)=∏i=1nFi(x)=∏i=1n(1−xfi+1)(1−x)nF(x)=\prod_{i=1}^n{F_i(x)}=\frac{\prod_{i=1}^n(1-x^{f_i+1})}{(1-x)^n}F(x)=∏i=1n​Fi​(x)=(1−...