前言就今年这题的风格真得多写 cf 了……感觉和 23、24 年的风格完全不一样vp 的训练价值感觉不是很大……一、A. Moo Language School#include bits/stdc.h #include cassert using namespace std; /* /\_/\ * ( ._.) * / \ */ /* *想好再写 *注意审题 注意特判 *不要红温 不要急躁 耐心一点 *WA了不要立马觉得是思路不对 先耐心找反例 */ #define endl \n #define dbg(x) cout#x xendl; #define vdbg(a) cout#aendl;for(auto x:a)coutx ;coutendl; #define YES coutYESendl;return ; #define Yes coutYesendl;return ; #define NO coutNOendl;return ; #define No coutNoendl;return ; #define popcount __builtin_popcount using lllong long; using i128__int128; using ldlong double; using piipairint,int; using pllpairll,ll; const int INF1e9; const ll INFLL1e18; const int dx[]{-1,1,0,0}; const int dy[]{0,0,-1,1}; const int ddx[]{-2,-1,1,2,2,1,-1,-2}; const int ddy[]{1,2,2,1,-1,-2,-2,-1}; void solve() { int n,k; cinnk; string s; cins; s s; int ans0; for(int i1;in;ik) { int ok0; for(int ji;jik-1;j) { if(s[j]0) { ok1; break; } } if(!ok) { ans; } } coutansendl; } /* 6 8 2 10011100 5 1 11111 8 4 01111110 5 1 00101 4 4 1101 4 4 1111 1 5 0 2 0 1 */ void init() { } signed main() { ios::sync_with_stdio(0);cin.tie(0);cout.tie(0); int t1; cint; init(); while(t--) { solve(); } return 0; }没啥好说的直接判断每组中是否有 0 即可。二、B. Minus Two#include bits/stdc.h #include cassert using namespace std; /* /\_/\ * ( ._.) * / \ */ /* *想好再写 *注意审题 注意特判 *不要红温 不要急躁 耐心一点 *WA了不要立马觉得是思路不对 先耐心找反例 */ #define endl \n #define dbg(x) cout#x xendl; #define vdbg(a) cout#aendl;for(auto x:a)coutx ;coutendl; #define YES coutYESendl;return ; #define Yes coutYesendl;return ; #define NO coutNOendl;return ; #define No coutNoendl;return ; #define popcount __builtin_popcount using lllong long; using i128__int128; using ldlong double; using piipairint,int; using pllpairll,ll; const int INF1e9; const ll INFLL1e18; const int dx[]{-1,1,0,0}; const int dy[]{0,0,-1,1}; const int ddx[]{-2,-1,1,2,2,1,-1,-2}; const int ddy[]{1,2,2,1,-1,-2,-2,-1}; void solve() { int n; cinn; vectorinta(n1); for(int i1;in;i) { cina[i]; } int one0; int odd0; int even0; for(int i1;in;i) { if(a[i]%2) { one; } else { if(a[i]/2%2) { odd; } else { even; } } } coutmax({one,odd,even})endl; } /* 5 2 1 3 4 1 1 1 2 3 6 7 8 4 2 2 2 2 5 1 10 100 1000 100000 2 3 1 4 3 */ void init() { } signed main() { ios::sync_with_stdio(0);cin.tie(0);cout.tie(0); int t1; cint; init(); while(t--) { solve(); } return 0; }由于是绝对值所以所有数在减到 0 以后就会进入循环。对于奇数就是一直是 1对于偶数就是 0 和 2 一直循环。那么就只需要统计奇数的个数以及偶数除以 2 后奇偶的个数因为需要判断偶数在某个时刻 0 的个数和 2 的个数。三、C. 101#include bits/stdc.h #include cassert using namespace std; /* /\_/\ * ( ._.) * / \ */ /* *想好再写 *注意审题 注意特判 *不要红温 不要急躁 耐心一点 *WA了不要立马觉得是思路不对 先耐心找反例 */ #define endl \n #define dbg(x) cout#x xendl; #define vdbg(a) cout#aendl;for(auto x:a)coutx ;coutendl; #define YES coutYESendl;return ; #define Yes coutYesendl;return ; #define NO coutNOendl;return ; #define No coutNoendl;return ; #define popcount __builtin_popcount using lllong long; using i128__int128; using ldlong double; using piipairint,int; using pllpairll,ll; const int INF1e9; const ll INFLL1e18; const int dx[]{-1,1,0,0}; const int dy[]{0,0,-1,1}; const int ddx[]{-2,-1,1,2,2,1,-1,-2}; const int ddy[]{1,2,2,1,-1,-2,-2,-1}; void solve() { int n; cinn; vectorinta(n1); for(int i1;in;i) { cina[i]; } int s0; for(int i1;in;i) { if(a[i]) { si; break; } } if(s0) { for(int i1;in;i) { couta[i] ; } coutendl; return ; } int e0; for(int in;i1;i--) { if(a[i]) { ei; break; } } a[s]1,a[e]1; for(int is;ie;i) { int ji1; while(je(a[j]0||a[j]-1)) { a[j]0; } ij-1; } for(int i1;in;i) { couta[i] ; } coutendl; } /* 10 6 1 0 -1 0 0 1 7 0 -1 0 0 1 0 1 5 -1 0 0 -1 0 4 0 0 0 0 1 -1 6 1 0 1 0 0 -1 7 0 1 0 0 0 1 0 6 -1 -1 -1 -1 -1 -1 7 -1 0 1 -1 0 0 1 3 -1 0 0 1 0 0 0 0 1 0 1 0 0 1 0 1 1 0 0 1 0 0 0 0 0 1 1 0 1 0 0 1 0 1 0 0 0 1 0 1 0 0 0 0 1 0 0 1 0 0 0 1 1 0 0 */ void init() { } signed main() { ios::sync_with_stdio(0);cin.tie(0);cout.tie(0); int t1; cint; init(); while(t--) { solve(); } return 0; }这个题一个最本质的想法就是找到一个 1然后贪心地往后扩碰到的 -1 全部变成 0直到碰到第一个确定的 1。那么就是找到最左和最右的 1 或 -1然后往后扩即可。四、D. MEX Multiset这题真写麻烦了……#include bits/stdc.h #include cassert using namespace std; /* /\_/\ * ( ._.) * / \ */ /* *想好再写 *注意审题 注意特判 *不要红温 不要急躁 耐心一点 *WA了不要立马觉得是思路不对 先耐心找反例 */ #define endl \n #define dbg(x) cout#x xendl; #define vdbg(a) cout#aendl;for(auto x:a)coutx ;coutendl; #define YES coutYESendl;return ; #define Yes coutYesendl;return ; #define NO coutNOendl;return ; #define No coutNoendl;return ; #define popcount __builtin_popcount using lllong long; using i128__int128; using ldlong double; using piipairint,int; using pllpairll,ll; const int INF1e9; const ll INFLL1e18; const int dx[]{-1,1,0,0}; const int dy[]{0,0,-1,1}; const int ddx[]{-2,-1,1,2,2,1,-1,-2}; const int ddy[]{1,2,2,1,-1,-2,-2,-1}; void solve() { int n; cinn; vectorinta(n); for(int i0;in;i) { cina[i]; } vectorvectorintcnts(n1); for(int i0;in;i) { if(a[i]n) { continue; } cnts[a[i]].push_back(i); } string s(n,A); for(int v0;vn;v) { int mcnts[v].size(); if(m0) { break; } if(m1) { if(v0) { NO; } s[cnts[v][0]]C; break; } if(m2) { s[cnts[v][1]]B; } else { s[cnts[v][1]]B; s[cnts[v][2]]C; } } coutYESendl; coutsendl; } /* 5 6 1 0 0 1 2 1 4 0 0 0 0 3 0 2 2 4 6 7 6 7 5 0 0 0 1 2 */ void init() { } signed main() { ios::sync_with_stdio(0);cin.tie(0);cout.tie(0); int t1; cint; init(); while(t--) { solve(); } return 0; }首先令 A 为最大值集合那么就有 BC 要大于等于 A。直接说简单的做法若 0 出现了一次那么就无解0 没出现过也合法直接结束。否则的话将所有 0 都分给 A 和 B然后将剩下的数都给 C 就行了。此时 A 和 B 的 MEX 是 1C 的 MEX 是 0所以直接合法。五、E. Treasure Map Destruction (Constructive Version)#include bits/stdc.h #include cassert using namespace std; /* /\_/\ * ( ._.) * / \ */ /* *想好再写 *注意审题 注意特判 *不要红温 不要急躁 耐心一点 *WA了不要立马觉得是思路不对 先耐心找反例 */ #define endl \n #define dbg(x) cout#x xendl; #define vdbg(a) cout#aendl;for(auto x:a)coutx ;coutendl; #define YES coutYESendl;return ; #define Yes coutYesendl;return ; #define NO coutNOendl;return ; #define No coutNoendl;return ; #define popcount __builtin_popcount using lllong long; using i128__int128; using ldlong double; using piipairint,int; using pllpairll,ll; const int INF1e9; const ll INFLL1e18; const int dx[]{-1,1,0,0}; const int dy[]{0,0,-1,1}; const int ddx[]{-2,-1,1,2,2,1,-1,-2}; const int ddy[]{1,2,2,1,-1,-2,-2,-1}; void solve() { int n; cinn; vectorinta(n2); for(int i1;in;i) { cina[i]; } vectorintvis(n2); for(int i1;in;i) { if(a[i]0) { int lmax(1,i-a[i]1); int rmin(n,ia[i]-1); vis[l],vis[r1]--; } } for(int i1;in;i) { vis[i]vis[i-1]; } for(int i1;in;i) { if(a[i]0) { if(vis[i]) { cout-1endl; return ; } } else if(a[i]0) { int ok1(i-a[i]1!vis[i-a[i]]); int ok2(ia[i]n!vis[ia[i]]); if(!ok1!ok2) { cout-1endl; return ; } } } for(int i1;in;i) { cout(!vis[i]); } coutendl; } /* 12 5 0 1 -1 -1 0 3 -1 0 2 5 -1 1 -1 1 -1 5 -1 -1 -1 -1 -1 5 -1 2 -1 3 -1 7 2 1 0 1 0 1 2 1 -1 3 1 -1 1 1 0 4 3 -1 -1 -1 6 -1 -1 0 -1 2 4 10 -1 1 -1 -1 1 1 -1 -1 2 -1 */ void init() { } signed main() { ios::sync_with_stdio(0);cin.tie(0);cout.tie(0); int t1; cint; init(); while(t--) { solve(); } return 0; }首先考虑根据每个确定的位置统计出所有不能是宝藏的地方这个可以通过差分解决。之后考虑默认所有没受到约束的位置都是宝藏。那么对于已经确定是宝藏的位置若不能是宝藏就无解。对于确定下不是宝藏的位置若两侧都不能是宝藏也无解。六、F. Binary Bubble Sort Inversions#include bits/stdc.h #include cassert using namespace std; /* /\_/\ * ( ._.) * / \ */ /* *想好再写 *注意审题 注意特判 *不要红温 不要急躁 耐心一点 *WA了不要立马觉得是思路不对 先耐心找反例 */ #define endl \n #define dbg(x) cout#x xendl; #define vdbg(a) cout#aendl;for(auto x:a)coutx ;coutendl; #define YES coutYESendl;return ; #define Yes coutYesendl;return ; #define NO coutNOendl;return ; #define No coutNoendl;return ; #define popcount __builtin_popcount using lllong long; using i128__int128; using ldlong double; using piipairint,int; using pllpairll,ll; const int INF1e9; const ll INFLL1e18; const int dx[]{-1,1,0,0}; const int dy[]{0,0,-1,1}; const int ddx[]{-2,-1,1,2,2,1,-1,-2}; const int ddy[]{1,2,2,1,-1,-2,-2,-1}; void solve() { int n; cinn; vectorinta(n1); for(int i1;in;i) { cina[i]; } string s; cins; s s; int cnt0; ll ans0; for(int i1;in;i) { if(a[i]0) { anscnt; } else { cnt; } } coutans ; int zero0,ln1; for(int i1;in;i) { if(a[i]1) { li; for(int ji;jn;j) { if(a[j]0) { zero; } } break; } } int one0,r0; for(int in;i1;i--) { if(a[i]0) { ri; for(int ji;j1;j--) { if(a[j]1) { one; } } break; } } for(int i1;in;i) { if(s[i]1) { ans-max(0,zero); l,one--; while(lna[l]0) { zero--; l; } } else { ans-max(0,one); r--,zero--; while(r1a[r]1) { one--; r--; } } coutans ; } coutendl; } /* 7 4 1 1 0 0 1010 7 0 1 0 1 1 0 0 0101001 4 0 0 1 1 1001 1 1 1 5 0 1 1 0 0 11101 3 1 0 0 000 6 1 0 1 1 0 0 011000 4 2 1 0 0 7 4 2 0 0 0 0 0 0 0 0 0 0 0 0 4 2 0 0 0 0 2 1 0 0 7 4 2 1 0 0 0 */ void init() { } signed main() { ios::sync_with_stdio(0);cin.tie(0);cout.tie(0); int t1; cint; init(); while(t--) { solve(); } return 0; }手玩一下可以发现正向冒泡就是将第一个 1 段最后一个 1 移动到最后消除的逆序对数就是中间 0 的个数反向冒泡就是将最后一个 0 段第一个 0 移动到最前消除的个数就是中间 1 的个数。那么就可以先统计出一开始的逆序对数然后统计出第一个 1 到最后 0 的个数和最后一个 0 到开头 1 的个数然后每次移动指针同步更新个数即可。题解的 deque 太妙了……七、G. Index Removal#include bits/stdc.h #include cassert using namespace std; /* /\_/\ * ( ._.) * / \ */ /* *想好再写 *注意审题 注意特判 *不要红温 不要急躁 耐心一点 *WA了不要立马觉得是思路不对 先耐心找反例 */ #define endl \n #define dbg(x) cout#x xendl; #define vdbg(a) cout#aendl;for(auto x:a)coutx ;coutendl; #define YES coutYESendl;return ; #define Yes coutYesendl;return ; #define NO coutNOendl;return ; #define No coutNoendl;return ; #define popcount __builtin_popcount using lllong long; using i128__int128; using ldlong double; using piipairint,int; using pllpairll,ll; const int INF1e9; const ll INFLL1e18; const int dx[]{-1,1,0,0}; const int dy[]{0,0,-1,1}; const int ddx[]{-2,-1,1,2,2,1,-1,-2}; const int ddy[]{1,2,2,1,-1,-2,-2,-1}; void solve() { ll n,k; cinnk; vectorlla(n1); for(int i1;in;i) { cina[i]; } vectorllpre(n1); for(int i1;in;i) { pre[i]pre[i-1]a[i]; } auto query[](int l,int r)-ll { if(rn||lr) { return 0; } return pre[r]-pre[l-1]; }; auto calc[](int L,int R,ll base,int right)-ll { if(LR) { return 0; } int lL; int rR; int m; int ans-1; while(lr) { mlr1; if(right) { int lenm-L1; if(a[m]baselen*k) { ansm; rm-1; } else { lm1; } } else { int lenR-m1; if(a[m]base-len*k) { ansm; lm1; } else { rm-1; } } } if(right) { if(ans-1) { ansR1; } int lenans-L; ll resquery(L,ans-1)-(1ll*base*lenk*(len1)*len/2); return res0?INFLL:res; } if(ans-1) { ansL-1; } int lenR-ans; ll resquery(ans1,R)-(1ll*base*len-k*(len1)*len/2); return res0?INFLL:res; }; for(int i1;in;i) { ll lefti1n?calc(1,i-1,a[i1],0):INFLL; ll right1i-1?calc(i1,n,a[i-1],1):INFLL; ll ansmin(left,right); coutans ; } coutendl; } /* 7 4 2 1 2 4 5 4 1 1 2 3 4 5 7 1 8 9 16 20 5 1000000000 1 6 7 67 6767 6 1 1 1 2 2 3 4 4 1 1 2 3 3 4 2 1 2 4 6 0 1 1 0 0 2 1 0 0 2 1 4 0 0 0 0 0 0 0 0 0 0 1 0 0 1 0 0 0 2 2 0 */ void init() { } signed main() { ios::sync_with_stdio(0);cin.tie(0);cout.tie(0); int t1; cint; init(); while(t--) { solve(); } return 0; }因为 n 是那么就只能考虑每次快速求出答案。那么在删除后只需要让和满足约束即可。那么就是要么让减小要么让减小。以右侧为例那么就是基准线对于之后的数每个位置都有一个阈值即最大不能超过。此时就可以考虑二分找到往右第一个数使得那么范围的数就是需要减小的数这个可以通过前缀和快速求区间和相减得到。八、H. Treasure Map Destruction (Counting Version)#include bits/stdc.h #include cassert using namespace std; /* /\_/\ * ( ._.) * / \ */ /* *想好再写 *注意审题 注意特判 *不要红温 不要急躁 耐心一点 *WA了不要立马觉得是思路不对 先耐心找反例 */ #define endl \n #define dbg(x) cout#x xendl; #define vdbg(a) cout#aendl;for(auto x:a)coutx ;coutendl; #define YES coutYESendl;return ; #define Yes coutYesendl;return ; #define NO coutNOendl;return ; #define No coutNoendl;return ; #define popcount __builtin_popcount using lllong long; using i128__int128; using ldlong double; using piipairint,int; using pllpairll,ll; const int INF1e9; const ll INFLL1e18; const int dx[]{-1,1,0,0}; const int dy[]{0,0,-1,1}; const int ddx[]{-2,-1,1,2,2,1,-1,-2}; const int ddy[]{1,2,2,1,-1,-2,-2,-1}; templateclass T constexpr T power(T a, ll b) { T res 1; for (; b ! 0; b / 2, a * a) { if (b 1) { res * a; } } return res; } templateint M struct ModInt { public: constexpr ModInt() : x(0) {} templatetypename T constexpr ModInt(T x_) { T v x_ % M; if (v 0) { v M; } x v; } constexpr int val() const { return x; } constexpr ModInt operator() { x; if (x M) { x 0; } return *this; } constexpr ModInt operator(int) { ModInt res *this; (*this); return res; } constexpr ModInt operator--() { if (x 0) { x M - 1; } else { x--; } return *this; } constexpr ModInt operator--(int) { ModInt res *this; --(*this); return res; } constexpr ModInt operator-() const { ModInt res; res.x (x 0 ? 0 : M - x); return res; } constexpr ModInt inv() const { return power(*this, M - 2); } constexpr ModInt operator*(const ModInt rhs) { x ll(x) * rhs.val() % M; return *this; } constexpr ModInt operator(const ModInt rhs) { x rhs.val(); if (x M) { x - M; } return *this; } constexpr ModInt operator-(const ModInt rhs) { x - rhs.val(); if (x 0) { x M; } return *this; } constexpr ModInt operator/(const ModInt rhs) { return *this * rhs.inv(); } friend constexpr ModInt operator*(ModInt lhs, const ModInt rhs) { lhs * rhs; return lhs; } friend constexpr ModInt operator(ModInt lhs, const ModInt rhs) { lhs rhs; return lhs; } friend constexpr ModInt operator-(ModInt lhs, const ModInt rhs) { lhs - rhs; return lhs; } friend constexpr ModInt operator/(ModInt lhs, const ModInt rhs) { lhs / rhs; return lhs; } friend constexpr bool operator(ModInt lhs, const ModInt rhs) { return lhs.val() rhs.val(); } friend constexpr bool operator(ModInt lhs, const ModInt rhs) { return lhs.val() rhs.val(); } friend constexpr bool operator(ModInt lhs, const ModInt rhs) { return lhs.val() rhs.val(); } friend constexpr bool operator(ModInt lhs, const ModInt rhs) { return lhs.val() rhs.val(); } friend constexpr bool operator(ModInt lhs, const ModInt rhs) { return lhs.val() rhs.val(); } friend constexpr bool operator!(ModInt lhs, const ModInt rhs) { return lhs.val() ! rhs.val(); } friend constexpr std::istream operator(std::istream is, ModInt a) { ll i; is i; a i; return is; } friend constexpr std::ostream operator(std::ostream os, const ModInt a) { return os a.val(); } private: int x; }; templateint M, typename T ModIntM struct Comb { vectorT fac; vectorT inv; Comb(int n) { fac.assign(n, 1); for(int i1;in;i) { fac[i]fac[i-1]*i; } inv.assign(n, 1); inv[n-1]fac[n-1].inv(); for(int in-2;i0;i--) { inv[i]inv[i1]*(i1); } } templatestd::signed_integral U T P(U n, U m) { if(nm) { return 0; } return fac[n] * inv[n - m]; } templatestd::signed_integral U T C(U n, U m) { if(nm||m0) { return 0; } return fac[n] * inv[n - m] * inv[m]; } }; //power函数切记强转成 Z !!!!! constexpr int M 1e97; using Z ModIntM; constexpr int N 2e55; CombMcomb(N); templatestd::signed_integral U Z P(U n, U m) { return comb.P(n, m); } templatestd::signed_integral U Z C(U n, U m) { return comb.C(n, m); } void solve() { int n; cinn; vectorinta(n1); for(int i1;in;i) { cina[i]; } vectorZfib(n1); fib[0]1,fib[1]2; for(int i2;in;i) { fib[i]fib[i-1]fib[i-2]; } int all0; vectorintno(n2); for(int i1;in;i) { if(a[i]0) { if(a[i]-1) { all; } continue; } int lmax(1,i-a[i]1); int rmin(n,ia[i]-1); no[l],no[r1]--; } for(int i1;in;i) { no[i]no[i-1]; } for(int i1;in;i) { no[i](no[i]0); } vectorintmust(n1); for(int i1;in;i) { if(a[i]-1) { continue; } if(a[i]0) { if(no[i]) { cout0endl; return ; } must[i]1; continue; } int l(1i-a[i]!no[i-a[i]]); int r(ia[i]n!no[ia[i]]); if(!l!r) { cout0endl; return ; } if(l!r) { must[i-a[i]]1; } else if(!lr) { must[ia[i]]1; } } vectorinttbd; for(int i1;in;i) { if(!no[i]!must[i]) { tbd.push_back(i); } } int mtbd.size(); Z ans1; for(int i0,len1;im;i) { if(im-1) { ans*fib[len]; continue; } int ltbd[i]; int rtbd[i1]; if((r-l)%20a[(lr)/2](r-l)/2) { len; } else { ans*fib[len]; len1; } } if(alln) { ans--; } coutansendl; } /* 12 5 0 1 -1 -1 0 3 -1 0 2 5 -1 1 -1 1 -1 5 -1 -1 -1 -1 -1 5 -1 2 -1 3 -1 7 2 1 0 1 0 1 2 1 -1 3 1 -1 1 1 0 4 3 -1 -1 -1 6 -1 -1 0 -1 2 4 10 -1 1 -1 -1 1 1 -1 -1 2 -1 4 0 5 31 0 1 1 1 1 1 0 3 */ void init() { } signed main() { ios::sync_with_stdio(0);cin.tie(0);cout.tie(0); int t1; cint; init(); while(t--) { solve(); } return 0; }那么对于一个已经确定的就要求所有的位置 j 都没有宝藏且对于和这两个位置至少有一个宝藏。在这样操作后就可以得到若干个可能有宝藏的位置序列 S使得其要满足每一个的限制。此时可以发现对于一个位置 i其对应的 L 和 R 在 S 中必然相邻。这是因为中间被限制不能有宝藏所以不可能插入别的约束。之后若两个候选位置 L 和 R 中有一个已经被禁止放宝藏了那么其只会贡献一种方案。然后对于一个被破坏的位置若其既没有被禁止又没有位置需要它那么其可以有宝藏也可以没有所以贡献两种方案。而若必须进行决策那么对于序列 S最后必然形成若干条满足相邻两个或起来为 1 的链。举个例子对于 a[-1,1,-1,1,-1]其要求和这就构成了一条长度为 3 的链。那么首先对于已经确定的宝藏其就可以切断这条链使得左右互不影响。之后问题就转化为有多少个长度为 k 的 01 串满足不存在连续两个 0。对于这个问题考虑定义为 i 长度的合法串个数初始。那么对于第 i 个位置由于要求所以若当前位置填 1 就只需要前 i-1 个位置合法即。而若当前位置填 0。那么就要求 i-1 位置必须填 1所以就要求前 i-2 个位置合法即。所以转移就是就是斐波那契。此时注意到如果将所有没有被禁止又没确定的位置都统计进来。那么对于既没有被禁止又没有位置需要它的位置其自己就是一条链贡献的两种方案可以被统计到。总结cf 还是太考验思维了……END Codeforces 1119 Div3（ABCDEFGH）
前言就今年这题的风格真得多写 cf 了……感觉和 23、24 年的风格完全不一样vp 的训练价值感觉不是很大……一、A. Moo Language School#include bits/stdc.h #include cassert using namespace std; /* /\_/\ * ( ._.) * / \ */ /* *想好再写 *注意审题 注意特判 *不要红温 不要急躁 耐心一点 *WA了不要立马觉得是思路不对 先耐心找反例 */ #define endl \n #define dbg(x) cout#x xendl; #define vdbg(a) cout#aendl;for(auto x:a)coutx ;coutendl; #define YES coutYESendl;return ; #define Yes coutYesendl;return ; #define NO coutNOendl;return ; #define No coutNoendl;return ; #define popcount __builtin_popcount using lllong long; using i128__int128; using ldlong double; using piipairint,int; using pllpairll,ll; const int INF1e9; const ll INFLL1e18; const int dx[]{-1,1,0,0}; const int dy[]{0,0,-1,1}; const int ddx[]{-2,-1,1,2,2,1,-1,-2}; const int ddy[]{1,2,2,1,-1,-2,-2,-1}; void solve() { int n,k; cinnk; string s; cins; s s; int ans0; for(int i1;in;ik) { int ok0; for(int ji;jik-1;j) { if(s[j]0) { ok1; break; } } if(!ok) { ans; } } coutansendl; } /* 6 8 2 10011100 5 1 11111 8 4 01111110 5 1 00101 4 4 1101 4 4 1111 1 5 0 2 0 1 */ void init() { } signed main() { ios::sync_with_stdio(0);cin.tie(0);cout.tie(0); int t1; cint; init(); while(t--) { solve(); } return 0; }没啥好说的直接判断每组中是否有 0 即可。二、B. Minus Two#include bits/stdc.h #include cassert using namespace std; /* /\_/\ * ( ._.) * / \ */ /* *想好再写 *注意审题 注意特判 *不要红温 不要急躁 耐心一点 *WA了不要立马觉得是思路不对 先耐心找反例 */ #define endl \n #define dbg(x) cout#x xendl; #define vdbg(a) cout#aendl;for(auto x:a)coutx ;coutendl; #define YES coutYESendl;return ; #define Yes coutYesendl;return ; #define NO coutNOendl;return ; #define No coutNoendl;return ; #define popcount __builtin_popcount using lllong long; using i128__int128; using ldlong double; using piipairint,int; using pllpairll,ll; const int INF1e9; const ll INFLL1e18; const int dx[]{-1,1,0,0}; const int dy[]{0,0,-1,1}; const int ddx[]{-2,-1,1,2,2,1,-1,-2}; const int ddy[]{1,2,2,1,-1,-2,-2,-1}; void solve() { int n; cinn; vectorinta(n1); for(int i1;in;i) { cina[i]; } int one0; int odd0; int even0; for(int i1;in;i) { if(a[i]%2) { one; } else { if(a[i]/2%2) { odd; } else { even; } } } coutmax({one,odd,even})endl; } /* 5 2 1 3 4 1 1 1 2 3 6 7 8 4 2 2 2 2 5 1 10 100 1000 100000 2 3 1 4 3 */ void init() { } signed main() { ios::sync_with_stdio(0);cin.tie(0);cout.tie(0); int t1; cint; init(); while(t--) { solve(); } return 0; }由于是绝对值所以所有数在减到 0 以后就会进入循环。对于奇数就是一直是 1对于偶数就是 0 和 2 一直循环。那么就只需要统计奇数的个数以及偶数除以 2 后奇偶的个数因为需要判断偶数在某个时刻 0 的个数和 2 的个数。三、C. 101#include bits/stdc.h #include cassert using namespace std; /* /\_/\ * ( ._.) * / \ */ /* *想好再写 *注意审题 注意特判 *不要红温 不要急躁 耐心一点 *WA了不要立马觉得是思路不对 先耐心找反例 */ #define endl \n #define dbg(x) cout#x xendl; #define vdbg(a) cout#aendl;for(auto x:a)coutx ;coutendl; #define YES coutYESendl;return ; #define Yes coutYesendl;return ; #define NO coutNOendl;return ; #define No coutNoendl;return ; #define popcount __builtin_popcount using lllong long; using i128__int128; using ldlong double; using piipairint,int; using pllpairll,ll; const int INF1e9; const ll INFLL1e18; const int dx[]{-1,1,0,0}; const int dy[]{0,0,-1,1}; const int ddx[]{-2,-1,1,2,2,1,-1,-2}; const int ddy[]{1,2,2,1,-1,-2,-2,-1}; void solve() { int n; cinn; vectorinta(n1); for(int i1;in;i) { cina[i]; } int s0; for(int i1;in;i) { if(a[i]) { si; break; } } if(s0) { for(int i1;in;i) { couta[i] ; } coutendl; return ; } int e0; for(int in;i1;i--) { if(a[i]) { ei; break; } } a[s]1,a[e]1; for(int is;ie;i) { int ji1; while(je(a[j]0||a[j]-1)) { a[j]0; } ij-1; } for(int i1;in;i) { couta[i] ; } coutendl; } /* 10 6 1 0 -1 0 0 1 7 0 -1 0 0 1 0 1 5 -1 0 0 -1 0 4 0 0 0 0 1 -1 6 1 0 1 0 0 -1 7 0 1 0 0 0 1 0 6 -1 -1 -1 -1 -1 -1 7 -1 0 1 -1 0 0 1 3 -1 0 0 1 0 0 0 0 1 0 1 0 0 1 0 1 1 0 0 1 0 0 0 0 0 1 1 0 1 0 0 1 0 1 0 0 0 1 0 1 0 0 0 0 1 0 0 1 0 0 0 1 1 0 0 */ void init() { } signed main() { ios::sync_with_stdio(0);cin.tie(0);cout.tie(0); int t1; cint; init(); while(t--) { solve(); } return 0; }这个题一个最本质的想法就是找到一个 1然后贪心地往后扩碰到的 -1 全部变成 0直到碰到第一个确定的 1。那么就是找到最左和最右的 1 或 -1然后往后扩即可。四、D. MEX Multiset这题真写麻烦了……#include bits/stdc.h #include cassert using namespace std; /* /\_/\ * ( ._.) * / \ */ /* *想好再写 *注意审题 注意特判 *不要红温 不要急躁 耐心一点 *WA了不要立马觉得是思路不对 先耐心找反例 */ #define endl \n #define dbg(x) cout#x xendl; #define vdbg(a) cout#aendl;for(auto x:a)coutx ;coutendl; #define YES coutYESendl;return ; #define Yes coutYesendl;return ; #define NO coutNOendl;return ; #define No coutNoendl;return ; #define popcount __builtin_popcount using lllong long; using i128__int128; using ldlong double; using piipairint,int; using pllpairll,ll; const int INF1e9; const ll INFLL1e18; const int dx[]{-1,1,0,0}; const int dy[]{0,0,-1,1}; const int ddx[]{-2,-1,1,2,2,1,-1,-2}; const int ddy[]{1,2,2,1,-1,-2,-2,-1}; void solve() { int n; cinn; vectorinta(n); for(int i0;in;i) { cina[i]; } vectorvectorintcnts(n1); for(int i0;in;i) { if(a[i]n) { continue; } cnts[a[i]].push_back(i); } string s(n,A); for(int v0;vn;v) { int mcnts[v].size(); if(m0) { break; } if(m1) { if(v0) { NO; } s[cnts[v][0]]C; break; } if(m2) { s[cnts[v][1]]B; } else { s[cnts[v][1]]B; s[cnts[v][2]]C; } } coutYESendl; coutsendl; } /* 5 6 1 0 0 1 2 1 4 0 0 0 0 3 0 2 2 4 6 7 6 7 5 0 0 0 1 2 */ void init() { } signed main() { ios::sync_with_stdio(0);cin.tie(0);cout.tie(0); int t1; cint; init(); while(t--) { solve(); } return 0; }首先令 A 为最大值集合那么就有 BC 要大于等于 A。直接说简单的做法若 0 出现了一次那么就无解0 没出现过也合法直接结束。否则的话将所有 0 都分给 A 和 B然后将剩下的数都给 C 就行了。此时 A 和 B 的 MEX 是 1C 的 MEX 是 0所以直接合法。五、E. Treasure Map Destruction (Constructive Version)#include bits/stdc.h #include cassert using namespace std; /* /\_/\ * ( ._.) * / \ */ /* *想好再写 *注意审题 注意特判 *不要红温 不要急躁 耐心一点 *WA了不要立马觉得是思路不对 先耐心找反例 */ #define endl \n #define dbg(x) cout#x xendl; #define vdbg(a) cout#aendl;for(auto x:a)coutx ;coutendl; #define YES coutYESendl;return ; #define Yes coutYesendl;return ; #define NO coutNOendl;return ; #define No coutNoendl;return ; #define popcount __builtin_popcount using lllong long; using i128__int128; using ldlong double; using piipairint,int; using pllpairll,ll; const int INF1e9; const ll INFLL1e18; const int dx[]{-1,1,0,0}; const int dy[]{0,0,-1,1}; const int ddx[]{-2,-1,1,2,2,1,-1,-2}; const int ddy[]{1,2,2,1,-1,-2,-2,-1}; void solve() { int n; cinn; vectorinta(n2); for(int i1;in;i) { cina[i]; } vectorintvis(n2); for(int i1;in;i) { if(a[i]0) { int lmax(1,i-a[i]1); int rmin(n,ia[i]-1); vis[l],vis[r1]--; } } for(int i1;in;i) { vis[i]vis[i-1]; } for(int i1;in;i) { if(a[i]0) { if(vis[i]) { cout-1endl; return ; } } else if(a[i]0) { int ok1(i-a[i]1!vis[i-a[i]]); int ok2(ia[i]n!vis[ia[i]]); if(!ok1!ok2) { cout-1endl; return ; } } } for(int i1;in;i) { cout(!vis[i]); } coutendl; } /* 12 5 0 1 -1 -1 0 3 -1 0 2 5 -1 1 -1 1 -1 5 -1 -1 -1 -1 -1 5 -1 2 -1 3 -1 7 2 1 0 1 0 1 2 1 -1 3 1 -1 1 1 0 4 3 -1 -1 -1 6 -1 -1 0 -1 2 4 10 -1 1 -1 -1 1 1 -1 -1 2 -1 */ void init() { } signed main() { ios::sync_with_stdio(0);cin.tie(0);cout.tie(0); int t1; cint; init(); while(t--) { solve(); } return 0; }首先考虑根据每个确定的位置统计出所有不能是宝藏的地方这个可以通过差分解决。之后考虑默认所有没受到约束的位置都是宝藏。那么对于已经确定是宝藏的位置若不能是宝藏就无解。对于确定下不是宝藏的位置若两侧都不能是宝藏也无解。六、F. Binary Bubble Sort Inversions#include bits/stdc.h #include cassert using namespace std; /* /\_/\ * ( ._.) * / \ */ /* *想好再写 *注意审题 注意特判 *不要红温 不要急躁 耐心一点 *WA了不要立马觉得是思路不对 先耐心找反例 */ #define endl \n #define dbg(x) cout#x xendl; #define vdbg(a) cout#aendl;for(auto x:a)coutx ;coutendl; #define YES coutYESendl;return ; #define Yes coutYesendl;return ; #define NO coutNOendl;return ; #define No coutNoendl;return ; #define popcount __builtin_popcount using lllong long; using i128__int128; using ldlong double; using piipairint,int; using pllpairll,ll; const int INF1e9; const ll INFLL1e18; const int dx[]{-1,1,0,0}; const int dy[]{0,0,-1,1}; const int ddx[]{-2,-1,1,2,2,1,-1,-2}; const int ddy[]{1,2,2,1,-1,-2,-2,-1}; void solve() { int n; cinn; vectorinta(n1); for(int i1;in;i) { cina[i]; } string s; cins; s s; int cnt0; ll ans0; for(int i1;in;i) { if(a[i]0) { anscnt; } else { cnt; } } coutans ; int zero0,ln1; for(int i1;in;i) { if(a[i]1) { li; for(int ji;jn;j) { if(a[j]0) { zero; } } break; } } int one0,r0; for(int in;i1;i--) { if(a[i]0) { ri; for(int ji;j1;j--) { if(a[j]1) { one; } } break; } } for(int i1;in;i) { if(s[i]1) { ans-max(0,zero); l,one--; while(lna[l]0) { zero--; l; } } else { ans-max(0,one); r--,zero--; while(r1a[r]1) { one--; r--; } } coutans ; } coutendl; } /* 7 4 1 1 0 0 1010 7 0 1 0 1 1 0 0 0101001 4 0 0 1 1 1001 1 1 1 5 0 1 1 0 0 11101 3 1 0 0 000 6 1 0 1 1 0 0 011000 4 2 1 0 0 7 4 2 0 0 0 0 0 0 0 0 0 0 0 0 4 2 0 0 0 0 2 1 0 0 7 4 2 1 0 0 0 */ void init() { } signed main() { ios::sync_with_stdio(0);cin.tie(0);cout.tie(0); int t1; cint; init(); while(t--) { solve(); } return 0; }手玩一下可以发现正向冒泡就是将第一个 1 段最后一个 1 移动到最后消除的逆序对数就是中间 0 的个数反向冒泡就是将最后一个 0 段第一个 0 移动到最前消除的个数就是中间 1 的个数。那么就可以先统计出一开始的逆序对数然后统计出第一个 1 到最后 0 的个数和最后一个 0 到开头 1 的个数然后每次移动指针同步更新个数即可。题解的 deque 太妙了……七、G. Index Removal#include bits/stdc.h #include cassert using namespace std; /* /\_/\ * ( ._.) * / \ */ /* *想好再写 *注意审题 注意特判 *不要红温 不要急躁 耐心一点 *WA了不要立马觉得是思路不对 先耐心找反例 */ #define endl \n #define dbg(x) cout#x xendl; #define vdbg(a) cout#aendl;for(auto x:a)coutx ;coutendl; #define YES coutYESendl;return ; #define Yes coutYesendl;return ; #define NO coutNOendl;return ; #define No coutNoendl;return ; #define popcount __builtin_popcount using lllong long; using i128__int128; using ldlong double; using piipairint,int; using pllpairll,ll; const int INF1e9; const ll INFLL1e18; const int dx[]{-1,1,0,0}; const int dy[]{0,0,-1,1}; const int ddx[]{-2,-1,1,2,2,1,-1,-2}; const int ddy[]{1,2,2,1,-1,-2,-2,-1}; void solve() { ll n,k; cinnk; vectorlla(n1); for(int i1;in;i) { cina[i]; } vectorllpre(n1); for(int i1;in;i) { pre[i]pre[i-1]a[i]; } auto query[](int l,int r)-ll { if(rn||lr) { return 0; } return pre[r]-pre[l-1]; }; auto calc[](int L,int R,ll base,int right)-ll { if(LR) { return 0; } int lL; int rR; int m; int ans-1; while(lr) { mlr1; if(right) { int lenm-L1; if(a[m]baselen*k) { ansm; rm-1; } else { lm1; } } else { int lenR-m1; if(a[m]base-len*k) { ansm; lm1; } else { rm-1; } } } if(right) { if(ans-1) { ansR1; } int lenans-L; ll resquery(L,ans-1)-(1ll*base*lenk*(len1)*len/2); return res0?INFLL:res; } if(ans-1) { ansL-1; } int lenR-ans; ll resquery(ans1,R)-(1ll*base*len-k*(len1)*len/2); return res0?INFLL:res; }; for(int i1;in;i) { ll lefti1n?calc(1,i-1,a[i1],0):INFLL; ll right1i-1?calc(i1,n,a[i-1],1):INFLL; ll ansmin(left,right); coutans ; } coutendl; } /* 7 4 2 1 2 4 5 4 1 1 2 3 4 5 7 1 8 9 16 20 5 1000000000 1 6 7 67 6767 6 1 1 1 2 2 3 4 4 1 1 2 3 3 4 2 1 2 4 6 0 1 1 0 0 2 1 0 0 2 1 4 0 0 0 0 0 0 0 0 0 0 1 0 0 1 0 0 0 2 2 0 */ void init() { } signed main() { ios::sync_with_stdio(0);cin.tie(0);cout.tie(0); int t1; cint; init(); while(t--) { solve(); } return 0; }因为 n 是那么就只能考虑每次快速求出答案。那么在删除后只需要让和满足约束即可。那么就是要么让减小要么让减小。以右侧为例那么就是基准线对于之后的数每个位置都有一个阈值即最大不能超过。此时就可以考虑二分找到往右第一个数使得那么范围的数就是需要减小的数这个可以通过前缀和快速求区间和相减得到。八、H. Treasure Map Destruction (Counting Version)#include bits/stdc.h #include cassert using namespace std; /* /\_/\ * ( ._.) * / \ */ /* *想好再写 *注意审题 注意特判 *不要红温 不要急躁 耐心一点 *WA了不要立马觉得是思路不对 先耐心找反例 */ #define endl \n #define dbg(x) cout#x xendl; #define vdbg(a) cout#aendl;for(auto x:a)coutx ;coutendl; #define YES coutYESendl;return ; #define Yes coutYesendl;return ; #define NO coutNOendl;return ; #define No coutNoendl;return ; #define popcount __builtin_popcount using lllong long; using i128__int128; using ldlong double; using piipairint,int; using pllpairll,ll; const int INF1e9; const ll INFLL1e18; const int dx[]{-1,1,0,0}; const int dy[]{0,0,-1,1}; const int ddx[]{-2,-1,1,2,2,1,-1,-2}; const int ddy[]{1,2,2,1,-1,-2,-2,-1}; templateclass T constexpr T power(T a, ll b) { T res 1; for (; b ! 0; b / 2, a * a) { if (b 1) { res * a; } } return res; } templateint M struct ModInt { public: constexpr ModInt() : x(0) {} templatetypename T constexpr ModInt(T x_) { T v x_ % M; if (v 0) { v M; } x v; } constexpr int val() const { return x; } constexpr ModInt operator() { x; if (x M) { x 0; } return *this; } constexpr ModInt operator(int) { ModInt res *this; (*this); return res; } constexpr ModInt operator--() { if (x 0) { x M - 1; } else { x--; } return *this; } constexpr ModInt operator--(int) { ModInt res *this; --(*this); return res; } constexpr ModInt operator-() const { ModInt res; res.x (x 0 ? 0 : M - x); return res; } constexpr ModInt inv() const { return power(*this, M - 2); } constexpr ModInt operator*(const ModInt rhs) { x ll(x) * rhs.val() % M; return *this; } constexpr ModInt operator(const ModInt rhs) { x rhs.val(); if (x M) { x - M; } return *this; } constexpr ModInt operator-(const ModInt rhs) { x - rhs.val(); if (x 0) { x M; } return *this; } constexpr ModInt operator/(const ModInt rhs) { return *this * rhs.inv(); } friend constexpr ModInt operator*(ModInt lhs, const ModInt rhs) { lhs * rhs; return lhs; } friend constexpr ModInt operator(ModInt lhs, const ModInt rhs) { lhs rhs; return lhs; } friend constexpr ModInt operator-(ModInt lhs, const ModInt rhs) { lhs - rhs; return lhs; } friend constexpr ModInt operator/(ModInt lhs, const ModInt rhs) { lhs / rhs; return lhs; } friend constexpr bool operator(ModInt lhs, const ModInt rhs) { return lhs.val() rhs.val(); } friend constexpr bool operator(ModInt lhs, const ModInt rhs) { return lhs.val() rhs.val(); } friend constexpr bool operator(ModInt lhs, const ModInt rhs) { return lhs.val() rhs.val(); } friend constexpr bool operator(ModInt lhs, const ModInt rhs) { return lhs.val() rhs.val(); } friend constexpr bool operator(ModInt lhs, const ModInt rhs) { return lhs.val() rhs.val(); } friend constexpr bool operator!(ModInt lhs, const ModInt rhs) { return lhs.val() ! rhs.val(); } friend constexpr std::istream operator(std::istream is, ModInt a) { ll i; is i; a i; return is; } friend constexpr std::ostream operator(std::ostream os, const ModInt a) { return os a.val(); } private: int x; }; templateint M, typename T ModIntM struct Comb { vectorT fac; vectorT inv; Comb(int n) { fac.assign(n, 1); for(int i1;in;i) { fac[i]fac[i-1]*i; } inv.assign(n, 1); inv[n-1]fac[n-1].inv(); for(int in-2;i0;i--) { inv[i]inv[i1]*(i1); } } templatestd::signed_integral U T P(U n, U m) { if(nm) { return 0; } return fac[n] * inv[n - m]; } templatestd::signed_integral U T C(U n, U m) { if(nm||m0) { return 0; } return fac[n] * inv[n - m] * inv[m]; } }; //power函数切记强转成 Z !!!!! constexpr int M 1e97; using Z ModIntM; constexpr int N 2e55; CombMcomb(N); templatestd::signed_integral U Z P(U n, U m) { return comb.P(n, m); } templatestd::signed_integral U Z C(U n, U m) { return comb.C(n, m); } void solve() { int n; cinn; vectorinta(n1); for(int i1;in;i) { cina[i]; } vectorZfib(n1); fib[0]1,fib[1]2; for(int i2;in;i) { fib[i]fib[i-1]fib[i-2]; } int all0; vectorintno(n2); for(int i1;in;i) { if(a[i]0) { if(a[i]-1) { all; } continue; } int lmax(1,i-a[i]1); int rmin(n,ia[i]-1); no[l],no[r1]--; } for(int i1;in;i) { no[i]no[i-1]; } for(int i1;in;i) { no[i](no[i]0); } vectorintmust(n1); for(int i1;in;i) { if(a[i]-1) { continue; } if(a[i]0) { if(no[i]) { cout0endl; return ; } must[i]1; continue; } int l(1i-a[i]!no[i-a[i]]); int r(ia[i]n!no[ia[i]]); if(!l!r) { cout0endl; return ; } if(l!r) { must[i-a[i]]1; } else if(!lr) { must[ia[i]]1; } } vectorinttbd; for(int i1;in;i) { if(!no[i]!must[i]) { tbd.push_back(i); } } int mtbd.size(); Z ans1; for(int i0,len1;im;i) { if(im-1) { ans*fib[len]; continue; } int ltbd[i]; int rtbd[i1]; if((r-l)%20a[(lr)/2](r-l)/2) { len; } else { ans*fib[len]; len1; } } if(alln) { ans--; } coutansendl; } /* 12 5 0 1 -1 -1 0 3 -1 0 2 5 -1 1 -1 1 -1 5 -1 -1 -1 -1 -1 5 -1 2 -1 3 -1 7 2 1 0 1 0 1 2 1 -1 3 1 -1 1 1 0 4 3 -1 -1 -1 6 -1 -1 0 -1 2 4 10 -1 1 -1 -1 1 1 -1 -1 2 -1 4 0 5 31 0 1 1 1 1 1 0 3 */ void init() { } signed main() { ios::sync_with_stdio(0);cin.tie(0);cout.tie(0); int t1; cint; init(); while(t--) { solve(); } return 0; }那么对于一个已经确定的就要求所有的位置 j 都没有宝藏且对于和这两个位置至少有一个宝藏。在这样操作后就可以得到若干个可能有宝藏的位置序列 S使得其要满足每一个的限制。此时可以发现对于一个位置 i其对应的 L 和 R 在 S 中必然相邻。这是因为中间被限制不能有宝藏所以不可能插入别的约束。之后若两个候选位置 L 和 R 中有一个已经被禁止放宝藏了那么其只会贡献一种方案。然后对于一个被破坏的位置若其既没有被禁止又没有位置需要它那么其可以有宝藏也可以没有所以贡献两种方案。而若必须进行决策那么对于序列 S最后必然形成若干条满足相邻两个或起来为 1 的链。举个例子对于 a[-1,1,-1,1,-1]其要求和这就构成了一条长度为 3 的链。那么首先对于已经确定的宝藏其就可以切断这条链使得左右互不影响。之后问题就转化为有多少个长度为 k 的 01 串满足不存在连续两个 0。对于这个问题考虑定义为 i 长度的合法串个数初始。那么对于第 i 个位置由于要求所以若当前位置填 1 就只需要前 i-1 个位置合法即。而若当前位置填 0。那么就要求 i-1 位置必须填 1所以就要求前 i-2 个位置合法即。所以转移就是就是斐波那契。此时注意到如果将所有没有被禁止又没确定的位置都统计进来。那么对于既没有被禁止又没有位置需要它的位置其自己就是一条链贡献的两种方案可以被统计到。总结cf 还是太考验思维了……END