Codeforces Round 922 (Div. 2) Blocking Elements算法本质思维、二分、dp题目大意（改）给定长度n数组a[]，玩家可以选择任意个元素涂成黑色：res1值为将所有黑色元素值之和2个相近黑色元素之间的元素（不含黑色元素）为一组，剩余的若干组，其中元素和最大值计为res2值输出最小化的max(res1, res2)值。n <= 1e5思路推演通常来说，这样的“最小化最大值”和“最大化最小值”的题目，我们可以首先尝试一下二分思路，其可以在增加log复杂度情况下多提供一个条件。当我们获取到当前回合的上限值时，有2个目标：每组元素和 < 上限值选择元素和 < 上限值用贪心的思路去想的话，会发现情景十分复杂，很难获取最优解。所以转变思路使用dp去处理。dp条件十分明显，dp[x]=y可以表示对于1~x来说，x必涂黑的情况下已经涂黑元素和值为y。因为有2个目标，所以肯定是需要维护一个、力求保证另一个，这里我们选择维护每组元素和，最后检查选择元素和。可以使用优先队列来解决，代码相对简洁，不懂可以看一下代码。ac核心代码头文件、宏定义、快读模板、常见变量、常见变量等略。 int a[maxn], dp[maxn], pre[maxn]; inline void solve() { cin>>n; for (int i=1; i<=n; i++) cin>>a[i], pre[i]=pre[i-1]+a[i]; a[n+1] = 0; // 为了方便就直接使用dp[n+1]，其需要保证a[n+1]为0 int l=1, r=1e13; int ans=r; while (l<=r) { int mid=(l+r)/2; priority_queue<pair<int,int>, vector<pair<int,int>>, greater<pair<int,int>>> q; q.push({0, 0}); // {val, idx} for (int i=1; i<=n+1; i++) { while (q.size() && pre[i-1] - pre[q.top().second] > mid) // 保证中间 q.pop(); dp[i] = a[i] + q.top().first; q.push({dp[i], i}); } if (dp[n+1]<=mid) { r=mid-1; ans=mid; } else l=mid+1; } cout<<ans<<endl; return; }title算法本质题目大意思路推演ac核心代码头文件、宏定义、快读模板、常见变量、常见变量等略。 title算法本质题目大意思路推演ac核心代码头文件、宏定义、快读模板、常见变量、常见变量等略。 title算法本质题目大意思路推演ac核心代码头文件、宏定义、快读模板、常见变量、常见变量等略。 title算法本质题目大意思路推演ac核心代码头文件、宏定义、快读模板、常见变量、常见变量等略。 title算法本质题目大意思路推演ac核心代码头文件、宏定义、快读模板、常见变量、常见变量等略。 title算法本质题目大意思路推演ac核心代码头文件、宏定义、快读模板、常见变量、常见变量等略。

Codeforces Round 921 (Div. 2) Good Trip算法本质思维、概论题目大意有n个孩子，其中有m对朋友，每对朋友有一个初始的友情值。初始分数为0，接下来会进行k轮游戏，每轮游戏会随机选择2个孩子，如果这2个孩子是朋友：这对朋友的友情值+1获得这对朋友友情值的分数如果不是朋友，则无事发生输出最后分数的期望值。（mod 1e9+7）n,m <= 1e5 k <= 2e5思路推演分数的增加首先需要发生在朋友上，所以我们可以将$\frac{n*(n-1)}{2}$种情况为了m种朋友情况和其他。我们将分数的获取分成两类，初始值友情分数和后续增加的友情分数，即这2个子问题：如果规则中，友情值不会改变如果规则中，友情值都默认为0第一个问题易于解决，简单的平均值可以搞定。对于第二个问题，这是一个比较经典情景，我们以单对朋友的视角来看，如果抽中他们x次，则收益是$\frac{x*(x-1)}{2}$，每次抽中的概论$p=\frac{2}{n(n-1)}$，一共抽k轮，则期望收益就是：$\sum_{i=0}^k\C_k^ip^i(1-p)^{k-i}\frac{i*(i-1)}{2}$这是单对朋友的期望收益，我们乘以m就可以得到所有朋友的增加友情分数的期望收益了。思路推演 - 进阶实际上这道题仍然有发挥空间：$\sum_{i=0}^k\C_k^ip^i(1-p)^{k-i}\frac{i*(i-1)}{2} * 2= \sum_{i=0}^k\C_k^ip^i(1-p)^{k-i}i^2 - \sum_{i=0}^k\C_k^ip^i(1-p)^{k-i}i$$\sum_{i=0}^k\C_k^ip^i(1-p)^{k-i}i$是二项式分布的期望$E(x)$，我们可以使用kp来O(1)计算。$\sum_{i=0}^k\C_k^ip^i(1-p)^{k-i}i^2$也可以看作是其的一种简单变形$E(x^2)$，根据概率论中的知识，使用$E(x^2) = D(x)+E(x)^2 = kp(1-p)+k^2p^2$来O(1)计算。所以实际上可以做到O(t)的复杂度（因为有多组数据），虽然在这道题上没有意义。ac核心代码头文件、宏定义、快读模板、常见变量、常见变量等略。 title算法本质题目大意思路推演ac核心代码头文件、宏定义、快读模板、常见变量、常见变量等略。 title算法本质题目大意思路推演ac核心代码头文件、宏定义、快读模板、常见变量、常见变量等略。 title算法本质题目大意思路推演ac核心代码头文件、宏定义、快读模板、常见变量、常见变量等略。 title算法本质题目大意思路推演ac核心代码头文件、宏定义、快读模板、常见变量、常见变量等略。 title算法本质题目大意思路推演ac核心代码头文件、宏定义、快读模板、常见变量、常见变量等略。

Codeforces Round 912 (Div. 2) Maximum And Queries (hard version)算法本质思维、dp题目大意给定长度n的数组a[]，接下来有q轮询问（询问之间独立），每次会给出k，玩家可以至多进行k次操作：选择数组a[]某个元素使其值+1输出最大化a[]所有值的按位AND值。a[] n q <= 1e6 k <= 1e18思路推演这个题十分有意思，让我们先来发散一下思维：每次操作需要在根号级别的复杂度下输出答案，所以肯定需要离线做或者预处理AND方式的求和，让我们按位思考，且具备贪心属性（如果可以选择更大的二进制位，则选择更大的）随便拿些样例模拟一下，发现一个特征，就是如果有二进制（左侧为高位）：10010、101、1，如果答案能选择的最高位暂时是二进制第三位，即100，则观察第一个和第三个数，其在二进制第三位上都是0，贪心地想，我们可以理解为其选择后的值变成了0。顺着这个思路想，如果我们已知ans的值和某个元素的值a[i]，是可以计算出a[i]需要的最少操作数的：找到二进制下的最高位，满足：a[i]这一位是0，ans这一位是1，假设这是二进制的第x位（注意这里的x是1下标开始的）如果不存在，花费即是0如果存在x，设变量$mask = 2^x-1$花费是：$cost_i = (ans \& mask) - (a_i \& mask)$这是一种逆向的思维，因为已知k和a[]来直接求ans比较困难。一个比较顺畅的想法是，预处理出所有的ans即可。注意观察a[]的值，其在1e6以内，但是k很大。如果$k + \sum_{i=1}^n a_i \ge n * 2^{20}$，那就可以说明所有的a[]值都是会被利用到的，可以使用$\left \lfloor \frac{k + \sum_{i=1}^n a_i}{n} \right \rfloor $来求解。反之，则最终答案一定小于2^20^，我们仅需处理2^20^以内的所有ans值即可，接下来构建dp。ac核心代码头文件、宏定义、快读模板、常见变量、常见变量等略。 title算法本质题目大意思路推演ac核心代码头文件、宏定义、快读模板、常见变量、常见变量等略。 title算法本质题目大意思路推演ac核心代码头文件、宏定义、快读模板、常见变量、常见变量等略。 title算法本质题目大意思路推演ac核心代码头文件、宏定义、快读模板、常见变量、常见变量等略。 title算法本质题目大意思路推演ac核心代码头文件、宏定义、快读模板、常见变量、常见变量等略。 title算法本质题目大意思路推演ac核心代码头文件、宏定义、快读模板、常见变量、常见变量等略。 title算法本质题目大意思路推演ac核心代码头文件、宏定义、快读模板、常见变量、常见变量等略。

Educational Codeforces Round 157 (Rated for Div. 2) Torn Lucky Ticket算法本质思维角度题目大意有若干由数字组成的短字符串（长度<=5），现在选择2个字符串（可以重复选择一个字符串），将其拼接得到字符串s，定义幸运s：注意不同的拼接方式算两种，但是重复选择一个字符串拼接方式只能算一种s.length()为偶数s前半部分的数字和等于后半部分数字和计算有多少种拼接方式可以组成幸运字符串。思路推演显然，我们看对于某个字符串s来说，我们希望在其身上提取出一些特征来进行匹配。如果对于字符串123，这些字符串可以和它匹配：右侧匹配：长度1、数字和为0长度3、数字和为6左侧匹配：长度1、数字和为4长度3、数字和为6但显然，我们可以写一个长度5的字符串来与其匹配。这里就发现了规律，对于幸运字符串来说，用长的字符串去找短的字符串是一个优解。我们构建一个映射(字符串长度, 字符串数字之和) --> 个数。然后匹配即可，注意同样长度需要特殊一点，别计算重复了。XOR Construction算法本质思维题目大意给定数字n，还有长度n-1的数组a[]，我们需要构建一个长度n的排列p[]（排列值为0~n-1），需要满足：p[i-1]^p[i] == a[i]题目保证有解。思路推演稍加模拟可以发现，每改变一个元素的值，所有元素的值都会被影响。我们可以先随意让p[1]=0，然后通过a[]求得p[]。p[]的所有元素异或某个值来满足答案。实际这个题是看题解才想到的，后面的思路是题解的既然可以改变二进制位，我们也从二进制位上观察最后的p[]，其每个二进制位上的01个数是一定的。所以我们只需要检查二进制位，如果不满足就异或这一位。题目保证有解还剩下一个问题，如果这个二进制位的01数目一致，则我们如何判断是否该改。稍加模拟或者思考，即可发现改不改不影响最后的答案。ac核心代码头文件、宏定义、快读模板、常见变量、常见变量等略。 inline void solve() { cin>>n; vector<int> v(n); for (int i=1; i<n; i++) // 给v[0]=0 { int x=in(); v[i] = x^v[i-1]; } for (int i=0, val=1; i<=30; i++, val*=2) { int cnt=0; for (int j=0; j<n; j++) cnt += (val & j) > 0; for (int j=0; j<n; j++) cnt -= (val & v[j]) > 0; if (cnt!=0) // 数目不对 { for (int j=0; j<n; j++) v[j] ^= val; } } for (int x:v) cout<<x<<" "; return; }Infinite Card Game算法本质思维题目大意A有n张卡、B有m张卡，每张卡有2个属性：攻击值和防御值。接下来有2个设定：桌面上至多存在一张卡x，如果希望使用另一张卡y击退它，必须y的攻击值严格大于x的防御值如果卡y击退了卡x，则卡x会退回给它的主人，卡y会留在桌上初始时，A会随机选择一张卡放在桌上，然后BA轮流行动，如果谁无法击退敌人的卡则算失败。现在计算A胜利、平局、失败的概论，为了方便输出将其乘以n。思路推演勇气，即是信念游戏有卡牌回收机制，这表明了每次战斗不需要留手，应该选出自己最强的卡牌：能够击败敌人的卡牌，且防御值最高（当攻击值超过敌人的防御时，攻击值就没有了意义。）我们先思考A可以胜利的情况，需要掏出防御力最强的卡牌，且对手无计可施。我们可以给这张卡牌涂上金色表示其掏出必胜。如果掏出任意一张卡牌，在对手给予回击后，我们可以掏出一张金色的卡牌，则当前卡牌为金色。这显然是图的传播方式，同时由于存在贪心思路，我们可以预处理我们每一张卡牌使用之后，对手的策略，然后检查我们是否可以使用金色卡牌。在脑海中模拟这个预处理的时候有所察觉，也许代码不需要写这么复杂。为了使得预处理，我们需要将A的卡牌防御值升序，B的卡牌攻击值升序，这有一个小结论：A的金色卡牌一定是一个后缀区间（使用防御值升序时）证：A的金色卡牌一定是一个后缀区间（使用防御值升序时） 反证法，假设存在金色卡牌不是一个后缀区间，则一定存在两张牌a b，其中a是金色卡牌，b非金色卡牌，且防御值：b>=a B用某张卡牌击退b时，A可以采取面对“B用某张卡牌击退a时”的相同策略。鉴于此，我们可以双指针搞一下即可。随后为了方便，来计算A失败的卡牌数目，则一定是B有一张强力的防御卡牌。于是我们可以同样方式求得B的金色卡牌，如果A的第一轮出的牌，B可以使用金色卡牌应对（取最大攻击值即可），则A注定失败。ac核心代码头文件、宏定义、快读模板、常见变量、常见变量等略。 // 防御优先 bool cmp(pair<int,int> p1, pair<int, int> p2) { if (p1.second == p2.second) return p1.first < p2.first; return p1.second < p2.second; } inline void solve() { vector<pair<int,int>> v1, v2; cin>>n; v1.resize(n); for (int i=0; i<n; i++) cin>>v1[i].first; for (int i=0; i<n; i++) cin>>v1[i].second; cin>>m; v2.resize(m); for (int i=0; i<m; i++) cin>>v2[i].first; for (int i=0; i<m; i++) cin>>v2[i].second; sort(v1.begin(), v1.end(), cmp); // v1防御优先 sort(v2.begin(), v2.end()); // v2攻击优先 int hackmax = 0; // 表示目前已经确定的金色卡牌的最大攻击值 int defenmax = -1; // 对手面临当前情况会出的牌，其中的最大防御值 // 初始的-1值是为了让初始的hack > defen int p2 = v2.size()-1; int p1; for (p1=v1.size()-1; p1>=0; p1--) { while (p2>=0 && v2[p2].first>v1[p1].second) // p2这张牌可以击败p1 defenmax = max(defenmax, v2[p2].second), p2--; if (hackmax <= defenmax) // 如果打不过对面 break; hackmax = max(hackmax, v1[p1].first); } // [p1+1 ~ v1.size()-1] 为金色卡牌 int num_win = n - (p1+1); // 必胜的次数 sort(v1.begin(), v1.end()); sort(v2.begin(), v2.end(), cmp); hackmax = 0; defenmax = -1; p1 = v1.size()-1; for (p2=v2.size()-1; p2>=0; p2--) { while (p1>=0 && v1[p1].first>v2[p2].second) defenmax = max(defenmax, v1[p1].second), p1--; if (hackmax <= defenmax) break; hackmax = max(hackmax, v2[p2].first); } // [p2+1 ~ v2.size()-1] 为金色卡牌 int num_lose=0; for (auto [x, y] : v1) if (y < hackmax) num_lose++; int num_draw = n - num_win - num_lose; cout<<num_win<<" "<<num_draw<<" "<<num_lose<<endl; return; }title算法本质题目大意思路推演ac核心代码头文件、宏定义、快读模板、常见变量、常见变量等略。 title算法本质题目大意思路推演ac核心代码头文件、宏定义、快读模板、常见变量、常见变量等略。 title算法本质题目大意思路推演ac核心代码头文件、宏定义、快读模板、常见变量、常见变量等略。 title算法本质题目大意思路推演ac核心代码头文件、宏定义、快读模板、常见变量、常见变量等略。

Codeforces Round 906 (Div. 2) Doremy's Connecting Plan算法本质思维题目大意给出n个点（暂时没有边），每个点有点值，若某2个点满足以下条件则可以连接一条边：对于第i个点和第j个点，若i点和j点的连通块的所有点值 >= i * j * c（c是给定的常数）输出是否可以使得图为连通块。思路推演首先想到是同点1连接，但是似乎不一定，于是来展开证明：证明： 若有两个非1点u v，若其可以连接成功，则一定存在某个点可以与1连接成功。 使用反证法。 若两点可以连接成功，可以写出式子： a[u] + a[v] >= u*v*c 若两点不可同1连接成功，可以写出式子： a[u] + a[1] < u*c a[v] + a[1] < v*c 由于u>1 v>1，则可以得出： 所以显然 a[u] + a[v] >= u*v*c >= u*c+v*c > a[u] + a[v] + 2*a[1] 可以看出存在问题，所以得证。这说明了，我们可以优先处理同1连接的情况，而且由于其仅需要连通，所以我们仅处理同1连接的情况。每个点同1连接的难度是固定的，所以可以用一个优先队列来处理即可。ac核心代码头文件、宏定义、快读模板、常见变量、常见变量等略。 inline void solve() { cin>>n>>k; vector<int> a(n+5); read(a, 1, n); int sum=a[1]; priority_queue<pair<int,int>, vector<pair<int,int>>, greater<pair<int,int>>> q; for (int i=2; i<=n; i++) q.push({i*k-a[i], i}); flag = 1; while (q.size()) { auto [cha, id] = q.top(); q.pop(); if (cha>sum) // 如果钱不够 { flag=0; break; } sum += a[id]; } cout<<(flag ? "Yes" : "No")<<endl; return; }Doremy's Drying Plan (Easy Version)算法本质思维题目大意思路推演ac核心代码头文件、宏定义、快读模板、常见变量、常见变量等略。 title算法本质题目大意思路推演ac核心代码头文件、宏定义、快读模板、常见变量、常见变量等略。 title算法本质题目大意思路推演ac核心代码头文件、宏定义、快读模板、常见变量、常见变量等略。 title算法本质题目大意思路推演ac核心代码头文件、宏定义、快读模板、常见变量、常见变量等略。 title算法本质题目大意思路推演ac核心代码头文件、宏定义、快读模板、常见变量、常见变量等略。 title算法本质题目大意思路推演ac核心代码头文件、宏定义、快读模板、常见变量、常见变量等略。