2025.2.26

发表于2077-03-02|更新于2025-03-06

|浏览量:

模拟赛

糖丸了

第一题写了个假做法——枚举中点，对左右部分分别排序

但这样并非正确，考虑 3 4 5 6 7 8 9 10 11 1 12 13 2 14 这个数据

显然最优解为 3 4 5 6 7 8 9 10 11 12 13 14 2 1

但是若用我们上边的那个方法，会跑出来 3 4 5 6 7 8 9 10 11 14 13 12 2 1

换言之，最终选择反转的数并不一定是连续的一段，而是离散的若干个点

所以考虑每个点是否转化为下降段

发现它与 [[AT_awtf2024_d Almost Bubble Sort 题解|之前mx那题]] 不太一样，具体而言，对于两个转化后的点 $A,B$ ，若有 $A$ 转化后比 $B$ 更大，那么 $B$ 无论是否转化都会产生逆序对贡献

换言之，所有的选择之间是独立的

然后就做完了

为什么会想歪呢？可能从一开始思考方向就错了，因为没注意到反例的存在

最后的解法能不能独立想出来呢？我觉得未必

可能思想还是不够跳跃吧，容易陷到先前一步的思考中

所以一方面在想到一个结论时，不应该先入为主的认为它就正确，多思考特殊情况的存在

另一方面，在这种统计贡献的题中，多从是否转换的角度分别去思考产生的贡献，以及对于其他的转换，转换与否是否统计出来的形式一致，进而推出独立性

对于T2，其实还是少拿了20pts，事实上没能想到对值域进行离散化

烦，省选的时候不能犯这样的问题啊

文章作者: my9r

文章链接: http://example.com/2077/03/02/%E6%97%A5%E8%AE%B0/mygr%E7%9A%84%E6%97%A5%E8%AE%B0/2025%E5%B9%B4/2025.2.26/

版权声明: 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来源 mygr main()！

日记 mygr的日记 2025年

相关推荐

模拟赛时间 T1 发现其实就是问卷不卷的问题而且求和再差导致了前面的决策并不会影响后边的然后从第二个开始选择所有正值即可 T2 点分治 T3 我不会树状数组上二分啊（其实就是找两个情况火大于等于冰的第一个瞬间以及冰大于火的瞬间两个其实相邻问题就变成了“如何寻找冰大于火的瞬间” 说不定卡常能过呢？万一呢？试试看吧先把T1T2敲了，再说T3

模拟赛时间 T1 感觉好像有点眼熟感觉要证明些贪心的结论啥的不管了，乱搞首先对于最大的元素，显然有答案要么是最大次大的和取模，要么是双指针搞定得到答案后显然后续的模数都必须大于这个值，发现砍掉了很大一块所以乱搞即可 T2 草，典思考我需要什么一个朴素的LCA，一个向上的 $2^k$ 级父亲的位置，一个向下的 $2^k$ 级父亲的位置我还需要知道某个点往上的第一个 xx 点的位置，这个其实倍增顺带求解即可 T3 发现他要求的其实是“结束排名的可能顺序有多少种” 而我们知道一种排名想要合法，那么应该满足其最小的使用数小于等于m 考虑设 $f_{S,i,j,k}$ 表示已经选的集合为 $S$ ，上一个选择的数为 $i$ ,上一次额外加的数为 $j$ ，总共额外加了 $k$ 的方案数然后你发现其实 j 根本就没有意义，因为 j 显然与 $S$ 中的 $a_i$ 的最大值相等最好(或加减1) 所以就变成 $f_{S,i,0/1,k}$ 表示已经选的集合为 $S$ ，上一个选择的数为 $i$ ,上一次的值为最大值是否加1 ，总共额外加了 $k$...

模拟赛时间题目链接 T1 发现这几个限制都可以转化为第一个对于最后一个那就是全局异或一下就好然后就变成一个区间异或，单点查询的问题爆搜就好 T2 最讨厌数学了考虑设 $a_{n,i}=x_i$ ，$a_{i,m}=y_i$ 然后你发现每个元素都只跟其行与列与 $a_{n,m}$ 有关系不妨设 $a_{n,m}=0$ ,接下来就只跟行列有关系了我们就得到了若干个和式我们想要让这里边的最大值减最小值尽可能的小发现你的每次操作其实就等价于“将间隔的一段加一减一” 二分图染色？我觉得它变换的次数不会很多，就像之前那道题一样试一下？ $$ \begin{array}{|c|c|c|c|}\hline & & -x_1-y_3-D & y_3\ \hline & x_2+y_2-D & x_1-y_2+D & y_2\ \hline -x_3-y_1-D & -x_2 +y_1+D & -x_1-y_1-D & y_1\ \hline x_3 & x_2 & x_1...

![[problem (2).pdf]] 沟槽的第一题不会做啊做第三先吧 T3 因为保安很神经的歪脖子，所以最右边的点一定会选然后设 $f_{i,j}$ 表示区间 $[i,j]$ 的答案因为一个保安能看到的范围是一段段不连续的区间，所以不连续的区间我们用 $f$ 去补齐就好 T2 我是不是有一个 $O(n^2 log)$ 的做法了？为啥要保证互不相同啊？ T1 考虑每个点的贡献当一个点收到普通传递时，取决于他是发送方还是接收方，产生正负自身标号的贡献当收到特殊传递时，那么无论如何都是当前标号如何判断是哪种传递呢？就是判断上一个数是否位置比自己大沟槽的，我感觉像状压考虑排序从小到大插入每种类型的数，也就是“对应位置赋值” 此时若上一个位置的数被插入过，则说明比当前位置小否则比当前位置大，那就是两种不同的贡献开始时用一个桶记录不同元素的相邻对的数量即可

模拟赛 T1 考虑每个格子最终的颜色，可以得出其对应的行和列的先后顺序然后暴力的考虑添加每个列的位置就好需要判断是否无解，最终的答案就是每个块内部随便排的方案数的乘积 T2 考虑在每段序列的结束处统计贡献不妨设 $f_{i,j}$ 表示当前位置在 $i$ ，当前的最长不降子序列考虑枚举最长上升子序列的长度为 $d$ 在此基础上跑dp，设 $f_{i,j}$ 表示当前位置为 $i$ ，最长上升子序列中对于一个序列的最长上升子序列，有 $$ans=n+\max_{i\in[0,n]}sum_i-sum_n-i$$ 我们考虑转换一下，要让最长上升子序列最大，同时令 1 的数量尽可能多，其实也就是要让 $ans \times n+count_1$ 最大，也就是 $$pans=\max_{i\in[0,n]}n\times(sum_i-sum_n+n-i)+$$ 考虑枚举 $ans$ 和 $c1$，此时问题就变成了问 “从右往左数第 $c1$ 个 $1$ 的位置大于 $ans-c1$ 且第 $c1+1$ 个 $1$ 的位置小于” 设 $f_{i,j,k,l}$ 表示当前在第...

首先考虑什么情况下会出现 7 发现有 8 就有 7 有 9 就有 8 以此类推所以最终答案一定不会超过 10 另外还需要考虑进位的影响当出现 $min \ge mex$ ，

数据加载中