Codeforces Round 899 (Div. 2) Card Game算法本质思维题目大意给定长度n序列，玩家初始金额0元，可以进行若干次以下操作之一：删除奇下标元素，并加+对应元素的金额删除偶下标元素结束游戏输出最大化最终金额。思路推演先贪心的想，所有>0的元素我们都希望得到，能否实现。奇下标元素当然容易实现，只需要从后往前拿即可。偶下标稍微困难一些，其核心在于，若前面有被拿掉的元素，则一定可以实现。考虑首个>0的元素下标是偶下标，我们也可以尝试删除下标2的元素，来实现前面拿到元素这个条件。所以可以知道，下标>2的元素，可以任取。然后再考虑下标1和下标2的元素情况即可。Tree XOR算法本质思维题目大意给定一棵树，每个点有初始值a[i]，希望最终使得所有点的值相等。玩家可以进行以下操作：选择某个节点u和正整数x，其含自己的所有子节点都异或x，成本是子树（含自己）节点数 * x对于这棵树的根是[1 ~ n]的情况，分别计算其最小成本。思路推演首先拆位是肯定的，拆位之后可以把图看成黑白双色的图。因为题目的要求对所有点都当根节点的情况，这十分贴合换根dp的特性，所以优先考虑换根dp。然后其实这就是一个相对基础的换根dp做法，推一下递推公式即可。ac核心代码头文件、宏定义、快读模板、常见变量、常见变量等略。 vector<int> g[maxn]; int c[maxn], a[maxn]; int wast[maxn], num[maxn], wast2[maxn]; // 有方向情况：num[x]表示包括其本身的子节点数目，wast[x]表示将其子树都变成和自己同一颜色的操作节点数 // 无方向情况（或者所有方向情况）：wast2[x]其作为根节点，需要操作的节点数 void dfs(int u, int fr=0) { wast[u] = 0; num[u] = 1; for (int v:g[u]) { if (v==fr) continue; dfs(v, u); num[u] += num[v]; wast[u] += wast[v]; if (c[v] != c[u]) wast[u] += num[v]; } } void dfs2(int u, int fr=0) { wast2[u] = wast[u]; if (fr!=0) { int wfu = wast2[fr] - wast[u]; if (c[u]!=c[fr]) wfu -= num[u]; wast2[u] += wfu; if (c[u]!=c[fr]) wast2[u] += n-num[u]; } for (int v:g[u]) { if (v==fr) continue; dfs2(v, u); } } inline void solve() { cin>>n; for (int i=1; i<=n; i++) cin>>a[i]; m = n-1; while (m--) { int u, v; cin>>u>>v; g[u].push_back({v}); g[v].push_back({u}); } vector<int> ans(n+5); for (int val=1, t=0; t<20; val*=2, t++) { for (int i=1; i<=n; i++) { if (a[i] & val) c[i] = 1; else c[i] = 0; } dfs(1); dfs2(1); for (int i=1; i<=n; i++) ans[i] += wast2[i]*val; } for (int i=1; i<=n; i++) { cout<<ans[i]<<" \n"[i==n]; g[i].clear(); } return; }Two Permutations (Hard Version)算法本质思维题目大意给定长度分别是n和m的排列a[] b[]，现在玩家可以进行若干次操作：选择i ja[i]左右两侧的元素交换，同时其内部顺序不变b[j]左右两侧的元素交换，同时其内部顺序不变目的是最终使得a[]和b[]同时有序。（不可行输出-1）简单版本1e4次操作内完成困难版本最少操作次数完成n m <= 2500思路推演 - 简单版本首先思考简单版本，显然是需要一个必胜法。朴素的想法是，维护有序区间，然后依次增长，说白了就是先找1，然后找1 2，然后找1 2 3。模拟的时候就可以发现，因为中间仅有一个元素位置不变，例如已经有了1 2 3，现在希望加入4，则4要成为这个被操作的元素。我们希望当时的情况类似于：x x x 4 x x x 1 2 3，这样通过一次操作就可以凑成1 2 3 4了。想要使得1 2 3出现在末尾，其实也比较简单，x x 1 2 3 p x x，操作p元素即可。至此我们就得到了一个简单的必胜法，每次至多2次操作即可使得维护的有序区间+1。接下来要解决的问题是同时有序。稍加模拟可以发现，对同一元素重复操作2次数组不变，意味如果其操作数之差是偶数，则两者可行。模拟过程中可以发现，对于长度n的序列，一定存在操作n次后不变的情况。所以考虑一下奇偶同步的情况即可。这个结论可以说是模拟后猜的，结合简单版本的限制，困难版本会证明思路推演 - 困难版本到这一步，需要抽象成一个全新的模型才能求解最小操作——每次操作的核心。每次操作会移动n-1个元素，这太复杂了，能否看作移动操作元素。至此需要引入循环数组。对于1 2 3 4 5，如果对3操作，理论上应该是4 5 3 1 2，如果我们只考虑移动3，则可以视作移动至开头的循环数组3 1 2 4 5。但是显然，下次移动就并非移动至开头，而是移动至上次3存在的地方。我们引入一个虚拟的0，每次操作可以视作选择某个非0元素与0的位置交换。最后保证有序的循环数组即可。（未完）ac核心代码头文件、宏定义、快读模板、常见变量、常见变量等略。 title算法本质题目大意思路推演ac核心代码头文件、宏定义、快读模板、常见变量、常见变量等略。 title算法本质题目大意思路推演ac核心代码头文件、宏定义、快读模板、常见变量、常见变量等略。 title算法本质题目大意思路推演ac核心代码头文件、宏定义、快读模板、常见变量、常见变量等略。 title算法本质题目大意思路推演ac核心代码头文件、宏定义、快读模板、常见变量、常见变量等略。

Codeforces Round 897 (Div. 2) green_gold_dog, array and permutation算法本质思维题目大意给定长度n的数组a[]，现在需要构造长度n的排列p[]，存在数组c[i] = a[i]-p[i]，使得c[]中不同元素个数最大化。输出p[]信息。思路推演c[]并不要求顺序、p[]也可以完全自定义，发挥空间是很大的。先想一想是否可以达到n个不同值，然后发现通过对p[]元素大小的调配就可以做到。XOR Palindromes算法本质思维题目大意（抽象）给定01串s，定义数字x为美丽：存在某个方案，反转s中的x位（不能同一位反转）能使得s成为回文串输出一个长度n+1的01字符串t，枚举i从0至s.size()，若i是美丽的，则t[i]=1，反之为0。思路推演首先将s对称的来看——s[i]和s[n-i]视作一对（0下标）记录两者不同的对数为cnt。这部分是必须且只能操作1次的，剩余的对都可以操作0次或2次——除了当n为奇数时，存在一个数的对，其可以操作0次或1次。所以可以分类讨论：n是奇数最小操作数：cnt，最大操作数：n-cnt，其中间数都是可行的n是偶数最小操作数：cnt，最大操作数：n-cnt，其中间数，与cnt模2同值的数可行Salyg1n and the MEX Game算法本质思维题目大意Alice和Bob玩游戏，初始给定无重复数字、大小n的集合set，随后Alice先手两人轮流行动，但是各自的规则有所不同：Alice插入一个范围[0, 1e9]的数字，不可与集合数字重复Bob删除集合某个数字，保证严格小于Alice上次插入的数字注意，游戏当Bob无法操作或者Alice执行了其n+1回合时结束，这意味一定是Alice走后结束游戏，set最终大小是n+1。交互题，Alice由玩家扮演，输出每回合策略，尽量使得set的MEX值最大。思路推演既然的MEX值，则0的存在一定关键。最开始无0则Alice的最后一步一定是放0，可以接着思考一下1是否存在的情况，随即发现——若Alice一开始不补0，则最后值至多为1。所以补0一定是最优解最开始有0稍加模拟可以发现，因为是Alice走最后一步，所以无论Bob如何破坏，Alice都可以即使修补，所以只需要把最开始的数字用于提高MEX值即可，随后Bob如何行动Alice就跟随行动即可Cyclic Operations算法本质思维题目大意初始存在长度n的全0数组a[]，给定长度n的数组b[]，其元素大小范围[1~n]，接下来希望通过若干次以下操作使得a[]变为b[]：构造一个元素各不相同的长度k的数组c[]，元素大小范围[1~n]，使得a[c[i]] = c[i%k+1]（同时改变）输出是否可行。思路推演思考操作本质，其与i无关，更像构建一个循环数组，且a[]的元素可以覆盖的。这使我们想到，所有可行的b[]，其最后一次操作的元素都未被覆盖。通过观察其特征，发现其组成了一个简单k环——借助于此可以发现，操作的本质就是构建一个简单k环，只不过结果可以被覆盖，询问b[]是否可以被构建出来。通过模拟可以发现，除了长度k的环，其他长度的环都无法构建出来，但是任何链是可以构建的。考虑到题目特征，使用拓扑跑一下图，最后仅剩下简单环，再检查环的长度即可。Salyg1n and Array (hard version)算法本质思维题目大意已知偶数n k，存在长度n的元素未知数组a[]，玩家仅可执行操作：? p询问a[p ~ p+k-1]的异或和，随机a[p ~ p+k-1]的顺序会反转在至多57次询问后，输出a[1~n]的异或和。1 <= k <= n <= k^2 <= 2500思路推演当k是n的因数时，显然简单，考虑k非n公因数的情况，那核心就是异或结果的部分相消。从简单样例出发，比如3 2，同时可以看一下为什么要保证n k都是偶数。模拟时可以发现，我们仅能得到a1^a2 a2^a3 a1^a3，是无法得到a1^a2^a3。稍加思考可以发现，对于n=3而言，以元素个数的加法来看，最合理的构建方法是：3=2+1，这个2可以由一次操作得到，而1无法得到。随后思考6 4，合理的构建方式是：6=4+2，4也可以由一次操作得到，这个2如何得到呢。我们唯一的手段只有异或结果的部分相消，因为每个基本操作的异或元素个数都是k，所以相消存在对称性。先不考虑反转的情况，若存在a b c d e，则一次操作得到a^b^c^d，另一次操作得到b^c^d^e，两者异或得到a^e，这样就是2个元素了。接着考虑反转，惊喜发现a b c d e在类似上面操作后，其分布可以视作a e b c d，我们可以得到a^e的结果——这意味在得到2个元素的异或值的同时，我们将这两个元素边缘化了！假设目前n=2b、k=2a，且k < n < 2k 接下来严谨的求解： 对于2b的长度来说，一个比较好的方案是：2b = 2a + 2(b-a) 重点是处理这个2(b-a)，依照上面的思路，将整体的前b长度提取出来，顺序分成3个部分：b-a 2a-b b-a，这三个部分分别称之为A B C 1. 先基础操作得到A^B的值，因为A+B部分需要反转，反转后将这部分顺序分成2个部分：b-a 2a-b，分别称之为A' B' 2. 随后基础操作得到B'^C的值，总体上顺序可以视作A' C B'，因为其内部顺序在之后的操作中无关紧要 由于A^B = A'^B'，所以可以得到A'^C的值 其中A'和C的长度都是b-a，这样就将多余的2(b-a)放在边缘了，后面部分仅需分成k长度的部分即可对于上述n >= 2k的情况，同样类似操作即可。ac核心代码头文件、宏定义、快读模板、常见变量、常见变量等略。 void ask(int x) {cout<<"? "<<x<<endl;} void hui(int x) {cout<<"! "<<x<<endl;} inline void solve() { cin>>n>>k; int ci=n/k, yu=n%k; int ans=0; for (int i=1; i<ci; i++) // 前面保留 k+yu个元素 { int pos=i*k + yu + 1; ask(pos); ans ^= in(); } int res=0; ask(1); res ^= in(); if (yu>0) { int b=(k+yu)/2, a=k/2; ask(1+b-a); res ^= in(); ask(2*b-2*a+1); res ^= in(); } ans ^= res; hui(ans); return; }title算法本质题目大意思路推演ac核心代码头文件、宏定义、快读模板、常见变量、常见变量等略。 title算法本质题目大意思路推演ac核心代码头文件、宏定义、快读模板、常见变量、常见变量等略。

Codeforces Round 896 (Div. 2) Fill in the Matrix算法本质思维题目大意给定n*m的棋盘，每个格子需要放一个数字，满足：每行数字是一个0开始的长度m的排列存在集合set，每列数字的MEX值放入set。最大化set的MEX值。输出这个值，且输出棋盘信息。思路推演从后往前推到，先考虑某列的MEX值为0，既然顺序不重要，所以我们可以假定：第i列（0下标）的MEX值为i随后稍加模拟可以写出一种方式，以5*4为例子：4 0 1 2 3 3 4 0 1 2 2 3 4 0 1 1 2 3 4 0 1 2 3 4 0稍加修改后观察可知，仅有前m-1行做出了贡献，若行数>=m-1，其贡献为m——第一行做出了2贡献，其他行做出1贡献。同时样例告诉我们，当m=1时，第一行无法做出2贡献，特判一下即可ac核心代码头文件、宏定义、快读模板、常见变量、常见变量等略。 inline void solve() { cin>>n>>m; if (m==1) { n++; while (n--) cout<<0<<endl; return; } int ans = min(m, n+1); cout<<ans<<endl; for (int i=1; i<=n; i++) { int s = (i >=m ? 1 : m-i); for (int j=0; j<m; j++) cout<<(s+j)%m<<" \n"[j==m-1]; } return; }Candy Party (Easy Version)算法本质思维题目大意给定数组a[]，表示n个人初始手中的糖果，每个人需要执行一次操作：给另外一人2^x^个糖果这个过程能否同时满足下列条件：每个人都收到糖果，且恰好来自于一个人操作后每个人的糖果数目一致思路推演首先特判糖果能否均匀。既然一个人又要给出，又要收到糖果，其得到的糖果可以用2^x - 2^y来表示。通过二进制观察，可以保证差集合与{x, y}组成的集合一一对应。所以此题十分简单，只需要事先构造一个映射：差 --> (x, y)，然后对于每个人初始糖果值与最后值做差。假设平均值是10，初始值是6，可以看作市场上会增加一张4卡牌，减少一张8卡牌，最后检查所有卡牌数目是否为0即可。ac核心代码头文件、宏定义、快读模板、常见变量、常见变量等略。 inline void solve() { cin>>n; vector<int> v; for (int i=1; i<=n; i++) v.push_back(in()); vector<int> er(40); er[0] = 1; for (int i=1; i<=30; i++) er[i] = er[i-1]*2; map<int, pair<int, int>> mp; // 插值 --> (x,y) for (int i=0; i<=30; i++) for (int j=0; j<=30; j++) mp[er[j]-er[i]] = {i, j}; int sum=accumulate(v.begin(), v.end(), 0ll); if (sum%n) // 考虑能否平均 { cout<<"NO"<<endl; return; } int avg=sum/n; flag = 1; map<int, int> cod; // cod[x]=y：表示市场上值x的卡牌有y张 for (int x:v) { int cha=x-avg; if (cha==0) continue; // 差值为0可以视作自己打自己 if (mp.count(cha)==0) { flag = 0; break; } auto [a, b] = mp[cha]; cod[a]++, cod[b]--; // 市场上a多一张、b少一张 } for (auto [val, cnt] : cod) if (cnt!=0) flag=0; cout<<(flag ? "YES" : "NO")<<endl; return; }Candy Party (Hard Version)算法本质思维题目大意给定数组a[]，表示n个人初始手中的糖果，每个人需要执行0次或1次操作：给另外一人2^x^个糖果这个过程能否同时满足下列条件：每个人满足下列条件之一：收到糖果，且恰好来自于一个人没有收到糖果操作后每个人的糖果数目一致思路推演与Easy版本不同的点在于，其可以只给糖果、只收糖果。比如对于某人需要4个糖果才能达到平均值，在Easy版本中，一定是收到8个、给出4个，但是在Hard中还有另一种情况：只给出4个。通过模拟可以发现：（差值为负数转换一下意思）差值的不满足2^x - 2^y整体不可解情况A：差值为0仍然可以忽视情况B：差值仅满足2^x - 2^y需要收到2^x，给出2^y情况C：差值满足2^x有两种可能：收到2^(x+1)，给出2^x收到2^x我们仍然以市场角度去记录，AB情况方案是固定的，先处理。现在对于C，力求通过转换方案使得市场整体为0——这是一种典型的思维题，通常用贪心或者dp搞定。给出2^x市场上x卡牌数目+1收到2^x市场上x卡牌数目-1现在市场有一个初始情况，只需要从最低为开始，力求满足即可。（贪心思路）ac核心代码头文件、宏定义、快读模板、常见变量、常见变量等略。 inline void solve() { cin>>n; vector<int> v; for (int i=1; i<=n; i++) v.push_back(in()); vector<int> er(40); er[0] = 1; for (int i=1; i<=30; i++) er[i] = er[i-1]*2; map<int, pair<int, int>> mp; // 插值 --> (x,y) set<int> st; for (int i=0; i<=30; i++) for (int j=0; j<=30; j++) mp[er[i]-er[j]] = {i, j}; // +i,-j for (int i=0; i<=30; i++) st.insert(er[i]), st.insert(-er[i]); // st记录一下2的指数，用于判断 int sum=accumulate(v.begin(), v.end(), 0ll); if (sum%n) { cout<<"NO"<<endl; return; } int avg=sum/n; flag = 1; map<int, int> cod; // cod[x]表示市面上x值的剩余数目 map<int, int> mp2; // {巧合差值， 数目} 巧合差值是指恰好为2的指数的差值 for (int x:v) { int cha=x-avg; if (cha==0) continue; // 差值为0忽略 if (st.count(cha)) // 相差恰好是2的指数情况，先保存，之后处理 { mp2[cha]++; continue; } if (mp.count(cha)==0) // 如果没有对应的操作，说明无解 { flag = 0; break; } auto [a, b] = mp[cha]; cod[a]++, cod[b]--; // 市场上的a卡-1，b卡+1 } set<int> alive; for (auto [val, cnt] : mp2) // 待会需要按巧合差值的绝对值升序遍历 alive.insert(abs(val)); for (int cha:alive) // 遍历巧合差值 { int p; for (int i=0, val=1; i<=30; i++, val*=2) // 检查巧合差值是多少 { p = i; if (val==cha) break; } if (cod[p] > mp2[cha]+mp2[-cha]) // 正巧合差值 + 负巧合差值 能使其为0的极限 { flag = 0; break; } cod[p] += mp2[cha] - mp2[-cha]; if (cod[p]%2!=0) // 比较巧地规避了复杂的公式计算 { flag=0; break; } cod[p+1] += cod[p]/2; cod[p] = 0; } cod[0] = 0; for (auto [val, cnt] : cod) if (cnt!=0) flag=0; cout<<(flag ? "YES" : "NO")<<endl; return; }Travel Plan算法本质组合数思维、一点组合数学题目大意给定top个点的无向图，满足下列条件的点对存在边：i点和2i点i点和2i+1点每个点的点值为[1~m]，定义一条路径的成本：经过点值的最大值输出遍历所有点值的情况，每种情况下的图计算所有路径的成本和的和。（包含单点自己到自己的情况）t <= 200 top <= 1e18（单个样例） m <= 1e5（所有样例之和）思路推演一个朴素的思路是，找出所有价值为x的路径的数目，然后相加求和即可。先将图画出来，是一个很标准的二叉树图（只是点特别多），两点的路径唯一。可以发现每层的点至多存在3种不同的状态，对于某个点，我们可以枚举其左侧延申数目、右侧延申数目，复杂度是log级别平方，大概是60*60，加上枚举层的循环、整体的样例数：200 * 60^3 ≈ 5e7是可行的。ac核心代码下列代码的整体思路是，先计算完整三角形的二叉图，然后再计算不规则部分，但是实际这样比较麻烦，这个题解的思路是上方的方法：每层算3个状态：Codeforces Round 896 (Div. 1) 1A - 1C - cup头文件、宏定义、快读模板、常见变量、常见变量等略。 int q(int x) {return (x%mod + mod)%mod;} inline void solve() { vector<int> er(70); // 未取模 er[0] = 1; for (int i=1; i<=60; i++) er[i]=er[i-1]*2; int top; cin>>top>>m; for (int i=0; i<=60; i++) { if (top >= er[i]-1) n = i; } n--; // 0~n层构成了完美倒三角 // debug(n) vector<int> cnt(130); // cnt[x]=y表示有x个点的链数目是y（总的图） // 现在先计算最上方的n层，覆盖了2^n-1个数 for (int i=n; i>=0; i--) { vector<int> now(130); // 当前层的点，now[x]=y有x个点的链数是y int ju = n-i; // 当前层与底层的距离 // l表示当前层的点，左侧向下层延申的距离，注意l=0或1时方案都是1 for (int l=0; l<=ju; l++) { for (int r=0; r<=ju; r++) { int wayl = (l>0 ? er[l-1]%mod : 1); int wayr = (r>0 ? er[r-1]%mod : 1); now[l+r+1] = q(now[l+r+1] + wayl*wayr%mod); } } // 将其加入总图 for (int j=1; j<=120; j++) cnt[j] = q(cnt[j] + now[j]*q(er[i])); // er[i]表示第i层的点数 } // 接下里计算第n+1层 int num = top - (er[n+1]-1); // 第n+1层还有num个数 if (num > 0) { vector<int> now(130); // 当前层的点，now[x]=y有x个点的链数是y // 首先考虑，链两侧都是n+1层的情况 now[1] = 1; for (int len=1, ju=3; len<num; len*=2, ju+=2) // 现在是以len个点为一个整体，和旁边的整体互动 { // ju表示两个组的点形成链的长度（点长度） int zu=(num + len-1) / len; // 一共有zu个整体 int res=0; if (zu%2==0) // 如果恰好能一一对应分配 { int last = num - (zu-1)*len; // 最后一个组的长度 // res += (zu/2-1)*len*len; // 其中前zu-2个组都是一定是完整的 res += (zu/2-1)%mod*q(len)%mod*q(len)%mod; res = q(res); // res += len*last; // 最后一个组的长度 res += q(len)*q(last)%mod; res = q(res); } else // res += zu/2*len*len; // 正好抛弃最后一个组 res += q(zu/2)*q(len)%mod*q(len)%mod, res = q(res); cnt[ju] = q(cnt[ju] + res); } // 然后考虑，链只有一侧是n+1层的情况 for (int i=n; i>=0; i--) // n+1层先走到i层，再往下走 { int ju1 = n+1-i+1; // 先走的距离，包含第i层的点 for (int j=i; j<=n; j++) { int ju2=j-i; int ways=1; // 从第i层走到第j层的方案数（不能走左边） if (ju2>=1) ways=er[ju2-1]%mod; now[ju1+ju2] = q(now[ju1+ju2] + ways); } } for (int j=1; j<=120; j++) cnt[j] = q(cnt[j] + q(now[j]*q(num))); } // 至此，我们已经拿到了图所有长度链的数目 int ans=0; for (int len=1; len<=119; len++) { if (cnt[len]==0) continue; for (int val=m; val>=1; val--) { // num：一条长度为len、价值为val的链本身的方案数 // cnt[len]：有cnt[len]条长度len、价值val的链本身的方案数 // num2：在这个图中，当放置了一条长度len、价值val的链后，其他top-len个点可以随机选择的方案数 int num = q(qpow(val, len, mod) - qpow(val-1, len, mod)); int num2 = qpow(m, top-len, mod); ans = q(ans + val * cnt[len] % mod * num % mod * num2 % mod); } } cout<<ans<<endl; return; }title算法本质题目大意思路推演ac核心代码头文件、宏定义、快读模板、常见变量、常见变量等略。 title算法本质题目大意思路推演ac核心代码头文件、宏定义、快读模板、常见变量、常见变量等略。 title算法本质题目大意思路推演ac核心代码头文件、宏定义、快读模板、常见变量、常见变量等略。

Codeforces Round 892 (Div. 2) United We Stand算法本质思维题目大意给定n个元素，要求放入B C两个集合中，满足：任意C集合元素非任意B集合元素的约数两个集合非空输出方案或者不可能。思路推演稍加模拟可知，若元素更大，则比不可能是约数，所以将最大的元素放入C集合即可（可能有多个最大的），全相等的情况则不可行。Olya and Game with Arrays算法本质思维题目大意给定n个大小>=2的集合，每个集合至多进行一次操作：将本集合的某个元素移动至另一集合输出最大化后所有集合的最小值之和。思路推演稍加模拟可以发现，集合只能移除一个元素，所以他的最小值有3个可能：自己最小的元素自己第二小的元素（把自己最小的元素移出去了）别人移动进来的更小元素当然，上面3个选择中，自己第二小的元素肯定是相对的最大值，所以尽可能使得所有集合都能选择这个方案，但是总要有集合来承载最小元素，则选一个集合即可，挨个模拟一次即可。Another Permutation Problem算法本质思维题目大意玩家需要给出长度n排列，输出最大化后的：$\sum_{i=1}^np_i*i - (\max_{j=1}^np_j*j)$思路推演稍加模拟，整个式子会发现比较缺乏贪心思路，即所谓的情况比较复杂，通常的解决方法有2种：dp可以将问题化成小而重复的问题解决假设已知某个信息（通常配合二分）可以用复杂度换取多一个信息当然这个题肯定只能二分，我们假设最大值为m，则可以看成这样：有两个1~n元素的集合元素，答案为其两两相乘之和-m，同时需要保证两两相乘<=m（这需要枚举n^2^个值）然后只需要贪心从大到小，找合适的数就好了：比如对于n找到一个x，使得nx<=m，然后再去找n-1的，这是显然贪心思维可以验证正确的通常来说，朴素的做可以用二分搞定，但是这样就O(n^3^logn)，复杂度堪忧，实际上是可以优化的：每对数组合，我们仅通过更大的数来找更小的数，对于值x，其可选范围是[1~m/x]。 根据贪心思路，我们必须不断从n往下看。 举例1~10，m=28 首先可以贪心的选择10--2和9--3 对于8来说，其范围是[1~3]，所以只能选择1了：8--1和7--4 当然到最后5 6是必须有一个>m的数的，所以可以说这样是无解的，但是思路是清晰的，以m/n为起始，后面选择的元素要么相邻在左或右，可以用指针或者堆来稍加维护。总体复杂度O(n^3^)。整体思考其实个人感觉，这个题的难度有点大了，即使赛时想到这个方向也感觉不是C的难度。当然过这么多，是因为打表打出来的，其形式如同：1 2 ... x-1 x n n-1 ... x+1。title算法本质题目大意思路推演ac核心代码头文件、宏定义、快读模板、常见变量、常见变量等略。 Maximum Monogonosity算法本质思维、dp题目大意给定数组a[] b[]和k，现在要求选择若干不相交的区间，要求：区间长度之和为k[l, r]区间价值为| b[l]-a[r] | + | b[r]-a[l] | 。输出最大化价值和。n k <= 3e3思路推演所谓情况复杂，基本需要使用dp。构建一个朴素的dp[l][r][x]表示区间l~r中选择了长度总和为x最大值。显然这个dp的空间复杂度、时间复杂度都是O(n^3^)，需要优化。首先优化空间复杂度——dp[i][x]表示区间1~i中选择了长度总和为x`最大值。什么情况需要用[l][r]来表示l~r区间，什么情况可以优化至[i]来表示1~i区间。目前还没有实力能够总结，但是有一条可以实践的：若能用[i]来表示，且无故障的，就可以用[i]谨记我们的目标：优化转移复杂度，写出转移方程：$dp[i][j] = \max_{t=1}^{i}val[i-t+1][i] + dp[i-t][j-t]$ （最后的i必选）$dp[i][j] = max_{t=1}^{i-1}dp[t][j]$ （最后的i不选，这个方程转移比较简单）这个式子无法优化，将上式的val[][]继续拆解：$dp[i][j] = \max_{t=1}^{i}dp[i-t][j-t] + \max \begin{Bmatrix}+b[i]-a[i-t+1]+b[i-t+1]-a[i] \\+b[i]-a[i-t+1]-b[i-t+1]+a[i] \\-b[i]+a[i-t+1]+b[i-t+1]-a[i] \\-b[i]+a[i-t+1]-b[i-t+1]+a[i]\end{Bmatrix}$$dp[i][j] = max_{t=1}^{i-1}dp[t][j]$上式第二个方程转移很简单，重点看第一个，抛开上式的a[i] b[i]，其他下标有着统一性，对于dp[i][i-x]来说，其希望有如下的预处理$\max_{t=x}^{i-1} \{dp[t][t-x] - a[t+1] + b[t+1]\}$这个式子维护需要用x作为标识对上式添加b[i]-a[i]，这样就O(1)得到了转移方程第一个式子的最大值，我们同法炮制，得到了转移方程4个式子的最大值，再取max即可。ac核心代码细节说明：pre[]数组默认值为-1e18是因为其可能为负数，dp则不可能为负数，所以直接给0即可4个pre[]数组维护的都是i元素必选的情况，记得写上i元素不选的情况j==0的预处理头文件、宏定义、快读模板、常见变量、常见变量等略。 inline void solve() { cin>>n>>k; vector<int> a(n+5), b(n+5), pre1(n+5, -1e18), pre2(n+5, -1e18), pre3(n+5, -1e18), pre4(n+5, -1e18); vector<vector<int>> dp(n+5, vector<int>(k+5, 0)); rep(i,1,n) cin>>a[i]; rep(i,1,n) cin>>b[i]; for (int i=0; i<=n; i++) { for (int j=0; j<=min(i, k); j++) { if (i>j) dp[i][j] = dp[i-1][j]; // 考虑第i个元素不选情况 int cha = i-j; int v1 = pre1[cha] + b[i] - a[i]; int v2 = pre2[cha] + b[i] + a[i]; int v3 = pre3[cha] - b[i] - a[i]; int v4 = pre4[cha] - b[i] + a[i]; int val = max(max(v1, v2), max(v3, v4)); // 第i个元素必选情况的最大值 dp[i][j] = max(dp[i][j], val); if (j==0) dp[i][j]=0; // 如果j==0，pre[]其实并未初始化，得到的值并不正确，所以手动处理为0 pre1[cha] = max(pre1[cha], dp[i][j]-a[i+1]+b[i+1]); pre2[cha] = max(pre2[cha], dp[i][j]-a[i+1]-b[i+1]); pre3[cha] = max(pre3[cha], dp[i][j]+a[i+1]+b[i+1]); pre4[cha] = max(pre4[cha], dp[i][j]+a[i+1]-b[i+1]); } } int ans = dp[n][k]; cout<<ans<<endl; return; }title算法本质题目大意思路推演ac核心代码头文件、宏定义、快读模板、常见变量、常见变量等略。 title算法本质题目大意思路推演ac核心代码头文件、宏定义、快读模板、常见变量、常见变量等略。

Codeforces Round 890 (Div. 2) D.More Wrong算法本质思维题目大意存在一个固定的未知长度n排序p[]，现在有5n*n硬币，可以进行操作：选择l r，花费(r-l)^2硬币，获得p[l~r]的逆序对通过交互，最后输出p[]最大值的下标。思路推演这类交互题的核心在于，如何用相对固定、巧妙的方式，去获得信息。现在需要求得最大值的下标，一种常见的贪心做法是，将数组二分划治，来减少花费，接下来需要验证思路是否可行。对于2个相邻的值而言，仅需判断他们之间的逆序对即可判断谁大谁小。但若对于2个不相邻的元素，如何判断。如果思考无果，可以从硬币数重新思考，若要判断两者的大小，至少需要两者距离平方的硬币。考虑最大情况，近似2的等比公式求和，答案需要2n^2^的硬币，所以这里大致允许2次逆序对，再额外来点常数。稍加模拟即可判断出，使用[l, r-1]和[l, r]的询问，可以求得p[l~r-1]中大于p[r]的个数，即可判断p[l]和p[r]孰大。ac核心代码头文件、宏定义、快读模板、常见变量、常见变量等略。 int ask(int l, int r) { if (l==r) return 0; cout<<"? "<<l<<" "<<r<<endl; return in(); } int dfs(int l, int r) { if (l==r) return l; int mid = (l+r)/2; int p1=dfs(l, mid), p2=dfs(mid+1, r); int x1 = ask(p1, p2); int x2 = ask(p1, p2-1); return x1-x2>0 ? p1 : p2; } inline void solve() { cin>>n; int p = dfs(1, n); cout<<"! "<<p<<endl; return; }E1.PermuTree (easy version)算法本质思维题目大意给定一棵树，每个点的权值由玩家决定，需要满足：点权的集合是一个排列对于一对点，若其满足：其两点的lca点值，处于两点值中间（不准相等）则贡献+1。输出最大化的贡献值。思路推演显然我们应该以每个顶点为lca进行思考，这时面对的一个问题就是：能否控制顶点下的所有其他点，任意调配其值大于或小于顶点，且不干扰之前点为lca点的判断。简单模拟和推理后发现可行，则整个题就变成了贪心地对待每个lca点，其可以转移题意为：所有除了根节点的节点都涂上黑色或者白色，任意一对点不在同一子树，则可以视为贡献+1，计算最大贡献值。但是现在面临若干个子树（可以视作n/2个），每个子树有若干种选择（可以视作n/2种），而合起来则有许多种情况，显然无法计算，还需要一些贪心的思路优化复杂度。一个朴素的想法是，是否一个子树中全黑或者全白为最优解。证： 设某条子树有n个点，其中x个点涂白，n-x点涂黑。 设其他子树有a个白点、b个黑点。 则当前子树的贡献化简后是（这里未除常数2）：a*n + (b-a)*x x范围[0, n] 其中n固定，a b会随着外界的情况变化，但是可见x=0或者x=n是最优解之一。现在得证其为全黑或全白，看似有2^n^次方种选择，但是实际上其特征可以合并，可以视作背包问题，由于其棋子数目的限制，可以在O(n)的时间复杂度下求得整体可以取多少黑子和白子，而目前黑子和白子不可能同属于一个子树，就可以整体相乘了——背包求得后，遍历算出最大贡献即可。ac核心代码头文件、宏定义、快读模板、常见变量、常见变量等略。 int fu[maxn], cnt[maxn]; // 记录父节点 vector<int> g[maxn]; int ans; void dfs(int u=1) { cnt[u] = 1; // 包括当前节点的节点数 vector<int> son; // 记录各个儿子节点的数目 for (int v:g[u]) { dfs(v); cnt[u] += cnt[v]; son.push_back(cnt[v]); } vector<int> dp(cnt[u]); // 建立背包dp dp[0] = 1; // 全涂 for (int x:son) { for (int i=cnt[u]-1; i>=x; i--) dp[i] |= dp[i-x]; } int num=0; for (int i=0; i<=cnt[u]-1; i++) { if (dp[i] && i*(cnt[u]-1-i) > num*(cnt[u]-1-num)) num = i; } ans += num * (cnt[u]-1-num); } inline void solve() { cin>>n; ans=0; for (int i=2; i<=n; i++) { cin>>fu[i]; g[fu[i]].push_back(i); } dfs(); cout<<ans<<endl; return; }title算法本质题目大意思路推演ac核心代码头文件、宏定义、快读模板、常见变量、常见变量等略。 title算法本质题目大意思路推演ac核心代码头文件、宏定义、快读模板、常见变量、常见变量等略。 title算法本质题目大意思路推演ac核心代码头文件、宏定义、快读模板、常见变量、常见变量等略。 title算法本质题目大意思路推演ac核心代码头文件、宏定义、快读模板、常见变量、常见变量等略。 title算法本质题目大意思路推演ac核心代码头文件、宏定义、快读模板、常见变量、常见变量等略。