Codeforces Round 875 (Div. 2) The BOSS Can Count Pairs算法本质思维题目大意给定长度n的数组a[] b[]，其元素范围是[1~n]。输出其中满足a[i]*a[j]==b[i]+b[j] && i<j的情况数。时间限制 4s n <= 2e5思路推演观察时限大概是n^1.5^的复杂度，观察元素范围，表示需要用类似桶排序的方式。题目条件给的很少，所以可以直接挨个尝试：b[i] = a[i]*a[j] - b[j]a[i] = (b[i]+b[j]) / a[j]这两个式子转换后并无法求解，但是其指出a[i]和a[j]的值不会特别大——其乘积不超过2n，结合复杂度，猜测是暴力+对取值限制。a[i]和a[j]的小值一定小于sqrt(2n)，则可以维护f[x][y]=z：表示a[]值为x、b[]值为y的对数有z个，同时只记录x <= sqrt(2n)的情况。然后遍历即可，注意考虑a[]相等、a[] b[]都相等的情况。ac核心代码注意，内存和时间都卡的比较极限，时间上用数组O(1)查询、内存上不能开全局longlong，给答案开即可。头文件、宏定义、快读模板、常见变量、常见变量等略。 inline void solve() { cin>>n; int top = sqrt(2*n)+1; vector<int> a(n+5), b(n+5); vector<vector<int>> mp(top+1, vector<int>(n+1)); rep(i,1,n) cin>>a[i]; rep(i,1,n) { cin>>b[i]; if (a[i] <= top) mp[a[i]][b[i]]++; } long long ans=0; for (int i=1; i<=n; i++) // 考虑不同a[]情况 { int v1=a[i]; for (int v2=1; v2<=min(v1-1, top); v2++) { int z = v1*v2-b[i]; if (z>=0 && z<=n) ans += mp[v2][z]; } } long long res=0; for (int i=1; i<=n; i++) // 考虑相同的a[]情况 { if (a[i]>top) continue; if (a[i]*a[i] == 2*b[i]) // 考虑相同b[]情况 res += mp[a[i]][b[i]]-1; else if (a[i]*a[i]-b[i]>=0 && a[i]*a[i]-b[i]<=n) res += mp[a[i]][a[i]*a[i]-b[i]]; } res /= 2; ans += res; cout<<ans<<endl; return; }Hyperregular Bracket Strings算法本质思维题目大意由玩家构建长度n的正则括号序列，且满足题目给出的m个条件：每个条件会指定l r，要求[l~r]也是正则括号序列输出可行的方案数。思路推演正则括号序列，与卡特兰数有关。主要思考不同区间之间的关系。如果两个区间有交集，可以简单证明出其交集也必然是正则括号序列。但如果是包含关系，那相对来说复杂一些，比如有某个大区间[1~10]，现在有2个被包含的小区间[1~4]和[7~8]，则剩余4个空间也需要是正则括号序列。以上规律推理相对简单，但是笔者没有想到实现部分的代码，下面是作者思路观察其本质发现，其核心在于某个点被哪些线段覆盖，如果多个点被覆盖的线段一致，则其需要构成正则括号序列。这可以用hash来搞定，同时搭配线段树即可。当然线段树只是一种思考方式，随后就发现因为本身需要遍历结果，所以用一个差分数组即可维护。ac核心代码关于这道题，我们只关心hash最后的值是否相同，所以需要取模足够大，这时可以用unsigned long long，会自动减去超出部分，再配合随机数即可。头文件、宏定义、快读模板、常见变量、常见变量等略。 int f[maxn]; mt19937_64 rnd(random_device{}()); uniform_int_distribution<unsigned long long> dist(0, ULLONG_MAX); // 生产ull范围内任意一个随机数 inline void solve() { cin>>n>>m; vector<unsigned long long> v(n+5); while (m--) { int l, r; cin>>l>>r; unsigned long long w=dist(rnd); v[l] += w; // 差分计算 v[r+1] -= w; } map<unsigned long long, int> mp; // 计算不同类型的点的数目 unsigned long long now=0; for (int i=1; i<=n; i++) { now += v[i]; mp[now]++; } int ans=1; for (auto [val, cnt] : mp) { if (cnt%2) ans = 0; // 不可行 else ans = ans * f[cnt/2] % mod; } cout<<ans<<endl; return; } inline void solve_init() { f[0] = 1; for (int i=1; i<=3e5; i++) // 预处理卡特兰数 f[i] = (4*i-2) * f[i-1] % mod * qpow(i+1, mod-2, mod) % mod; return; }title算法本质题目大意思路推演ac核心代码头文件、宏定义、快读模板、常见变量、常见变量等略。 title算法本质题目大意思路推演ac核心代码头文件、宏定义、快读模板、常见变量、常见变量等略。 title算法本质题目大意思路推演ac核心代码头文件、宏定义、快读模板、常见变量、常见变量等略。 title算法本质题目大意思路推演ac核心代码头文件、宏定义、快读模板、常见变量、常见变量等略。 title算法本质题目大意思路推演ac核心代码头文件、宏定义、快读模板、常见变量、常见变量等略。

Codeforces Round 872 (Div. 2) LuoTianyi and the Floating Islands (Hard Version)算法本质思维题目大意存在长度n的树（边权都是1），现在随机选择k个点建立房子。定义中点：点到所有房子的距离之和最短输出中点个数的期望值。思路推演若某条边，两侧的房子数不相等，则一定会向更大数目的一侧移动。这里也可以看出，若k是奇数，则中点一定在某个房子那，所以答案必定是1。偶数则任何情况都不止1个点，因为其形式上的对称。继续思考中点的本质：周围任意子树的点数$<= \frac{k}{2}$但是如果挨个点看待，这是一个至少目前无法解决的组合数问题。回想条件，实际上奇数已经被求得，偶数并没有，能否用边的视角去看待问题。如果希望这条边是可行的，则其两侧的点必须都是k/2：这意味着可行的边是一条链意味可行点数 = 可行边数+1所以我们仅需寻找可行的边数即可，以边的视角来看待问题，随后问题变得异常简单。ac核心代码头文件、宏定义、快读模板、常见变量、常见变量等略。 // 省略组合数板子极其初始化 int ans=0; vector<int> g[maxn]; int dfs(int u=1, int ft=0) { int res=1; for (int v:g[u]) { if (v==ft) continue; res += dfs(v, u); } ans += C(res, k/2) * C(n-res, k/2); ans %= mod; return res; } inline void solve() { cin>>n>>k; for (int i=1; i<=n-1; i++) { int u, v; cin>>u>>v; g[u].push_back(v); g[v].push_back(u); } if (k%2) // 奇数特判 { cout<<1<<endl; return; } dfs(); // 这里的+1很关键，根据推测，每种情况下，可行点 = 可行边+1 ans = ans * qpow(C(n, k), mod-2, mod) + 1; ans %= mod; cout<<ans<<endl; return; }title算法本质题目大意思路推演ac核心代码头文件、宏定义、快读模板、常见变量、常见变量等略。 title算法本质题目大意思路推演ac核心代码头文件、宏定义、快读模板、常见变量、常见变量等略。 title算法本质题目大意思路推演ac核心代码头文件、宏定义、快读模板、常见变量、常见变量等略。 title算法本质题目大意思路推演ac核心代码头文件、宏定义、快读模板、常见变量、常见变量等略。 title算法本质题目大意思路推演ac核心代码头文件、宏定义、快读模板、常见变量、常见变量等略。 title算法本质题目大意思路推演ac核心代码头文件、宏定义、快读模板、常见变量、常见变量等略。

Educational Codeforces Round 151 (Rated for Div. 2) A.Forbidden Integer算法本质分类讨论题目大意给定n k x三个数字，需要你用任意个1~k中除去x的的数相加为n。输出方案。思路推演显然，当x不为1时，直接用n个1即可。当x为1时，考虑大部分情况，有2、3就可以处理所有n非1的情况。再考虑只有2的情况。x!=1可行，全用1x==1k==1不可行k==2若n为偶数可行k>=3若n为>1的数可行B.Come Together算法本质思维题目大意在方格地图上给定3个点，其中Alice和Bob从点1出发，分别以最短路径走向点2、点3。输出最大化的重叠路径。思路推演显然，这与点的绝对坐标无关，点2、点3减去点1得到相对位置。方格地图，走只能是水平或者竖直。若x方向上，点2、点3方向一致，则可以一起走$min(|x2|, |x3|)$，y同理。C.Strong Password算法本质思维题目大意是否存在一个长度m由数字组成的密码ans[]，满足下列条件：l[i] < ans[i] < r[i]ans[]不能是s[]的子序列思路推演需要玩家在满足l[] r[]条件的同时，跳出s[]。对于ans[i]，有r[i]-l[i]+1种字符可能：若s[]对某个字符无法匹配，判断可行若s[]对所有字符匹配，以步步最优解的思想来看，我们应该选择第一次匹配下标靠后的字符ac核心代码int f(int pos, char cl, char cr) { set<char> st; for (int i=pos; i<s.length(); i++) { if (s[i]<cl || s[i]>cr) continue; st.insert(s[i]); if (st.size()==cr-cl+1) return i; } return -1; } inline void solve() { string l, r; cin>>s>>n>>l>>r; int last=0; flag=0; for (int i=0; i<n; i++) { last = f(last, l[i], r[i]); if (last==-1) flag=1; last++; } cout<<(flag ? "YES" : "NO")<<endl; return; }D.Rating System算法本质思维题目大意现在存在n个有序的加分a[]，你需要设定一个k，依次加分满足下列规则：若当前得分>=k，则会永久获得保护机制，每次加分下限得分为k输出可以最大化最终得分的k值。思路推演简单画一个图可以发现，所有的k值都是基于点来设置的——即k可以设定为某个前缀和，并假设前面的加分都不受影响。反向思考可以发现，加分都是一致的，核心在于如何让k值尽可能地去“捞分”——找到最小字段和。然后为了保证最小字段的分都可以捞上来，k值设为前缀和即可。思路推演2另外一种思考方式，首先仍是可以退出k为某个前缀和。考虑画图，图像应该类似于：先上升、走平、（上升、有限下降、走平）、上升先上升这部分可以用前缀和搞定，我们需要找到最后一次走平后的上升值。这其实就是后缀最大值，遍历前缀和结合后缀最大值即可得到答案。不过再结合图像观察，其实2个思路是一致的，反过来看就是找最小字段和。ac核心代码int a[maxn], dp[maxn]; inline void solve() { cin>>n; for (int i=1; i<=n; i++) cin>>a[i]; dp[n+1] = 0; for (int i=n; i>=1; i--) dp[i] = min(dp[i+1]+a[i], a[i]); int p = min_element(dp+1, dp+1+n) - dp; // 最小子段和的左端点 int ans = accumulate(a+1, a+p, 0ll); // 前缀和求值 cout<<ans<<endl; return; }E.Boxes and Balls](https://codeforces.com/contest/1841/problem/E)算法本质思维题目大意在一个[1,n]的一维方格地图中，存在若干空格、石头，分别用01表示。操控每个石头移动到相邻空格为一次操作。输出k次操作后的情况数。（mod 1e9+7）n k <= 1500 保证有方格为空、有方格存在石头、至少2方格思路推演容易发现的2个性质：石头的相对顺序固定符合dp性质，可以用下标特定指代某个石头可以来回空走石头这意味在处理中可以保证不空走石头，最后答案为与k同奇偶性的所有答案之和这道题的数据范围、性质都说明dp是较好解法，所以先思考dp。为了方便转移，我们规定其中当前占位置、石头数、操作次数都是必须的，所以先假设一个：dp[a][b][c] = num表示前a个方格、存在b个石头、使用了c次操作（无空走）的方案数num。转移方程如下：当前a方格存在石头dp[a][b][c] = dp[a-1][b-1][c-第b个石头到a的代价]a方格不存在石头dp[a][b][c] = dp[a-1][b][c]但是显然，这样是O(n^2^k)的复杂度，无法过题。考虑优化会发现，k的数目限制在1500，但想要能达到任意的情况，其实操作数最多需要n^2^左右。这时就可以反过来思考，当初始状态前a个方格存在x石头时，我们最终b的探索范围其实局限于$x\pm\sqrt{k}$，并非最初考虑的0~a。至此，复杂度优化至O(nk^1.5^)。同时，我们需要针对空间复杂度进行优化，使用滚动数组优化第一维度。ac核心代码头文件、宏定义、快读模板、常见变量、常见变量等略。 const int M=40; int a[maxn], pre[maxn], dp[maxn][maxn]; inline void solve() { cin>>n>>k; int num=0; // 记录石头的个数 map<int, int> pos; // 记录每个石头的位置 for (int i=1; i<=n; i++) { cin>>a[i]; pre[i] = pre[i-1] + a[i]; // 前缀和，记录左边有多少个石头，同时可以计算出右边的石头数目 if (a[i]==1) pos[++num] = i; // 每个石头的位置 } dp[0][0] = 1; // dp[a][b][c]被滚动数组压缩为dp[b]][c]：前a个方格有b个石头、用了c次操作的情况数 for (int i=1; i<=n; i++) // i表示前i个方格的情况 { int l = max(1ll, pre[i]-M); // k次操作最多可以从这个区间撤走M个石头，计算最少的数目可能 int r = min(num, pre[i]+M); // 可以给这个区间带来至多M个石头，计算最多数目可能 for (int j=r; j>=l; j--) // 滚动数组优化，需要从右往左 { int cost = abs(pos[j]-i); // 第j个石头移动到位置i需要的操作数 for (int t=cost; t<=k; t++) dp[j][t] += dp[j-1][t-cost], dp[j][t]%=mod; // 方程转移（2个转移方程，但是因为使用滚动数组优化后，刚好可以省略1个） } } int ans=0; for (int i=k; i>=0; i-=2) ans += dp[num][i], ans%=mod; cout<<ans<<endl; return; }title算法本质题目大意思路推演ac核心代码头文件、宏定义、快读模板、常见变量、常见变量等略。

Educational Codeforces Round 150 (Rated for Div. 2) A.Game with Board算法本质思维题目大意初始存在n个数字1，Alice和Bob轮流执行操作：选择多个相同数字组合为他们的和若无法执行操作，则获胜。给定n判断谁会获胜。思路推演通常来说，这种博弈论问题，通常将当前情况转化为更容易求得的情况来求解。但是考虑到是A题，我们直接从小模拟n的情况。当n较大时，可以发现Alice存在一个必胜法是：先组合n-2个数字1，Bob不得已组合剩下2个数字1，则Alice赢。通过计算各种条件，这需要n>=5才行。则n=2~4手动模拟，发现都是Bob胜利。B.Keep it Beautiful算法本质思维题目大意对于数组a[]，定义美丽的满足以下：选择a[]前缀若干元素顺序添加至末尾，保证不降序排列现给定空数组a[]，接下来挨个给定n个数字，若当前数组放入a[]末尾后a[]是美丽的，则必须放入。最后输出01字符串s[]，s[i]表示第i个数字是否放入。思路推演通过手动模拟可以发现，若数字一直不降序，则必然美丽。当发生第一次降序后，若其值小于第一个数字，并且大于前一个数字，则任然可以保持美丽。当发生第二次降序后，则不添加数字。ac核心代码头文件、宏定义、快读模板、常见变量、常见变量等略。 inline void solve() { string ans; int cnt=0, a1, ax; // a1 ax表示数组中的未降序前的最小、最大元素值， cnt表示降序次数 cin>>n>>a1; // 第一个元素手动初始化 ax = a1; ans.push_back('1'); for (int i=2; i<=n; i++) { int x, nw_cnt; cin>>x; nw_cnt = cnt + (x<ax); // 降序次数预测 if (nw_cnt==0 || (nw_cnt==1 && x<=a1)) // 若当前还没有降序 或者 当前降序了1次但是当前值小于a1 cnt=nw_cnt, ax=x, ans.push_back('1'); // 加入数组，更新答案 else ans.push_back('0'); // 不加入数组，更新答案 } cout<<ans<<endl; return; }C.Ranom Numbers算法本质思维题目大意现在给定一由ABCDE组成的字符串s[]，其中每个字符分别表示的值绝对值为1 10 100 1000 10000，当s[i]右侧不存在大于其的字符，其值为正数，反之为负数。s[]的值为字符之和。现在可以任意改变某个下标的字符，输出最大化的s[]的值。思路推演-朴素做法改变字符有2个思路：小改大，当前下标表示的值更多了，但是会使得部分字符符号由正变负大改小，当前下标的值减少了，单部分字符符号由负变正一个容易想到的朴素做法是，我们暴力枚举每个下标的改变，通过预处理O(1)获取改变的值。当我们目前这个下标绝对值变化时，我们需要知道2个东西：右侧的最大字符——用于判断当前绝对值的值左侧的正值、负值（因为谁而负）情况——判断左侧值的改变预处理：右侧最大字符相对容易，我们使用前缀和或者从右往左遍历即可获取。左侧的值情况，负值我们可以详细分成：不可改变负值（存在>=2个大于其的字符）和可改变负值（有且仅有一个大于它的字符，并保存他们的下标）思路推演-字符单位当我们以字符为单位的思考的时候，其实其中存在规律的。小改大：修改最前的字符是最优解对于任意2个相等的字符、不同位置，设为a1 a2，当中间不存在大于字符a的字符时，显然正确。现在考虑a1 b a2，其中b是大于a的字符。当a1修改为x值且大于等于b时，一定优于a2修改为x，同时也优于a2修改为小于b的值大改小：修改最后的字符是最优解显然，不证明ac核心代码-朴素做法头文件、宏定义、快读模板、常见变量、常见变量等略。 const int pow10[] = {1, 10, 100, 1000, 10000}; int fu[maxn]; char maxc_right[maxn]; inline void solve() { //init cin>>s; map<char, pair<int, int>> now; // 存那些符号为负，但是可能转正的信息 map<int, map<char, int>> mp; // 存放因为当前点阻拦而取负值的字符、数目 maxc_right[s.length()] = 'A'; // 相当于情况maxc_right[] for (int i=s.length()-1; i>=0; i--) { maxc_right[i] = max(maxc_right[i+1], s[i]); // 更新右侧的最大字符 if (now.count(s[i])==0) now[s[i]]={0,0}; now[s[i]].first++; // 数目+1 now[s[i]].second=i; // 最近下标更新 int num=0, p; for (char c=s[i]+1; c<='E'; c++) // 找到右侧大于其的数目 if (now.count(c)) num += now[c].first, p=now[c].second; if (num==0) fu[i]=1; else fu[i]=-1; if (num==1) // 说明是可能由负转正的 mp[p][s[i]]++; } //cal int ans=0; for (int i=0; i<s.length(); i++) // 不做改变的值 ans += pow10[s[i]-'A']*fu[i]; int yans=ans; map<char, int> left; // 仅存符号为正的信息 for (int i=0; i<s.length(); i++) { // 小改大 for (char c=s[i]+1; c<='E'; c++) { if (maxc_right[i+1]>c) continue; // 右侧有更大的 int more=0; more += pow10[c-'A']-pow10[s[i]-'A']*fu[i]; // 当前值的增加 for (char c2=s[i]; c2<c; c2++) // 左侧原本正值元素变为负值 more -= 2*pow10[c2-'A']*left[c2]; ans = max(ans, yans+more); } // 大改小 for (char c='A'; c<s[i]; c++) { int more=0; more -= pow10[s[i]-'A']*fu[i]; if (maxc_right[i+1]>c) // 说明改了之后是负号 more -= pow10[c-'A']; else more += pow10[c-'A']; for (char c2=c; c2<s[i]; c2++) more += 2*mp[i][c2]*pow10[c2-'A']; // 由负转正的值 ans = max(ans, yans+more); } // 信息更新 if (fu[i]==1) left[s[i]]++; } cout<<ans<<endl; return; }ac核心做法-字符单位头文件、宏定义、快读模板、常见变量、常见变量等略。 const int pow10[] = {1, 10, 100, 1000, 10000}; int f(const string &x) { int res=0; char c='A'; for (int i=x.length(); i--; i>=0) { if (c>x[i]) res -= pow10[x[i]-'A']; else res += pow10[x[i]-'A']; c = max(c, x[i]); } return res; } inline void solve() { //init cin>>s; map<char, pair<int, int>> mp; // 记录每个字符的首下标和末下标 for (int i=0; i<s.length(); i++) { if (!mp.count(s[i])) mp[s[i]] = {i, i}; else mp[s[i]].second = i; } int ans=f(s); for (char c='A'; c<='E'; c++) { if (!mp.count(c)) continue; for (char c2='A'; c2<='E'; c2++) { string ns = s; ns[mp[c].first] = c2; ans = max(ans, f(ns)); ns = s; ns[mp[c].second] = c2; ans = max(ans, f(ns)); } } cout<<ans<<endl; return; }D.Pairs of Segments算法本质思维题目大意给定n个（一维）线段区间，现在要求你删去任意条线段，使得剩下的线段满足：可两两分组同组线段必定相交（点相交也算相交）不同组线段必定不相交输出最小化的删除条数。n <= 2e3思路推演难点是抽象题意：我们任选2条相交线段，假定他们组成一组，可以用并集来表示他们的“管辖范围”，不能有其他任意的线段进入这个范围。如何对任意2条线段如法炮制，这就变成了一个会议问题：有4e6条一维线段，选则若干条线段出来，使其不相交同时保证数目最多。ac核心代码头文件、宏定义、快读模板、常见变量、常见变量等略。 inline void solve() { cin>>n; vector<pair<int, int>> p1, p2; // p1用于存放线段 p2存放线段的并集 m = n; while (m--) { pair<int, int> tmp; cin>>tmp.first>>tmp.second; p1.push_back(tmp); } for (int i=0; i<p1.size(); i++) { for (int j=i+1; j<p1.size(); j++) // 任意两条线段 { auto [l1, r1] = p1[i]; auto [l2, r2] = p1[j]; if (max(l1, l2) <= min(r1, r2)) // 说明相交了 p2.push_back({min(l1,l2), max(r1,r2)}); } } sort(p2.begin(), p2.end(), [](const pair<int, int> &a, const pair<int, int> &b) // 排序，右端点升序，伴随左端点升序 { if (a.second==b.second) return a.first<b.first; return a.second < b.second; }); int ans=0, last=-1; // ans表示最多可以保留的线段并集数，last表示上次线段的左端点位置 for (auto it:p2) { if (it.first > last) { last = it.second; ans++; } } cout<<n-ans*2<<endl; // 删除条数 = 所有条数 - 2*最多保留的线段并集数 return; }E.Fill the Matrix算法本质思维、st表题目大意给定n a[] m表示一个n*n的棋盘，第i行的前a[i]格子不能填写数字。目前拥有1~m数字，给其他格子填写，当j+1在j同行的下一列，贡献值+1。输出最大化后的贡献值。思路推演本质是找同行的连续线段，收益为线段长度-1。因为同列不可填的格子，都在最上方，所以可以用dfs分段来处理。ac核心代码头文件、宏定义、快读模板、常见变量、常见变量等略。 // 忽略了st表模板（返回最大值下标） map<int, int> mp; // mp[线段长度] = 数目 void dfs(int l=1, int r=n, int h=n) // 分类 { int mid = find_st(l, r); // 最大值的下标 int nh = a[mid]; // 最大值 mp[r-l+1] += h-nh; // 记录 if (l<=mid-1 && nh>0) // 左边 dfs(l, mid-1, nh); if (mid+1<=r && nh>0) // 右边 dfs(mid+1, r, nh); } inline void solve() { //init cin>>n; rep(i,1,n) cin>>a[i]; cin>>m; init_st(); //cal int ans=0; mp.clear(); dfs(); for (auto it=mp.rbegin(); it!=mp.rend(); it++) // 从大到小遍历 { if (m==0) break; int num = min(m/it->first, it->second); ans += num*(it->first-1); it->second -= num; m -= num*it->first; if (it->second>0 && m>0) { ans += m-1; it->second--; m = 0; } } cout<<ans<<endl; return; }title算法本质题目大意思路推演ac核心代码头文件、宏定义、快读模板、常见变量、常见变量等略。

Educational Codeforces Round 149 (Rated for Div. 2) A.Grasshopper on a Line算法本质思维题目大意给定n k，表示一维坐标中你在0点，需要达到n点，每次可以花费1秒时间走任意非k整数的距离。给出花费时间最少的方案。思路推演显然，如果n模k不为0，则可以一步走到。反之，我们手动模拟一下即可发现，n-1必定模k不为0，我们可以用1 + (k-1)来完成。B.Comparison String算法本质思维题目大意给定长度n由<和>组成的字符串s，用于指定长度n+1的a[]数组相邻元素大小比较。s[i] = >表示a[i]>a[i+1]，反之同理输出构建满足条件的a[]至少需要几个不同的值。（[1, 2, 3, 3]看作使用了3个不同的值）思路推演既然需要最少的值，核心思想就是复用。我们根据s画个轨迹图，形象地表示a[]，可以发现当某一段大量连续上升或者下降的时候，可以视作别人对其的复用。我们将每段连续上升、下降看作一个区间，设定一个上限值和下限值，每个区间的开头结尾都必须是上下限值，中间的复用即可。最后值的个数为：最长连续>或<符号长度+1。C.Best Binary String算法本质思维题目大意给定由0 1 ?组成的字符串s。其中?可以表示为0或1。现在需要确定?的表示，并使得最后得到的s成本最小。01字符串s的成本定义，最小的操作次数使得s呈现非递增序列：选择l r使得s[l~r]字符发生反转（010 --> 101这种）思路推演这个题从成本整体去思考，有一定的难度。我们先着眼于单个?的角度来看。当连续多个?，?的值应该一致当?的两侧一致都是1或0时，?的值应该与两侧相同当?两侧不一致时，任意取1或0当?在边缘，应该与另一侧值保持相同当?两侧都是边缘时，随意取值以上的规则我们可以简化为：若?存在前值，就取前值，否则取后值，否则取0（1也行）从字符角度去思考，讨论所有最佳情况即可。D.Bracket Coloring算法本质思维题目大意给定括号序s，定义括号序美丽满足：满足常见对应形式 或者 顺序颠倒后满足常见对应形式现对s顺序自由分成若干组，每组括号徐美丽，输出分组数最小的分组方案。思路推演容易发现的是，任何美丽的字符串按照原来顺序任意组合，任然美丽。所以显然，如果括号序可行，最多分成2组即可。我们开一个队列栈一一对应即可。E.Playoff Fixing算法本质思维题目大意现在有2**n支队伍，id从[1~2**n]分配，在比赛中id较小的队伍必然获胜。比赛采取常见的2分方法，比n个回合。现在我们希望，最后的排名完全符合队伍实力：id为1的队伍一定是冠军、id为2的队伍是第2名、id为34的队伍是第34名（因为赛制没法分出更细的名次），以此类推初始存在2**n个格子，每支队伍存在于一个格子，现在已有若干个格子已经确定好队伍了。请问有多少种情况，可以满足条件。（取模xxx）n <= 19思路推演首先需要考虑的就是，如何才能实现目标：每一轮比赛，都需要让id最大的队伍淘汰而情况数目来自于未知id的不定性。对于每一轮比赛，每支队伍有3种可能：当前需要淘汰的队伍、当前不需要淘汰的队伍、未知（以下简称“淘”“不淘”“未知”）每场比赛由2支队伍组成，就需要讨论8种情况，做出分类淘+淘 或者 不淘+不淘2支队伍都需要淘汰，但是无法做到，必然会导致最后不能达到目的。直接给ans赋值0未知+未知未知定义为淘汰和不淘汰淘汰队伍位置不定、id不定淘+非淘淘汰队伍位置确定、id确定不淘+未知未知定义为淘汰淘汰队伍位置确定、id不定我们每轮比赛，讨论当前轮次的情况数，同时更新下一轮的队伍id情况，即可算出。许多小细节没说明白，可以结合代码一起看思路推演-另辟蹊径这是别人的一种做法，思想上区别不大，核心区别是构建了队伍id-->队伍位置。每轮比赛，都遍历后一半的队伍id，收集他们所在的比赛场和不确定值数（对队伍位置用除法来判断所处的比赛场）根据这些数据来判断是无效或者具体情况数即可。ac核心代码头文件、宏定义、快读模板、常见变量、常见变量等略。 int dp[20][maxn]; int fac[maxn]; int ck(int x, int l, int r) // 判断x值是否属于[l,r]范围，正确返回1错误返回0，若x为-1则返回-1 { if (x==-1) return -1; return x>=l && x<=r; } inline void solve() { //init cin>>k; n = 1ll<<k; for (int i=1; i<=n; i++) cin>>dp[k][i]; // dp[x][y]表示第x个伦次的第y场比赛的胜者id int ans=1; for (int i=k; i>=1; i--, n/=2) // 第i轮，目前有n支队伍 { int l=n/2+1, r=n; // [l, r]表示当前伦次需要被淘汰的队伍id范围 int val=1, num=r-l+1; // val表示当前伦次的情况数，num表示当前伦次需要淘汰但是值不确定的id数 for (int j=1; j<=n; j+=2) // 有n/2场比赛，遍历每场比赛 { int p1=dp[i][j], p2=dp[i][j+1]; // 队伍id int a=ck(p1,l,r), b=ck(p2,l,r), res; // 队伍id带来的3个状态，res表示当前比赛的胜者id // 淘+淘 或者 不淘+不淘：无法达成目标，值归零 if (a==b && a!=-1) val = 0; // 未知+未知：未知定义为淘汰和不淘汰，淘汰队伍位置不定、id不定 else if (a==b && a==-1) res=a, val = (val*2)%mod; // 淘+非淘：位置确定、id确定 else if (a==1) res=p2, num--; else if (b==1) res=p1, num--; // 不淘+未知：未知为淘汰，位置确定、id不定 else if (a==0 && b==-1) res=p1; else if (a==-1 && b==0) res=p2; dp[i-1][j/2+1] = res; // 更新胜者id } val = (val*fac[num])%mod; // 有num个id的值不确定，阶乘种情况 ans = (ans*val)%mod; // 更新到总ans上 } cout<<ans<<endl; return; }title算法本质题目大意思路推演ac核心代码头文件、宏定义、快读模板、常见变量、常见变量等略。