Codeforces Round 809 (Div. 2) Chopping Carrots (Hard Version)算法本质思维题目大意给定长度n数组a[]，玩家需要构建长度n的p[]（元素范围[1~k]），最小化：$\max(\left \lfloor \frac{a_i}{p_i} \right \rfloor) - \min(\left \lfloor \frac{a_i}{p_i} \right \rfloor)$简单版本： n k a[] p[] <= 3e3 困难版本： n k a[] p[] <= 1e5思路推演 - 简单版本只需要枚举min值即可，枚举3e3次，每次枚举检查复杂度O(n)。思路推演 - 困难版本显然需要使用某种优化。对于某个a[i]值，我们取p[i]值时，其结果似乎没有a[i]个，其结果数目大概是根号个。证： 对于数n，i遍历1~n，求v=n/i(向下取整)的结果数目是根号个 当i的范围是[1~sqrt(n)]时，可以视作所有结果b各不相同——这里有sqrt(n)个v。 当i>sqrt(n)时，b<sqrt(n)，至多存在sqrt(n)个v。 得证。然后检查复杂度，题目给的时间应该允许O(n^1.5^)，一个朴素的想法是枚举这n^1.5^个可选值为min值，然后维护即可。根据上面的证明，这些值可以处理出来，这里介绍一种在线枚举的方式： 当v值增加时，有时候不仅+1，其可以用v = a[i] / (a[i] / (v+1))展示 这是因为p[]的取值并不重要，v值才是最后的值。 a[i] / (v+1)就是当v增加后的p[]值，然后求出新的v值ac核心代码注意这个代码会T，但是和这篇知乎题解的做法十分类似，复杂度也相同。这里是官方题解，有空看一下。头文件、宏定义、快读模板、常见变量、常见变量等略。 inline void solve() { cin>>n>>k; vector<int> a(n+5), p(n+5), v(n+5); // v[i] = a[i] / p[i] for (int i=1; i<=n; i++) cin>>a[i], p[i]=k, v[i]=a[i]/p[i]; sort(a.begin()+1, a.begin()+1+n); set<pair<int,int>> st; for (int i=1; i<=n; i++) st.insert({v[i], i}); int ans = st.rbegin()->first - st.begin()->first; while (1) { if (ans==0) break; int id=st.begin()->second; st.erase(st.begin()); p[id] = a[id] / (v[id] + 1); if (p[id]==0) break; v[id] = a[id] / p[id]; st.insert({v[id], id}); ans = min(ans, st.rbegin()->first - st.begin()->first); } cout<<ans<<endl; return; }Qpwoeirut and Vertices算法本质思维、数据结构题目大意顺序给定m条边，接下来给定q次询问：每次询问给定l r，若希望保证l~r的所有点在同一连通块，则至少需要前多少条边（注意这里是边的前缀）n q m <= 2e5思路推演由于每次询问的是一个区间的点，所以我们可以抽象出两个图：图1：正常图，即按照题目给定规则，每次给边的图2：有n个点，初始相邻点有没激活的边（n-1条）每次图1的操作后，其也会对图2做出改变。在模拟过程中发现，对于任意下标相邻的点来说，其距离可以视作图1中两点路径的最大边权，这个距离也可以视作图2两点的边权。对于l r的询问，实际是在图2中找这个区间的最大边权。所以现在我们希望对图1作处理，使其能够log级别查询任意两点的距离（这个距离是被我们定义的距离）。使用LCA类似的树上倍增即可实现。然后查询处理图2，最后应答询问。ac核心代码头文件、宏定义、快读模板、常见变量、常见变量等略。 title算法本质题目大意思路推演ac核心代码头文件、宏定义、快读模板、常见变量、常见变量等略。 title算法本质题目大意思路推演ac核心代码头文件、宏定义、快读模板、常见变量、常见变量等略。 title算法本质题目大意思路推演ac核心代码头文件、宏定义、快读模板、常见变量、常见变量等略。 title算法本质题目大意思路推演ac核心代码头文件、宏定义、快读模板、常见变量、常见变量等略。 title算法本质题目大意思路推演ac核心代码头文件、宏定义、快读模板、常见变量、常见变量等略。

Codeforces Round 808 (Div. 2) Difference Array算法本质（数学）思维题目大意给定长度n的不减数组a[]，进行n-1轮以下操作：将自身赋值为其差分数组（会使得其长度-1）重新排序（维持不减）输出最后a[]剩余的唯一数字。n <= 1e5 a[] <= 5e5思路推演对着规则稍加模拟，并没有发现什么核心规律。但是元素值的范围给的很不错，于是开始向这个方向思考。模拟过程中可以发现，通常情况来说，元素的值在操作时会降低的十分快，目前没有跑满的情况。这大概率有所问题。笔者思考到这后，没有想到之后的运用这实际上其核心在于种类有限。若当前有n个不同元素，希望下一轮的元素没有重复的，则当前元素的最大值应该是n^2级别。所以在经过第一次处理后，不同元素的种类至多有sqrt(5e5)个。如果我们可以对重复元素做出处理，加速计算过程，则可以直接暴力通过该题。对重复元素加速处理的方式有很多，其中用map会好写一些（看代码）。ac核心代码头文件、宏定义、快读模板、常见变量、常见变量等略。 void f(map<int, int> &mp1) { map<int, int> mp2; for (auto it=mp1.begin(); it!=mp1.end(); it++) { int val=it->first, num=it->second; if (num>1) // 避免出现数目为0的情况 mp2[0] += num-1; // 计算重复的元素（加速计算） auto it2 = next(it); if (it2!=mp1.end()) mp2[it2->first - val]++; } mp1 = mp2; } inline void solve() { cin>>n; map<int, int> mp; for (int i=1; i<=n; i++) mp[in()]++; n--; while (n--) f(mp); cout<<mp.begin()->first<<endl; return; }DFS Trees算法本质思维题目大意给定无向、联通、无重边的图，其中边权按边给出的下标顺序增加。Alice希望得到最小生成树的图，但她写了一个错误代码：bool vis[maxn]; void dfs(int u): v：根据u周边的边权按升序遍历 if (vis[v]) 将u-v放入有效边集合 dfs(v) 最后得到的边集合就是Alice认为的最小生成树的图现在请告诉Alice使用这段错误代码从哪些点开始可以得到正确图，哪些点不可行。思路推演由于没有相等权值的边，所以最小生成树的图是唯一的。可以知道图中存在一些违规边。核心就在于违规边对整体产生影响：对于任意一条违规边a--b可以先将所有点视作白色，a--b在最小树上的路径点被染成黑色，黑色点可以不路过a/b点可以抵达的点被染成灰色。在所有违规边中，都为白色的点，就是最后的可行点ac核心代码头文件、宏定义、快读模板、常见变量、常见变量等略。 省略了dsu和LCA板子 vector<pair<int,int>> die; // 记录被删除的边 int val[maxn]; vector <int> g[maxn]; // 注意这里替换g[] void f(int u, int fr=0) { val[u] += val[fr]; for (int v:g[u]) { if (v==fr) continue; f(v, u); } } inline void solve() { cin>>n>>m; DSU dsu(n); for (int i=1; i<=m; i++) { int u=in(), v=in(); if (dsu.same(u, v)) // 这里实际上是一个Kruskal，但是由于其边的权值给的十分规律，所以可以直接处理 die.push_back({u, v}); else g[u].push_back(v), g[v].push_back(u), dsu.merge(u, v); } dfs(1); // LCA处理 init_up(); for (auto [u, v] : die) { if (u==v) continue; if (deep[u] < deep[v]) swap(u, v); int zu = find_zu(u, v); if (zu!=v) { val[1]++; val[u]--; val[v]--; } else { int cha = deep[u] - deep[v]; int sonv = u; swim(sonv, cha-1); val[sonv]++; val[u]--; } } f(1); for (int i=1; i<=n; i++) cout<<(val[i]==0 ? 1 : 0); return; }title算法本质题目大意思路推演ac核心代码头文件、宏定义、快读模板、常见变量、常见变量等略。 title算法本质题目大意思路推演ac核心代码头文件、宏定义、快读模板、常见变量、常见变量等略。 title算法本质题目大意思路推演ac核心代码头文件、宏定义、快读模板、常见变量、常见变量等略。 title算法本质题目大意思路推演ac核心代码头文件、宏定义、快读模板、常见变量、常见变量等略。 title算法本质题目大意思路推演ac核心代码头文件、宏定义、快读模板、常见变量、常见变量等略。

Codeforces Round 800 (Div. 2) Keshi in Search of AmShZ算法本质思维！题目大意给定一个有向图，Alice在点1，希望走到点n，玩家每回合可以执行某个操作：删除某条边指挥Alice前进，Alice会随机选择一条可行的边前进输出最小化的至多操作次数。思路推演稍加思索可以发现，如果没有环，这就是一个十分简单的反向topo（含有一丢丢思维）：若对于u点来说，其有4个出点，其到n点的路是1 4 7 8如果不进行删除，则需要8步进行一次删除，则是1+1 4+1 7+1，还是需要8步进行2次删除需要6步进行3次删除需要4步，显然我们选择4步的现在来解决环的问题。看似环特别难，因为大家相互牵制、依赖。但是其数据范围1e5，其实反而是告诉我们，这个算法简单而高效。Dijkstra !这也是k短路的核心思想回想有向图，面临这种多样的情况时，dj最短路给出了思路：暴力维护最优即可。其解决环的核心在于，找到环中最近的点，这个最近不仅是距离最近，而是删除若干边后的最近。ac核心代码头文件、宏定义、快读模板、常见变量、常见变量等略。 inline void solve() { cin>>n>>m; vector<vector<int>> g(n+5); vector<int> chu(n+5), vis(n+5), dis(n+5, 1e9); while (m--) { int u, v; cin>>u>>v; g[v].push_back(u); chu[u]++; } priority_queue<pair<int,int>, vector<pair<int, int>>, greater<pair<int,int>>> q; // ! q.push({0, n}); dis[n] = 0; while (q.size()) { auto [last, u] = q.top(); q.pop(); if (vis[u]) continue; vis[u] = 1; dis[u] = last; for (int v:g[u]) { q.push({last + chu[v], v}); chu[v]--; } } int ans = dis[1]; cout<<ans<<endl; return; }title算法本质题目大意思路推演ac核心代码头文件、宏定义、快读模板、常见变量、常见变量等略。 title算法本质题目大意思路推演ac核心代码头文件、宏定义、快读模板、常见变量、常见变量等略。 title算法本质题目大意思路推演ac核心代码头文件、宏定义、快读模板、常见变量、常见变量等略。 title算法本质题目大意思路推演ac核心代码头文件、宏定义、快读模板、常见变量、常见变量等略。 title算法本质题目大意思路推演ac核心代码头文件、宏定义、快读模板、常见变量、常见变量等略。 title算法本质题目大意思路推演ac核心代码头文件、宏定义、快读模板、常见变量、常见变量等略。

Codeforces Round 804 (Div. 2) Almost Triple Deletions算法本质思维题目大意给定数组a[]，Alice希望不断执行以下操作使得a[]的元素种类唯一或者无元素：删除两个相邻且不相等的元素幸运的是，玩家可以指定Alice所选的元素。输出最大化剩余a[]的长度。n <= 5e3 a[] <= n思路推演很显然的dp题目。既然最后会留下某种元素，则朴素的想法就是，遍历选择元素种类，然后O(n)判断其最后剩余的最大数目。比如枚举x，接下来需要面对的就是，如何计算x之间元素的剩余。对于n个元素，我们希望其剩余最少个数：n%2==1res = max(1, 最多元素个数*2-n)n%2==0res = max(0, 最多元素个数*2-n)稍加思考，我们可以用O(n^2^)的时间来预处理所有区间，使其之后可以O(1)查询区间的最小剩余元素个数。接着来验证这样朴素的贪心是否可行，有一组样例表示不可行：14 3 3 3 3 2 2 1 1 2 2 2 2 2 2上面这组样例的最优解，应该是将1~8的区间优化至最少个数，然后用右侧的2减去即可。以2分割来看区间的做法是不正确的。如果对于每个值都如此操作，其复杂度是O(n^2^)，一共n个值就是O(n^3^)，我们需要优化。朴素的想法也相对简单——能否n个值同时处理。于是构建出dp[x]=y表示1~x元素最后剩余a[x]的数目为y。之后的转移方程和答案相对细微繁琐，但是比较简单，可以看代码思考一下。ac核心代码头文件、宏定义、快读模板、常见变量、常见变量等略。 inline void solve() { cin>>n; vector<int> a(n+5); read(a, 1, n); vector<vector<int>> ck(n+5, vector<int>(n+5)); for (int l=1; l<=n; l++) { vector<int> cod(n+5); int top=0; for (int r=l; r<=n; r++) { top = max(top, ++cod[a[r]]); ck[l][r] = top; } } auto f = [&](int l, int r) -> int { // 查询区间[l,r]的最少剩余元素个数 if (l>r) return 0; int len = r-l+1; int res = ck[l][r]*2 - len; return max(res, (len%2 ? 1ll : 0ll)); }; vector<int> dp(n+5); // dp[x]=y表示1~x元素最后剩余a[x]的数目为y int ans=0; for (int i=1; i<=n; i++) { dp[i] = 1 - f(1, i-1); // 注意这里可以是负数 for (int j=1; j<i; j++) if (a[i]==a[j] && f(j+1, i-1)==0) // 转移方程 dp[i] = max(dp[i], dp[j]+1); ans = max(ans, dp[i] - f(i+1, n)); } cout<<ans<<endl; return; }Three Days Grace算法本质思维题目大意给定n个元素其范围是[1~m]，玩家可以进行任意次操作：选择元素x，将其分解为a b，需要保证a*b==x输出最小化的极致差。n <= 1e6 m <= 5e6思路推演一个朴素的想法是，人为规定最小值或者最大值，然后检查。观察规则，对于x分解成1 x肯定是不聪明的，所以可以知道每个数至多分解成log个数——考验玩家如何利用。比如玩家规定最小值，则需要计算所有数的情况。显然遍历的复杂度都达到了O(nm)，思考能否用dp重复利用。写到这发现，题解有一些错误（或者个人理解有误）ac核心代码头文件、宏定义、快读模板、常见变量、常见变量等略。 title算法本质题目大意思路推演ac核心代码头文件、宏定义、快读模板、常见变量、常见变量等略。 title算法本质题目大意思路推演ac核心代码头文件、宏定义、快读模板、常见变量、常见变量等略。 title算法本质题目大意思路推演ac核心代码头文件、宏定义、快读模板、常见变量、常见变量等略。 title算法本质题目大意思路推演ac核心代码头文件、宏定义、快读模板、常见变量、常见变量等略。 title算法本质题目大意思路推演ac核心代码头文件、宏定义、快读模板、常见变量、常见变量等略。

Codeforces Round 803 (Div. 2) PermutationForces II算法本质思维题目大意给定长度为n排列a[] b[]，其中b[]的部分元素丢失，使用-1代替。玩家将执行以下n个操作，希望将a[]修改成b[]的合法情况：对于第i次操作，选择a[]中两个元素的值x y，保证其 i ≤ x ≤ y ≤ i+k，然后交换其位置（特别注意，是值而非下标）输出可以抵达b[]合法的种类数。（不是方法数！）思路推演规则看似复杂，上手模拟即可发现，大部分情况第i回合我们必须将a[]中值为i的元素放在合法位置，不然以后将无法移动。那接着思考，如果这个值已经在合法位置，能否为其他事情做一些贡献。当然我们希望其最好不能，不然情况会变得更加复杂这里值的其他事件例如：4 2 1 2 3 5 4 1 5 3 2 4在上面这个样例中，当2希望走到合法位置时，其需要与5交换，同时元素1已经直接在合法位置了，能否为2做一些贡献。显然不可行，因为2无法走到合法位置，就是因为其距离太远，而1<2，距离会更远了。接着思考-1带来的影响。当x希望找到合法位置时，也许其会发现自己的合法位置是-1，而-1的位置并不唯一。由于我们之前的操作，可以知道1~x-1都已经合法了——观察那些站立于-1位置上的值，其一定>=x，只要在可行范围内，皆可随意索取。注意思考核心，操作仅与元素值有关、与元素位置无关。我们的操作具备十足的方向性，在这个方向性下，元素位置完全无关紧要（对于-1情况还是存在一定影响的）朴素的想，我们从小开始遍历值x，如果这个值在b[]中有具体的位置，则我们按照题目要求操作即可。否则，我们遍历b[]中的-1，若其同下标的a[]的值>=x && <=x+k值，说明其对x来说是可选的，x可以随机选择一个（随机选择不会影响结果），然后按照题目要求操作即可。这样就可以得到最终的结果了。优化 - 虚拟修改我们可以将上面的两种操作分类：常规操作x在b[]有具体的位置-1操作x在b[]中没有具体的位置其中常规操作来说，b[i]==-1的a[i]来说，常规操作只会使其的值增加。所以我们完全没必要真实地进行操作，在-1操作时，只需要检查b[i]==-1且a[i]<=x+k的值即可。同理，-1操作也并不需要实际操作，只需要记录之前进行的-1操作次数，即不可占领的点会对应的减少。ac核心代码头文件、宏定义、快读模板、常见变量、常见变量等略。 inline void solve() { cin>>n>>k; vector<int> a(n+5), b(n+5), posa(n+5), cod(n+5), v; read(a, 1, n); read(b, 1, n); for (int p=1; p<=n; p++) { if (b[p]==-1) v.push_back(a[p]); else posa[b[p]] = p; } sort(v.begin(), v.end()); int cnt=0; // cnt记录-1的占领次数 int ans=1; for (int val=1; val<=n; val++) { if (posa[val]) // 普通情况 { if (a[posa[val]] - val > k) // 距离不够 ans=0; } else { int w = upper_bound(v.begin(), v.end(), val+k) - v.begin() - cnt; // 这个二分可以预处理把log优化掉的 ans = ans*w%mod; cnt++; } } cout<<ans<<endl; return; }title算法本质题目大意思路推演ac核心代码头文件、宏定义、快读模板、常见变量、常见变量等略。 title算法本质题目大意思路推演ac核心代码头文件、宏定义、快读模板、常见变量、常见变量等略。 title算法本质题目大意思路推演ac核心代码头文件、宏定义、快读模板、常见变量、常见变量等略。 title算法本质题目大意思路推演ac核心代码头文件、宏定义、快读模板、常见变量、常见变量等略。 title算法本质题目大意思路推演ac核心代码头文件、宏定义、快读模板、常见变量、常见变量等略。 title算法本质题目大意思路推演ac核心代码头文件、宏定义、快读模板、常见变量、常见变量等略。