提供一个简单的思路： 理解题意后可见最终状态是如下的其中一种   简而言之就是0块、1块交替，共4个块，两种情况分别考虑即可，此处行文以第一个情况为例。由于，可以接受直接枚举四个块的分界处。不妨将三个分界处记到前三个块的最后一个元素的索引。那么，对于第二个块，代价为  其中，指上0的个数，预处理即可。其他几个块的情况类似。 AC代码: #include <cassert> #include <climits> #include <iostream> #include <string> #include <vector> using n...

提供一个精简的AC代码 #include <cassert> #include <iostream> using namespace std; const unsigned int mask = 0b111111111111; int solve(int o, int x,int p){ switch (o) { case 1 : return (x<<p)&mask; case 2 : return (x>>p)|(mask^(mask>>p)); case 3 : return x&~(1<<p); c...

数位删除得到的值是原数值的子序列，只需要生成所有子序列，然后检查即可。 子序列的个数（至多）是，故时间复杂度为，可行. #include <climits> #include <iostream> #include <string> #include <utility> #include <vector> using namespace std; using vpii = vector<pair<int, int>>; vpii subseqSet(int a) { auto s = to_string(a);...

本题核心在于  因此，答案若分为奇数个段（段内取异或，段间取按位与），那么计算结果为1的位置都可以由上述等式改为异或运算，计算结果为0的位置改为异或后结果可能更大。因此，只弄成一个段取异或是奇数情况的最优解。 若分为偶数个段，讨论是类似的，由于偶数个1的异或为0，不能全部改成异或。但是可以将个段的按位与改成异或，和上面讨论类似，结果是更优的。因此，弄成2个段的按位与是偶数的最优。 因此，对于最优的答案，要么分成奇数段，要么分成偶数段，总能落到上面两种讨论中。对于奇数，取全部数的异或即可。对应偶数，由于不确定哪个地方分割出2个段，枚举即可。两种情况比较即可得出答案

便于分析的定义：  必胜态(记为N-position)：做出最优决策，必然胜利的状态 必败态(记为P-position):做出任何决策无法胜利的状态  形式化的，有定义：  无法移动的状态为P 存在移动可以到达到P的状态为N 任意移动都会到N的状态为P  注：需要将游戏考虑为一个状态图，状态指当前局面和下一步的玩家，特别的，对于这类公平组合游戏，状态图是DAG。N-position指 Next play win，即先手必胜；P-position指 Previous player win，即后手必胜。 基于以上定义，考虑题给的扩展巴什博弈，状态被量化为当前石子数量。  为P 可取个移动到P，故为...

提供一个码量小，无__int128的ac代码，不保证所有场景都正确(( #include <iostream> #include <cmath> #include <algorithm> using namespace std; void solve() { long long n, k; cin >> n >> k; long double ld_n = n; long long m = pow(ld_n, 1.0 / k); long double val1 = pow((long double)m, k); long doubl...

简单考虑一下，众数最多要么就全是同一个数有个，做不到则可以个1以及一个. 前者是简单的，考虑sum%n==0即可直接判断，并计算即可。 我们来考虑第二种情况，在这种情况下，最终结果将会是个和一个. 记为sum。那么满足  此时我们不知道哪个值会成为，不妨记为，那么最终操作次数就是各个值到最终值距离的一半。为了便于行文，我们忽略这个一半，记代价函数  那么最终答案就是 固定， 考虑增加1时，的变化： 第一项的变化值为，第二项中，若有个大于的，那么变化就是 我们发现，第二项的增量，换句话说，变换时，是增是减完全由第一项决定，因此要让第一项尽可能小，也即  否则就能让x变化，达到这个区间。而这个式子...

题目目标在于找到各个连续0序列，算出计数贡献后乘起来。 因此， 核心的任务在于，对于一个[l,0,0,...,0,r]的序列，如何求出其计数贡献。 我们将0的个数记为，形式化地，问题为：  个数的数列满足以下表达式，求符合的数量   这个事情的需求有两个：  单调不减 整个数列在内  如果我们要手动做这么个事情，有两种思考方式：从1入手考虑和从2入手考虑。 如果优先考虑单调不减 由得到范围，再由得到范围，这样计算方案是很困难的，需要个求和 如果优先考虑范围 如果我们选出范围符合的数列，如何得到单调不减？很简单，排序即可。 换句话说，我们（可重复）选出个范围符合的数，排序后就是一个解。 这个排序...

暴力即可：枚举起点dfs。理论上时间复杂度为, 不过由于路径值增长很快（每加一位数，相当于乘以2，大于后即可剪枝），因此单次dfs深度不超过，因此实际时间复杂度为  #include <iostream> #include <string> #include <vector> using namespace std; int main() { long long n, l, r; cin >> n >> l >> r; string s; cin >> s; vector<vector<int&gt...

计算即可，但需要注意，如果直接枚举计算，将会是的复杂度，我们需要跳过一些不必要的计算：如果对有贡献，那么对都有贡献，因此可以从枚举，计算对哪些项有贡献。 事实上，形如以下的(比如说大运算符换成求积)，若需要求整个，都可以这么算，可以证明总时间复杂度为.  时间复杂度的证明并不困难，这里仅粗略解释一下： 由于跳过了不整除的， 事实上求的工作量为，因此求和得到  #include <iostream> #include <vector> using namespace std; int main() { int n,a1,m; cin >> n >>...

#include <cassert> #include <iostream> #include <unordered_map> #include <vector> #include <bits/stdc++.h> using namespace std; struct DSU { vector<int> fa, sz; int component; DSU(int n, int type = 0) : fa(n + type), sz(n + type, 1) { iota(fa.begin(), fa.end(), 0)...

#include <iostream> using namespace std; // n=2 // 0 0 -> 0 // 1 0 -> 1 // 0 1 -> 1 // 1 1 -> 0 // inner loop : a_i&a1 | a_i&a2 | ... a_i&an, if(a_i==1) ->1 // if (a_i == 0) --> 0 // inner loop = a_i int solve(){ int n; cin >> n; int ans = 0; while(n--){ int...

#include <iostream> #include <queue> #include <vector> using namespace std; int main() { int n; cin >> n; vector<int>a(n,0); for(int i=0;i<n;i++) cin >> a[i]; int b; cin >> b; vector<int> hi; for(int i=0;i<n;i++) if(a[i]>b) hi.push_back(i); in...

#include <any> #include <cstdlib> #include <iostream> #include <utility> using namespace std; // corner case : 一者已经在终点--> bool arrive // dis(pos1,dst)=dis(pos2,dst)->true // 考虑同行情况，如果两者都在第一行，A近B远，对B做阻挡是无意义的，因此AB之间不会有障碍，对A做阻挡，同样也是对B的阻挡，因此总不行 // 考虑不同行情况，分三种，第二行的列大、等、小 // ...