11.3模擬賽
t1
你醒了，發現全世界 OI 能力下降 \(10^6\) 倍，只有今日聯考受影響。于是你打開 statement.pdf，準備閃擊聯考。
聯考大軍向你襲來，作為八校最強的 OIer，你準備在若干位置發動“閃擊”。
聯考大軍中，每一場聯考 \(i\) 都有一個編號 \(p_i\)，\(p\) 是一個排列。你能在一個位置發動“閃擊”，當且僅當這場聯考前的聯考編號全部小于這場，后的聯考編號全部大于這場。形式化地，\(x\) 能發動“閃擊”僅當：
同時，為了便于攻擊，你可以利用 OIer 強大的力量，進行一個操作：選擇兩個不同的下標 \(x, y\)，交換 \(p_x, p_y\)。
時間緊迫，你要快速決定且只能進行恰好一次這樣的操作。你的目標是最大化可以發動“閃擊”的位置。輸出最大的位置數量。
對于所有測試數據，保證 \(1 \leq T \leq 5 \times 10^4\)，\(2 \leq \sum n \leq 3 \times 10^5\)，\(p\) 是一個排列。
題解
考慮直接計算貢獻，對于每個點找出那些交換會使其產生貢獻，排除本來就是好的排列之后，發現交換一定更優，接下來分類討論。
- \(a_i=i\)
- 這個時候如果左邊數都小于他，那么這個數是合法的，直接計入答案，因為我們肯定不會交換這個數兩側的，因為左側數小于右側一定不優，直接計入答案即可。
- 否則這個數如果左右只有一對數不合法，交換這一對即可。
- \(a_i>i\)
- 考慮能不能交換 \(a_i\) 和 \(a_{a_i}\) 來讓 \(a_i\) 有貢獻，充分必要條件就是有 \(a_i-1\) 個小于 \(a_i\) 的數在 \([1,a_i]\) 之間。
- \(a_i<i\)
- 考慮能不能交換 \(a_i\) 和 \(a_{a_i}\) 來讓 \(a_i\) 有貢獻，充分必要條件就是 \(a_i\) 是 \([1,a_i]\) 之間最大的數字。
找到每個交換的最大值就可以了。原理是這種交換的總數是 \(O(n)\) 的。
code：
#include<bits/stdc++.h>
#define fi first
#define se second
#define int long long
#define lbt(x) (x&(-x))
#define pii pair<int,int>
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define per(i,a,b) for(int i=(a);i>=(b);i--)
using namespace std;
const int N=5e5+10;
int n,m,k,T,a[N],p[N],mx[N],mxp[N],t[N],ans;
map<pii,int> g;
void upd(int i,int x){while(i<N){t[i]+=x;i+=lbt(i);}}
int sc(int i){int ans=0;while(i>0){ans+=t[i];i-=lbt(i);}return ans;}
signed main(){
ios::sync_with_stdio(0);
cin.tie(0),cout.tie(0);
freopen("strike.in","r",stdin);
freopen("strike.out","w",stdout);
cin>>T;
while(T--){
cin>>n;g.clear();ans=0;
rep(i,1,n){t[i]=0;
cin>>p[i];a[p[i]]=i;mx[i]=max(mx[i-1],p[i]);
}rep(i,1,n) mxp[i]=max(mxp[i-1],a[i]);
rep(i,1,n){
upd(p[i],1);
if(p[i]==i){
if(mx[i]==i) ans++;
if(sc(i)==i-1) g[{a[mx[i]],mxp[i]}]++;
}else if(p[i]>i){
if(mx[p[i]]==p[i]) g[{i,p[i]}]++;
}else if(mxp[p[i]-1]==p[i]-1) g[{p[i],i}]++;
}int ma=-2;
for(auto x:g) ma=max(ma,x.se);
cout<<ans+ma<<'\n';
}
return 0;
}
t2
你醒了，你發現你是信競教練，準備為學生安排模擬賽。
這個賽季總共有 \(n\) 場聯考，第 \(i\) 場聯考的“特征”可以表示為一個整數 \(a_i\)。
如果有連續兩場聯考滿足 \(\gcd(a_i, a_{i+1}) = 1\)，那么兩場聯考風格差別巨大，會讓學生非常不滿抨擊教練。定義一個賽季模擬賽的“不滿度”為 \(1\) 到 \(n-1\) 中，\(\gcd(a_i, a_{i+1}) = 1\) 的下標 \(i\) 的數量。
為了避免差評，你決定對聯考特征進行最多 \(k\) 次修改。每次修改可以選定一個下標 \(i\) 和任意整數 \(x\)，將 \(a_i\) 改為 \(x\)。
你想求出這個賽季最小的不滿度。
對于所有測試數據，保證 \(T \leq 7\)，\(1 \leq k \leq n \leq 10^5\)，\(0 \leq a_i \leq 10^9\)。
題解
貪心，肯定是把數字一個一個變成0。先把能救兩個位置的拿下，然后再管1，因為每個1連續段，管到最后可以改最后一個1，一次救兩個。1救完后，再管剩下的互質的。
code：
#include<bits/stdc++.h>
#define fi first
#define se second
#define ls (p<<1)
#define rs (p<<1|1)
#define pb push_back
#define mset multiset
#define int long long
#define lbt(x) (x&(-x))
#define pii pair<int,int>
#define umap unordered_map
#define m(a) memset(a,0,sizeof(a))
#define m127(a) memset(a,0x3f,sizeof(a))
#define m128(a) memset(a,-0x3f,sizeof(a))
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define per(i,a,b) for(int i=(a);i>=(b);i--)
using namespace std;
const int N=5e5+10;
int n,m,k,T,a[N],q,b[N];
vector<int> g;
signed main(){
ios::sync_with_stdio(0);
cin.tie(0),cout.tie(0);
freopen("arrange.in","r",stdin);
freopen("arrange.out","w",stdout);
cin>>T;
while(T--){
cin>>n>>q;int sum=0,ans=0,tg=0;g.clear();
rep(i,1,n) cin>>a[i];
rep(i,1,n){
if(a[i]!=1) tg=1;
}rep(i,1,n-1){
b[i]=__gcd(a[i],a[i+1]);if(b[i]==1) sum++;
}if(tg==1){
rep(i,2,n-1){
if(b[i-1]==1&&b[i]==1&&a[i-1]!=1&&a[i+1]!=1&&q>0){
a[i]=0;q--;b[i-1]=a[i-1],b[i]=a[i+1],ans+=2;
}
}int l=0,r=n+1;
while(a[l+1]==1) l++;l++;
while(a[r-1]==1) r--;r--;
rep(i,l,r){
if(a[i]==1){
int x=i;
while(a[i+1]==1&&i<r) i++;
if(i!=n&&x!=1) g.pb(i-x+1);
}
}
sort(g.begin(),g.end());
for(int v:g){
if(v<=q) ans+=v+1,q-=v;
else ans+=q,q=0;
}cout<<max(0ll,sum-ans-q)<<'\n';
}else{
ans=min(q-1,n-1);
cout<<sum-ans<<'\n';
}
}
return 0;
}
t3
你醒了，你發現你成了構造 Master，秒了前兩題來殺 T3。
\(T\) 次詢問，每次給出正整數 \(k\)，你要構造一個長度 \(\leq 60\) 的 \(01\) 串，滿足其本質不同子序列數量恰好為 \(k\)。
對于所有測試數據，保證 \(1 \leq T \leq 10^5\)，\(1 \leq k \leq 10^9\)。
題解
然后考慮反向構造，那我枚舉以 \(0\) 開頭的串的個數，然后嘗試順次填數，假設我目標 \(0\) 開頭串剩余 \(X\) 個，\(1\) 開頭剩余 \(Y\) 個。
每次下一個位置如果填 \(0\)，那我以 \(0\) 開頭的串就會又產生 \(Y+1\) 個。
可以這樣考慮，把前面的所有 \(0\) 選上，后面接上一個 \(1\) 開頭的串，那有 \(Y\) 種，或者干脆什么都不接，那就又有 \(1\) 種，總的就是 \(Y+1\) 種，可以直接貪心地填上。
隨機化 \(X,Y\) 就能過了。當然有一種有道理的做法，考慮上面的做法其實就是折損相減，所以按理來說有一些接近 \(\phi\) 作為比值的點，從這里開始枚舉就好了。就是構造了一種 \(\frac{1-x}{x}=x\) 的東西讓他能盡量減。
code：
#include<bits/stdc++.h>
#define int long long
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define per(i,a,b) for(int i=(a);i>=(b);i--)
using namespace std;
const int N=5e5+10;
int n,m,k,T,a[N];
vector<int> g[N];
int work(int x,int y){
if(x==y){
if(x==0) return 0;
else return INT_MAX;
}if(x>y) swap(x,y);
int k=y/(x+1);
return k+work(x,y-k*(x+1));
}
void solve(int x,int y,bool b=0){
if(x==y) return;
if(x>y) swap(x,y),b^=1;
cout<<b;solve(x,y-(x+1),b);
}
signed main(){
ios::sync_with_stdio(0);
cin.tie(0),cout.tie(0);
freopen("construct.in","r",stdin);
freopen("construct.out","w",stdout);
cin>>T;
while(T--){
cin>>n;int cnt=0;
rep(i,(int)n*0.61803398874989484,n){
if(work(i,n-i)<=60){
solve(i,n-i);cout<<'\n';goto loop;
}
}loop:;
}
return 0;
}
t4
二操作先不管，因為是獨立存在的。考慮一操作，直接考慮對里邊葉子的貢獻，維護幾個葉子 $s z $, 子樹里邊每個節點有幾個葉子的和 $( s s z = \sum s z ) $, 自己這個節點被加了多少并維護加法 $\operatorname { t a g } $, 節點的答案。直接維護答案和節點的值，quy的時候直接把被包含的區間的答案，和沒被包含但是經過的節點的貢獻算上。 三和一對應的線段樹大概如此：
inline void push(uint u, Z x) {
tag[u] += x;
val[u] += x;
sum[u] += ssz[u] * x;
}
inline void down(uint u) {
if (!tag[u].val) return;
push(u << 1, tag[u]);
push(u << 1 | 1, tag[u]);
tag[u] = 0;
}
inline void modify(const uint ql, const uint qr, const uint u, const uint x) {
if (dfn[u] > qr || dfn[u] + siz[u] - 1 < ql) return;
if (ql <= dfn[u] && dfn[u] + siz[u] - 1 <= qr) {
return push(u, x);
}
down(u);
modify(ql, qr, u << 1, x);
modify(ql, qr, u << 1 | 1, x);
val[u] += (ql <= dfn[u] && dfn[u] <= qr) * x;
sum[u] = val[u] * Z(maxr[0][dfn[u]] - minl[0][dfn[u]] + 1) + sum[u << 1] +
sum[u << 1 | 1];
}
Z qres;
inline void query(const uint ql, const uint qr, uint u) {
uint L = minl[0][dfn[u]], R = maxr[0][dfn[u]];
if (L > qr || R < ql) return;
if (ql <= L && R <= qr) return qres += sum[u], void();
down(u);
qres += Z(min(R, qr) - max(L, ql) + 1) * val[u];
query(ql, qr, u << 1);
query(ql, qr, u << 1 | 1);
}
浙公網安備 33010602011771號