Xiaruize's Blog

CF1768D.Lucky Permutation By xiaruize 思路 考虑最小需要几步可以将原序列排序。 可以建一张图，其中边为 i→Pii \rightarrow P_ii→Pi​ 此时，这张图一定是若干个环，对于每个环，令它有 mmm 个点，必然至少需要 m−1m-1m−1 步 所以，最少步数=n−环数=K最少步数 = n - 环数 = K最少步数=n−环数=K 那么，此时再考虑去满足题目条件，再交换任意相邻的两个即可 若相邻的两个在同一个环内，即可少做最后一次操作，需要 K−1K-1K−1 步 否则需要额外的一次操作，需要 K+1K+1K+1 步 Code 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576777879808182838485868788/* Name: Author: xiaruize Date ...

Least Prefix Sum By xiaruize 分析 令 M=∑i=1maiM=\sum\limits^{m}_{i=1}a_iM=i=1∑m​ai​ , Sk=∑i=1kaiS_k=\sum\limits^{k}_{i=1}a_iSk​=i=1∑k​ai​ 当 Sk<MS_k<MSk​<M 时，分两类考虑 k<mk<mk<m 此时，对 a1⋯aka_1 \cdots a_ka1​⋯ak​ 执行题目所述的操作，都会同时使 SkS_kSk​ 和 MMM 增加 , 不会使得当前局面合法 那么只会对 ak+1⋯ama_{k+1} \cdots a_mak+1​⋯am​ 这些数执行操作 考虑怎样操作最优，容易发现，可以贪心的选择尽可能大的数进行操作 每次操作会使 M=M−ax×2M=M-a_x\times 2M=M−ax​×2 k>mk>mk>m 同上分析，可以发现，这次的操作对象为 am+1⋯aka_{m+1} \cdots a_kam+1​⋯ak​ ， 优先选择小的数进行操作 实现 从 mmm 开始，倒序循环 ...

D. Koxia and Game By xiaruize 思路 考虑在什么情况下Koxia可以必胜，发现以下几条特征： 对于每一次操作，Mahiru都有且只有一个数字可选，即Mahiru选什么完全确定 得出这样的结论 ai=bia_i=b_iai​=bi​ 时 , cic_ici​ 为任意数都满足条件 , 此时最终选择结果一定为 aia_iai​ ai≠bia_i\neq b_iai​​=bi​ 时， ci=aic_i=a_ici​=ai​ 或者 ci=bic_i=b_ici​=bi​ , 此时最终选择结果一定为 cic_ici​ 得出以上结论后，考虑将原来的数组转化为图，具体操作为在 aia_iai​ 与 bib_ibi​ 之间建边 此时, 这个图不一定联通，考虑对于一个联通块，有如下这些结论: 当且仅当联通块是一个基环树(包括自环)时，这个联通块才能转化为可行的 cic_ici​ 如果任意联通块不是基环树，则答案为0 按照环分两类: 自环/环 对于自环，答案 ×n\times n×n 对于正常的环, 答案 ×2\times 2×2 具体可以使用并查集维护 ...