House_of_Fan

CF2183C War Strategy CF2183C Generals.io 思路 显然最后的局面一定是一段包含 $k$ 的连续区间。 若选择向离 $k$ 更远的地方扩展而放弃离 $k$ 更近的某个兵营，则显然要花费更多的时间，一定更劣。 假设我们要向左扩张 $l$ 个兵营，向右扩张 $r$ 个兵营。 则 $l\le k-1,r\le n-k$，否则会超出边界。 而扩张到这样局面的时间最小为 $l+r+\max(l,r)-1$。 证明一定能取到这个时间 我们先等待直到 $k$ 中有 $\max(l,r)$ 个士兵，耗费 $\max(l,r)-1$ 天； 然后花费 $\max(l,r)$ 天直接向外扩展到极限距离； 此时 $k$ 中又会有 $\ge\min(l,r)$ 个士兵； 再花费 $\min(l,r)$ 的时间向外扩展到极限距离。 将这些时间相加即得到 $l+r+\max(l,r)-1$。 这已经是最优方案了，无法取到更快的时间，总会在某几步造成天数的空闲（等待兵力或走重复路程）。 实现 两边拓展的距离在都可以扩展的情况下最多相差 $1$，所以我们每次都向外将可扩展的边增...

CF2183B Yet Another MEX Problem 思路 首先我们观察样例，发现答案是直接在原数组中任选 $k-1$ 个数的 mex 最大值。 枚举了一些情况后，发现一定存在某种操作可以使得这些数都被取到。 考虑证明上面的结论。 易得到 $k-1$ 个数的最大 mex 值就是 $k-1$。 所以大于等于 $k-1$ 的数一定是对最终答案无法做出贡献的，有就直接删掉。 而如果同时存在一个以上的某个数，只会有一个能做出贡献，所以重复的也要删掉。 若选 $k$ 个数，没有数大于等于 $k-1$，则一定会有重复的数出现。 因为小于 $k-1$ 的非负整数只有 $k-1$ 个，就好比在 $k-1$ 个抽屉中要放 $k$ 个苹果，则一定会有一个抽屉不止放了一个苹果。 所以上面的两种情况 $a_i\ge k-1$ 和 $a_i=a_j$ 总会有至少一种出现，可以证得每个长度为 $k$ 的区间中都有这样的数可以被删除。 即证得答案是直接任选 $k-1$ 个数的最大值。 实现很简单，不多赘述，大概就是用一个数组记录每种数的出现次数，再统计前 $k-1$ 个数中第一个未出现的是哪一个就行...

AT_abc439_f AT_abc439_f [ABC439F] Beautiful Kadomatsu 思路 省流：线段树。 首先我们发现，若按照 $(i,a_i)$ 的坐标在平面直角坐标系中建图，并且将每个点与它前面和后面（如果存在的话）的点相连，那么趋势一定呈一个波浪状。 又发现题目中要求的两种点就是波浪的波峰和波谷。 显然这两种点的数量最多相差 $1$，且差值取决于开头和结尾的趋势。 若要使得波峰数量比波谷数量多，则开头必定为增加，而结尾必定为减少。 考虑对正序对及逆序对计数。 显然可以用线段树求出正、逆序对的数量，表示为 $smr$ 和 $bgr$。 然后由于 $l,r,l<r$ 中间怎么选点不影响，则每个正、逆序对之间的点可任意选或不选，方案数为 $2^{r-l-1}$ 次。 而当 $l=r$ 时，中间无点可选。 那所有贡献则为 $\sum_{i=1}^n smr_i\cdot bgr_i$ 加上 $\sum_{i=1}^n\sum_{j=i+1}^n smr_i\cdot bgr_j\cdot 2^{j-i-1}$。 第一部分可以 $O(n)$ 地求出，直接...

AT_abc439_d [ABC439D] Kadomatsu Subsequence 思路 我们发现对于每一个 $j$，它同侧可以匹配的 $i,k$ 的顺序和位置并不影响贡献，所以考虑在线处理。 对于每一个数，当它可以被 $3$ 或 $7$ 整除时记录相应的商，因为 $a_i\le 1$，所以它不可能同时作为 $i,k$；当它可以被 $5$ 整除时，统计它前面所有的相应商，在答案中加上对应的 $3,7$ 的商的乘积即可。 从后到前也类似。 代码 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162#include<bits/stdc++.h>#define fir first#define sec second #define int long long#define pii pair<int,int>#define fep(i,s,e) for(int i=s;i<e;i...

AT_abc439_c [ABC439C] 2026 思路 exactly one pair 注意到是“恰好一对”。 枚举 $x,y$，将所有合法的 $x^2+y^2$ 加入一个数组内。 这样的数最多有 $n$ 个。 考虑对这个数组排序。 在排序后的数组内统计答案，若一个数既不与其前一个相等，也不与其后一个相等，因为数组是有序的，则它对应的 $x,y$ 一定只有一对。 代码 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354#include<bits/stdc++.h>#define fir first#define sec second #define int long long#define pii pair<int,int>#define fep(i,s,e) for(int i=s;i<e;i++)#define pef(i,s,e) for(int i=s;i>e;i--)#defin...

CF2182E New Year’s Gifts 思路 题目中提到必须给 $i$ 号朋友买价值为 $y_i$ 的礼物，则这部分开销是不可避免的，直接从初始资金中减去。 此时对于朋友 $i$，他的贡献可以被形式化地表达为： 消耗 $\Delta=z_i-y_i$ 的剩余金钱产生 $1$ 的贡献。 消耗一个至少为 $x_i$ 美观度的礼盒产生 $1$ 的贡献。 且这两种操作不可重复计算。 我们可以贪心的将所有 $\Delta$ 按照大小排序，从小到大遍历所有礼盒，对于每个礼盒，找到它可以产生贡献的最大 $\Delta$，再使用这个礼盒，删除掉对应的 $\Delta$。 看到这里，我们需要一个可以支持插入、排序和删除的数据结构。 set 就非常合适。 但注意到这里面可能会出现相同元素，所以使用类似的 multiset。 还有一些细节，见代码中注释。 代码 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162...

CF2182B New Year Cake 思路 $a,b$ 都小于 $10^6$，而每一层都是上个相同颜色层的 $4$ 倍，最多层数不超过 $20$，所以直接枚举。 但是因为不知道最大的一层应该是什么颜色，所以要枚举形如 $a,b,a,\cdots$ 和 $b,a,b,\cdots$ 的两种构成方法，再取最大值即可。 代码 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455#include<bits/stdc++.h>#define fir first#define sec second#define int long long#define pii pair<int,int>#define fep(i,s,e) for(int i=s;i<e;i++)#define pef(i,s,e) for(int i=s;i>e;i--)#define rep(i,s,e) for(int i=s;i...

CF2182C Production of Snowmen 思路 首先我们发现 $a$ 与 $b$，$b$ 与 $c$ 的相对顺序之间并不互相影响。 换句话说这道题就等于求 $a$ 与 $b$，$b$ 与 $c$ 之间所有合法匹配方案的乘积。 题目数据范围较小，直接枚举 $a,b$ 和 $b,c$ 的合法匹配即可。 但是由于 $i,j$ 的匹配与 $i+1,j+1$ 的匹配是等价的，所以总方案数还要再乘上 $n$。 代码 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162#include<bits/stdc++.h>#define fir first#define sec second#define int long long#define pii pair<int,int>#define fep(i,s,e) for(int i=s;i<e;i++)#define pef...

CF2182D Christmas Tree Decoration 思路 手玩样例后发现这个拿装饰品的机制和班上轮换做清洁有点像啊。 不难发现在合法情况下，最少的拿取次数最多比最多的拿取次数少 $1$ 次。 那我们先判断是否合法，方法如下： 找到对应装饰品最多的一个人，设他的对应盒子中有 $mx$ 个装饰品。 将其他人的对应装饰品补足至 $mx-1$，不够的部分从 $p_0$ 中减掉。若在某一步 $p_0$ 不够了，则方案数为 $0$。 然后此时一定存在合法情况，我们考虑如何计算合法排列数。 首先这个排列中每个人的挂装饰品次数应当形如 $mx,\cdots,mx,mx-1,\cdots,mx-1$。 先扫描一遍整个数组，找到 $mx$ 有多少个，设它有 $a$ 个，则 $mx-1$ 有 $n-a$ 个。 此时分类讨论： 若 $p_0\le n-a$，则 $p_0$ 无法将所有 $mx-1$ 补到 $mx$，那么在补足后将会有 $a+p_0$ 个 $mx$，$n-a-p_0$ 个 $mx-1$，则答案为 $C_{n-a}^{p_0}\cdot A_{a+p_0}^{a+p_0...