mygr main()

模拟赛时间 题目链接 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$ ，

![[1.pdf]] T1 就是你考虑这么一件事情 首先情侣间一定是相反的 其次，连续三个中至少有一个相邻对是相反的 所以考虑建图，对 $a_i,b_i$ 之间连边，对 $i,i+1$ 之间连边 你发现他一定是一个二分图，所以二分图染色即可 ![[2.pdf]]

模拟赛 T2 首先对于一个序列而言，我们操作的最小代价就是他的逆序对数量 草我感觉像证结论然后贪心 但是我实在是没发现什么结论啊 T3 考虑先将图上所有点的连通性处理出来，我们发现接下来我们关注的只有这个联通块对应的行的区间 问题就变成了：给定若干个区间，要求用若干条垂线将其联通的最小代价 首先考虑将所有区间排序，然后扫描线，当某个区间的右端点被加入时则考虑更新答案 使用数据结构维护 $f_i$ 表示上一次修改在第 $i$ 行的最小代价 然后每次更新时找到当前区间内 “从右往左数第一个 1/2” 的位置， 连边的本质？ 我们回到一开始，如果用dp我们会如何解决这个问题 我们会设 $f_{i}$ 表示在第 $i$ 行使用了一次，并且所有 $l$ 小于等于 $i$ 的区间都已经联通的最小代价 其实就相当于转化为一个序列分割问题 我们发现 $i$ 实际上的取值只有可能是每个区间从右往左数第一个 $1/2$ 的位置，于是决策点的级别就缩到 $O(k)$ 了 什么样的点可以转移呢？满足它左边所有区间的右端点的最大值比 $i$ 更大的 然后就做完了？

模拟赛 T2 考虑像之前那道题一样将折线图画出来 然后利用JOI那题的trick，枚举最后一次被 clear 的位置在哪里 我们发现 clear 的充要条件是最高进制位被消去，只要没有被 clear 则后半部分的最高位置就是折线图的最高位 那么次高位呢？我们发现当我们确定最高位过后，那么第一个 $1$ 的位置就无关紧要了，所以以它+1的位置作为新的原点建坐标系，递归上述过程即可 如何统计答案呢？我们考虑枚举每一位，于是问题就变成了“答案前缀为 1010101******” 的方案数 如何控制前缀为这个呢？其实也就是通过计算出 算了先去部分分了 对于 1-6 的点直接暴力 $f_{i,j}$ 即可，当处理询问时则处理一个前缀的答案和一个后缀的答案，考虑从此处用 0 进行合并，时间复杂度 $O(n2^k)$ 对于 $7-14$ 的点，我们发现这样子是支持 $O(n^2k)$ 的 T3 求 $$\left( \sum_{i=1}^{n} f(a,b,i) \right) \mod{998244353}$$ 其中 $f(a,b,i)$ 表示 $ax \equiv b...

![[problem.pdf]] 不妨设 $d^k(n)=D(n^k)$ ，那么有 $$d^k(n)=\prod_{p\in pri}k\times cnt_{p}+1$$ 易证其为一个积性函数 要求的即为 $$\begin{eqnarray}& & \sum_{i=1}^{n}d^{k}(i)\ &=& \sum_{i=1}^{n} \prod_{p\in pri}(k \times cnt_{p}+1)\ \end{eqnarray}$$ 发现对于不同的 $k$ ,后边的形式也是确定的 所以其实就可以拆成关于 $k$ 的多项式即可 T2 考虑分身存在的位置，在时间轴上位置相同的一定是连续的一段 所以考虑变成一个序列分割问题，设 $f_{i}$ 表示是否存在用假人完成了第 $i$ 个任务的情况 考虑决策点 $j$ ，那么必须要满足条件：$j$ 到 $i$ 这段中独立走能够完成，$j$ 到 $i$ 这段能够额外走到 由于 $x$...

模拟赛 # 比赛链接 糖丸了 第一题写了个假做法——枚举中点，对左右部分分别排序 但这样并非正确，考虑 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$...

考前易错清单 注意测试前用题面提供的编译参数跑一遍，避免产生不必要的CE 注意实际评测时以全局内存为准，而非使用内存(要算) 为避免结论错误，无法证明/有疑问的题目一定要尝试暴力对拍 开场先将所有题面阅读一遍，并将暴力敲出，一方面方便结论证明，另一方面避免被拉开差距，在此基础上再去追求高档部分分 你觉得有点熟悉的题 $\not =$ 思路相近，如果能提供一种新的思路必然是好事，考虑在看到题目时先将所有思路全部列出来，然后再逐个去证明是否能够用于求解 你不会的题 $\Rightarrow$ 你不知道它的难度或算法 $\Rightarrow$ 无法证明是否别人都会做出来 $\Rightarrow$ 不用去思考别人会不会做，专注于自己眼下的事情 审题，注意序列/排列字眼 即使是读入，也可能要先取模 考试不到最后一刻不要放弃，也许最后半个小时也能想出更多分数 当想到可能会炸 long long 时，在代码一旁标记上，警示后面的自己记得开 long long，值得注意的是，区间的子区间数量也是有可能炸long long的 负数取模无论在什么情况下，只要不保留符号，那都是用...