Ximenana

分类

题解(11)

/ 注册

全部文章（共11篇）

题解 | #J.杰哥的直角三角恋#

J.杰哥的直角三角恋题解首先注意到任意一组勾股数 a2+b2=c2a^2+b^2=c^2a2+b2=c2 可以表示为 a=x2−y2a=x^2-y^2a=x2−y2 ，b=2xyb=2xyb=2xy ，c=x2+y2c=x^2+y^2c=x2+y2 那么问题可以转化成满足以下条件的 (x,y)(...

2022-06-05

0 397

题解 | # I 杰哥再找对象#

I 杰哥再找对象题解我们可以通过枚举结点 111 和结点 nnn 所在的连通块中结点的个数计算，设答案为 ana_nan ，则： an={∑k=2n((n−2k−2)bkcn−k)n≥21n=1a_n=\begin{cases} \displaystyle\sum\limits_{k=2}^{...

2022-06-05

1 362

题解 | #杰哥抓气球#

H. 杰哥抓气球题解明显，处于 (0,0)(0,0)(0,0) 的点不需要任何代价。如果点到原点的距离为整数，则代价为 222，比如 (3,4)(3,4)(3,4) 和 (0,5)(0,5)(0,5)。否则，任何点都可以通过走平行于 x,yx,yx,y 轴的直线到达，只需要两步，一去一来代价为...

2022-06-05

0 269

题解 | #G. 杰哥哄对象#

G. 杰哥哄对象解法一：朴素 DP：易知：当前字母的改变花费只和前一个字母的值和位置有关。很容易可以想到三维的 DP，一维代表当前的串，二维表示当前最后一个字母的值，第三维表示当前字母是在奇/偶数位置。用 0 来表示偶数位置，1表示奇数位置。首先有 f0,i,0←0,i∈Σf_{0,i,0...

2022-06-05

1 334

题解 | #F. 杰哥找对象#

F. 杰哥找对象题解设杰哥和猛男分别在结点 iii 和结点 jjj 的期望为 xi,jx_{i,j}xi,j ，npy 在结点 CCC，令与结点 iii 直接相连的结点的集合为 UUU，与 jjj 直接相连的结点的集合为 VVV，由期望公式可得出下列等式： xi,j={1∣U∣∣V∣∑u∈U∑...

2022-06-05

0 329

题解 | #E. 杰哥闯稻妻#

E. 杰哥闯稻妻题解是一道写起来很烦的搜索题题目保证最多 101010 次操作内肯定可以将所有方块朝向同一方向，510=9,765,625≈1075^{10} = 9,765,625 ≈ 10^7510=9,765,625≈107，于是这题直接搜索即可。至于题目要求答案序列...

2022-06-05

1 307

题解 | #杰哥的集合#

D. 杰哥的集合题解启发式合并模版题, 每次由小的集合向大的集合合并, 并维护最多的出现次数以及答案。时间复杂度: O(n2n)\mathcal O(n \log^2 n)O(nlog2n)。 std: #include<bits/stdc++.h> using namespace...

2022-06-05

2 442

题解 | #C. 杰哥，你带我走吧！杰哥#

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

2022-06-05

6 367

题解 | #杰哥的树#

题解 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...

2022-06-05

3 384

题解 | 武汉科技大学第十一届校赛题解A

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 1...

2022-06-05

1 358