Educational Codeforces Round 156 (Rated for Div. 2) Decreasing String算法本质思维题目大意给定由小写字母组成的字符串s和正整数p。存在一个空字符串，接下来做如下操作直至s为空：res = res+s删去s的一个字符，保证其删除后尽可能字典序小输出res[p]。思路推演此题的核心是找到每次操作的本质。通过思考可以发现，在每次仅删一个字符且保证删除后字典序小，其就是删除s第一个上升序列的最后一个元素。ac核心代码头文件、宏定义、快读模板、常见变量、常见变量等略。 inline void solve() { string s; int p; cin>>s>>p; n=s.length(); queue<char> q; for (char c:s) q.push(c); q.push('a'-1); // 方便后续 string res; int len=n; while (res.size()==0 || res.back()<=q.front()) // res为s中上升子序列部分 res.push_back(q.front()), q.pop(); while (p > len) { p -= len; len--; res.pop_back(); while (res.size()==0 || res.back()<=q.front()) // 维护res res.push_back(q.front()), q.pop(); } while (q.size()) // 注意这里需要将所有字符都放入res res.push_back(q.front()), q.pop(); char ans = res[p-1]; cout<<ans; return; }Monocarp and the Set算法本质思维题目大意玩家可以构建长度n的排列，初始存在一个长度n-1的字符串s来表示一些规则：s[i] == '>'第i+1个元素大于前i个元素s[i] == '<'第i+1个元素小于前i个元素s[i] == '?'第i+1个元素不能处于以上两种情况接下来有m次询问，每次询问会修改s的某个字符值，每次修改后玩家需要回答符合规则的排列数目。（特别输出没有修改的合法排列数目）思路推演此题思路简单，核心在于认知，模拟过程中会发现，其规则与相对位置息息相关，从这个角度入手在模拟过程中，可以发现，在出现?之前，元素的相对位置是固定的。当第i位出现问号时，则表示已有i个元素相对位置确定，现在需要添加第i+1个元素并且符合?规则，则有i-1种填法。而且当前问好填入后，也可以视作相对位置确定。ac核心代码头文件、宏定义、快读模板、常见变量、常见变量等略。 inline void solve() { string s; cin>>n>>m>>s; s = " " + s; int ans=1; for (int i=2; i<=n-1; i++) if (s[i]=='?') ans *= i-1, ans%=mod; cout<<ans*(s[1]!='?')<<endl; while (m--) { int p; char c; cin>>p>>c; if (s[p]!='?' && c=='?' && p!=1) ans *= p-1, ans%=mod; else if (s[p]=='?' && c!='?' && p!=1) ans *= qpow(p-1, mod-2, mod), ans%=mod; s[p] = c; cout<<ans*(s[1]!='?')<<endl; } return; }I Wanna be the Team Leader算法本质思维、dp题目大意存在n个员工和m个项目，目标完成所有项目，玩家可以按下列规则分配员工：员工有能力值a[]项目有难度值b[]当某个项目的当前项目员工数目 * 当前项目员工中最小能力值 >= 项目难度时，项目可以完成（员工数目不可为0）员工至多去一个项目输出项目的分配情况。n <= 2e5 m <= 20思路推演通过模拟可以知道，员工的顺序无意义，可以将a[]有序排列。然后可以贪心知道，某个项目的最优解一定是选择连续的员工（a[]值相近的），这给dp做法提供了方便。再通过一些细节，可以发现贪心不可行，唯有dp。其中最核心的问题是：无法确定项目解决的顺序。但是m=20这给提供了一个思路——通过状态压缩来无视顺序dp。于是可以构建dp[x]=y表示项目状态x时最少用了a[1~y]。然后枚举当前状态处理的项目即可转移。转移需要O(1)，因为对于某个项目，可能[1~4]和[2~3]两种方式都是可行的，所以需要预处理一下。（详细看代码）还有一个问题是最后需要输出状态，所以维护一下路径方便后续状态的查找。（这个也主要是代码细节）笔者赛时没出，因为把dp的复杂度想成了2^m^ * n，这里以后需要注意。ac核心代码头文件、宏定义、快读模板、常见变量、常见变量等略。 inline void solve() { cin>>n>>m; vector<int> a(n), b(m), rank_id(n); for (int i=0; i<n; i++) cin>>a[i], rank_id[i] = i; for (int i=0; i<m; i++) cin>>b[i]; sort(rank_id.begin(), rank_id.end(), [&](int x, int y) { return a[x] < a[y]; }); vector<vector<int>> to(m+5, vector<int>(n+5, 1e9)); // tor[i][l] = r表示对于第i个项目，如果其使用l作为开始，则最少需要到r for (int i=0; i<m; i++) { for (int l=0; l<n; l++) { int base=a[rank_id[l]]; int len=(b[i] + base - 1) / base; to[i][l] = l + len - 1; } for (int l=n-1; l>=0; l--) // 可能不会选择较小数 to[i][l] = min(to[i][l], to[i][l+1]); } vector<int> dp(1<<m, 1e9); // dp[x]=y表示项目状态x时最少用了前1~y个元素 vector<int> path(1<<m); // path[x]=y表示项目状态x时，上一次搞定的项目下标 dp[0] = -1; // 注意是0下标，所以初始值为-1 for (int i=0; i<1<<m; i++) { if (dp[i]>=n) continue; for (int j=0; j<m; j++) { if (i>>j & 1) continue; // 说明第j项目已经搞定 if (to[j][dp[i]+1] > n) continue; // 超出n了 if (dp[i | (1<<j)] > to[j][dp[i]+1]) { dp[i | (1<<j)] = to[j][dp[i]+1]; path[i | (1<<j)] = j; } } } if (dp[(1<<m) - 1] >= n) { cout<<"NO"<<endl; return; } cout<<"YES"<<endl; vector<vector<int>> ans(m); int v = (1<<m) - 1; while (v) { int id=path[v]; // 处理第id个项目 int val = (1<<id); int u = v ^ val; // u状态 --> v状态 int l=dp[u]+1, r=dp[v]; for (int i=r; i>=l; i--) // 检查第id个项目用了哪些元素 { ans[id].push_back( rank_id[i] ); if (a[rank_id[i]]*(r-i+1) >= b[id]) // 区间[l,r]对第id个项目可行，一定是某个后缀 break; } v = u; } for (auto vv:ans) { cout<<vv.size()<<" "; for (int x:vv) cout<<x+1<<" "; // 题目需要1下标，这里+1 cout<<endl; } return; }title算法本质题目大意思路推演ac核心代码头文件、宏定义、快读模板、常见变量、常见变量等略。 title算法本质题目大意思路推演ac核心代码头文件、宏定义、快读模板、常见变量、常见变量等略。 title算法本质题目大意思路推演ac核心代码头文件、宏定义、快读模板、常见变量、常见变量等略。 title算法本质题目大意思路推演ac核心代码头文件、宏定义、快读模板、常见变量、常见变量等略。

Codeforces Round 905 (Div. 2) 一剑，一念。You Are So Beautiful算法本质思维题目大意定义数组a[]中美丽子数组：a[]有且仅有一个子序列与其相等给定长度n的数组a[]，计数其美丽子数组。思路推演模拟：3 2 1 2 3 1比如其中3 2 1是一种显然不美丽的情况，因为1之后存在1。考虑是否所有数字都要满足身后没有重复的数字。进一步思考，发现对于3 2 1来说，需要保证1是最后一次出现、3是第一次出现。遍历拿下。Dances (Hard Version)算法本质思维题目大意给定长度n的数组a[] b[]，会进行m轮游戏，输出每轮游戏得到值的和。其中仅a[1]在第i轮游戏的值为i，其他信息每轮游戏不会改变。每轮游戏规则：玩家希望顺序执行以下操作，使得最后对于任意i来说都满足a[i]<b[i]：玩家删除k个a[]的元素和k个b[]的元素玩家改变a[]或者b[]元素顺序每轮游戏得到的值是最小化的k。n m <= 2e5 k <= n 元素值 <= 1e9思路推演首先思考每轮游戏如何处理。（即easy版本）显然在排序后，每个删除都会是删除a[]最大值、b[]最小值（最优删除）。那什么时候才算合法，举例：a[]: 1 2 3 4 5 6 7 b[]: 1 1 2 2 3 3 4按照最优删除处理，至少也得删除两次，使得b[1]>a[1]，如此一来，其实我们可以用连线来表示两者的关系。对于a[i]来说，其连线对象是b[]中大于a[i]且没有被占用的最小值。k显然是没有相连的元素个数。接着思考多轮游戏会如何变化。如果我们仅改变一个值，实际上对游戏的影响并不大。首先时候a[2~n]和b[]制作连线图，然后观察b[]未被连线的最大元素，若a[1]的值小于这个最大元素，则可以视作两者相连，反之则可以记作没有相连的元素。这里是一个贪心思路，可能需要仔细思考一下ac核心代码头文件、宏定义、快读模板、常见变量、常见变量等略。 inline void solve() { cin>>n>>m; vector<int> a, b; a.push_back(2e9); // 这里可以给一个无限大或者不给 for (int i=2; i<=n; i++) a.push_back(in()); for (int i=1; i<=n; i++) b.push_back(in()); sort(a.begin(), a.end()); sort(b.begin(), b.end()); // 排序后将其放入双端队列中，需要其取前、取后的功能 for (int x:a) dqa.push_back(x); for (int x:b) dqb.push_back(x); vector<int> sheng; // 记录b[]中没有被占线的元素 int res=0; // 记录删除元素个数 while (1) { int x=dqa.front(); while (dqa.size() && dqb.front()<=dqa.front()) // 如果不合法，则需要删除元素，使用最优删除操作 { sheng.push_back(dqb.front()); dqa.pop_back(), dqb.pop_front(), res++; } if (dqa.size()==0) // 说明已经合法了 break; dqa.pop_front(); dqb.pop_front(); } int top = sheng.back(); // 找到b[]中没有占线元素的最大值 int ans=0; int p=min(top-1, m); ans += p * (res-1); // a[1] = 1~p，其k值是res-1 ans += (m-p) * res; // a[1] = p+1~m，其k值是res cout<<ans<<endl; return; }Time Travel算法本质思维、模拟题目大意（抽象）存在n个点m条无向边，但是m条边分布在t张图中。在这场旅行中一共有k天，玩家希望从点1走至点n，当玩家处于第i天时，仅能使用第a[i]张图的边进行移动。为了方便理解，我们可以视作玩家仅能在白天行动，在第0天的傍晚玩家处于点1处、接着休息了一晚上，第1天清晨仍然处于点1且准备行动。玩家每天行动至多一条边（可以不动）。输出抵达点n的天数（通常来说是傍晚抵达的），或者告知k天内无法抵达。n m k <= 2e5思路推演刚开始看，觉得像传说中的分层图，但是转念一想，cf不会这样出的最短路思想，用dj即可解决。ac核心代码头文件、宏定义、快读模板、常见变量、常见变量等略。 vector<pair<int,int>> g[maxn]; // {w, v} inline void solve() { int t; cin>>n>>t; for (int i=1; i<=t; i++) { cin>>m; while (m--) { int u, v; cin>>u>>v; g[u].push_back({i, v}); // i表示第i张图的边 g[v].push_back({i, u}); } } cin>>k; vector<vector<int>> cod(t+5); // cod[x] = {a, b, c}表示第x张图会在第a、b、c天出现 for (int i=1; i<=k; i++) cod[in()].push_back(i); vector<int> dis(n+5, 1e18), vis(n+5); // 最短路结构 priority_queue<pair<int, int>, vector<pair<int,int>>, greater<pair<int, int>>> q; q.push({0, 1}); // 第0天傍晚抵达点1 dis[1] = 0; while (q.size()) { auto [t, u] = q.top(); q.pop(); if (vis[u]) continue; vis[u] = 1; for (auto [w, v]:g[u]) { auto it = lower_bound(cod[w].begin(), cod[w].end(), t+1); // 第二天清晨，需要w>=t+1 if (it==cod[w].end()) continue; int nt = *it; // 在nt的傍晚抵达点v if (nt < dis[v]) { dis[v] = nt; q.push({dis[v], v}); } } } int ans = (dis[n]<=k ? dis[n] : -1); cout<<ans<<endl; return; }title算法本质题目大意思路推演ac核心代码头文件、宏定义、快读模板、常见变量、常见变量等略。 title算法本质题目大意思路推演ac核心代码头文件、宏定义、快读模板、常见变量、常见变量等略。 title算法本质题目大意思路推演ac核心代码头文件、宏定义、快读模板、常见变量、常见变量等略。 title算法本质题目大意思路推演ac核心代码头文件、宏定义、快读模板、常见变量、常见变量等略。

Codeforces Round 904 (Div. 2) Counting Rhyme算法本质思维题目大意给定n个数字，定义美丽数字对a b：若x满足a%x==0 && b%x==0则x必然不等同于n个数字的某个计数美丽数字对。n <= 1e6 元素 <= n思路推演显然，其实就是gcd(a,b)不能被任意一个存在的数字整除，比如设其为g这里每次运算其实存在3个元素：a b g，我们希望找到gcd(a,b) % g等于0或者不等于0的情况。显然，从a入手是不可行的，题目讲元素大小限制在n，这些行为都在告诉我们，要从g入手。从g入手也面临一些问题，其中最大的问题是重复。观察某个例子：4 2 3 12 4这个例子中，需要考虑g为2 3 4的情况。笔者在赛时对于重复的做法，采取容斥解决（因为其复杂度不会特别高），赛时没写完，赛后发现会T这里实际是巧妙利用了调和级数的复杂度，g也是处于这个限制内的，这点是容易思考错过的。ac核心代码头文件、宏定义、快读模板、常见变量、常见变量等略。 int f(vector<int> &cnt, vector<int> &dp, int idx) { if (dp[idx]!=-1) return dp[idx]; int num=0; for (int i=idx; i<=n; i+=idx) num += cnt[i]; int res = num*(num-1)/2; for (int i=idx*2; i<=n; i+=idx) res -= f(cnt, dp, i); return dp[idx] = res; } inline void solve() { cin>>n; // cnt[x]=y：值为x的元素个数是y // dp[x]=y：有x对元素的gcd值是y // vis[x]=1：元素对的gcd值为x时是不合法的，反之是合法的 vector<int> cnt(n+5), dp(n+5, -1), vis(n+5); for (int i=1; i<=n; i++) cnt[in()]++; f(cnt, dp, 1); // 记忆化搜索处理dp[] int ans=n*(n-1)/2; for (int val=1; val<=n; val++) { if (cnt[val]>0) for (int w=val; w<=n; w+=val) vis[w] = 1; ans -= dp[val] * vis[val]; } cout<<ans<<endl; return; }title算法本质题目大意思路推演ac核心代码头文件、宏定义、快读模板、常见变量、常见变量等略。 title算法本质题目大意思路推演ac核心代码头文件、宏定义、快读模板、常见变量、常见变量等略。 title算法本质题目大意思路推演ac核心代码头文件、宏定义、快读模板、常见变量、常见变量等略。 title算法本质题目大意思路推演ac核心代码头文件、宏定义、快读模板、常见变量、常见变量等略。 title算法本质题目大意思路推演ac核心代码头文件、宏定义、快读模板、常见变量、常见变量等略。 title算法本质题目大意思路推演ac核心代码头文件、宏定义、快读模板、常见变量、常见变量等略。

Codeforces Round 902 (Div. 2) Autosynthesis算法本质思维、图题目大意给定数组a[]，玩家可以顺序圈出任意元素（可以重复圈出某一元素），在某个操作后停止，根据当前局面得到2个数组：v1[]：由a[]没有圈中的元素值顺序构成v2[]：由玩家圈元素的下标顺序构成玩家能否使得上面两个数组相等，如果可以输出相等数组信息（任意一个即可），否则输出-1。思路推演下标与值需要相等，这种问题的经常套路就是连接当前元素和其值下标的元素。为了方便思考，笔者的连接方式是反向的，即当前元素值对应的元素作为元素的父节点。然后在这个基础上思考，有规则：每个点仅存在一个父节点（这比较合理，也是反向连边的原因）抽象题意：思考可知，不用理会圈出元素的顺序，可以将圈出的元素看作涂了黑色，黑色点下的子节点会被默认涂成灰色，则需要满足以下条件：黑子节必须有一个儿子灰节点灰节点的父节点必须是黑节点所有点非黑即灰抽象之后，再次模拟思考，发现如果是链结构，则十分简单，核心难点在于环结构。先用topo处理链结构，这里需要注意自环的情况。接着看环情况。由于规则的限制，有可能一些环的点，必须是黑色，先检查。如果存在这样的点，就可以topo求出环，然后检查是否可行即可。如果不存在，则其所有点性质相同，随机指定一个点赋予颜色即可。赛时因为图写的太少，思路不够清晰（少部分原因在于思路，大部分原因在于图写少了），结果没出来。（不过即可出来了，也其实有一个小bug）ac核心代码头文件、宏定义、快读模板、常见变量、常见变量等略。 int fu[maxn], chu[maxn]; // 父节点、出度 vector<int> g[maxn]; // 仅存儿子节点 int color[maxn]; // 颜色，1代表灰色、2代表黑色 vector<int> tmpv; set<int> tmpst; void dfs(int u) // 找环点 { if (tmpst.count(u)) return; else { tmpv.push_back(u); tmpst.insert(u); dfs(fu[u]); } } int getc(int u) // 根据子节点推理颜色（颜色在子节点都涂色才有效） { int cnt1=0, cnt2=0; for (int v:g[u]) { if (color[v]==1) cnt1++; if (color[v]==2) cnt2++; } return (cnt1>0 ? 2 : 1); // 儿子有灰色，则必黑色，反之黑色 } inline void solve() { cin>>n; for (int v=1; v<=n; v++) { int u=in(); if (u==v) continue; fu[v] = u; g[u].push_back(v); chu[u]++; } flag = 1; // 处理所有的非环点 queue<int> q; for (int i=1; i<=n; i++) if (chu[i]==0) q.push(i); vector<bool> vis(n+5); while (q.size()) // topo处理 { int u=q.front(); q.pop(); vis[u]=1; color[u] = getc(u); chu[fu[u]]--; if (chu[fu[u]]==0 && fu[u]!=0) q.push(fu[u]); } for (int i=1; i<=n; i++) // 检查非环点是否存在冲突 { if (vis[i] && fu[i]==0 && color[i]!=2) flag = 0; } if (!flag) { cout<<-1<<endl; return; } // 处理环上点 for (int i=1; i<=n; i++) { if (vis[i]) continue; tmpv.clear(); tmpst.clear(); dfs(i); int num=0; for (int u:tmpv) { if (getc(u)==2) // 因为还有儿子，如果2值，说明必须是黑色，如果1值则不一定 { color[u]=2; vis[u] = 1; chu[fu[u]]--; num++; } } if (num==0) // 保证环有一个点被打开——才能开始topo { int u=tmpv.front(); color[u] = 2; vis[u] = 1; chu[fu[u]]--; num++; } queue<int> q; for (int u:tmpv) // 找环上的叶节点 { if (vis[u]) continue; if (chu[u]==0) q.push(u); } while (q.size()) // topo跑环 { int u=q.front(); q.pop(); vis[u]=1; color[u] = getc(u); chu[fu[u]]--; if (chu[fu[u]]==0) q.push(fu[u]); } for (int u:tmpv) // 检查环点是否存在冲突 if (getc(u)!=color[u]) flag = 0; } if (!flag) { cout<<-1<<endl; return; } vector<int> ans; for (int i=1; i<=n; i++) { if (color[i]==1) // 灰色 ans.push_back(fu[i]); } cout<<ans.size()<<endl; for (int x:ans) cout<<x<<" "; cout<<endl; return; }title算法本质题目大意思路推演ac核心代码头文件、宏定义、快读模板、常见变量、常见变量等略。 title算法本质题目大意思路推演ac核心代码头文件、宏定义、快读模板、常见变量、常见变量等略。 title算法本质题目大意思路推演ac核心代码头文件、宏定义、快读模板、常见变量、常见变量等略。 title算法本质题目大意思路推演ac核心代码头文件、宏定义、快读模板、常见变量、常见变量等略。 title算法本质题目大意思路推演ac核心代码头文件、宏定义、快读模板、常见变量、常见变量等略。 title算法本质题目大意思路推演ac核心代码头文件、宏定义、快读模板、常见变量、常见变量等略。

Codeforces Round 901 (Div. 2) Jellyfish and EVAEVA，出击！算法本质思维、dp题目大意给定有向图，其中保证边：由编号较小点 指向 编号较大点现在玩家和Alice一起从点1前往点n，玩家和Alice需要各自选择一条出点为当前点的边，Alice会随机选择（且玩家选择前不知道Alice的选择）：选择道路一致玩家和Alice沿着选择边前进选择道路不一致选择的两条道路被破坏输出最大化两人抵达n点的概率。n <= 5e3 m <= 2e5思路推演稍加模拟可以发现，dp做法，需要从后向前推。核心在于，假设前方存在3个点，每个点的胜率不一致，当前玩家应该如何抉择。朴素的想，我们肯定希望尽可能地走胜率高的点，由于Alice的随机选择，核心在于计算出去不同点的概率。稍加模拟，发现并不存在一个简单的计算规律。但是有2个点提醒了玩家，n的范围给的相对奇怪，且每次失败会破坏2条道路。这实际上在提示玩家使用递推的方式去计算走不同点的概率。这里值得一提的是，在赛时，我们力求将走通概率最高的点分配给胜率高的点，实际上在计算走通概率时，完全没有必要。我们可以计算出所有点的走通概率之后，再排序就好。当时思路不够清晰。假设之后存在n个点可走。首先第一个点无论如何选择，其走通概率是1/n，考虑失败的情况，则需要在剩余n-1个点中选择一个点作为同样失败的点。如果第二个点选择的n-1个点中的第x个点，则剩余的n-2个点，就可以套用n-2的情况概率一一对应即可。考虑x的不同还有先前概率等细节，就可以递推求出不同点的概率了。求出之后，倒着dp即可。ac核心代码头文件、宏定义、快读模板、常见变量、常见变量等略。 inline void solve() { cin>>n>>m; vector<vector<double>> pi(n+5, vector<double>(n+5)); // 这里记录了胜率情况 for (int i=1; i<=n; i++) // 递推处理 { double base = 1.0/i; if (i%2) // 奇数层比较特殊，其胜率均分 { for (int j=1; j<=i; j++) pi[i][j] = base; continue; } pi[i][1] = base; int cntl=0, cntr=i-2; for (int j=2; j<=i; j++) // 这里递推公式看着有些复杂，实际不难，可以自行推导 { // cntl cntr表示第j个元素左右元素个数，如果去掉右侧元素，则其对应的为上一层的j-1位置，去掉左侧对应的是j-2位置 pi[i][j] = pi[i-2][j-1]*cntr + pi[i-2][j-2]*cntl; // 这里注意对应关系 pi[i][j] *= base; cntl++, cntr--; } } vector<vector<int>> g(n+5), g2(n+5); // g2记录反向图 vector<int> chu(n+5); vector<double> dp(n+5); while (m--) { int u, v; cin>>u>>v; g[u].push_back(v); g2[v].push_back(u); chu[u]++; } dp[n] = 1; queue<int> q; for (int i=1; i<=n; i++) if (chu[i]==0) q.push(i); while (q.size()) { int u=q.front(); q.pop(); int num = g[u].size(); vector<double> nxt; // 下一个点的胜率 for (int v:g[u]) nxt.push_back(dp[v]); sort(nxt.begin(), nxt.end()); nxt.push_back(0); // 维持1下标 reverse(nxt.begin(), nxt.end()); // 胜率大的在前 for (int i=1; i<=num; i++) // 当前点的胜率 = 选择下一个点的概率 * 下一个点的胜率 dp[u] += pi[num][i]*nxt[i]; for (int v:g2[u]) // 倒着向前topo { chu[v]--; if (chu[v]==0) q.push(v); } } double ans = dp[1]; cout<<fixed<<setprecision(12)<<ans<<endl; return; }title算法本质题目大意思路推演ac核心代码头文件、宏定义、快读模板、常见变量、常见变量等略。 title算法本质题目大意思路推演ac核心代码头文件、宏定义、快读模板、常见变量、常见变量等略。 title算法本质题目大意思路推演ac核心代码头文件、宏定义、快读模板、常见变量、常见变量等略。 title算法本质题目大意思路推演ac核心代码头文件、宏定义、快读模板、常见变量、常见变量等略。 title算法本质题目大意思路推演ac核心代码头文件、宏定义、快读模板、常见变量、常见变量等略。 title算法本质题目大意思路推演ac核心代码头文件、宏定义、快读模板、常见变量、常见变量等略。