企业官网建设流程全解析

前言

就今年这题的风格，真得多写 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<<" "<<x<<endl; #define vdbg(a) cout<<#a<<endl;for(auto x:a)cout<<x<<" ";cout<<endl; #define YES cout<<"YES"<<endl;return ; #define Yes cout<<"Yes"<<endl;return ; #define NO cout<<"NO"<<endl;return ; #define No cout<<"No"<<endl;return ; #define popcount __builtin_popcount using ll=long long; using i128=__int128; using ld=long double; using pii=pair<int,int>; using pll=pair<ll,ll>; const int INF=1e9; const ll INFLL=1e18; 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; cin>>n>>k; string s; cin>>s; s=" "+s; int ans=0; for(int i=1;i<=n;i+=k) { int ok=0; for(int j=i;j<=i+k-1;j++) { if(s[j]=='0') { ok=1; break; } } if(!ok) { ans++; } } cout<<ans<<endl; } /* 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 t=1; cin>>t; 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<<" "<<x<<endl; #define vdbg(a) cout<<#a<<endl;for(auto x:a)cout<<x<<" ";cout<<endl; #define YES cout<<"YES"<<endl;return ; #define Yes cout<<"Yes"<<endl;return ; #define NO cout<<"NO"<<endl;return ; #define No cout<<"No"<<endl;return ; #define popcount __builtin_popcount using ll=long long; using i128=__int128; using ld=long double; using pii=pair<int,int>; using pll=pair<ll,ll>; const int INF=1e9; const ll INFLL=1e18; 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; cin>>n; vector<int>a(n+1); for(int i=1;i<=n;i++) { cin>>a[i]; } int one=0; int odd=0; int even=0; for(int i=1;i<=n;i++) { if(a[i]%2) { one++; } else { if(a[i]/2%2) { odd++; } else { even++; } } } cout<<max({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 t=1; cin>>t; 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<<" "<<x<<endl; #define vdbg(a) cout<<#a<<endl;for(auto x:a)cout<<x<<" ";cout<<endl; #define YES cout<<"YES"<<endl;return ; #define Yes cout<<"Yes"<<endl;return ; #define NO cout<<"NO"<<endl;return ; #define No cout<<"No"<<endl;return ; #define popcount __builtin_popcount using ll=long long; using i128=__int128; using ld=long double; using pii=pair<int,int>; using pll=pair<ll,ll>; const int INF=1e9; const ll INFLL=1e18; 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; cin>>n; vector<int>a(n+1); for(int i=1;i<=n;i++) { cin>>a[i]; } int s=0; for(int i=1;i<=n;i++) { if(a[i]) { s=i; break; } } if(s==0) { for(int i=1;i<=n;i++) { cout<<a[i]<<" "; } cout<<endl; return ; } int e=0; for(int i=n;i>=1;i--) { if(a[i]) { e=i; break; } } a[s]=1,a[e]=1; for(int i=s;i<=e;i++) { int j=i+1; while(j<=e&&(a[j]==0||a[j]==-1)) { a[j++]=0; } i=j-1; } for(int i=1;i<=n;i++) { cout<<a[i]<<" "; } cout<<endl; } /* 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 t=1; cin>>t; 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<<" "<<x<<endl; #define vdbg(a) cout<<#a<<endl;for(auto x:a)cout<<x<<" ";cout<<endl; #define YES cout<<"YES"<<endl;return ; #define Yes cout<<"Yes"<<endl;return ; #define NO cout<<"NO"<<endl;return ; #define No cout<<"No"<<endl;return ; #define popcount __builtin_popcount using ll=long long; using i128=__int128; using ld=long double; using pii=pair<int,int>; using pll=pair<ll,ll>; const int INF=1e9; const ll INFLL=1e18; 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; cin>>n; vector<int>a(n); for(int i=0;i<n;i++) { cin>>a[i]; } vector<vector<int>>cnts(n+1); for(int i=0;i<n;i++) { if(a[i]>n) { continue; } cnts[a[i]].push_back(i); } string s(n,'A'); for(int v=0;v<=n;v++) { int m=cnts[v].size(); if(m==0) { break; } if(m==1) { if(v==0) { NO; } s[cnts[v][0]]='C'; break; } if(m==2) { s[cnts[v][1]]='B'; } else { s[cnts[v][1]]='B'; s[cnts[v][2]]='C'; } } cout<<"YES"<<endl; cout<<s<<endl; } /* 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 t=1; cin>>t; init(); while(t--) { solve(); } return 0; }

首先令 A 为最大值集合，那么就有 B+C 要大于等于 A。

直接说简单的做法，若 0 出现了一次那么就无解，0 没出现过也合法直接结束。否则的话将所有 0 都分给 A 和 B，然后将剩下的数都给 C 就行了。此时 A 和 B 的 MEX 是 1，C 的 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<<" "<<x<<endl; #define vdbg(a) cout<<#a<<endl;for(auto x:a)cout<<x<<" ";cout<<endl; #define YES cout<<"YES"<<endl;return ; #define Yes cout<<"Yes"<<endl;return ; #define NO cout<<"NO"<<endl;return ; #define No cout<<"No"<<endl;return ; #define popcount __builtin_popcount using ll=long long; using i128=__int128; using ld=long double; using pii=pair<int,int>; using pll=pair<ll,ll>; const int INF=1e9; const ll INFLL=1e18; 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; cin>>n; vector<int>a(n+2); for(int i=1;i<=n;i++) { cin>>a[i]; } vector<int>vis(n+2); for(int i=1;i<=n;i++) { if(a[i]>0) { int l=max(1,i-a[i]+1); int r=min(n,i+a[i]-1); vis[l]++,vis[r+1]--; } } for(int i=1;i<=n;i++) { vis[i]+=vis[i-1]; } for(int i=1;i<=n;i++) { if(a[i]==0) { if(vis[i]) { cout<<-1<<endl; return ; } } else if(a[i]>0) { int ok1=(i-a[i]>=1&&!vis[i-a[i]]); int ok2=(i+a[i]<=n&&!vis[i+a[i]]); if(!ok1&&!ok2) { cout<<-1<<endl; return ; } } } for(int i=1;i<=n;i++) { cout<<(!vis[i]); } cout<<endl; } /* 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 t=1; cin>>t; 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<<" "<<x<<endl; #define vdbg(a) cout<<#a<<endl;for(auto x:a)cout<<x<<" ";cout<<endl; #define YES cout<<"YES"<<endl;return ; #define Yes cout<<"Yes"<<endl;return ; #define NO cout<<"NO"<<endl;return ; #define No cout<<"No"<<endl;return ; #define popcount __builtin_popcount using ll=long long; using i128=__int128; using ld=long double; using pii=pair<int,int>; using pll=pair<ll,ll>; const int INF=1e9; const ll INFLL=1e18; 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; cin>>n; vector<int>a(n+1); for(int i=1;i<=n;i++) { cin>>a[i]; } string s; cin>>s; s=" "+s; int cnt=0; ll ans=0; for(int i=1;i<=n;i++) { if(a[i]==0) { ans+=cnt; } else { cnt++; } } cout<<ans<<" "; int zero=0,l=n+1; for(int i=1;i<=n;i++) { if(a[i]==1) { l=i; for(int j=i;j<=n;j++) { if(a[j]==0) { zero++; } } break; } } int one=0,r=0; for(int i=n;i>=1;i--) { if(a[i]==0) { r=i; for(int j=i;j>=1;j--) { if(a[j]==1) { one++; } } break; } } for(int i=1;i<=n;i++) { if(s[i]=='1') { ans-=max(0,zero); l++,one--; while(l<=n&&a[l]==0) { zero--; l++; } } else { ans-=max(0,one); r--,zero--; while(r>=1&&a[r]==1) { one--; r--; } } cout<<ans<<" "; } cout<<endl; } /* 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 t=1; cin>>t; 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<<" "<<x<<endl; #define vdbg(a) cout<<#a<<endl;for(auto x:a)cout<<x<<" ";cout<<endl; #define YES cout<<"YES"<<endl;return ; #define Yes cout<<"Yes"<<endl;return ; #define NO cout<<"NO"<<endl;return ; #define No cout<<"No"<<endl;return ; #define popcount __builtin_popcount using ll=long long; using i128=__int128; using ld=long double; using pii=pair<int,int>; using pll=pair<ll,ll>; const int INF=1e9; const ll INFLL=1e18; 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; cin>>n>>k; vector<ll>a(n+1); for(int i=1;i<=n;i++) { cin>>a[i]; } vector<ll>pre(n+1); for(int i=1;i<=n;i++) { pre[i]=pre[i-1]+a[i]; } auto query=[&](int l,int r)->ll { if(r>n||l>r) { return 0; } return pre[r]-pre[l-1]; }; auto calc=[&](int L,int R,ll base,int right)->ll { if(L>R) { return 0; } int l=L; int r=R; int m; int ans=-1; while(l<=r) { m=l+r>>1; if(right) { int len=m-L+1; if(a[m]<=base+len*k) { ans=m; r=m-1; } else { l=m+1; } } else { int len=R-m+1; if(a[m]>=base-len*k) { ans=m; l=m+1; } else { r=m-1; } } } if(right) { if(ans==-1) { ans=R+1; } int len=ans-L; ll res=query(L,ans-1)-(1ll*base*len+k*(len+1)*len/2); return res<0?INFLL:res; } if(ans==-1) { ans=L-1; } int len=R-ans; ll res=query(ans+1,R)-(1ll*base*len-k*(len+1)*len/2); return res<0?INFLL:res; }; for(int i=1;i<=n;i++) { ll left=i+1<=n?calc(1,i-1,a[i+1],0):INFLL; ll right=1<=i-1?calc(i+1,n,a[i-1],1):INFLL; ll ans=min(left,right); cout<<ans<<" "; } cout<<endl; } /* 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 t=1; cin>>t; 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<<" "<<x<<endl; #define vdbg(a) cout<<#a<<endl;for(auto x:a)cout<<x<<" ";cout<<endl; #define YES cout<<"YES"<<endl;return ; #define Yes cout<<"Yes"<<endl;return ; #define NO cout<<"NO"<<endl;return ; #define No cout<<"No"<<endl;return ; #define popcount __builtin_popcount using ll=long long; using i128=__int128; using ld=long double; using pii=pair<int,int>; using pll=pair<ll,ll>; const int INF=1e9; const ll INFLL=1e18; 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}; template<class 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; } template<int M> struct ModInt { public: constexpr ModInt() : x(0) {} template<typename 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; }; template<int M, typename T = ModInt<M>> struct Comb { vector<T> fac; vector<T> inv; Comb(int n) { fac.assign(n, 1); for(int i=1;i<n;i++) { fac[i]=fac[i-1]*i; } inv.assign(n, 1); inv[n-1]=fac[n-1].inv(); for(int i=n-2;i>=0;i--) { inv[i]=inv[i+1]*(i+1); } } template<std::signed_integral U> T P(U n, U m) { if(n<m) { return 0; } return fac[n] * inv[n - m]; } template<std::signed_integral U> T C(U n, U m) { if(n<m||m<0) { return 0; } return fac[n] * inv[n - m] * inv[m]; } }; //power函数切记强转成 Z !!!!! constexpr int M = 1e9+7; using Z = ModInt<M>; constexpr int N = 2e5+5; Comb<M>comb(N); template<std::signed_integral U> Z P(U n, U m) { return comb.P(n, m); } template<std::signed_integral U> Z C(U n, U m) { return comb.C(n, m); } void solve() { int n; cin>>n; vector<int>a(n+1); for(int i=1;i<=n;i++) { cin>>a[i]; } vector<Z>fib(n+1); fib[0]=1,fib[1]=2; for(int i=2;i<=n;i++) { fib[i]=fib[i-1]+fib[i-2]; } int all=0; vector<int>no(n+2); for(int i=1;i<=n;i++) { if(a[i]<=0) { if(a[i]==-1) { all++; } continue; } int l=max(1,i-a[i]+1); int r=min(n,i+a[i]-1); no[l]++,no[r+1]--; } for(int i=1;i<=n;i++) { no[i]+=no[i-1]; } for(int i=1;i<=n;i++) { no[i]=(no[i]>0); } vector<int>must(n+1); for(int i=1;i<=n;i++) { if(a[i]==-1) { continue; } if(a[i]==0) { if(no[i]) { cout<<0<<endl; return ; } must[i]=1; continue; } int l=(1<=i-a[i]&&!no[i-a[i]]); int r=(i+a[i]<=n&&!no[i+a[i]]); if(!l&&!r) { cout<<0<<endl; return ; } if(l&&!r) { must[i-a[i]]=1; } else if(!l&&r) { must[i+a[i]]=1; } } vector<int>tbd; for(int i=1;i<=n;i++) { if(!no[i]&&!must[i]) { tbd.push_back(i); } } int m=tbd.size(); Z ans=1; for(int i=0,len=1;i<m;i++) { if(i==m-1) { ans*=fib[len]; continue; } int l=tbd[i]; int r=tbd[i+1]; if((r-l)%2==0&&a[(l+r)/2]==(r-l)/2) { len++; } else { ans*=fib[len]; len=1; } } if(all==n) { ans--; } cout<<ans<<endl; } /* 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 t=1; cin>>t; 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