Codeforces Round 837 (Div. 2) A.Hossam and Combinatorics算法本质思维题目大意找出相差值最大的元素对（ij和ji算2对）数目。思路推演找最大值个数*最小值个数。最大值 == 最小值情况特殊考虑。B.Hossam and Friends算法本质思维题目大意（改）有n个人[1~n]，其中m对人有仇。请问[l r]中无仇家的数组数目。n、m <= 1e5思路推演对于每个左端点，检查右端点的可行范围。对于每对仇人，先初步确立一些左端点的范围。然后从n~1，依次取小。最后就得到了真实的可行范围，都加到ans里即可。ac核心代码头文件、宏定义、快读模板、常见变量、常见变量等略。 int R[maxn]; inline void solve() { //init cin>>n>>m; rep(i,1,n) R[i]=n; while (m--) { int u, v; cin>>u>>v; if (u>v) swap(u, v); R[u] = min(R[u], v-1); } //cal int ans=0; for (int i=n-1; i>=1; i--) { R[i] = min(R[i], R[i+1]); ans += R[i] - i + 1; } cout<<ans+1<<endl; //因为i==n的还没加 return; }C.Hossam and Trainees算法本质思维题目大意n个数字之间是否存在一对不互质。n <= 1e5 元素 <= 1e9思路推演直接可以想到用分解质因数来判断。但是根号级别的判断方法是无法满足的，于是先处理部分素数（<=1e9根号），再分解质因数来优化。值得注意的是，为了卡掉根号的做法，时间设置相对极限。当时粗略地将1e5作为1e9根号替代，最后超时。ac核心代码头文件、宏定义、快读模板、常见变量、常见变量等略。 int a[maxn]; map<int, int> mp; void f(int x) { for (int su:prime) //prime用埃氏筛得到的，手动筛也是可行的 { if (x%su==0) { while (x%su==0) x/=su; mp[su]++; } } if (x>1) mp[x]++; } inline void solve() { //init cin>>n; mp.clear(); rep(i,1,n) cin>>a[i]; //cal flag=0; for (int i=1; i<=n; i++) f(a[i]); for (auto it:mp) if (it.second>=2) flag=1; if (flag) cout<<"YES"<<endl; else cout<<"NO"<<endl; return; }D.Hossam and (sub-)palindromic tree算法本质思维、dp题目大意具有n个节点的树，每个节点有一个字符，求树任意路径的最长回文子序列的最长值。n <= 2e3思路推演字符串的最长回文子序列是一个较为经典的dp问题。二维dp：dp[l][r]表示l~r的字符串的最长回文子序列长度。转移公式：s[l]==s[r] --> dp[l][r]=dp[l+1][r-1]+2s[l]!=s[r] --> dp[l][r] = max(dp[l+1][r], dp[l][r-1])复杂度：O(n^2)现在需要转移到树上，主要考虑的就是一手复用。这样的不确定情况下，通常用记忆化搜索，而不是预处理。思考：树上实现的较为困难的地方：方向。前面的l+1 r-1在树上不明确，于是需要对每个点都预处理：对于任意点，如果其想向u靠近，其下一步应该如何走。ac核心代码头文件、宏定义、快读模板、常见变量、常见变量等略。 vector<int> edges[maxn]; int dp[maxn][maxn]; //dp[l][r]表示 l r的最长回文子序列长度 int nxt[maxn][maxn]; //nxt[] int f(int l, int r) { if (l==r) return 1; //单个字符就是1 if (nxt[l][r] == r) return 1+(s[l]==s[r]); //2个字符也直接处理了 if (dp[l][r]>0) return dp[l][r]; //记忆化搜索 dp[l][r] = max(f(nxt[l][r], r), f(l, nxt[r][l])); //常规丢左丢右 if (s[l]==s[r]) //相等情况另算 dp[l][r] = max(dp[l][r], f(nxt[l][r], nxt[r][l]) + 2); return dp[l][r]; } void gravity(int u, int fr, int yuan) //gravity译为重力 { nxt[u][yuan] = fr; for (auto v:edges[u]) if (v!=fr) gravity(v, u, yuan); } inline void solve() { //init cin>>n>>s; s = " " + s; rep(i,1,n) edges[i].clear(); //清空 rep(i,1,n) rep(j,1,n) dp[i][j]=0; rep(i,1,n-1) { int u, v; cin>>u>>v; edges[u].push_back(v); edges[v].push_back(u); } //cal for (int i=1; i<=n; i++) //预处理nxt[][] gravity(i, 0, i); int ans=0; for (int u=1; u<=n; u++) { for (int v=1; v<=n; v++) ans = max(ans, f(u, v)); } //out cout<<ans<<endl; return; }

Codeforces Round 836 (Div. 2) B.XOR = Average算法本质思维题目大意给定一个n，请给出n个范围为(1~1e9)的数字（可重复），使其异或和==平均值。思路推演n为奇数时，任意个相同数即可。n为偶数时，事情有了变化，暂时没有明确规律。那先手动计算一些情况。当n==2时，可以找出1 3、2 6等等方法。考虑当n==4时，发现十分不好找，但是当利用n==2的情况，可以很快找出1 3 2 2。随即找到n为偶数的规律：1 3 2 2 2 ...C.Almost All Multiples算法本质思维题目大意对于一个长度为n的排列p[]，已知整数x，如果满意以下条件则是美丽的：p[1]=xp[n]=1对于i<n：p[i] % i == 0在所有美丽的排列中选择字典序最小的输出。思路推演首先尝试构造一下p[]，从大到小构造。很容易发现，只有n是还没用的，只有n的因数可以填n。如果x不是n的因数，则没有美丽排列。如果是n%x==0，就通过a[x]=n一定可以获得一个美丽排序，就考虑如何才能构造字典序最小的美丽排序。首先小于x部分不动，动了会增大字典序，同时我们希望把a[x]=n往后移动一下，即找后面下标是n因数的位置。即可发现规律。（规律相对简单，这里略过）注意考虑x=1 和 x=n的情况，可能需要特判，根据代码的鲁棒性。D.Range = √Sum算法本质思维题目大意给定一个n，请给出n个范围为(1~1e9)的数字（不可重复），使其max_val - min_val == √Sum。思路推演因为Sum需要开方，所以先设定Sum的值，当设置为n n+1 n+2的时候，调整空间过小导致了一些问题。所以这里直接设2n，即Sum = 4n^2构造就是一个尝试的过程则平均数就是4n，范围为3n ~ 5n。然后依次填入即可。E.Tick, Tock算法本质思维、加权并查集题目大意给你一个n*m的矩形，每个格子有一个0 ~ h-1的数字，若为-1表示不确定。如果一个矩形可以通过任意次以下操作使所有数字为0，则称其为美丽的：选择任意一行或一列数字+1，然后对h取模输出可能存在的美丽狙矩阵个数。（取模1e9+7）思路推演首先来看看美丽矩阵具有的特征。通过手动模拟可以发现，美丽矩阵的每一行中，其列下标之间的数字差是一样的：mp[x1][y1]-mp[x1][y2] == mp[x2][y1]-mp[x2][y2]（对h取模）。以列为单位看也是一样的，值得注意的是：如果能保证每个行中，其对应位置的数字差一致，则不需要考虑列情况。这时我们把每一列看作一个节点。每行的某2个不为-1的数字，都代表了一种关系——表示这两列的节点之间的差值。我们历便所有行，拿到所有关系，如果关系之间有冲突，说明是不可行的，输出0结束。看似每行最多有m^2条关系，实际因为加法的结合律，可以最多使用m-1条关系来表示m个节点的关系。建图+dfs可以维护这些关系，且可以判断冲突。但是带权并查集十分适合当前情况，更加推荐。随后思考：当关系不冲突时，有多少种情况。当m个节点组合成一个连通块时，说明只有当前情况。当他们组成x个连通块时，还可以用x-1条新关系填充，即qpow(k, x-1)。假设已经补充了新关系，现在m个节点组成了一个连通块。当某一行值全为-1时，即使知道他们的关系（差值），因为没有初始值，所以仍有k种可能。所以ans = qpow(k, 全为-1值的行数 + 连通块数 - 1, mod)ac核心代码头文件、宏定义、快读模板、常见变量、常见变量等略。 inline int mu(int x) { return (x%k+k)%k; } // 先使用init_set()初始化 int fu[maxn], val[maxn]; // 加权并查集板子 void init_set() { for (int i=1; i<=m; i++) fu[i] = i; // i 就在它本身的集合里 for (int i=1; i<=m; i++) val[i] = 0; return; } int find_set(int x) { if (x != fu[x]) // x 不是自身的父亲，即 x 不是该集合的代表 { int fx=fu[x]; fu[x] = find_set(fu[x]); // 路径优化代码 val[x] += val[fx]; val[x] = mu(val[x]); } return fu[x]; } void union_set(int x, int y, int v) // x家族 --> y家族（x为儿子，y为父亲） { int fx = find_set(x); int fy = find_set(y); if (fx==fy) return; fu[fx] = fy; // 把 x 的祖先变成 y 的祖先的儿子 val[fx] = -val[x] + v + val[y]; } bool vis[maxn]; //计算连通块数 inline void solve() { //init cin>>n>>m>>k; init_set(); //cal int ans=0; flag=1; for (int x=1; x<=n; x++) { int y0=-1, v0=0; //y0表示这一行第一个不为-1的位置，val是其值 for (int y=1; y<=m; y++) { int v; cin>>v; if (v==-1) continue; if (y0==-1) { y0=y; v0=v; } else //同一行多个值，需要建立关系 { int f1=find_set(y0), f2=find_set(y); if (f1==f2 && mu(val[y0]-val[y])!=mu(v0-v)) //说明关系起冲突了，直接爆炸 flag=0; else if (f1!=f2) //说明关系还没建立，建立关系 union_set(y0, y, mu(v0-v)); } } if (y0==-1) //说明这行全是-1 ans++; } rep(i,1,m) vis[i]=0; for (int i=1; i<=m; i++) //连通块数 { int fi=find_set(i); ans += vis[fi]==0; vis[fi]=1; } ans--; //out ans = qpow(k, ans, mod); if (!flag) ans=0; cout<<ans<<endl; return; }

Codeforces Round 833 (Div. 2) A.The Ultimate Square算法本质思维题目大意给n块木板，第i块木板的规格是1 * (i+1)/2。请问可以拼成的最大正方形边长。思路推演第一时间想不到解法，但是思考其A题，应该相对简单，就打表n块木板的最大面积：1 2 4 6 9 12 16 20 ...。可以看到的是，对于n为奇数的情况，其总面积是平方数。然后拿个奇数n来手动拼一下，验证一下是否可行：可以分为(n+1)/2个1 * (n+1)/2的矩形：(n+1)/2 (n+1)/2-1和1 (n+1)/2-1和1 (n+1)/2-2和2 ...说明是可行的，而且偶数n情况也不会大于下一个平方数。所以答案输出(n+1)/2即可。B.Diverse Substrings算法本质思维题目大意给定由0~9组成的字符串S。对于其中的一个子串，称其为美丽：某字符的数目 <= 字符种类请问美丽的非空字串数目。s.length <= 1e5思路推演普通的想法是，看看某字符的数目和字符种类有没有单调性，可以前缀+二分搞定。手动模拟了一下，发现没有。但是发现了一个忽略的条件：字符串只由0~9组成，说明字符种类最多也就10个，当某字符数目>10时，就一定不能是美丽的。所以直接暴力搜就好，写个条件剪枝。C.Zero-Sum Prefixes算法本质思维题目大意给定长度为n的数组a[]，其中值为0的元素可以修改为任意值。对于数组a[]，其魅力值的计算如下：设其前缀和数组为pre[]，魅力值为pre[]元素为0的数目最大化a[]的魅力值并输出。n <= 2e5思路推演对于下标为i的0值来说，其整体改变会影响其pre[i~n]的值。所以实际上，0值之间的pre[]元素会上下移动，让其最多的元素值移动到0值即可。D.ConstructOR算法本质思维题目大意给定3个整数a b d。输出是否存在整数x，使得：a|x % d == 0b|x % d == 0a,b,d <= 2**30 x <= 2**60思路推演要同时满足a b两个数，比较难。因为是or运算，所以考虑，x对于a b都满足x|a == x和x|b == x。即把a b都看作同一个数：a|b。这里看成同一个数，只是单纯地为了简化思考难度。如果后面发现不能，我们也完成了对单个数的思考，从而进一步思考两个数情况。设：c = a|b目前存在2个式子（要求）x|c == x（二进制下，c的某位为1，x的这位必须为1）同时需要lowbit(x) == lowbit(c)x%d == 0思维推演-1回忆一下，通常对于多个要求的情况，都是先满足一个相对简单、有规律的要求，然后去靠近另外的要求。所以我们这里先满足x%d==0的要求。下面结论得出有些跳跃，实际做的时候是不断尝试+经验得到的结论假设目前x=0随后找到c为1但是x为0的二进制位，现在需要用左移的d对这些位填充。假设c的二进制为：0000000011010100（左高右低，从右往左下标1开始）则x的第1、2位只能为0，现在3、5、7、8位必须要填充为1。整体填充没有找到合适方法从左往右填充在填充位置更小的1时，d的值可能改变前面位置更大的需要填充的1从右往左填充合理ac核心代码-1头文件、宏定义、快读模板、常见变量、常见变量等略。 int er[100]; //solve_init()预处理了 int wei(int x, int c) //找到最低的一位：c为1，x为0的位 { for (int i=0; i<=60; i++) { if ((c&er[i])>0 && (x&er[i])==0) return i; } return -1; //说明已经合格了 } inline void solve() { //init int a, b, c, d; cin>>a>>b>>d; c = a|b; if (lowbit(d) > lowbit(c)) { cout<<-1<<endl; return; } //cal int x=0, p0=0, tmp=d; //p0表示d的前缀0个数 while ((tmp&1)==0) { p0++; tmp/=2; } while (1) { int w = wei(x, c); //找到最低的一位：c为1，x为0的位 if (w==-1) break; //如果没找到，就说明填充完了，直接退出 x += d*er[w-p0]; //填充 } cout<<x<<endl; return; }https://zhuanlan.zhihu.com/p/582922871https://zhuanlan.zhihu.com/p/583789192https://zhuanlan.zhihu.com/p/583087619https://zhuanlan.zhihu.com/p/582927038E.Yet Another Array Counting Problem算法本质思维、树形dp题目大意给定长度为n的数组a[]，其元素值在1~m之间。对于长度为n数组b[]，其是美丽的如果满足下列条件：元素值在1~m之间对于所有的区间[l r]，b[]在区间内的最左端的最大值的下标同a[]的一样，下面用函数f(l,r)表示找出美丽b[]的数目。（mod 1e9+7）n,m <= 2e5 n*m <= 1e6思路推演手动模拟一下，如果对于a[]，f(1,n)=i。则当l<=i && r>=i的时候，其f(l,r)=i。这一下子解决了许多区间！继续思考左右两边是不是独立的，手动模拟（题目样例），发现确实是独立的。不过左区间需要保证值<b[i]而右区间的值<=b[i]。这是相当典型的二叉树结构。思考，能否log级别找到区间最大值下标——ok的，只需要稍微改动一下st表。ac核心代码-1头文件、宏定义、快读模板、常见变量、常见变量等略。 int a[maxn]; vector<int> cnt[maxn]; //cnt[pos][val]：b[pos]值为val的方案数（只算树下部分） vector<int> pre[maxn]; //cnt的前缀和 pair<int,int> st[maxn][20]; //st板子 void init_st() { for (int i=1; i<=n; i++) //st[]初始化 st[i][0]={a[i], n-i}; //值大、位置小优先 for (int len=1; len<=20; len++) for (int pos=1; pos+(1<<len)-1<=n; pos++) st[pos][len] = max(st[pos][len-1], st[ pos+(1<<(len-1)) ][len-1]); } int find_st(int l, int r) //返回的是最左边的最大值的下标 { int len=log2(r-l+1); pair<int, int> u=max( st[l][len] , st[r-(1<<len)+1][len]); return n-u.second; } int sonl[maxn], sonr[maxn]; int dfs(int l=1, int r=n, int fr=0, int val=m) //开始造树结构 { int pos = find_st(l, r); //找到最左边的最大值 if (pos>l) sonl[pos] = dfs(l, pos-1, pos, val-1); if (pos<r) sonr[pos] = dfs(pos+1, r, pos, val); if (sonl[pos]==0 && sonr[pos]==0) // 如果左右都没有儿子，那就把所有可以取到的值设为1 { for (int i=1; i<=val; i++) { cnt[pos][i] = 1; cnt[pos][i] %= mod; pre[pos][i] = pre[pos][i-1] + cnt[pos][i]; pre[pos][i] %= mod; } } else if (sonl[pos]==0) { for (int i=1; i<=val; i++) { cnt[pos][i] = pre[sonr[pos]][i]; //右区间的值不降 cnt[pos][i] %= mod; pre[pos][i] = pre[pos][i-1] + cnt[pos][i]; pre[pos][i] %= mod; } } else if (sonr[pos]==0) { for (int i=1; i<=val; i++) { cnt[pos][i] = pre[sonl[pos]][i-1]; //左区间的值降1 cnt[pos][i] %= mod; pre[pos][i] = pre[pos][i-1] + cnt[pos][i]; pre[pos][i] %= mod; } } else { for (int i=1; i<=val; i++) { cnt[pos][i] = pre[sonl[pos]][i-1] * pre[sonr[pos]][i]; cnt[pos][i] %= mod; pre[pos][i] = pre[pos][i-1] + cnt[pos][i]; pre[pos][i] %= mod; } } return pos; } inline void solve() { //init cin>>n>>m; rep(i,1,n) cin>>a[i]; rep(i,1,n) { cnt[i].clear(); //cnt[]和pre[]可以不用赋初始值 cnt[i].resize(m+5); pre[i].clear(); pre[i].resize(m+5); sonl[i]=0; //因为dfs()中需要判断是否为空，所以要赋初值0 sonr[i]=0; } init_st(); //稍作改动的st表 //cal int root=dfs(); int ans = pre[root][m]; cout<<ans<<endl; return; }

Codeforces Round 830 (Div. 2) A.Bestie算法本质思维题目大意给定长度n的数组a[]，经过一下付费操作，使得最后所有元素的gcd运算为1：n-x+1元：使a[x] = gcd(a[x], x)输出最小化花费。思路推演这个花费，意味靠右元素操作更好。另外，相邻的2个自然数gcd值为1，所以可以保证，对n-1和n元素操作后，全部gcd值都为1。所以只有3种情况：对n操作对n-1操作两者都操作B.Ugu算法本质思维题目大意给定01字符串s，需要进行多次以下操作，使得s不递减：选择下标i，取反[i,n]的字符最小化操作次数。思路推演直接暴力从左往右推，记录一下取反次数，得到当前字符即可。C2.Sheikh (Hard Version)算法本质思维题目大意给定长度n的数组a[]。对于数组a[]的[l, r]区间，定义：元素和：sum(l,r) = a[l] + a[l+1] + ... + a[r]异或和：xor(l,r) = a[l] ^ a[l+1] ^ ... ^ a[r]魅力值：f(l,r) = sum(l,r)-xor(l,r)接下来跟有q次询问，每次询问会给出L R，需要你找到一对l r满足：（条件先后存在优先级）L <= l <= r <= R最大化魅力值最小化r-ln <= 2e5 q = n思路推演显而易见的是（或者手动模拟一下），当一个区间新加入一个元素时，魅力值可能不变 or 增加（单调性）。所以f(L,R)一定是最大值。注：因为a[]元素不改变，所以可以预处理，O(1)做到对区间魅力值的查询。我们的目标就是减少左右两边的元素，同时保持魅力值不变。通过魅力值的单调性可知：若丢弃某个元素会导致魅力值下降，则这个元素一定不可丢弃理想情况，肯定是先丢左边的、再丢右边的。实际上，模拟一下也很快发现，左边元素是否丢弃，会影响右边元素是否可以丢弃。例如1 2 4 3可以变成1 2 4或者4 3。此时就有一个显然的暴力做法：枚举l，r的位置用二分找出，单次询问复杂度nlog，可以应付简单版本显然，还缺一个特性来优化算法，而此题用到了异或，大概率是从异或上找个特性。异或的特性基本都要从二进制形式去找，结合刚才模拟的情况，可以发现：若某个元素，其二进制下为1的位，剩下的元素都无交集，即可以去除同时魅力值不减这样的话，最多有30个元素可以去掉。所以我们可以放心的枚举l，只要遇到枚举时降低了魅力值就break即可。但是这道题有0的存在，0百分百可以去掉的，但是如果手动O(n)去掉则复杂度会超的。预处理一个数组，可以O(1)找到下个不为0的元素下标即可。ac核心代码头文件、宏定义、快读模板、常见变量、常见变量等略。 int a[maxn]; int pre_sum[maxn]; int pre_xor[maxn]; int to[maxn]; // to[i]：[i~n]中最左端的不为0值的下标 int f(int l, int r) // 区间魅力值 { return pre_sum[r]-pre_sum[l-1] - (pre_xor[r]^pre_xor[l-1]); } inline void solve() { //init int q; cin>>n>>q; rep(i,1,n) cin>>a[i]; rep(i,1,n) pre_sum[i]=pre_sum[i-1]+a[i]; rep(i,1,n) pre_xor[i]=pre_xor[i-1]^a[i]; to[n+1] = n+1; for (int i=n; i>=1; i--) // 维护to[] { if (a[i]!=0) to[i]=i; else to[i] = to[i+1]; } //cal while (q--) { int L, R; cin>>L>>R; int ans_l=L, ans_r=R; // ans_r-ans_l最小 int zhi=f(L, R); // 魅力值 int l=L; while (l<=R && f(l, R)==zhi) //枚举r（最多枚举30个不为0的r { int z=l, y=R; //二分r int r=y; while (z<=y) { int mid=(z+y)/2; if (f(l, mid)==zhi) { r=mid; y=mid-1; } else z=mid+1; } if (r-l < ans_r-ans_l) //更新答案 { ans_l=l; ans_r=r; } l = to[l+1]; //更新l } cout<<ans_l<<" "<<ans_r<<endl; } return; }D1.Balance (Easy version)D2.Balance (Hard version)算法本质思维题目大意初始有一个空的集合，接下来有q次操作，每次操作为以下某种情况：+ x：添加x到集合中- x：从集合中删去x（Easy版本不存在- x操作）? k：查找不存在集合中、%k为0、最小正数q：[1, 2e5] x k：[1, 1e18]思路推演-D1（Easy版本）如果就模拟题目的描述，用set存放x，每次查询的复杂度是q/k，如果查询的k都是较小数，则时间不可行。检查一下，很轻易地就发现了重复计算的部分，加上不会删除元素，所以每次查询时，保存一下上次查询进度，下次继承即可。思路推演-D2（Hard版本）Hard版本引入了删除操作，沿用之前的思路的话，问题是如果集合已有2 4 6 8 10 ...，现在删除元素8，不仅对k=2的查询有影响，还对k=4、k=8等查询有影响。我们之前的查询进度将会作废。假设称k 2*k 3*k ...的形式为k链条。x的最大值为1e18，所以其最多因数的个数也相当大 即可以对许多链条造成影响 不过因为q最大2e5 所以最多对2e5条链条造成影响 继续看能否优化一下 手动模拟一下，当x影响的最多链条数 与 集合内元素个数开方 相关整理一下思路：当查询k时，我们同D1一样，维护k链条的最值 当删除x时，找到有x值的链条，然后给他们打上缺失x的标记 当增加x时，找到有x值的链条，清除缺失x的标记 还需要维护链条是否存在x值，这里放在查询时建立链条中使用ac核心代码头文件、宏定义、快读模板、常见变量、常见变量等略。 set<int> vis; // 表示集合中的数 map<int, int> lian; // lian[x]表示x链条的最值 map<int, set<int>> que; // que[x]表示x链条缺失的值（用set是为了快速找出最小的值） map<int, vector<int>> change; // change[x]表示存在x值的链条集合 inline void solve() { //init int q; cin>>q; while (q--) { char op; int x; cin>>op>>x; if (op=='+') { vis.insert(x); // 集合添加x for (int u:change[x]) // u链条需要删除缺值x que[u].erase(x); } else if (op=='-') { vis.erase(x); // 集合删除x for (int u:change[x]) // u链条需要添加缺值x que[u].insert(x); } else if (op=='?') { if (lian.count(x)==0) // 还没有建链条 lian[x] = 0; // 初始化链条 if (que[x].size()) // 存在缺失的值 { cout<<*que[x].begin()<<endl; // 输出最小的缺失值 continue; } // 没有缺值则输出链条不可达值 while (vis.count(lian[x]+x)) // 维护链条 { lian[x]+=x; change[lian[x]].push_back(x); // 记录x链条存在lian[x]值 } cout<<lian[x]+x<<endl; // 输出链条不可达值 } } return; }

Codeforces Round 825 (Div. 2) A.Make A Equal to B算法本质思维题目大意给定长度都是n的01数组a[] b[]。可以通过花钱对a[]操作，使得a[]最终等于b[]，求最少花销：1元：选择某个下标i：a[i]=1-a[i]1元：重新排列a[]元素，以任何方式皆可思路推演一般情况，都是先将a[]中的01数目改得跟b[]一样，再重排列。需要考虑的一点是：可能a[]改后不需要重排列。这个逻辑相对简单，但是也可以更暴力一些。将a[]分成2种情况：需要使用重排列、不需要使用。然后分别计算，求小值。B.Playing with GCD算法本质思维题目大意给定长度n的数组a[]。对于长度为n+1的数组b[]，满足下列条件则美丽：对任意i：a[i] == gcd(b[i], b[i+1])是否存在美丽的数组b[]。思路推演显然可知，最优解中：b[1]=a[1] b[n+1]=a[n]对于b[i]来说，其最优解为：lca(a[i-1], a[i])获得了所有最优解后，检查b[]是否美丽即可。C1.Good Subarrays (Easy Version)算法本质思维、双指针（or 二分）题目大意对于长为m的数组b[]，其满足下列条件则是美丽的：b[i] >= i现在给定长度为n的数组a[]，求其美丽连续子数组个数。思路推演对于l，如果a[r]-r >= 0-l+1则说明b[l~r]中b[r]是满足条件的（只是说这个元素满足，并不一定美丽）如果a[l~r]美丽，则a[l+1~r]一定美丽所以对于b[]是具备单调性的，可以用双指针or二分解决。sac核心代码头文件、宏定义、快读模板、常见变量、常见变量等略。 int a[maxn]; inline void solve() { //init cin>>n; rep(i,1,n) cin>>a[i]; //cal int ans=0; int r=1; for (int l=1; l<=n; l++) //历便左端点 { while (r<=n && a[r]-r >= -l+1) // r表示第一个不满足条件的 r++; ans += r-l; } cout<<ans<<endl; return; }C2.Good Subarrays (Hard Version)算法本质思维、数据结构题目大意对于长为m的数组b[]，其满足下列条件则是美丽的：b[i] >= i现在给定长度为n的数组a[]，接下来会有q次查询，每次查询前会修改a[]中某个元素的值，然后询问a[]美丽连续子数组个数。（这意味每次查询都是独立的——修改不继承）思路推演此题其实不适合文字题解，结合画图讲解会清晰很多，但是懒得画假设修改为：a[p]=x当下标p的元素值被修改了，其影响的是p之前的贡献值，即p做右端点的区域。进一步思考，发现a[p]值的增加和减少是两种情况，需要分开讨论。为了方便叙述，这里定义2个词：理论左端点：对于右端点r，其值为val，理论上能找到的最左左端点是r+1-val，即理论左端点对于这些左端点，r点可行，但是小于r的点不一定可行计算：r+1-val可以直接计算可行左端点：对于右端点r，保证整体区域可行的最左左端点。（可行左端点肯定小于）计算：双指针找“l的最右实际可行r”时，可以顺带处理了以下图为例，绿色部分代表对于p的理论可行的左端点，最左的绿色点称之为理论左端点。蓝色部分代表对于p的实际可行的左端点，最左的蓝色点称之为可行左端点。询问的计算中，贡献值会改变的左端点范围为与下列两值有关：修改前的可行左端点：pre_l修改后的可行左端点：suf_l最后计算只与可行左端点有关，但是为了更好叙述，定义了理论左端点思路推演-a[p]值减少值减少意味对于一部分左端点，原本可以通过p点，但是现在无法通过了——即suf_l >= pre_l。具体的改变范围计算：因为suf_l >= pre_l，所以修改后中间肯定不存在坏点，所以可以简单地用理论左端点约束：suf_l = max(pre_l, p+1-x)具体改变值计算：这些左端点，原来都有着自己的可行右端点，现在因为a[p]值的减小——a[p]成了坏点，其可行右端点都变成了p-1。我们减去这些左端点原来的贡献值（前缀和预处理），加上之后的贡献值（等差数列）即可。思路推演-a[p]值增加值增加意味对于一部分左端点，原来不能通过p点，但是现在可以通过了——即suf_l <= pre_l。具体的改变范围计算：首先用理论左端点约束范围，之后如何保证没有坏点呢——用p-1的可行左端点！（这里有点小绕）于是得到：suf_l = max(p-1的可行左端点， p+1-x)具体改变值计算：新增的这部分左端点，原来的可行右端点都是p-1，被p阻拦了，现在p点值增加，不再阻拦了。具体能跑到哪与左端点自己的值有关。所以得想个办法维护：可行右端点2——对于l来说，允许忽略第一个碰到的坏点下，的最右右端点。这里也存在单调性，用再开一个指针即可预处理，然后前缀和预处理。ac核心代码看似定义的东西很多，实际很多数组都是前缀和延申、对立数组延申头文件、宏定义、快读模板、常见变量、常见变量等略。 int a[maxn]; int lef[maxn]; // lef[p2]=p1：[p1, p2]真实可行，且对于p2来说，p1是最左的真实可行区间 int rig[maxn]; // rig[p1]=p2：[p1, p2]真实可行，且对于p1来说，p2是最右的真实可行区间 int rig_2[maxn]; // rig_2[p1]=p2：对于p1为左端来来说，忽略rig[p1]+1的影响，的可行区间 int ctb[maxn]; // ctb[l]=y：固定左端点l时，其对答案贡献值为y（即rig[l]-l+1 = y） int pre_ctb[maxn]; // ctb[]前缀和 int pre_more[maxn]; // 定义more[x]=rig_2[x]-rig[x]，即多出的贡献值，pre_more[]是more[]的前缀和 int get_ctb(int l, int r) { return pre_ctb[r] - pre_ctb[l-1]; } int get_more(int l, int r) { return pre_more[r] - pre_more[l-1]; } int best_l(int r, int val) // 下标为r的值为val，理想情况下的最左端点（中间没有坏点） { return r+1-val; } inline void solve() { //init cin>>n; rep(i,1,n) cin>>a[i]; //cal 先找到原数组的答案，后面的询问在原数组上修改答案 int r=1, r2=1; for (int l=1; l<=n; l++) // 遍历左端点 { while (r<=n && a[r]-r >= -l+1) // r表示第一个不满足条件的 { lef[r] = l; // 可行左端点 r++; } rig[l] = r-1; // 可行右端点 ctb[l] = rig[l] - l + 1; // 左端点贡献值 pre_ctb[l] = pre_ctb[l-1] + ctb[l]; // 前缀和——左端点贡献值 r2 = max(r2, rig[l]+2); //忽略rig[l]+1的影响 r2 = min(r2, n+1); while (r2<=n && a[r2]-r2 >= -l+1) // r2表示第2个不满足条件的 r2++; rig_2[l] = r2-1; // 可行右端点（忽略rig[l]+1的影响） pre_more[l] = pre_more[l-1] + rig_2[l] - rig[l]; // 前缀和——多出的贡献值 } int ans = get_ctb(1, n); // 原数组的答案 //cal int q; cin>>q; while (q--) { int p, x, ans_now=ans; cin>>p>>x; if (x < a[p]) // 即a[p]值减少了 { int pre_l = lef[p]; // pre_l:修改前的可行左端点 int suf_l = max(lef[p], best_l(p, x)); // suf_l:修改后的可行左端点 // debug2(pre_l, suf_l) // [lef[p] ~ l-1]这些左端点，原来的右端点都>=p，现在因为缩水变成了p-1 ans_now -= get_ctb(pre_l, suf_l-1); // 减去原来的贡献值 ans_now += (p-pre_l + p-suf_l+1) * (suf_l-pre_l) / 2; // 加上新的贡献值（等差数列s） } else if (x > a[p]) // 即a[p]值增加了 { int pre_l = lef[p]; int suf_l = max(lef[p-1], best_l(p, x)); ans_now += get_more(suf_l, pre_l-1); // 加上原来的多出贡献值 } cout<<ans_now<<endl; } return; }D.Equal Binary Subsequences算法本质思维题目大意给定长度为2n的01字符串s，必须对其进行一次以下操作：选择任意长度的下标组成有序列b[]，然后对s中的这部分下标的字符，进行向右旋转一个位置即s[b[x+1]] = s[b[x]]。假设s=100010，可以选择b[]={1,2,5,6}，则操作后的为010001尽量使得操作后的s可以被完全分为2个长度为n的相等子序列。输出b[]信息、操作后s分出的其中一个子序列信息。（若不能输出-1即可）思路推演-1此题给了操作+满足xx条件，显然，需要我们对xx条件有一个认知，然后用操作去贴合xx条件。cf一般情况会把操作和条件的范围卡的极限——就是刚好符合，但是这题……正常的思路是：思考满足分为2个相等子序列的01字符串最低要求（即把规则转化为，更有规律的要求）操作去贴合要求手动模拟的时候发现，01字符串分开最大的问题是：相同字符的对标。比如1001001001这里面4个1，第一个1和谁是对标的，第二个还是第三个。根据经验来说，这里的规律应该要一定程度的简洁，所以我们可以假设前一半的1和后一半的1对标、1和相邻的1对标。继续模拟，得到一结论：当第1个c和第x个c对标可以分割时，其与第2~x-1中任意一个c对标一定成功当第1个c和第x个c对标不可分割时，其与第2~x-1中任意一个c对标可以成功所以可知：字符会找最近的相同字符对标同时01字符串里的0和1都有相同的性质，于是我们优先处理第一个出现的字符，这样还可以避免前导0（前导1）的情况。当使用了这个操作后，无法分割，则表面某个地方出了问题，需要修复。比如对于字符串`101001101001` 前`1010`可以分割，直接丢掉，剩下：`01101001` 然后会先得到2份： 011 0 还剩下`1001`，最开始的1放入2队 011 01 剩下`001`，这个0只有放入1队，依次类推得到 01100 011 不相等，说明出了问题，出的问题就在多的那部分0上问题找到了，但是不够完全，修改的操作无地下手。（这里略述了，可以自行造一些例子试一下）实际上，赛时就在这个地方卡住了，不明白哪一步错了思路推演-2这个可以算作经验主义犯的错，或者另一方面说，思考的不够完全。这次的操作有比较特殊，不是那种常见的行为，这说明操作本身也有探索空间。反过来思考操作，操作只能看作2种情况：将某个元素从塞在前面任意位置01交叉地循环换一轮位置思考了之前的情况的话，可以较为轻松地找到一个样例，使用操作1是不可行的。（但是存在其他方法可行）所以思考操作2的情况。手动模拟一下，会有一个相当大的发现：我们可以将孤独的字符和其相同字符放在一起。进一步思考就会发现，可以人为规定a[2*k]==a[2*k+1]，只需要找到不相等的对，就可以完成了。ac核心代码头文件、宏定义、快读模板、常见变量、常见变量等略。 vector<int> v, ans; void dfs(int p=0, char val='0') //其实可以写成循环 { if (p>=v.size()) return; if (s[v[p]]==val) ans.push_back(v[p]); else if (s[v[p]+1]==val) ans.push_back(v[p]+1); dfs(p+1, val=='0' ? '1':'0'); } inline void solve() { //init cin>>n>>s; s = " " + s; //cal 1 检查可行性 int cnt[2] = {0}; for (int i=1; i<=2*n; i++) cnt[s[i]-'0']++; if (cnt[0]%2 || cnt[1]%2) { cout<<"-1"<<endl; return; } //cal 2 v.clear(); ans.clear(); for (int i=1; i<=2*n; i+=2) { if (s[i]!=s[i+1]) v.push_back(i); //v存放不相等的对 } dfs(); //out cout<<ans.size()<<" "; for (int u:ans) cout<<u<<" "; cout<<endl; for (int i=1; i<=2*n; i+=2) cout<<i<<" "; cout<<endl; return; }E.Kth Number（来自atcoder）算法本质思维、数学题目大意给n个范围[0, m]的元素。其中的0值有随机变成[1, m]中的一个数。（概率平均）求第k大元素的期望值。（取模mod）n,m,k：[1, 2e3]思路推演-正解正解如何想出来的，暂时不得而知，但是做法确实巧妙，可能以后学习了数学知识可以知道吧设某个0值随机变成了x值，则x值的期望用E(x)表示为：i遍历[1,m]，变成i值的概率 * i值的和等价于：（只有从1开始的平均随机期望可以这样转换）i遍历[1,m]，大于等于i值概率之和$E(x) = \sum_{i=1}^{m} i * p_{x=i} = \sum_{i=1}^{m} p_{x\ge i}$所以题目的问题可以转化为a[k]>=i （排序后）的概率之和：$ans = \sum_{i=1}^{m} p_{a_k\ge i}$其中$p_{a_k\ge i}$的概率可以转化为：至少有n-k+1个元素>=i的概率。具体值推理 设： 有cnt0个0值、(a+b)个已知值 对于i值来说，有a个已知值<i元素、b个已知值>=i元素 我们的目标是求得：至少有 n-k+1 个元素 >=i 的概率。 即0值中至少 n-k+1-b 个元素 >=i 的概率 （PS：如果 n-k+1-b<=0 说明百分百可行，则概率为1，若 n-k+1-b>cnt0 说明不可能满足，概率为0） 这是一个典型的二项式分布问题 p = (m-i+1)/m 一个0值>=i的概率 x = n-k+1-b 需要至少x个0值都>=i C(cnt0, x) * p^x * (1-p)^(cnt0-x) 恰好x个0值>=i的概率 然后恰好x、x+1、……、cnt0个值>=i的概率之和ac核心代码头文件、宏定义、快读模板、常见变量、常见变量等略。 inline void solve() { //init vector<int> v; int cnt0=0; cin>>n>>m>>k; for (int i=1; i<=n; i++) { int x; cin>>x; if(x==0) cnt0++; else v.push_back(x); } sort(v.begin(), v.end()); //cal int ans=0; for (int i=1; i<=m; i++) { int b=v.end() - lower_bound(v.begin(), v.end(), i); //有b个已知元素 >=i int p=(m-i+1) * qpow(m, mod-2, mod) %mod; // 一个0值>=i的概率 int q=(1-p+mod)%mod; // q=1-p int x=n-k+1-b; //至少需要x个0值>=i int res=0; if (x<=0) //说明百分百成功 res=1; else if (x>cnt0) // 说明不可能满足 res=0; else { for (int y=x; y<=cnt0; y++) res += C(cnt0, y) * qpow(p, y, mod) %mod * qpow(q, cnt0-y, mod) %mod; res %= mod; } ans += res; ans %= mod; } cout<<ans<<endl; return; }