WORIA

https://codeforces.com/gym/103055 F. Fair Distribution   题意：给定 n,mn,mn,m，nnn 只能减少，mmm 只能增加，问要使得 mmm 是 nnn 的倍数，两者变化量的绝对值之和最小是多少？1≤n,m≤1081 \le n, m \le 10^81≤n,m≤108 整除分块 暴力的做法是枚举 nnn，再计算 mmm 的最少改变量。这其中会有很多无效的枚举。 对于 ⌊mx⌋\lfloor\frac{m}{x}\rfloor⌊xm​⌋ 相同的这一段 xxx，这一段的最小值或最大值处一定存在这一段的最优解（虽然其它位置可能也有）。所以其实整除分块后，每一块只需要计算两个端点处即可。 1234567891011121314151617181920212223242526272829303132333435363738394041#include <bits/stdc++.h>bool dbg = true;#define debug(x) if (dbg) cout << #x << " ...

https://ac.nowcoder.com/acm/contest/17148 C - Alice and Bob   题意：给定数组 aaa，常数 KKK，多次询问，每次问区间 [L,R][L,R][L,R] 中有几个连续子区间中不同的数的个数大于等于 KKK。 尺取+二分/主席树 首先尺取求出以每个位置为右端点时满足条件的最右的左端点。 查询时只要找到最靠左的完整在 [L,R][L,R][L,R] 中的区间。可以二分做到。 但这里脑子一热写了个主席树，就当是实现下上次浙江省赛的那道主席树了。 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374757677787980818283848586878889#include <bits/stdc++.h>bool dbg = true;#define debug(x) if (dbg) cout & ...

http://codeforces.com/gym/103104 I. Sequence 题意：mmm 个限制条件：pindex≠valuep_{index}\neq valuepindex​=value。问有多少个四元组 (A,B,L,R)(A,B,L,R)(A,B,L,R) 满足 ∀i∈[A,B]\forall i\in [A,B]∀i∈[A,B]，pip_ipi​ 可以取 [L,R][L,R][L,R] 中任意数。1≤A,B,L,R≤N1 \le A,B,L,R \le N1≤A,B,L,R≤N 单调栈 问题转化为二维网格上有 mmm 个坏点，问有几个只包含好点的矩形。 dp[i][j]dp[i][j]dp[i][j] 表示以 (i,j)(i,j)(i,j) 为右下端点的矩形的个数。 遍历行，遍历列，对每一行维护一个递增的单调栈，左上端点的取法等于栈顶的左上位置取法数+当前位置到栈顶位置构成的矩形中的点数。 12345678910111213141516171819202122232425262728293031323334353637383940414243444546#in ...

http://codeforces.com/gym/103102 I. Modulo Permutations 题意：给定 nnn，问满足 pi mod pi+1≤2p_i \text{ mod } p_{i+1} \le 2pi​ mod pi+1​≤2，（pn+1=p1p_{n+1}=p_1pn+1​=p1​），的排列 ppp 的个数。 dp 首先 1 和 2 可以放在任意位置。 由于这个题目要的其实是个环，所以可以从 1 的位置切开，变成 1,x,x,x,2,x,x,x,x。1 和 2 把整个排列分成两段。每一段内一定是递减的，因为如果有递增，则 pi mod pi+1=pi>2p_i \text{ mod } p_{i+1}=p_{i}>2pi​ mod pi+1​=pi​>2。 从小到大遍历，每一轮在上一轮的基础上插入数 iii，考虑把 iii 放在第一段还是第二段。 假设现在枚举到 iii，数组 dp[j]dp[j]dp[j] 表示与 iii 处于不同段的数中最大的数为 jjj 时的方案数。sum[j]sum[j]sum[j] 表示 jjj 的所有因数的 ...

https://ac.nowcoder.com/acm/contest/5674 F - Groundhog Looking Dowdy   题意：给定 n 个数列，要求从其中 m 个数列中各取一个数，使得取出的数最大值与最小值的差最小。 尺取法 把所有数放在一起从小到大排序，并且要记录好每个数属于哪个数组。 维护首尾两个指针，满足中间包含 m 个不同的数组（如果一个数组被包含多次也是可以的），从头开始向后蠕动，每次更新答案。 因为尾指针不会回头，所以每点最多遍历两次。 其实很像单调队列。 1234567891011121314151617181920212223242526272829303132333435363738#include<bits/stdc++.h>using namespace std;#define ll long longconst int INF = 0x3f3f3f3f;const int N = 2e6 + 10;const ll mod = 1e9 + 7;int n, m;typedef pair<int, int>pii;in ...

https://ac.nowcoder.com/acm/contest/5673#question E - Enigmatic Partition   题意：给定 n，要求分解为几个非递减的数的和，并且相邻数的差不超过 1，且最后一个数 - 第一个数 = 2. 做法一：枚举。 题解的做法。 设 n=nl∗l+m∗mid+nr∗rn=nl*l+m*mid+nr*rn=nl∗l+m∗mid+nr∗r。因为 l=mid−1=r−2l=mid-1=r-2l=mid−1=r−2。所以每两个 midmidmid 可以分解为 1 个 lll + 1 个 rrr，共有 mmm 个 midmidmid，则共有 ⌊(m−1)/2⌋\lfloor (m-1)/2 \rfloor⌊(m−1)/2⌋ 种分解情况，-1 是因为至少要留一个 midmidmid。 枚举 lll，再分两种情况：nl>nrnl>nrnl>nr 和 nl≤nrnl\le nrnl≤nr，由于分解 midmidmid 不会改变两者的大小关系，所以这两种情况没有交集。对于第一种情况，枚举 nl−nrnl-nrnl−nr，即多 ...

https://ac.nowcoder.com/acm/contest/5672 J - Pointer Analysis   题意：给定了一段程序，有种操作，26个object用小写字母表示，26个全局指针用大写字母表示，每个object也有26个成员指针变量也用小写字母表示，程序会不断重复执行，且执行顺序随机，问最终每个全局指针指向的object。 模拟 P[A][a]P[A][a]P[A][a] 表示全局指针 A 是/否 指向object a。 O[a][b][c]O[a][b][c]O[a][b][c] 表示object a 的 成员指针 b 是/否 指向object c。 接下来直接暴力模拟即可。 要注意的是由于不断随机顺序执行，所以对与每个语句要执行所有可能的情况，所以最外层要迭代 n 次。迭代 n 次就可以得到所有情况了，把程序复制n次排下去，可以发现任意排列都可以在新的程序中找到（每段里选一句即可）。若少于 n 次则必定缺少，比如倒序。 对此还需要注意的是只有当所有语句都是重复执行不影响结果时才可以。 比如 1234A++;B = A;B = A;A++; 1234A+ ...

https://ac.nowcoder.com/acm/contest/5671 B - Binary Vector   题意：n 维的 01 向量空间，每次随机选一个向量，问 n 次后所有向量线性无关的概率。 假设已选出 i 个向量，则这 i 个向量构成的向量空间包含 2i2^i2i 个向量：其实就是 i 个向量的线性组合，也就是子集大小。 则下一个要选的向量必须不在这个空间内，已知 n 维向量空间中所有向量总数为 2n2^n2n，则所选向量的概率为 2n−2i2n\frac{2^n-2^i}{2^n}2n2n−2i​。对于每一步选择，即每一个 i 都有上面的要求，所以最终概率为 ∏i=0n−12n−2i2n\prod_{i=0}^{n-1}\frac{2^n-2^i}{2^n}∏i=0n−1​2n2n−2i​。 fn=∏i=0n−12n−2i2n=∏i=0n−12n−i−12n−i=∏i=1n2i−12i⇓fn=fn−1⋅(2n−12n)=fn−1⋅(1−12n)\begin{align} f_n&=\prod_{i=0}^{n-1}\frac{2^n-2^i}{2^n}\ ...

https://ac.nowcoder.com/acm/contest/5670 I - Hard Math Problem   题意：一个无限大的二维网格，每格可以填 1，2，3，要求每个 1 四周至少有一个 2 和一个 3。问 1 的密度最大多少。 构造 如上图，在 (i+j)%3==0(i+j)\%3==0(i+j)%3==0 处放 2 或 3，其它地方放 1 ，并满足 1 和 2，3 相邻。 123456#include<bits/stdc++.h>using namespace std;int main() { puts("0.666667"); return 0;} D - Drop Voicing   题意：给定一个 1 到 n 的排列，2 种操作：所有数环形向左平移一位；前 n-1 个数环形向右平移一位。连续的第 2 种操作算作一次大操作，问最少用几次大操作使得排列变为有序。 贪心+最长上升子序列 先进行一次连续 k 个第 2 种操作，再进行连续 k 个第 1 种操作，则原先的最后一个数向前平移了 k 位。其中 k ...

https://ac.nowcoder.com/acm/contest/5669 H - Harder Gcd Problem   题意：给定 n，把 1 到 n 这 n 个数两两配对，每对不互质，要求对数最多。 构造 先处理出每个质数的倍数，每个质数对应一个集合，从大到小处理这些质数，大于 n/2 的质数显然不会有能够配对的数了，所以直接忽略。从最大的质数开始，贪心地把没有配对过的两两配对，可能多出一个，则让 2*p 作为多出的那个，放进一个备用集合里。这样处理完所有集合之后，备用集合里都是 2p，则都是 2 的倍数，这些数可以两两任意配对了。 如果这样再多出一个数，就必定只能多出来了，因为这种做法已经把所有能够配对的都用到了，只剩一个数是绝对无法再使用的了。 至于要从大到小遍历质数，则是因为最终备用集合里的数gcd都是2，也就相当于多出来的这些数都有共同因子 2 接着，如果从小到大遍历，则要从 3 开始，这样才能保证所有多出来的数都能有共同因子 2。 123456789101112131415161718192021222324252627282930313233343536373 ...