Codeforces Round 824 (Div. 2) A.Working Week算法本质思维题目大意（改）n-1个连续白色格子，选择2个不靠边、且不相邻的格子涂黑。这样会出现3段连续的白色格子。最大化（任意两段连续白色格子的格子数差 的 最小值）思路推演这实际意味，n-3个块饼干，分割三个人，假设三人的饼干数为a a+b a+b+c。答案为min(b,c)，若b!=c，实际上会无故浪费饼干。另外答案与a值无关，a值取最小的1。三人的饼干数：1 1+x 1+2x（相同ans下所用饼干最少的方案） 于是答案为：ans = (n-3)/(3+3x)B.Tea with Tangerines算法本质思维题目大意给n个元素，可以进行以下操作：选择一个元素分成两个元素（和不变）最小化操作次数，使得任意两个元素x y都保证x < 2y。思路推演首先想到的就是，若存在某个数字很小，其他元素需要进行多次操作。所以我们找到最小的元素作为标值，分割出任意小于标值的操作收益为负，不会进行。所以只需要保证其他元素在标值的两倍以内即可。C.Phase Shift算法本质思维题目大意给定长度n的字符串s，由26个小写字母组成。这个26个字母乱序形成了一个环，当前字符存在对顺时针方向字符的映射。s中所有字符通过映射改变后变成了t通过调整字母环的的顺序，最小化t的字典序并输出。思路推演每个字母都有一个入度、一个出度，并且他们会整体形成一个环。样例也明确表示，不能形成一些小环。从左往右，对于靠前的字符，其肯定想映射能够映射的最小字符。若说c1-->c2的能够映射包含的条件有：c1的出度为0c2的入度为0c1-->c2，若会形成环，则必须是26字母形成的大环其中出度、入度使用数组很容易解决，判断是否成环，则可以使用并查集来表示。判断集合是否有26个元素：修改一下并查集，新增一个数组：26n的复杂度直接暴力检查，最多26*26n的复杂度ac核心代码头文件、宏定义、快读模板、常见变量、常见变量等略。 // 略作修改的并查集板子略了 inline void solve() { //init cin>>n>>s; map<char, char>to; set<char> chu, ru; init_set(); // 初始化并查集 //cal for (char c1:s) { for (char c2='a'; c2<='z'; c2++) { if (chu.count(c1)==0 && ru.count(c2)==0) // 检查入度出度 { if (find_set(c1)==find_set(c2) && len[c1]+len[c2]<26) // 检查成环的特殊情况 continue; union_set(c1, c2); // 这里的union_set存在对集合内元素结合的鲁棒性判断 to[c1] = c2; // 维护映射、入度、出度 chu.insert(c1); ru.insert(c2); } } } for (char c:s) cout<<to[c]; cout<<endl; return; }D.Meta-set算法本质思维题目大意给n张卡片的id（保证不同），每张卡片的id由k个数字（数字仅限0 1 2）组成。定义一个三元组（由三张卡片组成）为美丽三元组：每张卡片的id第i位要么都相同、或都不同定义一个五元组为美丽五元组：其中可以选出至少2个美丽三元组求美丽五元组*数目。n：[1, 1e3] k：[1, 20]思路推演首先看到这个范围，想能否找出所有的美丽三元组，如果可行的话最好。理论上暴力需要n^3，不够，但是题目给定了限制条件，灵活使用限制条件说不定可行。这只是看到题目的第一反应和尝试，美丽三元组对后面要求的美丽五元组有帮助，所以简单尝试思考一下，但是不花太多时间。目前得到的结论是：可能可行具体怎么解，还是要从题目整体视角去看。美丽五元组需要至少2个美丽三元组，那就从2个入手。手动模拟一下容易发现，这2个美丽三元组会有1个 or 2个卡片相重合。2个卡片相重合的情况很快就被抛弃了，只有1个卡片重合的情况。当卡片a可以组成x个美丽三元组，其为重合卡片组成的美丽五元组有C(x, 2)种情况。这时就可以发现，必须找到所有的美丽三元组。当需要降低复杂度时，映射是一个很好的选择。对于美丽三元组，我们两两组合卡片，剩余的一张卡片id可以计算获得，然后去映射池里寻找。映射单位可以是数字（三进制转十进制），不过压缩成数字反而代码会写多一些，所以直接vectorac核心代码头文件、宏定义、快读模板、常见变量、常见变量等略。 void to(vector<int> &a, vector<int> &b, vector<int> &c) // 2卡片检测缺失的另一卡片 { for (int i=1; i<=k; i++) { if (a[i] == b[i]) c[i] = a[i]; else c[i] = 3-a[i]-b[i]; } } inline void solve() { //init cin>>n>>k; vector<vector<int>> cun(n+1, vector<int>(k+1)); // 存放id map<vector<int>, int> mp; // id-->组合成美丽三元组次数 * 3 for (int i=1; i<=n; i++) { cun[i][0] = 0; for (int j=1; j<=k; j++) cin>>cun[i][j]; mp[ cun[i] ] = 0; } //cal vector<int> v(k+1); v[0] = 0; for (int i=1; i<=n; i++) { for (int j=i+1; j<=n; j++) { to(cun[i], cun[j], v); if (mp.count(v)) { mp[v]++; mp[ cun[i] ]++; mp[ cun[j] ]++; } } } //out int ans=0; for (auto u:mp) { int x = u.second/3; // 记得除3 ans += x*(x-1)/2; } cout<<ans<<endl; return; }

Codeforces Round 821 (Div. 2) A.Consecutive Sum算法本质思维题目大意给长度n的数组a[]，下标对于k同余的元素为同一组，同一组的元素可以任意调换位置。任意次操作后，选择长度为k的连续子数组，输出最大化其元素和。思路推演显然是每个组出一个元素，每组出最大的元素即可。B.Rule of League算法本质思维题目大意一队列原有n个人，id1~n顺序占位（1号占队头）。头的两个人会决斗，输掉的人出队，赢家仍站在队头。比赛进行n-1次直到最后剩下一个人。给定n x y，规定同一个id的人只允许赢x或y场决斗，检测是否存在如此情景，若存在输出每场胜者id，反之输出-1。思路推演手动模拟一下会发现，对于第一场比赛，1号胜利则2号直接出局——2号赢0场。所以x y中必须有一个等于0、一个大于0（n>1的情况下）。设x=0假设第一场1号必输，则2号连赢y场后必须输掉比赛，换2+y上场连赢y场，以此类推，n-1必须能整除y。即得到答案。C.Parity Shuffle Sorting算法本质思维题目大意给长度n的数组a[]，最多进行n次以下操作：选择一对l r，如果a[l]+a[r]为奇数，则a[r]=a[l]；反之a[l]=a[r]使得a[]单调不减。输出操作的l r。思路推演既然跟奇偶性有关，则考虑一下4种情况。若两者都是奇数或者偶数，其操作后两者奇偶性不变。这下我们就通过奇偶性来分成两条线，这两条线可以分别处理，思考如何整合到一起。此时就需要思考，奇数+偶数的情况，会a[r]=a[l]。所以若a[1]是奇数，则我们将所以的奇数向最右的奇数看齐，然后再将所有的偶数向a[1]看齐。D2.Zero-One (Hard Version)算法本质思维、dp题目大意（改）有长度n的01字符串，有2种操作方式，将其变成一个全0字符串：x元：选择两个相邻字符反转y元：选择两个不相邻字符反转最小化成本。（或者输出-1）n:[1, 5e3]思路推演显然，奇数个1会导致失败。显然操作2更为灵活，如果x>=y的情况下，有且仅有2个连续1相邻的这种情况，可能用操作1，否则都会使用操作2。于是可以单独讨论x>=y的情况，这部分比较简单不详述。实际上easy版本也提醒了我们：单独讨论x>=y的情况到了这个地步，要么贪心、要么dp。（也有可能是没见过的神奇数据结构、图论之类的）贪心的话，思考一段时间，发现找不到角度贪，所以思考一下dp。显然dp应该用二维区间dp。思考一会就发现：对于l rint val_ll = dp[l][l+1] + dp[l+2][r]; // 左边2个+右边 int val_rr = dp[l][r-2] + dp[r-1][r]; // 左边+右边2个 int val_lr = dp[l+1][r-1] + y; // 左右各给1个 dp[l][r] = min(val_ll, min(val_rr, val_lr));即得，思路很顺。ac核心代码头文件、宏定义、快读模板、常见变量、常见变量等略。 int dp[maxn][maxn]; inline void solve() { //init int x, y; string s1, s2; vector<int> v; cin>>n>>x>>y>>s1>>s2; s1 = " " + s1; s2 = " " + s2; s = s1; for (int i=1; i<=n; i++) { if (s1[i] == s2[i]) s[i] = '0'; else { s[i] = '1'; v.push_back(i); } } //cal 特殊情况判断 int ans; if (v.size()%2==1) { cout<<-1<<endl; return; } if (x>=y) { if (v.size()==2 && v[0]+1==v[1]) ans = min(x, 2*y); else ans = v.size()/2*y; cout<<ans<<endl; return; } //cal 2 n = v.size(); for (int i=1; i<=n-1; i++) dp[i][i+1] = min(x*(v[i]-v[i-1]), y); // 注意v是零下标 for (int len=4; len<=n; len+=2) { for (int l=1, r=len; r<=n; l++, r++) { int val_ll = dp[l][l+1] + dp[l+2][r]; // 左边2个+右边 int val_rr = dp[l][r-2] + dp[r-1][r]; // 左边+右边2个 int val_lr = dp[l+1][r-1] + y; // 左右各给1个 dp[l][r] = min(val_ll, min(val_rr, val_lr)); } } ans = dp[1][n]; cout<<ans<<endl; return; }

Codeforces Round 816 (Div. 2) A.Crossmarket算法本质思维题目大意有一个n*m的地图，小蓝在(1,1)目标(n,m)，小红在(n,1)目标(1,m)，每走一步花费一秒。小红走过的路径会留下空间之力，小蓝在任意具备空间之力的格子，可以花费一秒的代价，去到任意具备空间之力的格子。小红先走，到终点后小蓝再出发。输出最小化其所用时间。思路推演小红所用时间固定n+m-2，对于小蓝，有3种走法：直接走，不使用空间之力使用空间之力在y轴方向传送使用空间之力在x轴方向传送三种情况都计算，然后取小输出即可。B.Beautiful Array算法本质思维题目大意对于长度为n的数组，定义魅力值为：元素/k之和。（除法取下限）现在需要你构造一个长度为n、魅力值为b、元素和为s的数组a[]。（若不可能输出-1）思路推演显然，若保证数组魅力值为b，其元素和范围：[bk, bk+n*(k-1)]将bk随便放到某个下标去，然后将s-bk平均分配到n个元素内即可。C.Monoblock算法本质思维题目大意给定长度n的数组a[]。定义a[l, r]的魅力值：可以拆分数组的连续相同数字的最小块数不懂的看一下题目中的样例解释定义a[]的帅气值：所有区间魅力值之和接下来有q次询问，每次询问会改变某元素的值（之后永久有效），需要输出当前a[]的帅气值。思路推演ac核心代码头文件、宏定义、快读模板、常见变量、常见变量等略。 title算法本质题目大意思路推演ac核心代码头文件、宏定义、快读模板、常见变量、常见变量等略。

Codeforces Round #840 (Div. 2) E.Partial Sorting算法本质分类讨论思维、容斥（一点点）题目大意给出n、mod，列出长度为3n的所有排列，每个排列都有自己的价值x——最少经过x次操作后使得排列为[1~3n]的形式。下面是可以对排列进行的2种操作：前排：递增sort前2n个元素后排：递增sort后2n个元素求所有排列价值之和（取余mod）。思路推演-1首先可以拿出的一个结论是，任何排列经过3次操作可以恢复。既然只有3次操作，显然是一个分类讨论+组合数的题目。分类讨论的重点就在于，该如何分类讨论，这里通常有2个方法：贴近答案分类讨论每个排列只有4种价值，则按照不同价值分类贴近数据本身的结构分类讨论可以看到，每个排列分为了3个大区间，思考排列的特殊结构不论哪种分类方法，最后都疏通同归，但是思考的难易程度会有所不同。同时注意，这题给的复杂度宽裕，支持在分类讨论中O(n)的暴力。固定思维想着组合数问题需要O(1)解决，是没做出来的原因之一。思路推演-2这里选择贴近答案分类讨论，同时在分类的时候，发现先用小于等于处理较好。价值==0只有一种可能。价值<=1意味着只需要一次前排or后排就可以搞定，这分别对应2种情况：[2n+1, 3n]的数字已就位且[1, 2n]数字任意排序[1, n]的数字已就位且[n+1, 3n]的数字任意排序同时这两种情况有交叉的地方fac[2n] + fac[2n] - fac[n]价值<=2这里可以反向思考一下，价值为3的情况是什么——存在最小的n个数在[2n+1, 3n]且存在最大的n个数在[1, n]思索片刻可知，操作必然是前排+后排或者后排+前排，这里也对应2种情况：最小的n个数只在[1, 2n]最大的n个数只在[n+1, 3n]这里注意理解一下同时这两种情况也存在交叉的地方。思考最小的n个数只在[1, 2n]有多少种情况：[1,2n]选择n个位置，然后全排列：C(2n, n)*fac[n]剩下位置全排列：fac[2n]思考交叉部分的情况：细细一琢磨，发现情况有点多，但是我们可以接受O(n)的暴力。于是设最小的n个数，在[1,n]中有n-x个数，在[n+1,2n]中有x个数。[1,n]中选n-x个位置给最小的n个数：C(n, n-x)[n+1,2n]中选x个位置给最小的n个数：C(n, x)[n+1,3n]中剩下2n-x个位置留给最大的n个数选择：C(2n-x, n)最小、中、大的n个数分别自我全排列：fac[n] * fac[n] * fac[n]枚举x ~ [0,n]价值<=3全排列：fac[3n]ac核心代码头文件、宏定义、快读模板、常见变量、常见变量等略。 组合数板子未给出 inline void solve() { //init cin>>n>>mod; init_c(); //cal vector <int> v(4, 0); //v[x]表示价值<=x的方案数 v[0] = 1; v[1] = fac[2*n] + fac[2*n] - fac[n]; v[1] %= mod; v[2] = C(2*n, n) * fac[n] %mod * fac[2*n] * 2 %mod; int n3 = fac[n] * fac[n] %mod * fac[n] %mod; for (int x=0; x<=n; x++) //减去容斥 { v[2] -= C(n, n-x) * C(n, x) %mod * C(2*n-x, n) %mod * n3 %mod; v[2] = (v[2]%mod + mod) %mod; } v[3] = fac[3*n]; //cal v[3] -= v[2]; v[3] = (v[3]%mod + mod) %mod; v[2] -= v[1]; v[2] = (v[2]%mod + mod) %mod; v[1] -= v[0]; v[1] = (v[1]%mod + mod) %mod; ans = 0; for (int i=0; i<=3; i++) { ans += i*v[i]; ans %= mod; } //out cout<<ans<<endl; return; }F.Wonderful Jump算法本质思维、dp思路推演-1整个题目看上去，很明显的线性dp，同时也很明显的发现复杂度不够，作为2900的题目，肯定是需要在某些地方做出改进的。然后观察不同寻常的地方：元素范围[1,n]成本公式：min*(j-i)^2^目标非常明确，通过这2个不同寻常的条件，改进dp方式，从而满足复杂度。同时注意有平方，复杂度可能为n^1.5^，或者nlog~2~n。元素范围暂时看不出什么花样来，那就算看成本公式。通过成本公式可以推出2个性质：性质1：对于i --> j，如果存在i<k<j && a[k]<a[i] && a[k]<a[j]，则i-->k-->j 优于 i-->k这个性质相当不错，这意味我们简化了模型，只用讨论最小值在两端的情况当前的性质1作为定性讨论的，其实可以深挖定量，但是定量出来的公式未知数多，没有明确的关系。性质2： 成本公式是抛物线上升的，如果每次走一格，则成本是线性上升的，当i j相差过大时，每次走一格的成本较低对于性质1来说，可以简化我们讨论的情况，但是对于最小值在两端的情况，依然没有什么好的方法去解决。对于性质2来说，就比较有用了，因为在最朴素的n^2^算法中，我们需要对前面所有的元素都遍历一次。但性质2给我们提供了一个新的思路，或许我们可以找到i j相差过大的阈值，然后减少遍历的次数。对于i-->j (i<=k<=j)，设a[k]为其最小值，设A为a[i~j]的平均值i-->j（直达）的成本是：a[k]*(j-i)*(j-i)i-->j（步步走）的成本是：A*(j-i)发现当j-i > A/a[k]时，则直达的成本>步步走的成本，这并不意味我们会选择步步走，而是说，那部分i j的直达可以不用讨论了，肯定不是最优解。但是同时，我们并不确定A a[k]的范围，没有一个较大的意义，所以我们在这里必须强制规定，假设a[k]>=根号n。为什么这里假设的是根号n而非log~2~n之类的：1.根号n的复杂度是ok的2.后面可能会用到一些除法翻转，这里数设置小了，可能下一步的算法复杂度更大了3.先随便假设一下，大了小了后面看着调整当保证了a[k]>=根号n，考虑最坏的情况（A==n），则可以推出：当i j差超过了sqrt(n)时，则直达一定不是最优解。这表明了，当a[k]>=根号n，算法复杂度被降低为了n^1.5^。思路推演-2随后我们需要考虑a[k]<根号n的情况。（a[k]是指是a[i~j]的最小值）兜兜转转找了一会，并没有发现什么不错的公式，那没办法了，只有老实用性质1分类讨论一下。如果最右边的元素是最小值（a[j]是最小值 && a[j]<根号n）那这就好办了，既然又要保证a[j]是最小值，又要保证a[j]<根号n。我们让i从j-1遍历到1，暴力i j，但是因为上面2个条件的限制，我们的总体复杂度为n^1.5^。这里理解逻辑的话可以配合代码一起看。讲一下为什么复杂度为n^1.5^：当a[j]>=根号n时不会处理当a[j]<根号n时，对于多个同样的值（值指a[j]），其总体复杂度为n，一共最多有根号n个不同值，所以复杂度为n^1.5^如果最左边的元素是最小值（a[i]是最小值 && a[i]<根号n）这里我们把这些最小值用一个栈存起来，并且保证是递增的。（单调栈）代码思路我们固定j，移动i，每次i j变化的时候，就只会存在上述3种情况：a[k]>=根号n让i从j-1开始向后暴力遍历根号n个数即可。同时在这里，其实并不需要真的去判断a[k]>=根号n，可以直接计算，也不会增加复杂度的。a[j]是最小值 && a[j]<根号n注：这里必须保证a[j]<根号n当固定好j时，移动i时，前几个数可能会高于a[j]形成这种情况。不过一旦遇到某个元素<=a[j]则会打破这种情况，进入下一个情况else这个else情况，全部都可以转化为a[i]是最小值 && a[i]<根号n。对于固定的j来说，只需要和单调栈中存放的下标一一暴力历遍即可。这里也没有什么硬性要求，可以直接计算，不会增加复杂度。ac核心代码-思路1头文件、宏定义、快读模板、常见变量、常见变量等略。 int dp[maxn]; inline void solve() { //init cin>>n; rep(i,1,n) cin>>ar[i]; mem(dp, 0x3f); m = sqrt(n); //根号n vector <int> v; //单调栈 //cal dp[1] = 0; v.push_back(1); //第一位特殊处理 for (int j=2; j<=n; j++) { //case 1 //a[k]>=根号n int mi = ar[j]; //mi表示区间[i, j]中的最小值 for (int i=j-1; i>=max((int)1, j-m); i--) { mi = min(mi, ar[i]); dp[j] = min(dp[j], dp[i] + mi*(j-i)*(j-i)); } //case 2 //a[j]是最小值 && a[j]<根号n if (ar[j]<=m) //这里必须有条件，不然复杂度会炸 { for (int i=j-1; i>=1 && ar[i]>ar[j]; i--) dp[j] = min(dp[j], dp[i] + ar[j]*(j-i)*(j-i)); } //case 3 //其他情况-->转化为`a[i]是最小值 && a[i]<根号n` for (int i:v) dp[j] = min(dp[j], dp[i] + ar[i]*(j-i)*(j-i)); //维护一下单调栈 if (ar[j]<=m) { while (!v.empty() && ar[v.back()]>=ar[j]) //当前点的值更小，就删去之前的 v.pop_back(); v.push_back(j); } } //out for (int i=1; i<=n; i++) cout<<dp[i]<<" \n"[i==n]; return; }

Codeforces Round #840 (Div. 2) D.Valid Bitonic Permutations算法本质dp、思维题目大意生产一个长度为n的排列，且要求这个排列为单峰形式（先上后下——峰值不在边缘）并且会明确规定排列的某2个下标对应的值，求数目。思路推演-1看了部分题解，才发现有dp的解题方式。dp方法的核心在于，是否能构建一个具有一定传递性的的意义。以dp[l][r]=x，表示在下标[l, r]中（共r-l+1个位置），有从n、n-1、n-2...n-r+l这r-l+1个数，其能构成合格的单峰数目为x上面这句话比较重要，需要完全理解。所以当我们考虑，dp[l][r]扩展到dp[l-1][r]时可以发现，我们实际上是把多加的一个数字放于最左边。同理，扩展到dp[l][r+1]时可以发现，我们实际上是把多加的一个数字放在最右边。思考单峰排列的构造，我们也是会先讲n放于中间，然后在左右两边添加较小值。而这个dp的思考方式即如此，同时配合固定下标，可以完成其对下标的要求。由此，也可以知道，dp的起点应该从dp[i][i]=1，同时发现单峰不允许峰值在边缘，所以dp[1][1]=dp[n][n]=0。同时在转移的过程中，需要注意的是得满足确定的2个下标+值这个条件，只需要在每次转移的过程中，检查一下是否满足，要是不满足就放弃这个转移即可。ac核心代码-思路1头文件、宏定义、快读模板、常见变量、常见变量等略。 int dp[105][105]; int p1, p2, v1, v2; bool check(int pos, int val) //检查pos位置放val值可行否 { if (pos==p1 && val!=v1) return 0; if (pos==p2 && val!=v2) return 0; return 1; } inline void solve() { //init mem(dp, 0); cin>>n>>p1>>p2>>v1>>v2; for (int i=2; i<=n-1; i++) if (check(i, n)) dp[i][i]=1; //cal for (int len=2; len<=n; len++) { for (int l=1; l+len-1<=n; l++) { int r=l+len-1; //可以看作dp[l+1][r]加了一个数在左边 if (check(l, n-len+1)) dp[l][r] += dp[l+1][r]; //可以看作d[l][r-1]加了一个数在右边 if (check(r, n-len+1)) dp[l][r] += dp[l][r-1]; dp[l][r] %= mod; } } //out ans = dp[1][n]; cout<<ans<<endl; return; }思路推演-2这里的思路推演请结合代码、图片（暂懒得画）一起看。目前的条件有：单峰形式、确定的2个下标+值。这两个条件能创造出的情景就相对有限，所以第一时间想到的是分类组合数。这里的分类组合数也有2个解法，一是O(n^2^)每次枚举n出现的位置，这样的组合数也相对好写，下面这个题解中的D组合数方法就是这样写的：Codeforces Round #840 (Div. 2) and Enigma 2022 - Cybros LNMIIT A~E还有一个究极分类讨论方法，预处理组合数O(nlog~2~n)，每次O(n)，下面讲解：首先我们讨论分类的情况，可以发现的是，这个线性模型对称，所以我们可以保证确定的2个值，在左边的一定更小。这里l r表示2个确定值的下标，vl vr表示2个确定值的值：int l, r, vl, vr; //l r为下标，vl vr为值 cin>>n>>l>>r>>vl>>vr; if (vl > vr) //等价替换，保证左边的值一定小于右边 { l = n-l+1; r = n-r+1; swap(l, r); swap(vl, vr); }加上单峰曲线，这样就可以分为2种情况：右值恰好为n（特殊情况）右值不为n如果右值不为n，我们则需要讨论n出现的位置可能：l r n：峰值n出现r的右边l n r：峰值n出现在l r的中间同时，我们也找到这个模型的一些公有变量。以下标为横轴，我们可以分为3个位置：小于l、l r之间、大于r。不同位置所拥有的位置个数，分别命名为：l_wei m_wei r_wei。以值大小为纵轴，我们也可以分为3种大小的值：小于vl、vl vr之间、大于vr。不同大小的值的个数，分别命名为：l_val m_val r_val。固定2个确实位置+值这个条件我们已经做到了，接下来的构造中，需要保证确定是单峰这个条件。右值恰好为n（特殊情况）（vr==n）当r==n时，这个时候不是单峰，则ans=0。如果r!=n的话，我们以横轴为基准，先填充左边的下标，然后填充中间的，剩下的在右边摆好即可：ans = C(l_val, l_wei) * C(m_val, m_wei)右值不为n（vr!=n）这里有2个可能：l r n：峰值n出现r的右边还是先填充左边、再填充中间：C(l_val, l_wei) * C(m_val, m_wei)值大于vr的那些数（共r_val个），会自动填充在右边的，考虑他们的结构问题，可知结构个数：qpow(2, r_val-1)同时想一想，这种情况可能导致非单峰的出现，在某个特点情况下，可能会导致n被放于最右边，那个时候需要结构个数-1l n r：峰值n出现在l r的中间先填充左边、再把值大于vr的那些数（共r_val个）强制填入中间，并考虑结构个数，最后把中间剩下的部分填满最后最后剩下的数字填充右边即可。这样就搞定了所有情况了。ac核心代码-思路2头文件、宏定义、快读模板、常见变量、常见变量等略。 //注：qpow默认对mod取模！ //组合数板子 int fac[maxn],inv[maxn]; //fac[x]代表x!，inv[x]代表x的逆元 void init_c(int max_num=maxn-2) { max_num = min(max_num, mod-1); //大于等于mod的情况用lucas定理 inv[0]=fac[0]=1; for(int i=1;i<=max_num;i++) fac[i]=fac[i-1]*i%mod; inv[max_num]=qpow(fac[max_num], mod-2, mod); for(int i=max_num-1;i>=1;i--) inv[i]=inv[i+1]*(i+1)%mod; } int C(int a,int b) //C(下，上) { if(a<b) return 0; if (a<0 || b<0) return 0; if(a>=mod || b>=mod) return C(a%mod, b%mod)*C(a/mod, b/mod)%mod; //lucas定理，处理mod较小情况 return fac[a]*inv[b]%mod*inv[a-b]%mod; } inline void solve() { //init int l, r, vl, vr; //l r为下标，vl vr为值 cin>>n>>l>>r>>vl>>vr; if (vl > vr) //等价替换，保证左边的值一定小于右边 { l = n-l+1; r = n-r+1; swap(l, r); swap(vl, vr); } //cal int l_wei=l-1; //左边的位置个数 int m_wei=r-l-1; //中间的 int r_wei=n-r; //右边的 int l_val=vl-1; //小值：小于vl的值个数 int m_val=vr-vl-1; //中值：大于vl、小于vr的值个数 int r_val=n-vr; //大值：大于vr的值个数，含n //特殊情况 //r处放n if (vr==n) { // cout<<"特殊情况"<<endl; int d=1; d *= C(l_val, l_wei); //选一些小数去左边位置 d %= mod; d *= C(m_val, m_wei); //选一些中数去中间位置 d %= mod; ans = d; if (r==n) ans=0; } else //普遍情况 { //cal 1 //n在r右边情况 int d1=1; d1 *= C(l_val, l_wei); //选一些小数去左边位置 d1 %= mod; d1 *= C(m_val, m_wei); //选一些中数去中间位置 d1 %= mod; if (r_wei == r_val) d1 *= qpow(2, r_val-1)-1; //防止n靠在最右边的情况 else d1 *= qpow(2, r_val-1); //中间部分的选择情况 d1 %= mod; //cal 2 //n在l r中间的情况 int d2=1; d2 *= C(l_val, l_wei); //选一些小数去左边位置 d2 %= mod; d2 *= qpow(2, r_val-1); //中间先放最大的那些数 d2 %= mod; d2 *= C(m_val, m_wei-r_val); //选一些合格的数字来填充中间剩下的位置 d2 %= mod; ans = d1+d2; } //out ans %= mod; cout<<ans<<endl; return; }