2025.2.12
发表于|更新于
|浏览量:
![[1.pdf]]
T1
就是你考虑这么一件事情
首先情侣间一定是相反的
其次，连续三个中至少有一个相邻对是相反的
所以考虑建图，对 $a_i,b_i$ 之间连边，对 $i,i+1$ 之间连边
你发现他一定是一个二分图，所以二分图染色即可
![[2.pdf]]
文章作者: my9r
版权声明: 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来源 mygr main()！
相关推荐
2077-03-02
2025.1.20
模拟赛时间 T1 发现其实就是问卷不卷的问题 而且求和再差导致了前面的决策并不会影响后边的 然后从第二个开始选择所有正值即可 T2 点分治 T3 我不会树状数组上二分啊（ 其实就是找两个情况 火大于等于冰的第一个瞬间以及冰大于火的瞬间 两个其实相邻问题就变成了“如何寻找冰大于火的瞬间” 说不定卡常能过呢？ 万一呢？ 试试看吧 先把T1T2敲了，再说T3
2077-03-02
2025.1.21
模拟赛时间 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$...
2077-03-02
2025.1.22
模拟赛时间 题目链接 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...
2077-03-02
2025.1.23
![[problem (2).pdf]] 沟槽的第一题不会做啊 做第三先吧 T3 因为保安很神经的歪脖子，所以最右边的点一定会选 然后设 $f_{i,j}$ 表示区间 $[i,j]$ 的答案 因为一个保安能看到的范围是一段段不连续的区间，所以不连续的区间我们用 $f$ 去补齐就好 T2 我是不是有一个 $O(n^2 log)$ 的做法了？ 为啥要保证互不相同啊？ T1 考虑每个点的贡献 当一个点收到普通传递时，取决于他是发送方还是接收方，产生正负自身标号的贡献 当收到特殊传递时，那么无论如何都是当前标号 如何判断是哪种传递呢？就是判断上一个数是否位置比自己大 沟槽的，我感觉像状压 考虑排序从小到大插入每种类型的数，也就是“对应位置赋值” 此时若上一个位置的数被插入过，则说明比当前位置小 否则比当前位置大，那就是两种不同的贡献 开始时用一个桶记录不同元素的相邻对的数量即可
2077-03-02
2025.2.10
模拟赛 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}$ 表示当前在第...
2077-03-02
2025.2.11
首先考虑什么情况下会出现 7 发现有 8 就有 7 有 9 就有 8 以此类推 所以最终答案一定不会超过 10 另外还需要考虑进位的影响 当出现 $min \ge mex$ ，
