差别

这里会显示出您选择的修订版和当前版本之间的差别。

--- 2020-2021:teams:farmer_john:jjleo:codeforces_round_639_unrated [2020/05/07 18:52]
jjleo
+++ 2020-2021:teams:farmer_john:jjleo:codeforces_round_639_unrated [2020/05/10 22:07] (当前版本)
jjleo [C]
@@ 行 1: / 行 1: @@
 =====A=====
-  * 题意:定义一个变换,每个位置$i$变换到位置$(i+a_{i\%n})$处,$|a_i|< =10^9$,问是否有两个位置经过一次变换后变换到同一个位置。
+  * 题意:有无限个位置，定义一个变换,每个位置$i$变换到位置$(i+a_{i\%n})$处,$|a_i|< =10^9$,问是否有两个位置经过一次变换后变换到同一个位置。
   * 题解:求出$0,1…n-1$模$n$意义下变换后的位置，只要没有冲突就可以，因为是无限的；反之如果有冲突，显然能找到至少2个变到一个位置上的。
 =====B=====
   * 题意:一个$n*m$的黑白染色方格，每个格子可以放若干个N极和S极，问在满足下列条件的前提下最少需要摆放几个N极（或无解）。1.每行每列至少有一个S极。2.所有黑色格子都可以通过数次磁铁间的吸引（只有N级可以动）将N极移动到这个格子上。3.无论进行多少次磁铁间的吸引都不能将N极移动到任意一个白色格子上。
+  * 题解:如果出现某一行或某一列出现“黑白黑”显然无解。如果只有行空缺或只有列空缺也是无解的，但如果行列都有空缺是合法的（比赛时没想到），因为可以放在交汇处，这样不影响其它磁铁。答案为连通块个数。
+=====C=====
+  * 题意:离 散 数 学，给出$n$个变元和一个由$m$个不等式组成的合取式，每个不等式形如$x_i<x_j$，要求按$1$到$n$的顺序添加$n$个量词（全称量词或存在量词）使得其成为永真式，要求全称量词的数量最**多**，或判断无解。
+  * 题解:按照不等式建出有向图，如果有环显然无解，因为自己不能小于自己。按照$1$到$n$的顺序遍历每个点，如果这个点能到达的某个点或能到达这个点的某个点已经被访问过了，那么显然这个点不能任意了，否则可以任意。因此先判环，然后建正图和反图，分别dfs即可。注意vis数组对于正图和反图要分别建，比赛的时候合一起就WA了，因为在正图被访问的时候并不能继续访问反图里面能访问的点。
+=====D=====
+  * 题意:给出一个序列$a_i$，求序列$b_i$使得$\sum\limits_{i=1}^n b_i(a_i-b_i^2)$的最小值，其中要求$0\le b_i \le a_i$且$\sum\limits_{i=1}^n b_i=k$。
-  * 题解:如果出现某一行或某一列出现“黑白黑”显然无解。如果只有行空缺或只有列空缺也是无解的，但如果行列都有空缺是合法的（比赛时没想到），因为可以放在交汇处，这样不影响其它磁铁。答案为连通块个数
+  * 题解:对于某一个$i$，当$b_i$为$x$时，如果令其加$1$，对答案的贡献为$\Delta_i (x):=\left[x(a_i-x^2)\right]-\left[(x-1)(a_i-(x-1)^2)\right]=a_i-3x^2+3x-1,$，可以看到这个二次函数是开口向下而且顶点横坐标在$\frac{1}{2}$，因此在本题定义域中是严格单调递减的。我们可以让所有$b_i$为$0$，然后贪心地看给哪个$b_i$增加$1$的贡献最大就增加哪个。由于$k$太大，因此我们二分每次增加$1$所产生贡献的最小值，对于要验证的值，再套一个二分（或者解方程）算每个$bi$可以加几次，保证总和大于等于$k$，最后如果总和超出$k$，一定可以将多余的增加值等于二分出来的值的$b_i$减少$1$，否则二分的值可以更小。

CVBB ACM Team

用户工具

站点工具

差别

页面工具