题解1203 div cf
Codeforces Round 897 (Div. 2)
目录写在前面ABCDE1/E2F写在最后 写在前面 比赛地址：https://codeforces.com/contest/1867。 简略题解。 还好没掉分。 A 令原数列中第 \(k\) 大对应 \(k\) 即可。 // /* By:Luckyblock */ #include <bits/st ......
【题解】Educational Codeforces Round 141（CF1783）
评价：educational A.Make it Beautiful 题目描述： 如果一个数组中存在一个数恰好等于该数前面所有数之和，那么这个数组就是丑的。如果一个数组不是丑的，就是美的。 比如说： 数组 $ [6, 3, 9, 6] $ 是丑的，因为 \(9 = 6 + 3\) ； 数组 $ [5 ......
CF1129D Isolation
考虑 dp，令 \(f_i\) 为 \([1,i]\) 这个前缀的分段方案数。\(i\) 从小到大扫描线，动态维护 \(c_j\) 表示 \([j+1,i]\) 中只出现恰好一次的数的个数： \[f_i=\sum\limits_{c_j\le k}f_j \]考虑如何维护 \(c_j\)，扫描线过程 ......
Educational Codeforces Round 34 (Rated for Div. 2) C(multiset、思维)
C. Boxes Packing 思路：每一次选择一段递增的子段, 将其删除, 最高的一个会能够被看到。这个过程可以用 std::multiset 模拟, 主要是两个函数的应用： extract(x)：删除集合中的一个 $ x $，upper_bound(x)：返回集合中第一个大于 $ x $ 的元 ......
【题解】DP选练（23.9.11 - 23.9.12）
一些写过题解的题我就直接挂连接了。 [NOIP2018 提高组] 货币系统 题目描述： 在网友的国度中共有 \(n\) 种不同面额的货币，第 \(i\) 种货币的面额为 \(a[i]\)，你可以假设每一种货币都有无穷多张。为了方便，我们把货币种数为 \(n\)、面额数组为 \(a[1..n]\) 的 ......
Codeforces Round 895 (Div. 3)
Codeforces Round 895 (Div. 3) A. Two Vessels 解题思路: \(d = \lceil {\frac {abs(a - b)} 2}\rceil\) \(ans = \lceil {\frac d c}\rceil\) 代码: #include <bits/s ......
Codeforces Round 897 (Div. 2)
Codeforces Round 897 (Div. 2) 比赛链接 A. green_gold_dog, array and permutation 题目 给你一个长度为n的数组a，要求你找出一个数组长度为n的数组b，大小是1-n，保证每个数字出现一次，使得a数组与b数组对应位置上的差值和最大。 ......
CF447B
随机跳题跳到的，写篇题解吧 题意 给定字符串 \(s\)，和每个字母的价值，问你在字符串后再增加 \(k\) 个字符后能获得的最大价值。 题目中定义价值为 \(\sum_{i=1}^{len} i \times W_{S_i}\)。 思路 仔细观察发现题目不难，是个贪心，找出这些价值中的最大值，然后 ......
Sol.CF383D
可以看出本题可以使用DP。 可将前 \(i\) 个和为 \(j\) 的方案数表示为 \(f_{i,j}\) ,则每次状态转移需要考虑减 \(a_i\) 或加 \(a_i\)。 显而易见状态转移方程如下: \(f_{i,j}=f_{i,j}+f_{i-1,j \pm a_i}\) 由于可能有负数，则需 ......
CF510C
其实是一道板子题，建议评黄。 题意 求一种满足让\(n\)个字符串合法排列的字典序。 思路 不难想到使用拓扑排序。 具体地说，我们可以把字符串当作点，若有两个字符串 \(s1,s2\) 且满足 \(s1\) 的字典序小于 \(s2\) ，则建一条从 \(s1\) 到 \(s2\) 的边。 注意到如果 ......
Sol.CF1037B
又是随机跳题跳到的，再来写一篇题解。 不难发现又是一道用贪心解决的问题。 首先先对序列进行排序。 然后发现题目分为以下三种情况（\(mid\) 为中位数,当前中位数为 \(s\)) \(s=mid\) 输出特判即可。 \(s>mid\) 在序列的左边只要找到比 \(s\) 大的就累加他们的差进答案。 ......
CF113C
前置知识: 费马二平方和定理 内容如下： 除 \(2\) 以外的素数 \(x\) 都可以表示成 \(x\equiv 1 \pmod{4}\) 或 \(x\equiv 3 \pmod{4}\)。 当且仅当素数 \(x\) 可以表示成 \(x\equiv 1 \pmod{4}\) 时， \(x\) 为两 ......
CF441C
一道超级水的思维题，又是exlg跳题跳到的，建议评红。 思路 分类讨论的思维题 如果一队有必胜策略，则二队无论如何布置阵形都无法打败一队，则一队必须有一个人攻击值比二队两个人都大，另外一个人防守值比二队两个人防守值都大。 if(a1>c2&&a1>d2&&b2>c1&&b2>d1||a2>c1&&a ......
Sol.CF811B
题意 给定长度为 \(n\) 的排列，每次选一段区间 \([l,r]\) 排序，问位置 \(x\) 上的数在排序前后是否发生了改变。保证 \(x\in[l,r]\)，共 \(q\) 次询问。 思路 可以暴力枚举区间 \([l,r]\) 内比 \(a_x\) 小的数，每找到一个 \(cnt\) 累加一 ......
Sol.CF301A
签到题中夹带着贪心 考虑要尽可能把所有数变成正数。 若 \(n\) 为奇数，则一定可以变成全部正数，首先翻出 \(n\) 个负数，其他的下一次翻完。 若 \(n\) 为偶数，显然定有一个数还是负数，考虑最小的哪个。 Accept 代码如下： #include<iostream> #include<c ......
Codeforces Round 897 (Div. 2)
F. Most Different Tree 当 \(n=2\) 时，只能构造一条长度为 \(2\) 的链。 当 \(n\ge 3\) 时，对于 \(i\) \((1\le i\le n)\)，以 \(i\) 作为根的树记为 \(h_i\)，考虑枚举树找一个大小为 \(s\) 的树 \(t\)，使得 ......
html div && span 容器元素
html div && span 容器元素 div 标签定义 HTML 文档中的一个分隔区块或者一个区域部分, 标签常用于组合块级元素，以便通过 CSS 来对这些元素进行格式化 span 用于对文档中的行内元素进行组合 标签提供了一种将文本的一部分或者文档的一部分独立出来的方式 <html> <he ......
CF521E. Cycling City
套路的，先随便找这张图的一棵生成树，原条件等价于存在一条路径同时被两条非树边覆盖。 直接枚举非树边进行覆盖，发现如果只要有一条树边的覆盖次数达到了 2 就可以退出了。因此，我们选取这张图的 dfs 树作为我们的生成树。 这样做有一个很好的性质：非树边只会是返租边或是前向边。由于这是一张无向图，前向边 ......
Codeforces Round 897 (Div. 2)
Codeforces Round 897 (Div. 2) A. green_gold_dog, array and permutation 分析: 由题意: \[c_i = a_i - b_i \]\(c_i\)种类最多就是\(n\)个数都不同。 若\(a_i\)不断变大，\(b_i\)不断变小， ......
[题解]AT_arc116_b [ARC116B] Products of Min-Max
思路 我们容易可以得到一个朴素的做法，首先对 \(a\) 数组排序，然后枚举最大值和最小值 \(a_i,a_j\)，那么对于中间的元素都有选与不选两种情况，得到答案： \[\sum_{i = 1}^{n}(a_i \times a_i + (\sum_{j = i + 1}^{n}a_i \time ......
CF1868C
问题链接 题意：\(n\)个点，每个点的点权在\([1,m]\)之间，求所有方案的所有路径的最大值的总和 首先，对于一条长度为\(x\)的路径，设它的贡献为\(pre_x\)，他的最大值取值有\(m\)种，其中最大值为\(i\)的取值有\(i^x-i^{x-1}\)种，而除了该路径外的所有点的取值一 ......
Codeforces Round 897 (Div. 2) A~E
Codeforces Round 897 (Div. 2) A~E A： 原先数组里面最小的位置放最大的数，次小的放次大的即可。 void solve(){ int n; cin>>n; for(int i=1;i<=n;i++){ int x; cin>>x; c[i]={x,i}; } sort ......
Codeforces Round 896 (Div. 2)
Codeforces Round 896 (Div. 2) A. Make It Zero 代码: #include <bits/stdc++.h> using namespace std; using ll = long long; using i128 = __int128; int n, m; ......
CF1867D Cyclic Operations
前言 赛时没调出来，赛后调了一个上午，最后发现是有个地方没清零。 思路 首先对于位置 \(i\)，我们必须要保证进行的操作中，最后一次出现 \(i\)，\(i\) 的后面一定是 \(a_i\)。 那么我们考虑统计所有位置上的要求，用有向边链接，那么就会出现一个有环有向图（一定有环，因为点数等于边数） ......
CF1867A green_gold_dog, array and permutation
思路 很简单的一道题，洛谷大概都不会开放题解通道？（实际上貌似每场比赛的 A 都没开放？） 显然，对于原数组较小的数，我们尽量让大的数，取全排列的较小的数，这样可以保证差是逐渐变小的，也就让 \(c\) 数组差异变大。 所以直接拿个 struct 存，然后两边排序就好。 AC code #inclu ......
CF1867C Salyg1n and the MEX Game
思路 看着无从下手，实际上又是一道诈骗题。 假设原数列不存在 \(0\)，那么我们可以直接加入 \(0\)，然后游戏结束，假设答案是 \(k\)。那么，如果我们选择加入 \(k\)，来试图让答案变大，那么 Bob 就会移除一个数，最优的话是 \(1\)，这样的话，你无论加入 \(1\) 还是 \(0 ......
CF1867E1 Salyg1n and Array (simple version)
思路 首先考虑，\(n\) 是 \(k\) 的倍数的情况，直接枚举询问所有每一段就好，然后输出每一段的异或和的异或和。 如上图，每次询问都没有重叠部分，颠转互不干扰。 那么，\(n\) 不是 \(k\) 的倍数的情况呢？ 可以看到，与第一种情况的区别就是末尾多了一小截，那么我们需要考虑如何计算这一小 ......
CF1867E2 Salyg1n and Array (hard version)
其实如果你在做 E1 的时候想到正解了，这道题都甚至不需要改 E1 的代码，直接交就好，这大概也是 E2 的分还没 E1 的高的原因。 因为一摸一样的思路，所以这里就不作介绍了，可以看看我的题解。 在这里呢，主要是稍微证明一下询问次数不会超，如下： 可以发现，有余数的情况，只会增加两次询问，而后面的 ......
202309 at&cf题目选讲
题目链接 题解 目录A AtCoder abc318_c Blue SpringB AtCoder abc318_d General Weighted Max MatchingC AtCoder abc318_e SandwichesD AtCoder abc318_f OctopusE AtCod ......
CF1867B XOR Palindromes
思路 题目问的是改 \(i\) 位，能不能让原串变成回文串，其中 \(0\le i \le n\)。 首先，我们可以统计前后对称位置不一样的对数，记为 \(k\)，那么至少也得改 \(k\) 次，假设剩下前后对称位置一样的有 \(m\) 对（如果 \(n\) 为奇数，则最中间的一位不计入 \(m\) ......