锁和钥匙
...
Communication
2025 ICPC 沈阳 C 2025 ICPC 沈阳 C 【题意】第一次运行给定 NNN 个正整数 Xi∈[1,M]X_{i} \in [1,M]Xi∈[1,M]，为每个数构造一个长度为 3M3 M3M 的序列，每个序列中 111 到 MMM 的整数恰好出现 3 次。jury 独立地将每个序列映射成二进制序列，第二次运行需要从这些二进制序列中解密出每个 XiX_{i}Xi。 很牛的题。喜欢 communication。 【思路】既然是 3M3M3M 且恰好出现 3 次，我们就分成三段，每段是长为 MMM 的 permutation。第一段就设为 1,2,…,M1,2,\dots,M1,2,…,M，这样直接知道每个字符映射成 0 还是 1 了。然后想想后面两个 permutation 怎么搞才能保证是单射。 最简单的方法是 rotation（循环移位），直接移 XiX_{i}Xi 位。 可以吗？有个小问题，如果映射出的序列有周期 TTT，那就分不出来了。比如原串是 1010，移位后是 0101，移了 1 还是 3 不得而知。 如何修正？什么串没有周期？素数！给...
01 串
1733D 01 串。每次选择两个下标 flip，若相邻代价为 XXX，否则为 YYY。最小化变成全 0 的总代价。 X⩾YX \geqslant YX⩾Y 时，贪心。 X<YX<YX<Y，对于第 iii 个差异点 pip_{i}pi，我们取以下两种策略的最小值： 策略 A（不用 xxx，留给 yyy 配对）：fi=fi−1+Y2f_{i} = f_{i-1} + \dfrac{Y}{2}fi=fi−1+2Y 策略 B（和上一个差异点用连续的 xxx 连线）：fi=fi−2+(pi−pi−1)Xf_{i} = f_{i-2} + (p_{i} - p_{i-1}) Xfi=fi−2+(pi−pi−1)X CF1753C 01 串。重复执行：随机等概选择两个下标 i<ji < ji<j，如果 Ai>AjA_i > A_jAi>Aj，则交换 AiA_iAi 和 AjA_jAj 的值，否则不做处理。求排序的期望操作次数。 设有 ccc 个待归位的 0，答案为...
树
2219C. Coloring a Red Black Tree 每个节点初始为红色或黑色。 每次选择某个 node aaa，均匀随机选择 aaa 的一个相邻 node bbb，将 aaa 的颜色变为 bbb 的颜色。 求使整棵树染成红色的次数的最小期望。 期望复杂度 O(NlogN)O(N \log N)O(NlogN)。 状态： fu,0f_{u, 0}fu,0：以节点 uuu 为根的子树，父节点未染，完成目标所需次数的最小期望。 fu,1f_{u, 1}fu,1：以节点 uuu 为根的子树，先染父节点，完成目标所需次数的最小期望。 转移： 若 uuu 初始为红， fu,0=fu,1=∑c∈children(u)fc,1f_{u, 0} = f_{u, 1} = \sum_{c \in \text{children}(u)} f_{c, 1} fu,0=fu,1=c∈children(u)∑fc,1 若 uuu 初始为黑，为将节点 uuu 染红，设 uuu 有 kkk 个红色邻居，成功概率为...
按值按下标综合 DP
给定长度为 NNN 的整数序列 A=(A1,A2,…,AN)A = (A_1, A_2, \dots, A_N)A=(A1,A2,…,AN)，将其划分为若干个连续子段。各个段的按位异或和序列 b1,b2,…,bmb_1, b_2, \dots, b_mb1,b2,…,bm 必须满足单调不降（即 bi≤bi+1b_i \le b_{i+1}bi≤bi+1）。 求出最大划分段数，以及在最大段数下的划分方案数。 1≤N≤30001 \le N \le 30001≤N≤3000，0≤Ai≤30000 \le A_i \le 30000≤Ai≤3000。 定义前缀异或和序列 SSS，异或和的值域上限 V=4095V = 4095V=4095。 设 f(i,v)f(i, v)f(i,v)：将前缀 A[1…i]A[1 \dots i]A[1…i] 合法划分，且最后一段子段的异或和等于 vvv 时，能达到的最大段数。 f(i,v)=1+max0≤j<iSj=Si⊕vmax0≤u≤vf(j,u)f(i, v) = 1 + \max_{\substack{0...
CF2210E
CF2210E. Binary Strings are Simple? 交互。 猜测长度为 NNN 的 01 串。 每次询问子串 S[l…r]S[l\dots r]S[l…r]，返回子串所有循环移位的逆序对数 mod 子串长度的集合大小。 询问的代价为 Nr−l+1\dfrac{N}{r-l+1}r−l+1N，总询问代价不超过 max(30,3N)\max(30,3 N)max(30,3N)。 最多可以猜测 222 次。 当循环左移 1 时贡献是 −c0=c1−n-c_0=c_1-n−c0=c1−n，否则是 c1c_1c1，逆序对在模意义下的增量总是 c1c_1c1。因此询问实际是 #{x:x=kc1 mod N,k∈[1,N]}=Ngcd(N,c1)\#\{x : x=kc_1\bmod N, k\in[1,N]\} = \displaystyle\frac{N}{\gcd(N,c_1)}#{x:x=kc1modN,k∈[1,N]}=gcd(N,c1)N。 奇偶。在仅知道 gcd(N,c1)\gcd(N,c_{1})gcd(N,c1)...
关于文化认同和设计理论的实验报告 by 迷湮
社会学、语言学以及身份认同，大众媒体塑造和强化对特定族群的刻板印象，个人如何通过语言选择来构建或掩盖自己的社会身份。