Educational Codeforces Round 144 (Div. 2) Prime Deletion算法本质思维题目大意给定长度9的排列数组，删除其中至多7个元素，剩下的元素按顺序以十进制拼接为一个新数，使得其为素数。输出最后的素数。思路推演考虑是A题，应该具有简单的方法，其中一个想法就是，存在ab是素数且ba是素数，这样可以覆盖所有情况。查阅100以内的素数表，发现79和97都是素数。Two Binary Strings算法本质思维题目大意给定2个长度相等的01字符串a b，保证以0开头、以1结尾，接下来可以执行任意次操作：选择a或b字符串，选择2个相等的字符，将其中间字符都修改为所选字符检查a b最终是否可以相等。思路推演显然的一个找规律的题目，或者叫做洞察其本质。观察样例，可行的情况稍微有点多，反过来观察不可行的情况——一定是存在某个下标p，a[p]和b[p]不同且无法通过操作来改变。但是这样的情况有很多，继续找其特征。因为操作无限制，且可以对两个字符串都使用，所以还有一个特征是：若两者可行，一定可以变为000011111的形式到此为止，只需要检查是否存在某个下标p，能作为01的分界线即可。分界线是否可行，判断十分简单，这里就不说了。Queries for the Array算法本质模拟、思维题目大意初始存在一个空数组，接下来会有3种操作：新添加一个随机数字放置末尾移出末尾的数字检查数组是否单调不减（需要返回0或1，0表示非，1表示满足）现在Alice展示了她玩这个的指令，检查这个指令是否可能存在。思路推演这是一个典型的模拟题，其中0或1会告诉我们信息，重点在于用什么形式将这些信息完全捕获：1的信息数字有序是一个连续的性质，所以仅需要一个下标存储就好了。当有新增元素时，下标不变，当元素减少时，若当前下标元素没了，下标后退一步即可0的信息表示当前数组不有序，即至少存在某个元素不有序，其实也可以这样理解，假如现在有n个数字，被告知不有序，则我们可以假设存在一个p<n，前p个元素是有序的，但是这个p是不定的。通过上面的分析，可以发现的是，对于数组来说，可以分成三段：下标[1, l]的部分，是保证有序的下标[1, r]的部分，是可能有序、可能无序的下标[1, 末尾]的部分，是一定无序的对于每个操作来说，维护l r值即可，若其有冲突，则不可行。ac核心代码头文件、宏定义、快读模板、常见变量、常见变量等略。 void solve() { string s; cin>>s; flag = 1; int siz=0, l=0, r=0; // siz表示当前数组长度，l r同上含义 for (char c:s) { if (c=='+') { siz++; if (r==siz-1) // 新增元素时，l不需要移动，r需要判断是否移动 r=siz; } else if (c=='-') // 删除元素时，保证l r不越界 { siz--; l = min(l, siz); r = min(r, siz); } else if (c=='1') { if (siz > r) // siz>r表示一定是无序的，起了冲突，不可行 { flag=0; break; } l = r = siz; // 重新赋值l r } else if (c=='0') { if (siz<2 || siz==l) // 一定有序的条件 { flag=0; break; } if (r==siz) r--; } } cout<<(flag ? "YES" : "NO")<<endl; return; }Sorting By Multiplication算法本质思维题目大意给定长度n的正整数数组，现在可以若干次执行操作：选择l r x，使得a[l~r]都乘上x（x可以为任意值，包括零和负数）使得操作后数组严格递增，输出最小化的操作次数。思路推演还是老样子，分析一下操作的本质：如果x>0的话，因为只关心元素的相对大小，所以这个操作其实可以看作加法。那这个就非常简单了，只需要检查相邻元素之间非递增关系的个数即可。但是这里存在x<=0的情况，继续思考。稍加模拟可以发现：因为最后是升序情况，所以最终必然是前一部分为负数，后一部分为正数的情况。而初始全正，前一部分的负数用一次操作统一处理，而且具体哪个负值没有意义，视作都用-1即可。一个朴素的想法是，那检查正负分界线即可。前面负数部分，操作数是：相邻元素之间非递减关系的个数+1后面整数部分，操作数是：相邻元素之间非递增关系的个数这里只需要用前缀和处理一下即可，注意考虑全正全负的情况。这里还有一个小坑导致赛时wa了一发，就是假如前负数部分是[1, p]，正数部分是[p+1, n]，p和p+1之间的关系是不用考虑的，其必然严格递增。ac核心代码代码会稍微奇怪一点，构建了a[]，长度n-1，表示n个元素之间的关系：1表示严格大于0表示等于-1表示严格小于头文件、宏定义、快读模板、常见变量、常见变量等略。 { cin>>n; n--; vector<int> a(n+5), pre0(n+5), pre1(n+5); int last=in(); for (int i=1; i<=n; i++) { int now=in(); if (now > last) a[i] = 1; else if (now < last) a[i] = -1; last = now; } for (int i=1; i<=n; i++) { pre0[i] = pre0[i-1]; // pre0[i]=x表示前i个关系中，有x个关系都是等于或大于 pre1[i] = pre1[i-1]; // 类似pre0[] if (a[i]==0 || a[i]==1) pre0[i]++; if (a[i]==0 || a[i]==-1) pre1[i]++; } int ans = pre1[n]; // 考虑全正的情况 pre1[n+1] = pre1[n]; // 可能会越界，特殊处理 for (int i=1; i<=n; i++) { int res = pre0[i] + pre1[n] - pre1[i+1] + 1; // 考虑前i个关系为负数 ans = min(ans, res); } cout<<ans<<endl; return; }Non-Intersecting Subpermutations算法本质思维、dp题目大意给定n k，表示合法合规数组长度n，元素范围1~k。定义数组的美丽值：将其任意划分，若某个部分为长度k的排列则贡献值+1，划分方案所能达到的最大贡献值输出所有合法合规数组的美丽值之和。k n <= 4e3思路推演-初步思路这种题通常有2个思考方向：计算美丽值为x的合法数组个数，然后最后统一乘法求和计算某个部分对整体的贡献值，统一相加但是不管选择哪种方法，其最大的问题在于，用贪心思路去计算，会计算重复——这表明只能用dp去解决，通过巧妙的设计，解决重复计算的问题。这里为了避免重复计算，设定一个规则，比如数组[3, 2, 1, 2, 3]对于k=3的情况来说，这个数组的美丽值为1，但是有2种分割方式，根据贪心可知，总是用靠前的分割方式是最优解，所以视作[3, 2, 1]和[2, 3]，为了方便叙述，我们称这个下标3的位置为奇点。一个朴素的想法是，通过制造方向性来避免重复计算：假设f[i]表示填写[1~i]位且i是奇点的方案数。（注意，这里的每个方案数，其最后k位可以视作已经固定了的）这样答案就可以表示为：$\sum_{i=1}^nf(i)*k^{n-i}$转移方程的话，可以通过枚举上一个奇点位置来转移。接下来研究两个奇点如何转移。设靠前奇点位置是j，靠后奇点位置是i，首先因为题目规定，所以j <= i-k。其次通过模拟可以发现，如果i是第一个奇点，情况会比较特殊，要特殊处理，这里先讨论i非第一个奇点的情况。讨论1——i不是第一个奇点的情况转移方程用文字描述是：（暂时没有考虑i是第一个奇点的情况）$f(i) = \sum_{j=k}^{i-k}f(j)*(已知ij是奇点、且ij之间不存在奇点、且已知j为奇点的排列方式的方案数)$为了解决这个问题，通过模拟发现，贪心比较难，但是可以用dp来解决。所以构建式子g[x]表示：存在某个下标p是奇点、已知p奇点的排列方式、p+x是下一个奇点（中间无其他奇点）的方案数。这样的话可以优化f[]的求解为：$f(i) = \sum_{j=k}^{i-k}f(j)*g(i-j)$接着完善g[]的维护方程，这里引入g[]的前缀和函数pre[]方便描述：i<k已知了p奇点的排列方式，要使得p+i为奇点，则所选的元素种类的固定的，可以改变的是其排列方式，再减去重复的方案即可（中间有奇点的情况）$g(i) = i!-pre(i-1)$i>=k则后k个元素一定是排列，还剩余的i-k个元素随意取，减去重复方案即可（中间奇点情况）$g(i) = k!*k^{i-k}-pre(i-1)$讨论2——i是第一个奇点的情况前面的讨论给了我们很大的启发，i是第一个奇点的情况显然也可以使用dp来维护。设h[i]表示i是第一个奇点的方案数。思考出转移方程：i<kh[i]=0i>=k$h(i) = k!*k^{i-k}-\sum_{j=1}^{i-1}h(j)*g(i-j)$显然这里也可以用前缀和辅助优化汇总当预处理好了g[]和h[]就可以表示f[]：$f(i) = \sum_{j=k}^{i-k}f(j)*g(i-j) + h(i)$$ans = \sum_{i=1}^nf(i)*k^{n-i}$第一个式子，前部分表示i是非第一个奇点的方案数，后部分表示i是第一个奇点的方案数。注意f[<k]显然为0ac核心代码头文件、宏定义、快读模板、常见变量、常见变量等略。 title算法本质题目大意思路推演ac核心代码头文件、宏定义、快读模板、常见变量、常见变量等略。 title算法本质题目大意思路推演ac核心代码头文件、宏定义、快读模板、常见变量、常见变量等略。

Educational Codeforces Round 153 (Rated for Div. 2) Yet Another Permutation Problem算法本质思维题目大意需要玩家构建长度n的循环排列，定义其美丽值：相邻元素的gcd值的不同个数输出最大化的构建方案。思路推演稍加模拟：对于1而言，其跟和相邻，gcd值都是1，对于2而言，其与2的倍数相邻gcd值才是2，考虑其与4相邻是最优解（因为其他元素可能有更好的解法）。同理，2的右边放4，左边没什么用了，就放1吧。对于4而言，右侧应该放4的倍数，8是最优解，以此类推，我们找到了gcd值的1 2 4 8 ...，当大小不够时，回身找3，同理即可。最终构建出的数组形如：[1, 2, 4, 8, 16, ...., 3, 6, 12, 24, ...., 5, 10, 20, ....]Trees and Segments算法本质思维题目大意给定01串，设置l0表示串中连续0的最大长度，l1表示串中连续1的最大长度。现在至多可以执行k次操作：反转某位有式子：f(x) = x*l0 + l1独立地回答，当x属于[1~n]，输出操作后最大化的f(x)。n <= 3e3思路推演稍加模拟可以发现，首先完全贪心思路是无法解决的，所以寻求dp解决。这里会有个经常的问题是，大概率不会是O(n)求一个f(x)，若需要如此，完全可以将n修改为1e6，然后随机赋予一个x值求解。所以一定会有用到n^2^的算法的：预处理O(n^2^)，所有x都能受益x之间存在关系，可以借用操作完后，肯定是存在2个无交集区间，分别是全0的最长区间和全1的最长区间，暂且默认全0区间在左。dp处理同时维护全0区间和全1区间不行（其权重未知，没有同一标准），但是维护单个信息还是可行的。比如dp[i][j]表示[1~i]中用j次操作后，最长的0区间长度。一个想法是，区间之间一定存在分界线，枚举分界线，然后枚举左边的操作次数和右边的操作次数，就能得到两个区间的长度。但是，对于每种区间长度，还需要枚举x的n个取值，这总体的复杂度达到了O(n^3^)。一个朴素的优化方式是：这里有n^2^种两个区间的长度，其存在部分单调性，用0区间长度作为key来记录，1区间的长度就具备了单调性，情况可以优化至n种。然后再对这相对优解枚举其x值，就可以O(n^2^)解决。回过头来，再来看dp[][]的设置，其实是存在一些小问题的。之前的状态设置完全转移困难，所以重新设计dp[i][j]表示操作j次以i结尾的最长0区间长度。这样转移十分好写：if s[i]==0: dp[i][j] = dp[i-1][j] + 1 # 不需要额外操作 else: dp[i][j] = dp[i-1][j-1] + 1 # 需要额外操作，注意i j边界然后再建立一个状态：$pre[i][j] = \max_{t=1}^idp[t][j]$来表示以1~i中，使用j次操作后的最长连续0区间。这样就拿到了所需要的东西，但是这仅仅是某一个，其实有4个东西需要拿到：1~i中，使用j次操作后的最长连续0区间长度i~n中，使用j次操作后的最长连续0区间长度1~i中，使用j次操作后的最长连续1区间长度i~n中，使用j次操作后的最长连续1区间长度建议使用函数优化。ac核心代码头文件、宏定义、快读模板、常见变量、常见变量等略。 vector<vector<int>> f(string s, char c) { s = " " + s; vector<vector<int>> dp(n+5, vector<int>(k+5)), pre(n+5, vector<int>(k+5)); for (int i=1; i<=n; i++) { for (int j=0; j<=min(k, i); j++) // 注意操作数可能为0，要从0开始 { if (s[i]==c) dp[i][j] = dp[i-1][j] + 1; else if (j>0) // 注意别越界 dp[i][j] = dp[i-1][j-1] + 1; pre[i][j] = max(pre[i-1][j], dp[i][j]); } } return pre; } inline void solve() { string s; cin>>n>>k>>s; vector<vector<int>> pre0, suf0, pre1, suf1; pre0 = f(s, '0'); pre1 = f(s, '1'); reverse(s.begin(), s.end()); // 倒过来就是suf了 suf0 = f(s, '0'); suf1 = f(s, '1'); vector<int> to(n+5, -1); // to[0区间长度] = 最大的1区间长度 for (int i=0; i<=n; i++) // 枚举分界点 { for (int l=0; l<=k; l++) /// 枚举左右方的操作数 { int r=k-l; int len0=pre0[i][l]; // 假设0区间在左，1区间在右的情况 int len1=suf1[n-i][r]; to[len0] = max(to[len0], len1); len0=suf0[i][r]; // 假设0区间在右，1区间在左的情况 len1=pre1[n-i][l]; to[len0] = max(to[len0], len1); } } vector<int> ans(n+5, -1); for (int len0=0; len0<=n; len0++) // 存在n个相对优解 { if (to[len0]==-1) continue; for (int x=1; x<=n; x++) ans[x] = max(ans[x], x*len0 + to[len0]); } for (int i=1; i<=n; i++) // 输出 cout<<ans[i]<<" \n"[i==n]; return; }Rollbacks (Easy Version)算法本质思维题目大意初始存在一个空数组，接下来有q次操作：+ x数组末尾增加值x的元素- x数组末尾减去x个元素!回溯上一个操作（类似于栈，无法回溯回溯的操作）?询问目前数组不同元素的个数Hard版本强制要求在线全部值 <= 1e6思路推演Eszy版本并不要求在线，这点提醒了我们。稍加模拟可以发现，减法的形态，有点类似于树的一个分支。例如当[1, 3, 2, 5, 3, 6]遇到减去3个元素后，数组末尾的[5, 3, 6]就可以视作树的一个分支。同时当前点需要跳转至2，这样的大幅度跳转需要优化至log级别，在线倍增符合我们的要求。还需要注意的一个点是回溯操作，其实其本质很简单，回溯到上一次操作的点，我们仅需要每次操作的时候，都记录一下之前的点即可。遇到问好，就在树上做个标记：第x个问号在次询问。ac核心代码头文件、宏定义、快读模板、常见变量、常见变量等略。 vector<int> g[maxn]; int up[maxn][20]; int a[maxn]; vector<int> cod[maxn]; int swim(int x, int step) // 向上移动step步的基础函数 { for (int wei=0; step>0; wei++) { if (step&1) x=up[x][wei]; step /= 2; } return x; } int ans[maxn]; int mp[maxn]; // 这里用map会爆内存（题目卡的比较死） int siz=0; void dfs(int u=0) { if (u < 0) return; if (u!=0) { mp[ a[u] ]++; if (mp[a[u]]==1) siz++; } for (int pos:cod[u]) ans[pos] = siz; for (int v:g[u]) dfs(v); mp[ a[u] ]--; if (mp[a[u]]==0) siz--; } inline void solve() { int q=in(); int y=q; int cnt=0, p=0, wen=0; // cnt记录出现的点数，p记录当前点的id，wen记录?出现的次数 vector<int> lastp; // 记录操作前的id，方便回溯 while (q--) // 维护树结构，然后记录有的节点需要答案 { string op; cin>>op; if (op=="+") { lastp.push_back(p); int num=in(); int u = ++cnt; // 新增点 g[p].push_back(u); // 记录其父亲多了一个子节点，方便之后访问 a[u] = num; // 记录点的值 up[u][0] = p; for (int i=1; i<=19; i++) // 更新一下树上倍增 up[u][i] = up[ up[u][i-1] ][i-1]; p = u; // 更新当前点 } else if (op=="-") { lastp.push_back(p); int num=in(); int u = swim(p, num); // 利用倍增log级别查询 p = u; // 更新当前点 } else if (op=="?") cod[p].push_back(++wen); // 记录问号 else if (op=="!") p=lastp.back(), lastp.pop_back(); } dfs(); for (int i=1; i<=wen; i++) cout<<ans[i]<<endl; return; }title算法本质题目大意思路推演ac核心代码头文件、宏定义、快读模板、常见变量、常见变量等略。 title算法本质题目大意思路推演ac核心代码头文件、宏定义、快读模板、常见变量、常见变量等略。 title算法本质题目大意思路推演ac核心代码头文件、宏定义、快读模板、常见变量、常见变量等略。 title算法本质题目大意思路推演ac核心代码头文件、宏定义、快读模板、常见变量、常见变量等略。

Educational Codeforces Round 152 (Rated for Div. 2) Max to the Right of Min算法本质思维++、单调栈题目大意给定排列p[]，定义[l, r]为合法区间：p[l~r]的最大值下标 > p[l~r]的最小值下标输出合法区间数。n <= 1e6思路推演这样的题，朴素思想一来有两种：固定区间左端点，枚举右端点固定区间最大值，枚举最小值至于具体固定左还是右，大还是小，本质上是一样的第一种方式，区间内的最值变化严重，无规律可言，直接放弃。相比而言，第二种方式可以把合法区间有条理分类去找。假设找以p[i]为最大值的合法区间，然后这天然就存在的限制是：区间内不能有>p[i]的值，这个由p[i]最大值引起的限制可以用单调栈来搞定。随后枚举<i的下标，找合法区间的最小值。通过数次模拟可以发现，左边可行的合法区间最小值，是一个单调递减的形式，其下标用j表示。用lmin[] lmax[] rmin[] rmax[]表示某个元素左右方向第一个大于、小于其的值的下标。每个合法区间，将其范围缩减至区间最值暴露于左右两端，用[j, i]表示——即对于a[j]为最小值、a[i]为最大值的合法区间的数目为：$(j-\max(lmin[j], lmax[i]))*(min(rmin[j], rmax[i])-i)$不过显然，最坏情况这样的复杂度为O(n^2^)，复杂度不支持，思考优化。可以发现的是，如果枚举最大值下标i是从左往右枚举时，由于最小值在左的规则，i+1作为最大值下标找的合法区间最小值下标与i相同的地方许多，也许可以做些预处理来。而且由于这些最小值下标j从左往右是递增的，所以其rmin[]值也是递减的，而在上面可以公式可以看到，这个公式最大的问题就是max min值的分割处理（才能进行整体特征合并优化），而rmin值递增为公式右侧部分提供了分割处理的基础。公式左侧部分，可以通过lmin[j]的值来寻找可行的最小值下标。ac核心代码头文件、宏定义、快读模板、常见变量、常见变量等略。 a[maxn]; inline void solve() { cin>>n; rep(i,1,n) cin>>a[i]; ddz(a, n); vector<int> s, sum; int ans=0; for (int i=1; i<=n; i++) { while (s.size() && a[s.back()]>a[i]) // s[]维护的是一个递增、且全部<a[i]的下标数组 { s.pop_back(); sum.pop_back(); } // 保证a[i]为最大值的合法区间中，s[l]是最靠左的合法区间最小值下标！（这里比较重要，画图理解） int l=upper_bound(s.begin(), s.end(), lmax[i]) - s.begin(); if (l < s.size()) // 存在这样的值 { int j=s[l]; // j为合法区间最小值下标（以a[i]为最大值、最左边的下标） ans += (j-lmax[i]) * (min(rmin[j], rmax[i]) - i); // 按照公式计算[j,i]的可达合法区间数 l++; // 接下来的s[l]不再是最左边的最小值下标，所以公式的左侧取`lmin[j]`而不是`lmax[i]`，同时lmin[j]可以很好的合并 // 上面这几步代码，实际上已经将公式左侧的情况分开讨论了，随后也讨论右侧的情况 int r=partition_point(s.begin()+l, s.end(), [&](int x) { return rmin[x] > rmax[i]; }) - s.begin(); // 找到s[]中第一个rmin[?]<=rmax[i]的下标 ans += (s[r-1] - s[l-1]) * rmax[i]; // 这部分区间，公式左侧取`lmin[j]`，公式右侧取`rmax[i]` ans += sum.back() - sum[r-1]; // 这部分用前缀和处理，具体看sum那的处理 ans -= (s.back() - s[l-1]) * i; } int pre = sum.size() ? sum.back() : 0; int last = s.size() ? s.back() : 0; sum.push_back(pre + (i-last) * rmin[i]); // 预处理一部分，画图理解 s.push_back(i); } cout<<ans<<endl; return; }title算法本质题目大意思路推演ac核心代码头文件、宏定义、快读模板、常见变量、常见变量等略。 title算法本质题目大意思路推演ac核心代码头文件、宏定义、快读模板、常见变量、常见变量等略。 title算法本质题目大意思路推演ac核心代码头文件、宏定义、快读模板、常见变量、常见变量等略。 title算法本质题目大意思路推演ac核心代码头文件、宏定义、快读模板、常见变量、常见变量等略。 title算法本质题目大意思路推演ac核心代码头文件、宏定义、快读模板、常见变量、常见变量等略。 title算法本质题目大意思路推演ac核心代码头文件、宏定义、快读模板、常见变量、常见变量等略。

CodeTON Round 6 (Div. 1 + Div. 2, Rated, Prizes!) Prefix Purchase算法本质思维题目大意给定长度n的数组c[]，初始拥有长度n的全0数组a[]和k元。可以进行任意次操作：花费c[i]元，使得a[1~i]元素都+1输出操作后最大化的a[]（字典序）。思路推演稍加模拟可知：价格相同，下标大的优下标相同，价格低的优可以选择不同价格的，但是要保证次数不减少这说明了，可以用贪心的思路去遍历可能的点，其符合：下标递增价格递增首个点是价格最低中，最靠右的点根据此模拟即可。（详细看代码）ac核心代码头文件、宏定义、快读模板、常见变量、常见变量等略。 void solve() { cin>>n; map<int, int> mp; for (int i=1; i<=n; i++) mp[in()]=i; cin>>k; vector<int> ans(n+5); int max_ci=1e9, lastid=0, bo=0; // max_ci表示选择次数上限、lastid记录上次访问id（排序保证价格递增，lastid维护id递增）、bo表示价格底部 for (auto [w, id]:mp) { if (id < lastid) continue; // 维护id递增 int ci=k/(w-bo); ci = max(ci, 0ll); // 范围在[0~max_ci]之前 ci = min(ci, max_ci); k -= ci*(w-bo); // 计算“剩余的钱” ans[id] = ci; // 记录选择 max_ci = ci; // 更大最大值限制 bo = w; lastid = id; } for (int i=n; i>=1; i--) // 因为是选取了一部分点，没有覆盖全部，手动覆盖 ans[i] = max(ans[i], ans[i+1]); for (int i=1; i<=n; i++) cout<<ans[i]<<" \n"[i==n]; return ; }Another MEX Problem算法本质思维、dp题目大意给定长度n数组a[]，元素值为[0~n]。玩家可以选择若干个互不相交的子数组，输出最大化的每个子数组的mex值的异或和。n <= 5e3思路推演显然需要用到dp，在不考虑复杂度的情况下，构建dp解决（这个过程很可能领悟题目的特性）。首先来说表示一个范围的精确值十分好计算，但是这显然不合适题意来dp——因为可以空许多地方，意味分割线的数目会很多。所以自然而然的，使用dp[l][r][x] = 0/1来表示区间a[l~r]是否可以制造出x值。同时考虑转移方程，发现并不需要精确的左右端点范围，所以修改为：dp[r][x] = 0/1表示区间a[1~r]是否可以制造出x值。转移方程也相对简单：1~r可以视作由完全自己构成dp[r][ mex(a[1~r]) ] = 1看作由2个区间异或而成dp[r][ dp[mid][x] ^ mex(a[mid+1~r]) ] = 1通过设计dp状态，目前空间复杂度n^2^、时间复杂度n^3^，寻找特征继续优化。考虑mex的特征，当一个区间向外延申时，其mex值可能不变。定义不可替代区间：当区间长度为1 或者 不存在真子区间也可以获得相等的mex值通过继承方式，我们可以只用在不可替代区间上更新。证明：不可替代区间的数目是O(n)量级 区间长度为1的都是不可替代：有n个 考虑区间长度>1的情况： 对于任意长度>1的不可替代区间，其左右端点元素一定不相同，则先假定左端点值>右端点值 反证法： 对于每个左端点l，若存在多个r端点可以组成不可替代区间，先取2个为r1 r2，其r1<r2 首先可以知道mex(l, r1)>l（不可替代区间特点），r2<l<mex(l,r1)，所以r2显然无贡献，删除r2不会对mex值产生影响。 所以可得，对于每个左端点l，至多有1个r端点可以组成不可替代区间（长度>1） 然后反过来，不可替代区间的数目是3n （也可以修改定义使其求为2n，但是这种方式不改变数量级，无所谓）所以，对于每个左端点，转移复杂度降低至O(n)。另外有担心异或导致值超出n，实际上没有这种数据，手动模拟，应该是存在什么数学式子约束。但是没有题解做出回答，所以目前无法解答。ac核心代码头文件、宏定义、快读模板、常见变量、常见变量等略。 void solve() { cin>>n; vector<int> a(n+5); vector<vector<int>> dp(n+5, vector<int>(n+5)), mex(n+5, vector<int>(n+5)), cod(n+5); for (int i=1; i<=n; i++) cin>>a[i]; // 初始化mex[][] for (int i=1; i<=n; i++) { vector<bool> zhi(n+5); int val=0; for (int j=i; j<=n; j++) { zhi[ a[j] ] = 1; while (zhi[val]) val++; mex[i][j] = val; } } // 维护cod，cod[l]记录了所有以l为左端点的**不可替代区间** for (int l=1; l<=n; l++) { cod[l].push_back(l); for (int r=l+1; r<=n; r++) { if (mex[l][r]!=mex[l+1][r] && mex[l][r]!=mex[l][r-1]) cod[l].push_back(r); } } dp[0][0] = 1; for (int l=0; l<=n; l++) { if (l>0) // 继承，表示中间有部分没有选择 { for (int x=0; x<=n+1; x++) if (dp[l-1][x]) dp[l][x] = 1; } for (int r:cod[l+1]) { for (int x=0; x<=n; x++) { if (dp[l][x]==0) continue; dp[r][ x^mex[l+1][r] ] = 1; } } } int ans=0; for (int i=0; i<=n; i++) if (dp[n][i]) ans = i; cout<<ans<<endl; return; }title算法本质题目大意思路推演ac核心代码头文件、宏定义、快读模板、常见变量、常见变量等略。 title算法本质题目大意思路推演ac核心代码头文件、宏定义、快读模板、常见变量、常见变量等略。 title算法本质题目大意思路推演ac核心代码头文件、宏定义、快读模板、常见变量、常见变量等略。 title算法本质题目大意思路推演ac核心代码头文件、宏定义、快读模板、常见变量、常见变量等略。 title算法本质题目大意思路推演ac核心代码头文件、宏定义、快读模板、常见变量、常见变量等略。

CodeTON Round 5 (Div. 1 + Div. 2, Rated, Prizes!) Tenzing and Balls算法本质思维、dp题目大意存在n个小球排成一列，给定数组a[]表示每个小球颜色，玩家可以执行任意次操作：选择2个相同颜色的小球，删除两球中间包括其在内所有小球输出最大化删除的小球个数。思路推演稍加模拟可以发现，核心在于不同颜色小球的交错。相同颜色小球可以用连续区间来表示，问题在于如何处理不同颜色区间的交。再次模拟思考，发现没有特定规律，于是考虑dp：dp[x]=y表示在区间1~x中最多可以删除y个小球。转移的方式有二：不删除当前小球dp[i] = dp[i-1]当前小球作为区间右端点删除dp[i] = max(dp[x] + i-x)其中a[x+1] = a[i]复杂度在于第二个转移方程，朴素去做的话复杂度达到O(n^2^)，既然是向前寻找，能否维护一个极值：dp[x]-x即可。当然也可以转换dp定义，这样看起来更直观：dp[x]=y表示区间1~x中最少剩余y个小球：不删除当前小球dp[i] = dp[i-1] + 1删除当前小球dp[i] = min(dp[x])其中a[x+1] = a[i]，这里开个数组记录一下即可ac核心代码头文件、宏定义、快读模板、常见变量、常见变量等略。 inline void solve() { cin>>n; vector<int> dp(n+5, 1e9), cod(n+5, 1e9); // dp[x]表示下标1~x中，保留的最少球数 dp[0] = 0; // cod[x]表示，当前小球颜色为x，之前状态的最少小球数 for (int i=1; i<=n; i++) { int x=in(); dp[i] = min(dp[i-1]+1, cod[x]); // 直接继承和跳跃继承 cod[x] = min(cod[x], dp[i-1]); // 维护 } int ans = n-dp[n]; cout<<ans<<endl; return; }Tenzing and His Animal Friend算法本质思维题目大意（抽象）给定无向有权图，玩家可以进行任意次操作：将点设置为白点或黑点（1必须是白点、n必须是黑点），任意边两侧点颜色不一致，则边权-1在保证边权不出现负数情况下，输出玩家至多可以进行的操作次数，并且输出每次操作的信息（用01表示点的黑白）。若可以无限次输出inf。n <= 1e2思路推演稍加模拟可以发现，若1 n两点不连通，则可以进行无限次操作。题目核心在于固定1是白点、n是黑点，那一定有中间点受伤。若画出1 n的任意一条路径，可以发现，每次操作至少路径上某边的边权会-1。这不难推出，理论上最多操作次数即其最短路，带着这个思路去模拟发现：若某点与n的最短路径是0，则其必须是黑点。随后以最短路的思维，从n出发，除开必须黑点的点，其余点每次操作都取白点。随着操作数的增加，可以视作黑点的面积不断扩大——正是最短路的模型。随后代码模拟即可。ac核心代码头文件、宏定义、快读模板、常见变量、常见变量等略。 // 省略DSU板子 inline void solve() { cin>>n>>m; vector<vector<int>> g(n+5, vector<int>(n+5, 1e18)); // 两点的初始距离 DSU dsu(n); while (m--) { int u, v, w; cin>>u>>v>>w; dsu.merge(u, v); g[u][v] = g[v][u] = w; } if (dsu.same(1, n)==0) // 检查是否联通 { cout<<"inf"<<endl; return; } string now(n+1, '1'); // 初始情况：除了n点全选白点 now[n] = '0'; vector<int> cod(n+5); for (int i=1; i<=n-1; i++) cod[i] = g[i][n]; int tim=0, ci=0; vector<pair<string, int>> ans; while (1) { int minw=1e18, id=-1; for (int i=1; i<=n; i++) if (now[i]=='1' && cod[i]<minw) minw=cod[i], id=i; if (minw > 0) // 需要记录 { ans.push_back({now.substr(1, n), minw}); tim += minw; ci++; } for (int i=1; i<=n; i++) if (now[i]=='1') cod[i]-=minw; now[id] = '0'; for (int i=1; i<=n; i++) if (now[i]=='1') cod[i] = min(cod[i], g[id][i]); if (id==1) // 当1必须是黑点时，就无法继续操作了 break; } cout<<tim<<" "<<ci<<endl; for (auto [s, t] : ans) cout<<s<<" "<<t<<endl; return; }Tenzing and Triangle算法本质思维、线段树题目大意存在一个区间由3条直线围成：y=0x=0x+y=k思路推演一个重要的特性是，三角形之间不存在交集。观察x+y=k线，我们需要在这选择若干不相交区间。在一维坐标上，我们需要选择若干区间（不同选择有不同成本），最后完全覆盖整个区间。这是一个经典的dp[]做法：dp[x]=y表示覆盖区间[1~x]的最小成本是y。先假设所有点都是单独消除，整体成本目前是sum，设f(l,r)表示x轴l~r三角形覆盖点的成本和 - A*(r-l)。这样就可以把题目转为sum减去若干个不相交的f(l,r)——求若干个不相交的f(l,r)的最大值。dp[x]=y表示处理完所有1~xac核心代码头文件、宏定义、快读模板、常见变量、常见变量等略。 title算法本质题目大意思路推演ac核心代码头文件、宏定义、快读模板、常见变量、常见变量等略。 title算法本质题目大意思路推演ac核心代码头文件、宏定义、快读模板、常见变量、常见变量等略。 title算法本质题目大意思路推演ac核心代码头文件、宏定义、快读模板、常见变量、常见变量等略。 title算法本质题目大意思路推演ac核心代码头文件、宏定义、快读模板、常见变量、常见变量等略。