耕云种月

分类

格式整理(10) 题解(107)

/ 注册

全部文章（共117篇）

出题人题解 | #最小相似度#

原题解链接：https://ac.nowcoder.com/discuss/157310 此题可以用FWTFWTFWT通过，但是出题时的想法是一道BFSBFSBFS就可过的题。 MMM最大只有202020，如果把每个二进制串看成一个状态，最多只有220=10485762^{20}=1 048 576...

2022-01-25

0 390

出题人题解 | #抓捕***犯#

原题解链接：https://ac.nowcoder.com/discuss/157310 把每个地点看作一个点，那么每个点一定有且仅有一条有向出边。每个点出度只有111，如果某些点组成了一个有向环，这个环上所有点不会有额外的出边，即这个环一定是一个简单环。也易证每个点最终都会走向一个环。结论:...

2022-01-25

0 317

出题人题解 | #666RPG#

原题解链接：https://ac.nowcoder.com/discuss/157310 简单的计数dpdpdp。 dp[i][j]dp[i][j]dp[i][j]代表第iii个回合后分数为j的方案数则:dp[i][j]=dp[i−1][j−ai]dp[i−1][−j]dp[i][j]=dp[i-...

2022-01-25

0 507

出题人题解 | #翻硬币问题#

原题解链接：https://ac.nowcoder.com/discuss/157310 因为mmm是一个偶数,不妨分类讨论: 1.一回合可以直接翻转所有硬币(n=m)(n=m)(n=m) 很显然，答案YesYesYes 2.一回合不能直接翻转所有硬币，因为mmm是偶数，所以只需要讨论nnn的奇偶性...

2022-01-25

0 477

出题人题解 | #小D的剑阵#

原题解链接：https://ac.nowcoder.com/discuss/154293 先将w,v0,v1 w,v_0,v_1w,v0,v1 求和，然后将选择/不选择视为在此基础上付出代价，问题就转化为了求最小代价。对于每个约束，考虑如下的一个图，s,ts, ts,t表示源点和汇点，x,y ...

2022-01-25

0 298

出题人题解 | #小D的Lemon#

原题解链接：https://ac.nowcoder.com/discuss/154293 默认n≤m n \leq mn≤m ∏i=1n∏j=1mg(gcd⁡(i,j))\prod_{i=1}^{n} \prod_{j=1}^{m} g(\operatorname{gcd}(i, j))∏i=1n...

2022-01-25

0 391

出题人题解 | #小A与最大子段和#

原题解链接：https://ac.nowcoder.com/discuss/154293 令Ax=∑i=1xai×i,Bx=∑i=1xaiA_{x}=\sum_{i=1}^{x} a_{i} \times i, B_{x}=\sum_{i=1}^{x} a_{i}Ax=∑i=1xai×i,Bx...

2022-01-25

0 420

出题人题解 | #小A与欧拉路#

原题解链接：https://ac.nowcoder.com/discuss/154293 先考虑回路的情况。由于是一棵树，任两点间路径只有一条，从一条边走到深度更大的点，一定还会从同一条边返回以回到起点或者遍历其他子树，所以每条边需要复制一次，此时答案是边权和的两倍。不是回路的情况可以减掉从终点回...

2022-01-25

0 232

出题人题解 | #小A与任务#

原题解链接：https://ac.nowcoder.com/discuss/154293 以完成时间为关键字从小到大排序(可以交换两个完成时间不同的任务来证明这样的正确性)，按这个顺序来做任务，同时维护一个关于zi z_izi 的大根堆，如果规定时间内完不成任务，就从堆里取出zi z_izi 最...

2022-01-25

2 315

出题人题解 | #小D的剧场#

原题解链接：https://ac.nowcoder.com/discuss/154293 令 dpi,j,kdp_{i,j,k}dpi,j,k表示目前序列放入到第i ii位，最后两个数字为j,k j,kj,k时的方案数，提前将不合法的子段标记转移方程为 dpi,k,l=∑j=149can⁡j,k...

2022-01-25

0 315