【实战题解】逆序对排列数 给定两个数n，k，如果1~n的某个排列p[]，在满足下面2个条件的时称之为美丽： - p[1] < p[2] - p[]的逆序对数目<=k 输出美丽的排列数目（取模1e9+7） n, k = 200 n >= 3思路首先显然是一个经典的dp[s][t]=z：表示用1~s的数字构成的排列，逆序对数目为t的个数是z。这个经典的dp解法比较多，比如我们可以每次转移的时候，看作是新添加了数字s，这样我们仅需枚举s所处的位置即可，其实也就是枚举新增加的逆序对数目p：$$ dp[s][t] = \sum_{p=0}^{\min(s-1,t)}dp[s-1][t-p] $$显然p的范围应该是[0, s-1]，但是考虑到dp中t的设计，所以最大也只能取t当然上面这个做法的复杂度显然就是O(n^2^k)或者O(nk^2^)的，这个复杂度还可以优化一下（虽然在这个题里是可行的）。其实这个优化也很容易看出来，我们先假设dp[s][<0] = 0，这样的话公式就可以去掉min值，也就可以转为，这样就可以O(nk)计算了：$$ dp[s][t] = \sum_{p=0}^{s-1}dp[s-1][t-p] = dp[s-1][t] + dp[s][t-1] - dp[s-1][t-s] $$如果不能理解上述式子，可以画格子图加深理解，计算过程略另外dp还有一种思路，即每次添加的数字位置固定是最后一位，枚举添加数字的值，这个看似比较奇怪，但是由于逆序对本身只考虑值的相对大小，而非绝对值，所以也是可以的，用类似的思路也是可以优化到O(nk)的当然记得初始化dp[0][0]=1随后我们枚举p[1]和p[2]的值，baseInv就是后面n-2个元素和p[1] p[2]的逆序对数目，这是一个确切值，先计算。invMax就是后n-2个元素，自己逆序对的最大数目。这题来说，这里也可以暴力求解，不过还是使用了一个前缀和进行优化。代码#include<bits/stdc++.h> using namespace std; #define int long long const int mod = 1e9 + 7; const int maxn = 2e2 + 5; int n, k; int dp[maxn][maxn]; int pre[maxn][maxn]; signed main() { cin >> n >> k; dp[0][0] = 1; for (int s = 1; s <= n - 2; ++s) { for (int t = 0; t <= k; ++t) { dp[s][t] = 0; for (int l = 0; l <= min(s - 1, t); ++l) dp[s][t] = (dp[s][t] + dp[s - 1][t - l]) % mod; } } for (int s = 0; s <= n - 2; ++s) { pre[s][0] = dp[s][0]; for (int t = 1; t <= k; ++t) pre[s][t] = (pre[s][t - 1] + dp[s][t]) % mod; } int ans = 0; for (int p1 = 1; p1 <= n; ++p1) { for (int p2 = p1 + 1; p2 <= n; ++p2) { int baseInv = p1 + p2 - 3; // 基础的逆序对数 if (baseInv > k) continue; int invMax = k - baseInv; // 剩下 n-2 个数的逆序对数的上限 ans += pre[n - 2][invMax]; ans %= mod; } } cout << ans << endl; return 0; }

Codeforces Round 930 (Div. 2) Bitwise Operation Wizard算法本质思维题目大意存在长度n的排列p（0开始），现在需要找到下标i j，使得p[i]^p[j]的值最大。玩家至多可以进行3n轮以下询问：询问每次需要给出a b c d四个整数，会返回p[a] | p[b]于p[c] | p[d]的大小关系：小于、等于、大于思路推演4个整数的询问比较少见，变数比较多，所以我们反向思考——怎样的两个数异或值最大。举个例子，若n=14，异或最大值就是>=n的最小2的幂值，即16，显然较大的值是比较容易得到16的。如果我们使用a a b b的询问，显然n轮就可以得到谁是最大值p。接下来需要找到另外一个恰好的值：所有与p或是16的下标的最小值。这个讲起来比较玄学，但是没法，这种题就是不断发散思维一直碰撞ac核心代码下面代码对询问次数进行了一些压缩，属于没必要的优化。头文件、宏定义、快读模板、常见变量、常见变量等略。 char ask(int a, int b, int c, int d) { cout<<"? "<<a<<" "<<b<<" "<<c<<" "<<d<<endl; char ans; cin>>ans; return ans; } int getmax(const vector<int> &v) { int p = v[0]; for (int i=1; i<v.size(); i++) { if (ask(p, p, v[i], v[i]) == '<') p = v[i]; } return p; } int getmin(const vector<int> &v) { int p = v[0]; for (int i=1; i<v.size(); i++) { if (ask(p, p, v[i], v[i]) == '>') p = v[i]; } return p; } inline void solve() { cin>>n; vector<int> v(n); iota(v.begin(), v.end(), 0); int maxp = getmax(v); int last=(maxp==0?1:0); v.clear(); v.push_back(last); for (int i=last+1; i<n; i++) { if (i==maxp) continue; char c=ask(maxp, last, maxp, i); if (c=='<') last=i, v.clear(), v.push_back(last); else if (c=='=') v.push_back(i); } int q = getmin(v); cout<<"! "<<maxp<<" "<<q<<endl; return; }Pinball算法本质思维、数据结构题目大意给定由>和<组成的长度n字符串。如果小人现在处于>上，就会花费1秒向右移动一格，同时>会反转为<。现在请给出小人初始在1~n的情况，花费多少时间会掉出字符串。思路推演模拟一下，这个游戏实际很简单，可以改成这样：（初始时）小人左侧的>看作一个墙，<看作空地小人右侧的<看作一个墙，>看作空地小人脚下的字符表示初始行动方向小人遇到墙，会将墙撞碎（变为空地），然后向反方向行走我们想要知道小人多久出去，先得知道从哪边出去。需要判断一下小人左侧和右侧的墙的数目（使用前缀和），根据小人的初始方向就可以确定。这个时候我们可以得到2个值：撞碎左边墙的数目、撞碎右边墙的数目。现在需要计算撞碎这些墙所需要的时间。这个的解决方法有很多，我们可以维护一个花费时间的前缀和，然后使用数目前缀和+二分来确定位置，确定位置后使用时间前缀和得到时间。ac核心代码代码写的比较复杂，还没有优化就不放了。头文件、宏定义、快读模板、常见变量、常见变量等略。 title算法本质题目大意思路推演ac核心代码头文件、宏定义、快读模板、常见变量、常见变量等略。 title算法本质题目大意思路推演ac核心代码头文件、宏定义、快读模板、常见变量、常见变量等略。 title算法本质题目大意思路推演ac核心代码头文件、宏定义、快读模板、常见变量、常见变量等略。 title算法本质题目大意思路推演ac核心代码头文件、宏定义、快读模板、常见变量、常见变量等略。 title算法本质题目大意思路推演ac核心代码头文件、宏定义、快读模板、常见变量、常见变量等略。

Codeforces Round 931 (Div. 2) Find a Mine算法本质思维题目大意矩阵地图中，有2颗地雷（坐标未知），玩家可以进行至多3次探测：制定一个坐标返回2颗地雷与坐标的曼哈顿值的较小值最后输出某颗地雷的坐标。思路推演矩阵中的曼哈顿值很有趣，如果在中间部分放置，其地雷可能存在的地方是一个正菱形。显然，如果我们在角落进行探测，可能的范围会缩小。进一步可以发现，如果在两个对角进行探测，则可以锁定两个地雷所在的斜线，在任意选一个位置探测即可。经验这类题其实比较典型，既然是3个操作，2个地雷，其过程很有可能是，通过前1-2次操作，可以获得两颗地雷的部分信息（两者的信息量是一致的），然后使用最后的操作获取某个地雷的所有信息。ac核心代码头文件、宏定义、快读模板、常见变量、常见变量等略。 int ask(int x, int y) { cout<<"? "<<x<<" "<<y<<endl; return in(); } bool ck(int x, int y) { if (x<1 || x>n || y<1 || y>m) return 0; return 1; } inline void solve() { cin>>n>>m; int d1=ask(1, 1), d2=ask(n, m), d3=ask(n, 1); set<pair<int,int>> cod; if ((d1+d3-n+1)%2==0) // 说明左侧上下有交点 { int rt = (d1+d3-n+1)/2; int y = rt + 1; int x = d1 - rt + 1; if (ck(x, y)) cod.insert({x, y}); } if ((d2+d3-m+1)%2==0) { int up = (d2+d3-m+1)/2; int x = n - up; int y = d3 - up + 1; if (ck(x, y)) cod.insert({x, y}); } if (cod.size()==2) { auto [x, y] = *cod.begin(); int dis = ask(x, y); if (dis) cod.erase({x, y}); else { cod.clear(); cod.insert({x, y}); } } auto [x, y] = *cod.begin(); cout<<"! "<<x<<" "<<y<<endl; return; }XOR Break --- Solo Version算法本质思维题目大意给定初始值x和目标值y，需要玩家进行至多63回合，最终使得x==y值：（以下2个操作记作1回合）将x分解成2个值a b，需要保证：a^b == xa < xb < x然后选择将a或者b赋值给x输出转换过程1 < y < x < 1e18思路推演既然我们最后会选择a或b进行赋值，这明显告诉我们，不用管另一个值，只需要保证其合法即可。为了之后方便叙述，我们这里强制保证a < b模拟一下分解过程，发现一个很不错的性质：若x的二进制位高的某几位1并非单独b的话，之后的所有二进制位都可以任意分配这个性质特别好，如果y是比较小的情况的话，我们可以先构建a为y的超集，然后再得到y。我们进行了更多的模拟，发现如果y的最高位不超过初始x的次高位（从高往低，第2个出现1的位），则可以如此构建。如果x仅有1位，显然不可行例如：（左边是高位） x = 101000 y = 000101 我们构建 a = y 如果y在x的次高位上没有值，则a=y+x次高位 a = 001101 b = x^a 同时这样会保证：b<x 且 a是y的超集接着我们考虑其他情况，如果y的最高位介于x的最高位和次高位之间，可以证明这样没有解。如果y的最高位同x的最高位一致，又因为保证了y<x——所以我们可以直接使得b=y, a=x^b，一步到位。63次操作属于障眼法ac核心代码头文件、宏定义、快读模板、常见变量、常见变量等略。 int get_top(int x) { while (x > lowbit(x)) x-=lowbit(x); return x; } inline void solve() { int a, b, c; cin>>a>>b; int tar=b; c = a^b; if (get_top(a) == get_top(b)) { cout<<1<<endl; cout<<a<<" "<<b<<endl; return; } flag = 1; int val = a; val -= get_top(val); val = get_top(val); // 获取次高位的值 if (b >= val*2) // 如果介于高位和次高位之间,无解 { cout<<"-1"<<endl; return; } else if ((b&val)==0) // 有解,开始制造超集 b+=val, c-=val; if (b==tar) // 有可能超集刚好相等，所以一步到位 { cout<<1<<endl; cout<<a<<" "<<b<<endl; } else // 使用超集作为中间值 { cout<<2<<endl; cout<<a<<" "<<b<<" "<<tar<<endl; } return; }XOR Break --- Game Version算法本质思维、简单博弈题目大意（小改）玩家和系统进行博弈游戏，两者轮流执行以下操作：从a b两个值中选择一个作为x将x分解成2个值a b，需要保证：a^b == xa < xb < x如果无法分解，记作当前玩家输掉游戏初始系统给定的a b保证a==b（但是游戏过程中不一定会相等了）。玩家可以选择先手或者后手，需要在63回合内击败对手（自己行动才记作一个回合）。输出游戏过程。思路推演我们考虑，如果x值的二进制位仅有一个1，则显然无法分解，会失败。所有有两个1就是必胜态。但是当继续推理时，情况就十分复杂了——因为对手有2个选择。博弈论的一部分，需要我们观察到更加内核本质的变化，从而逼迫对手一直处于必败态。奇偶是一个比较常思考的方向，考虑到异或的特殊性，我们可以一直让对手的x处于由奇数个1组成，而我们的x由偶数个1组成。稍加模拟，发现可行。接下来我们需要在63回合获胜，就需要防止对手一直拖回合。考虑到单个1无法分解，于是对于x，我们可以把最高位的1作为a，剩余的值作为b，对手就会被迫选择b，这样每回合至少都减少了一个高位1，63回合绰绰有余。这题2400，不理解，从过题人数结合难度来看，大概2100-2200吧。因为当时标2400，思考简单博弈的时候，还自我否定，想着2400怎么可能一个简单博弈出来了。ac核心代码头文件、宏定义、快读模板、常见变量、常见变量等略。 int get_top(int x) { while (x > lowbit(x)) x-=lowbit(x); return x; } int get_num(int x) { int res=0; while (x) x-=lowbit(x), res++; return res; } void send(int x) { int a=get_top(x); int b=x-a; cout<<a<<" "<<b<<endl; } int recceive() { int a, b; cin>>a>>b; return (get_num(a)%2==0 ? a : b); } inline void solve() { int x; cin>>x; if (get_num(x)%2) cout<<"second"<<endl; else { cout<<"first"<<endl; send(x); } while (1) { x = recceive(); if (x==0) break; send(x); } return; }title算法本质题目大意思路推演ac核心代码头文件、宏定义、快读模板、常见变量、常见变量等略。 title算法本质题目大意思路推演ac核心代码头文件、宏定义、快读模板、常见变量、常见变量等略。 title算法本质题目大意思路推演ac核心代码头文件、宏定义、快读模板、常见变量、常见变量等略。 title算法本质题目大意思路推演ac核心代码头文件、宏定义、快读模板、常见变量、常见变量等略。

Codeforces Round 926 (Div. 2) Sasha and the Casino算法本质思维题目大意玩家初始有a个硬币，可以选择进行任意回合游戏，每回合游戏规则如下：玩家选择y个硬币作为门票主办方直接决定玩家的胜负，如果玩家胜利会获得ky个硬币，反之什么得不到同时也有一条对主办方的限制：无法使得玩家连续失败x+1次。已知k x a，询问玩家是否可以赢得$100^{100^{100}}$个硬币。思路推演联想到“倍投法”。显然这个游戏规则十分适合倍投，因为在x+1回合里必然有胜利。但不同的是，玩家胜利获得的硬币数是ky而不一定是2y。这引导我们深入一些思考倍投的内涵。显然我们以每次胜利作为一个阶段，我们仅需保证每个阶段都不亏钱即可——保证每次的收益都可以覆盖之前的损失，同时保证投的钱最少即可。检查复杂度，可行。ac核心代码头文件、宏定义、快读模板、常见变量、常见变量等略。 inline void solve() { int k, x, a; cin>>k>>x>>a; int pre=0; flag = 1; for (int i=1; i<=x+1; i++) { int y = (pre + k-2) / (k-1); y += (pre % (k-1) == 0); pre += y; if (pre > a) { flag = 0; break; } } cout<<(flag?"YES":"NO")<<endl; return; }Sasha and a Walk in the City算法本质思维、dp题目大意给定树结构，节点初始全白，玩家可以给任意节点涂黑，如果涂色后树结构满足任意一条简单路径上黑点数目<=2则称之为美丽。输出玩家可以创造的美丽树结构数目。思路推演很显然的树形dp题目，所以从树形dp的角度去思考，可以缩小方法。如果要记录中途点u状态，我们仅能记录点u到其子树的任意一条简单路径上的最多黑点数目。构建dp[u][i]表示：点u到其子树的任意一条简单路径上的最多黑点数目为i个的方法数。dp[u][0]显然只能为1。dp[u][1]，考虑两种情况：u是黑色和u非黑色。dp[u][2]，考虑两种情况：u是黑色和u非黑色。具体的公式看代码ac核心代码头文件、宏定义、快读模板、常见变量、常见变量等略。 void dfs(int u, int fr, vector<vector<int>> &g, vector<int> &dp1, vector<int> &dp2) { for (int v:g[u]) { if (v==fr) continue; dfs(v, u, g, dp1, dp2); dp1[u] = dp1[u] * (dp1[v]+1) % mod; dp2[u] += dp1[v] + dp2[v]; dp2[u] %= mod; } } inline void solve() { cin>>n; vector<vector<int>> g(n+5); vector<int> dp1(n+5, 1), dp2(n+5); for (int i=1; i<n; i++) { int u, v; cin>>u>>v; g[u].push_back(v); g[v].push_back(u); } dfs(1, 0, g, dp1, dp2); int ans = 1 + dp1[1] + dp2[1]; ans %= mod; cout<<ans<<endl; return; }title算法本质题目大意思路推演ac核心代码头文件、宏定义、快读模板、常见变量、常见变量等略。 title算法本质题目大意思路推演ac核心代码头文件、宏定义、快读模板、常见变量、常见变量等略。 title算法本质题目大意思路推演ac核心代码头文件、宏定义、快读模板、常见变量、常见变量等略。 title算法本质题目大意思路推演ac核心代码头文件、宏定义、快读模板、常见变量、常见变量等略。 title算法本质题目大意思路推演ac核心代码头文件、宏定义、快读模板、常见变量、常见变量等略。

Codeforces Round 924 (Div. 2) Lonely Mountain Dungeons算法本质思维、数学、三分题目大意给定整数b x，有n种士兵，c[]表示每种士兵的数目。玩家需要将所有士兵分成k支队伍：（k由玩家指定）分成k支队伍花费(k-1)*x若某2个士兵属于同兵种且不在同一支队伍，则收益b输出最大收益。思路推演首先想到的就是，士兵如何分队才能收益最大。显然每种士兵之间互不打扰，然后就是没有任意同种士兵同一队伍，这肯定可以收益最大，但是同理我们需要付出更多的成本。但是这是一种思考方式，我们可以假设最初得到所有士兵的收益，若有同种士兵同队就扣去收益，这样计算显然更方便。退而求其次，我们考虑对于一种士兵，有a个分配到k个队伍中。隐约觉得平摊分是最合理的，我们可以来证明。证：若存在a个同种士兵面对k支队伍，尽可能平摊分配是最优解。 平摊分配的意思是： a%k 支队伍有 a/k+1 人 k-a%k 支队伍有 a/k 人 我们使用反证法： 对于任意一种非平摊分配法，都可以视作在平摊仅执行任意次以下操作： * 选择2支队伍，其人数分别是a b，保证a>=b，将其人数更改为a+1 b-1 接下来我们证明，执行这个操作会导致收益降低或不变 对于任意一支有c同种人数的队伍，其收益会降低：f(c)=c(c-1)/2 所以实际上就是证明 f(a)+f(b) <= f(a+1)+f(b-1) 自行计算即可，实际上最后发现是必定小于的，没有等于情况我们可以得到公式：$f(x)=\frac{x*(x-1)}{2}$$sum = \sum_{i=1}^nf(c_i)*b$$cost(k) = (k-1)*x + b*( (k-c_i\%k)*f(c_i/k) + (c_i\%k)*(c_i/k+1) )$$ans(k) = sum - cost(k)$注意公式中的除法表示向下整除所以我们实际上是需要找到一个k来最小化ans。其中sum的值是固定的，观察cost(k)，这个函数由2部分组成，一部分是递增的线性函数，另一部分是递减双曲线函数的平方。显然这可以使用三分搞定。ac核心代码头文件、宏定义、快读模板、常见变量、常见变量等略。 int a[maxn]; int f(int x) { if (x<=0) return 0; return x*(x-1)/2; } int g(int k, int b, int x) // 注意这个计算的是负收益 { int res = (k-1)*x; for (int i=1; i<=n; i++) res += b*( (k-a[i]%k)*f(a[i]/k) + (a[i]%k)*f(a[i]/k+1) ); return res; } int tri_search(int l,int r, int b, int x) { // 求凹函数的极小值 int f1, f2; while(l < r) { int lp = l + (r - l) / 3; int rp = r - (r - l) / 3; f1 = g(lp, b, x), f2 = g(rp, b, x); if(f1 <= f2) r = rp - 1; else l = lp + 1; } //查找的是极小值 return min(f1,f2); //查找的是极小值对应的下标 return f1<f2?l:r; } inline void solve() { int b, x; cin>>n>>b>>x; for (int i=1; i<=n; i++) cin>>a[i]; sort(a+1, a+1+n); int cost = tri_search(1, a[n], b, x); int ans=0; for (int i=1; i<=n; i++) ans += f(a[i])*b; ans -= cost; cout<<ans<<endl; return; }title算法本质题目大意思路推演ac核心代码头文件、宏定义、快读模板、常见变量、常见变量等略。 title算法本质题目大意思路推演ac核心代码头文件、宏定义、快读模板、常见变量、常见变量等略。 title算法本质题目大意思路推演ac核心代码头文件、宏定义、快读模板、常见变量、常见变量等略。 title算法本质题目大意思路推演ac核心代码头文件、宏定义、快读模板、常见变量、常见变量等略。 title算法本质题目大意思路推演ac核心代码头文件、宏定义、快读模板、常见变量、常见变量等略。 title算法本质题目大意思路推演ac核心代码头文件、宏定义、快读模板、常见变量、常见变量等略。