Codeforces Round 889 (Div. 2) C2.Dual (Hard Version)算法本质题目大意思路推演ac核心代码头文件、宏定义、快读模板、常见变量、常见变量等略。 D.Earn or Unlock算法本质思维、dp、bitset优化题目大意给定顺序n张卡牌，初始时玩家默认获得第一张卡牌（剩余的n-1张卡牌在牌堆）。每张卡牌有数字x[i]，玩家的操作有且仅有两种方式使用手中的卡牌：加分：消耗掉一张卡牌，积分增加x[i]无中生有：消耗掉一张卡牌，获得牌堆最上方的x[i]张卡牌（若牌堆剩余数<x[i]，则全部拿走）输出最大化的积分。n <= 1e5 x[i] <= n思路推演贪心地想，什么情况能获得最多积分——手牌一定要用完，即拿到i张牌，得分是固定的：pre[i] - (i-1)。（pre[]是x[]的前缀和数组）现在问题在于，如何鉴定是否能恰好抵达某个点。手牌选择、价值、恰好抵达某个状态，这其实比较类似01背包，但是有所不同。以上的题面稍显复杂，适合用dp，暂时抛弃复杂度的考虑，思考dp能否求得某个点是否能恰好抵达。dp[i][j]表示使用前i张牌，能否恰好抵达j转移方程也比较好写：继承：dp[i][j] |= dp[i-1][j]使用x[i]：dp[i][j] |= dp[i-1][j-x[i]]但是同理，这样复杂度太高了，但是这又是布尔类型的dp，思考能否用bitset的位运算思想进行优化。既然要用bitset优化复杂度，则必须以x[i]为单位，而非点：bit[]表示当前点能否恰好抵达。于是自然得出了使用时的转移方程：bit |= bit<<x[i]，但是这样也存在问题，就是许多原本无法恰好变成了可行。可以测试这组数据：41 2 0 0原本无法恰好拿3张牌，但是用以上的转移方程可行。观察原因，发现本质是，是因为在对第i张牌做转移时，其bit[<i]的情况也会被转移，但是实际上那些情况都无法抵达i，就不存在说用x[i]作为手牌进行转移了。所以只需要忽略前部分的即可，只需要每次转移后消除当前bit[i]的记录就好。同时还有一个小问题，如果将所有卡牌都取完，拿得分不一定是pre[n]-(n-1)，考虑到x[i]的值<=n，所以可以将牌堆底部扩展n张x[]为0的卡牌，这样就能保证得分规则一定是pre[i]-(i-1)。ac核心代码头文件、宏定义、快读模板、常见变量、常见变量等略。 int a[maxn], pre[maxn]; inline void solve() { cin>>n; rep(i,1,n) cin>>a[i], pre[i]=pre[i-1]+a[i]; for (int i=n+1; i<=2*n; i++) a[i]=0, pre[i]=pre[i-1]+a[i]; // 牌堆底部添加n张0价值卡牌 bitset<200005> bit; // bit[i]表示[1~i]个卡牌，能否有组合恰好抵达i位置 bit.set(1); // 系统免费送第一张卡牌 int ans = 0; for (int i=1; i<=2*n; i++) { if (bit.test(i)) // 说明当前点可恰好达 ans = max(ans, pre[i]-i+1); // 则计算价值 bit |= bit<<a[i]; // i-1回合可达的点，这次经过a[i]能达的更多点 bit.reset(i); // 删除当前的点的可达值，详细看题解解释 } cout<<ans<<endl; return; }title算法本质题目大意思路推演ac核心代码头文件、宏定义、快读模板、常见变量、常见变量等略。 title算法本质题目大意思路推演ac核心代码头文件、宏定义、快读模板、常见变量、常见变量等略。 title算法本质题目大意思路推演ac核心代码头文件、宏定义、快读模板、常见变量、常见变量等略。 title算法本质题目大意思路推演ac核心代码头文件、宏定义、快读模板、常见变量、常见变量等略。 title算法本质题目大意思路推演ac核心代码头文件、宏定义、快读模板、常见变量、常见变量等略。

Codeforces Round 884 (Div. 1 + Div. 2) A.Subtraction Game算法本质模拟题目大意Alice和Bob玩取石子游戏，Alice先取，每回合每个人只能取a或b个石头，无法行动则失败。规定初始的石子数（大于0），在双方智力在线的情况下，保证Bob能赢。思路推演这与传统的取石子游戏有所区别，能取的值只能是a b。首先想到的就是，能不能让Alice取不了，即<min(a, b)。若a==1，则考虑选2，这样一人取一个就好。但是考虑b==2的特殊情况：选3即可。B.Permutations & Primes算法本质思维题目大意需要玩家构建长度n的排列p[]，每个区间若其MEX()值为素数，则得分+1。输出构建最高得分的p[]。思路推演素数先枚举几个：2、3、5、7、……考虑MEX值，而且还是区间考虑，所以基本只用考虑前几个数的位置即可。首先思考的区间必须包含1，最大化可行区间数，把1放在中间，同时不希望2、3同区间，这样会可能出现4值。一个朴素的思想——将2、3至于两侧，这样仅有一个区间的值为4。C.Particles算法本质思维题目大意给定数组a[]信息，执行若干次操作直到a[]仅剩一个元素：选择某个元素删除，相加合并两侧第一个元素（若在边缘则不合并）输出最大化的剩余元素值。思路推演手动模拟，即可发现元素之间只能合并取决于其奇偶下标，同一奇偶性下标的元素一定能合并。同时，其奇偶性下标合并时，也可以删除任意元素。所以只需要相加奇/偶下标的所有正数即可。（若无任何正数，输出最大值即可）ac核心代码头文件、宏定义、快读模板、常见变量、常见变量等略。 int a[maxn]; inline void solve() { cin>>n; rep(i,1,n) cin>>a[i]; int maxval = *max_element(a+1, a+1+n); if (maxval <= 0) { cout<<maxval<<endl; return; } int sum[2] = {0}; for (int i=1; i<=n; i++) if (a[i]>0) sum[i%2] += a[i]; int ans = max(sum[0], sum[1]); cout<<ans<<endl; return; }D.Row Major算法本质思维题目大意玩家需要构建长度n的小写字母字符串s，保证：若存在a*b==n，将s从左至右从上至下写入a*b的矩形，保证任意相邻的字符不能相等输出s。思路推演a b即n的约数，每个约数表示两个字符不相等的关系，这是典型的图论。但是不能用经典图论来做，因为其边数过大。但是这些边的距离固定，较好计算。获得n的所有约数，逐个遍历下标，当i下标选择c值时，其i+约数下标无法选择c值，标记一下即可。（也可以反过来，i下标无法选择i-约数的值）这时可以发现，所有的字符都是与相同距离的字符存在不相等关系（约数距离），而循环数组通过设定好循环节，完美符合这个要求。找到最小非n约数值x，因为其非n约数，能保证相邻距离为x的字符无关系——即可以相等。 以x作为循环节，有且仅有相距x倍数的字符相等，符合要求。 （这也解释了26个字母保证有解的原因）ac核心代码 - 朴素做法头文件、宏定义、快读模板、常见变量、常见变量等略。 int ans[maxn]; bool vis[maxn][30]; inline void solve() { cin>>n; vector<int> v; // 存放约数 for (int i=1; i<=n; i++) { if (n%i==0) v.push_back(i); fill(vis[i], vis[i]+30, 0); // 清空 } for (int i=1; i<=n; i++) { int val=1; while (vis[i][val]) // 找到可选的val val++; ans[i] = val; for (int x:v) // 对之后的i+x位置做出限制 if (i+x <= n) vis[i+x][val] = 1; } for (int i=1; i<=n; i++) cout<<(char)(ans[i]+'a'-1); cout<<endl; return; }ac核心代码 - 极致优化头文件、宏定义、快读模板、常见变量、常见变量等略。 inline void solve() { cin>>n; int yue=1; while (n%yue==0) // 找到第一个非n约数的数，作为循环节长度 yue++; string ans; for (int i=1; i<=n; i++) ans.push_back('a'+i%yue); cout<<ans<<endl; return; }E.Great Grids算法本质思维题目大意给定n*m的方格，存在3个基础规则：每个方格仅能填a b c某个字符任意2*2的方格需要包含3个种类的字符任意相邻方格字符不许相同接下来给定k个特殊要求：每个特殊要求会给定x轴、y轴距离差都为1的两个点，要求这两个点字符一致判断是否存在满足所有要求的图。n m k <= 4e3思路推演 - 1 - 需求入手观察样例，特别是样例4，这意味着特殊要求肯定能产生影响并可传递（不然无法在相对远的地方判断不行）。所以寻找可传递的影响，然后模拟也可以发现，其传递是通过行列传播的，观察行列传播的特点。随机选一组数据，向下延申，仅有2种可能：1 3 3 2 1 3 1 3 3 2 3 2 1 3 2 1继续延申，发现会有重复，其这两列只有：1 3+3 2+2 1这三种情况。继续模拟研究，发现是最上方的1 3决定的，与主/副对角线相等无关。称1 3+3 2+2 1为第一组情况，3 1+2 3+1 2为第二组情况，若某行的两列是第一组情况，则任意行的这两列都是第一组情况（只要保证相邻行不重复即可）。第一组和第二组的区别也可提取出来，即左元素 + x = 右元素。当某个2*2方格要求主对角线一致时，其行列必须是不同组的情况，反之要求副对角线一致，其行列必须是相同组的情况。所以可以把i列 i+1列看成a组的点，i行 i+1行看成b组的点，k个要求看作k条边，每条边分别连接ab组点，要求这两个点的值相同或者不同。检测是否存在满足条件的图。思路推演 - 2 - 性质入手给出的多个性质都是2*2的矩形性质，所以可以将其为单位思考，2个2*2之间可以看作其的关系。将n*m的原矩阵，看作(n-1)*(m-1)的新矩阵。若主对角线用0表示，副对角线用1表示，新矩阵的2*2仅有4种可能：01 01 00 00 01 10 00 11若存在0 0 0 1的情况，会失败。继续模拟，可以发现，若（新矩阵）第一行确定了，则随后的行只能与其值保持一致或者反转（01互换）。先以每列为点，若某一行的i j列分别有初值：1 0，这表示i j列必然是相反的两列，使用带权并查集标记相反。依次类推，如果发现冲突则表示不可行。ac核心代码 - 1 - 需求入手头文件、宏定义、快读模板、常见变量、常见变量等略。 // 带权并查集板子省略 inline void solve() { cin>>n>>m>>k; flag = 1; // 表示可行 DSU dsu(n+m, 2); // 1~n-1是行代表的点，n+1~n+1+m-1是列代表的点 while (k--) { int x1, y1, x2, y2; cin>>x1>>y1>>x2>>y2; if (y1 > y2) { swap(x1, x2); swap(y1, y2); } int x=x1, y=y1; // 定义2*2的左上角 if (x1>x2) // 副对角线，两者需要相同 { x--; if (dsu.same(x, n+y) && dsu.val[x]!=dsu.val[n+y]) // 如果两者已经被保证不同了 flag=0; dsu.merge(x, n+y, 0); } else // 主对角线，两者需要不同 { if (dsu.same(x, n+y) && dsu.val[x]==dsu.val[n+y]) flag=0; dsu.merge(x, n+y, 1); } } cout<<(flag ? "YES" : "NO")<<endl; return; }ac核心代码 - 2 - 性质入手头文件、宏定义、快读模板、常见变量、常见变量等略。 // 带权并查集板子省略 写wa了，但是理论是对的，给一篇别人的https://zhuanlan.zhihu.com/p/643164860: #include <bits/stdc++.h> #define rep(i,a,b) for(int i=(a);i<=(b);++i) #define pb push_back using namespace std; const int N = 4e3 + 10; int par[N]; inline int find(int x) { return x == par[x] ? x : par[x] = find(par[x]); } void merge(int x, int y) { x = find(par[x]), y = find(par[y]); if(x == y) return ; par[x] = y; } struct node { int x, val; }; signed main() { if(fopen("yl.in", "r")) { freopen("yl.in", "r", stdin); freopen("yl.out", "w", stdout); } ios::sync_with_stdio(false); cin.tie(NULL); int T; cin >> T; while(T --) { int n, m, k; cin >> n >> m >> k; vector<vector<node>> vec(m); -- n, -- m; rep(i,1,n << 1) par[i] = i; int a, b, c, d; rep(i,1,k) { cin >> a >> b >> c >> d; if(a + 1 == c && b + 1 == d) { vec[b].pb({a, 1}); } else { vec[d].pb({a, 2}); } } rep(i,1,m) { int sz = vec[i].size(); rep(j,1,sz - 1) { if(vec[i][j].val == vec[i][0].val) merge(vec[i][0].x, vec[i][j].x), merge(vec[i][0].x + n, vec[i][j].x + n); else merge(vec[i][0].x, vec[i][j].x + n), merge(vec[i][0].x + n, vec[i][j].x); } } bool flg = true; rep(i,1,n) { if(find(i) == find(i + n)) { flg = false; break; } } cout << (flg ? "YES" : "NO") << endl; } return 0; }title算法本质题目大意思路推演ac核心代码头文件、宏定义、快读模板、常见变量、常见变量等略。 title算法本质题目大意思路推演ac核心代码头文件、宏定义、快读模板、常见变量、常见变量等略。

Codeforces Round 880 (Div. 2) Lottery算法本质思维题目大意（略微抽象）初始存在玩家和另外n个人参加彩票游戏，每个人可以在[0~m]中选择一个数字，随后会公布其中随机的一个数字作为中奖值，最靠近中奖值的k个人会获奖：玩家在同等情况下处于劣势：当玩家选择3，另一人选择7，中将数字是5时，另一人的中将优先级更高作为玩家，在公布中奖值前你已经拿到了其他n人选择的数字，做出最优解选择——若多个最优解，选择最小的数字。输出选择可以覆盖的中奖值数目、选择的数字。n k <= 1e6 m <= 1e18思路推演这个复杂度明确告诉我们，以数字为单位思考不可行，必须以人为单位思考，顺其自然的发现，其编号无意义，将其按大小排列后审视。既然是以人为单位，以样例1为例子1 3 4为例子，一种朴素的想法就是：O(1)计算出[0, 1)的最佳值、O(1)计算出[1, 3)的最佳值……假设我们选择x值，则尝试计算可以覆盖的中奖值数目，显然那需要是一个区间，思考区间的左右值由什么确定。对于区间左端点而言，一定是x值恰好为k个最近值的最右边的值。假设k=3，现在x在v[7]和v[8]之间（不含端点）左端点其实可以视作x和v[5]的争夺，同理右端点可以视作x和v[10]的争夺，如果x为某个具体的数字的话，可以相对简单的计算出左右端点的值（这里会得到一个简单的公式）。但是x是处于某个范围的，观察公式可以发现，如果x在范围内移动偶数的距离，右端点-左端点+1的结果会保持不变，考虑题目喜欢最小的值，所以我们可以只考虑x=v[7]+1和x=v[7]+2的情况，当然需要保证x<v[8]。然后再特殊考虑x=v[i]的情况。综合来看，写一个函数，可以通过位置求得覆盖个数。ac核心代码（还没过）头文件、宏定义、快读模板、常见变量、常见变量等略。 title算法本质题目大意思路推演ac核心代码头文件、宏定义、快读模板、常见变量、常见变量等略。 title算法本质题目大意思路推演ac核心代码头文件、宏定义、快读模板、常见变量、常见变量等略。 title算法本质题目大意思路推演ac核心代码头文件、宏定义、快读模板、常见变量、常见变量等略。 title算法本质题目大意思路推演ac核心代码头文件、宏定义、快读模板、常见变量、常见变量等略。 title算法本质题目大意思路推演ac核心代码头文件、宏定义、快读模板、常见变量、常见变量等略。 title算法本质题目大意思路推演ac核心代码头文件、宏定义、快读模板、常见变量、常见变量等略。

Codeforces Round 879 (Div. 2) title算法本质题目大意思路推演ac核心代码头文件、宏定义、快读模板、常见变量、常见变量等略。 Survey in Class算法本质思维题目大意存在m道题目、n个同学，每个同学会做的题目恰好能做l[i] ~ r[i]的题目。现在老师可以出若干道题（每种题至多出一次），若遇到不会做的题，同学分数-1，反之+1。输出最大化的同学分数差。思路推演最大的同学分数差，即最高分-最低分。枚举任意2个同学，其分数区间用AB表示，分数差最大可以表示为：A - A∩B。思维惯性可以想到，使用某种排序，可以在局部优化部分。比如以左-右端点排序，如果相交的线段不存在包含的情况，则确实有序，但是包含的情况计算方式不一样，无法排序。处理这点核心还是在于最大分数差这个思路的核心，对于某个区间来说，若其为最高分，那最低分的选择，最好是那种毫不相关的——交集为0，这个可以通过检查排序后两侧的区间来实现。包含的情况，交集至少就是低分区间本身长度，其越短越好，所以我们可以直接检查最短的区间，特判其和当前区间的情况（无论包含、相交、无交集），可以保证的是，任意其他包含区间的情况都非最优解。至此我们就可以用排序的方式解决问题，但是这里答案提供了一个优雅至极的方式：在遍历高分区间的基础上考虑高分区间和低分区间是包含的情况直接计算len(高分区间) - len(低分区间)，这样相当于计算了所有包含区间的值其他情况找到最大的l端点和最小的r端点ac核心代码头文件、宏定义、快读模板、常见变量、常见变量等略。 inline void solve() { cin>>n>>m; int maxl=0, minr=m, len=1e9; vector<pair<int, int>> v; for (int i=1; i<=n; i++) { int l, r; cin>>l>>r; v.push_back({l, r}); maxl = max(maxl, l); minr = min(minr, r); len = min(len, r-l+1); } int ans=0; for (auto [l,r] : v) { int res = max(max(r-minr, maxl-l), r-l+1-len); res = min(res, r-l+1); ans = max(ans, res); } ans *= 2; cout<<ans<<endl; return; }MEX of LCM算法本质思维题目大意给定长度n的数组a[]，任意区间的最小公倍数放入set，求得set的mex值。n <= 3e5思路推演求mex值，总方法有2：从1开始遍历，直到某个元素发现无法求解计算某个数字是否可行，至少需要log复杂度计算出所有元素，找到mex值显然第二个方法可行度高一些，但是朴素来说一共有n^2^的元素个数，复杂度不行，接下来就需要找到lcm的特征来优化。对于一个区间，若其扩展，其lcm值不一定发生变化，若固定某个端点，另一次延申，则至多有log(A)个lcm值。这告诉我们，此题的最优算法复杂度可达O(nlogn)，接下里就是去优化。假如顺序遍历，固定左端点，右侧存在log个lcm值，但是左端点移动时，信息并不能充分利用。如果固定右端点，左侧存在log个lcm值，移动右端点，其可以较好复用。ac核心代码头文件、宏定义、快读模板、常见变量、常见变量等略。 inline void solve() { cin>>n; vector<int> a(n+5); int top = n*n; for (int i=1; i<=n; i++) cin>>a[i]; set<int> st, pre; for (int i=1; i<=n; i++) // 枚举右端点 { set<int> now; st.insert(a[i]); // 新增的情况 now.insert(a[i]); for (auto x:pre) // 继承的情况 { int y=lcm(x, a[i]); if (y > top) continue; // 过大的数字会爆且其没有意义 st.insert(y); now.insert(y); } pre = now; } int ans=1; while (st.count(ans)) ans++; cout<<ans<<endl; return; }title算法本质题目大意思路推演ac核心代码头文件、宏定义、快读模板、常见变量、常见变量等略。 title算法本质题目大意思路推演ac核心代码头文件、宏定义、快读模板、常见变量、常见变量等略。 title算法本质题目大意思路推演ac核心代码头文件、宏定义、快读模板、常见变量、常见变量等略。 title算法本质题目大意思路推演ac核心代码头文件、宏定义、快读模板、常见变量、常见变量等略。

Codeforces Round 877 (Div. 2) Bracket Walk算法本质思维、数据结构题目大意给定一个括号串s，现在存在m个询问：每次询问会给出一个下标p，使得s[p]的括号反转（继承不消除影响）然后询问，玩家从s头走到尾，走过的路程组成新括号串t，能否有方式使得t合法n m <= 2e5思路推演 - 朴素模拟先思路，对于固定的s，如何情况才能有解：显然，s长度是奇数时不可能有解。然后发现，当多个相同的字符出现时，其数目可以视作增加任意偶数。例如(()))的字符串就可以视作还剩余奇数个(。随后可以发现，对于第一次出现的多个)之前，必须存在多个(来使其合法同理，最后一次出现的多个(之后，必须存在多个)使其合法首尾特判一下上述的规律相对容易好找，而且因为保证了长度是偶数，所以不会存在剩余奇数个(或)的情况。 这里麻烦的地方在于需要维护的东西：连续出现的(位置连续出现的)位置为了维护以上东西并且支持动态修改，又必须得维护单个括号的位置——常用set维护某个字符的区间范围，辅助函数保证其增加（包括融合）、减少。在这个基础上，再维护连续出现的字符位置。整体难度不大，相当于模拟题了，需要思路清晰。思路推演 - 巧取核心这个思路由作者提供，没有什么思路过程，但是解题方法还算巧妙维护连续出现的(和)，核心其实仅需第一次出现(和)的位置，还有最后一次出现的位置。通过观察可以发现，如果不存在连续相同字符，则(一定出现在奇数下标、)出现在偶数下标，我们可以定义如何位置是合法，反之是违法。连续相同字符必然存在违法行为（首尾也顺便特判了），我们只需要检查第一个违法行为是(还是)、最后一个违法行为是(还是)即可。同时，因为反转操作也十分容易维护——消除违法或者新增违法即可。ac核心代码 - 朴素模拟笔者这里都使用的set维护，也有方法使用线段树来维护的。头文件、宏定义、快读模板、常见变量、常见变量等略。 set<pair<int, int>> st[2]; // st[0]表示(所占的区间 set<int> cod[2]; // cod[0]表示连续(所占的区间，只存左端点即可 void jia(int l, int r, int id) // 向cod[id]加入区间[l,r] { if (r-l+1 <= 1) return; cod[id].insert(l); } void diu(int l, int id) // cod[id]删除以l为左端点的区间 { cod[id].erase(l); } void add(int l, int r, int id) // 向st[id]加入[l,r]的区间 { if (l>r) return; jia(l, r, id); st[id].insert({l, r}); // 每个st[id]的insert，必须伴随jia()函数 auto it = st[id].lower_bound({l,r}); if (it!=st[id].begin() && prev(it)->second==l-1) // 检查能否和左边区间合并 { l = prev(it)->first; diu(prev(it)->first, id); st[id].erase(prev(it)); } if (next(it)!=st[id].end() && next(it)->first==r+1) // 检查能否与右边区间合并 { r = next(it)->second; diu(next(it)->first, id); st[id].erase(next(it)); } diu(it->first, id); st[id].erase(it); jia(l, r, id); st[id].insert({l,r}); } void del(int x, int id) { auto it = st[id].upper_bound({x, 1e9}); if (it==st[id].begin()) return; it = prev(it); // 找到x所在的区间 auto [l, r] = *it; if (r<x) return; diu(it->first, id); // 分裂 st[id].erase(it); add(l, x-1, id); add(x+1, r, id); } inline void solve() { string s; cin>>n>>m>>s; for (int i=0; i<n; i++) { if (s[i]=='(') add(i, i, 0); else add(i, i, 1); } while (m--) { int p=in(); p--; // 0下标 if (s[p]=='(') { s[p] = ')'; del(p, 0); add(p, p, 1); } else { s[p] = '('; del(p, 1); add(p, p, 0); } flag = 1; if (s[0]==')' || s[n-1]=='(') // 首尾特判 flag = 0; if (n%2==1) // 长度奇数特判 flag = 0; // 第一个连续)前方必须有连续的(守护 if (cod[1].size() && (cod[0].size()==0 || (*cod[1].begin()) < (*cod[0].begin()) )) flag = 0; // 最后一个连续的(后方必须有连续的)守护 if (cod[0].size() && (cod[1].size()==0 || (*cod[0].rbegin()) > (*cod[1].rbegin()) )) flag = 0; cout<<(flag ? "YES" : "NO")<<endl; }title算法本质题目大意思路推演ac核心代码头文件、宏定义、快读模板、常见变量、常见变量等略。 title算法本质题目大意思路推演ac核心代码头文件、宏定义、快读模板、常见变量、常见变量等略。 title算法本质题目大意思路推演ac核心代码头文件、宏定义、快读模板、常见变量、常见变量等略。 title算法本质题目大意思路推演ac核心代码头文件、宏定义、快读模板、常见变量、常见变量等略。 title算法本质题目大意思路推演ac核心代码头文件、宏定义、快读模板、常见变量、常见变量等略。 title算法本质题目大意思路推演ac核心代码头文件、宏定义、快读模板、常见变量、常见变量等略。