零、前言

經過七七四十九天的分別，本期 ABC 題解又和大家見面啦！

經過七周的奮勇殺題，我終于達成了三個小心愿：

1. 不吃罰時AK
2. 上金
3. 排名 $100$ 以內 且 Rated（悲催的是，我 ABC400 排名兩位數但沒Rated）

咳咳，言歸正傳，開始講題：

一、正文

第 A 題 G1

十分簡單，即求 $K$ 小于等于 $a$ 中幾個數即可。

代碼：

#include <bits/stdc++.h>
using namespace std;
int a[1110];
int main(){int n; cin>>n;for (int i=1; i<=n; i++) cin>>a[i];int k,ans=0; cin>>k;for (int i=1; i<=n; i++){if (a[i]>=k) ans++;}cout<<ans;
} 

第 B 題 Reverse Proxy

本題題意為維護 $n$ 個盒子，$m$ 次操作，每次可以往特定一個盒子或球數量最小（如有多個則取編號最小的）的盒子里放一個球，問每個球被放進那些盒子里了。

考慮到 $n,m\le 100$ 可以暴力查詢球數量最小的盒子編號。

代碼：

#include <bits/stdc++.h>
using namespace std;
int a[1110];
int main(){int n,q; cin>>n>>q;for (int i=1; i<=q; i++){int x; cin>>x;if (x!=0) cout<<x<<" ",a[x]++;else{int mn=1000000000,id;for (int i=1; i<=n; i++){if (a[i]<mn) mn=a[i],id=i;}cout<<id<<" "; a[id]++;}}
} 

第 C 題 Rotatable Array

題意為維護一個數組，有三種操作：

1. 單點修改
2. 單點查詢
3. 旋轉（即把第一個元素放到最后）

我們發現，數組長度不變，旋轉 $n$ 次可以抵消。

假設我們的下標從 $0$ 開始，那么旋轉 $u$ 次的第一個元素就是 $a_{u\%n}$。

修改、查詢第 $p$ 個點轉化為修改、查詢第 $(p+{\sum }_{i=1}^{id}{k}_i)\%n$ 個點， $id$ 表示當前操作編號，$k$ 為旋轉次數。

代碼：

#include <bits/stdc++.h>
using namespace std;
int a[2000010];
int main(){int n,q,st=0; cin>>n>>q;for (int i=1; i<=n; i++) a[i-1]=i;for (int i=1; i<=q; i++){int op; cin>>op;if (op==1){int p,s; cin>>p>>s; p--;a[(p+st)%n]=s;}else if (op==2){int p; cin>>p; p--;cout<<a[(p+st)%n]<<"\n";}else{int k; cin>>k;st=(st+k)%n;}}
} 

第 D 題 XOR Shortest Walk

一句話題意：給你 $n$ 個點 $m$ 條邊的圖，求 $1$ 到 $n$ 的最小異或路徑。

發現 $w<2^{10}=1024$，可以維護 $o{k}_{i,j}$ 表示從 $1$ 走到 $i$ 是否有異或和為 $j$ 的路徑。

BFS 維護，時間復雜度為 $O(w\times (n+m))$ 可以通過本題。

代碼：

#include <bits/stdc++.h>
using namespace std;
bool vis[2010][2010];
vector <pair<int,int>> vc[2010];
int main(){int n,m; cin>>n>>m;for (int i=1; i<=m; i++){int u,v,w; cin>>u>>v>>w;vc[u].push_back({v,w});}vis[1][0]=1;queue <int> qx,qy;qx.push(1); qy.push(0);while (qx.size()){int x=qx.front(),y=qy.front();qx.pop(); qy.pop();for (auto z:vc[x]){if (!vis[z.first][z.second^y]){vis[z.first][z.second^y]=1;qx.push(z.first); qy.push(z.second^y);}}}for (int i=0; i<=2000; i++){if (vis[n][i]) {cout<<i; return 0;}}cout<<-1;
} 

第 E 題 Battles in a Row

題意：有 $n$ 個怪物，每個怪物有兩個參數 $a_i,b_i$，你也有兩個參數 $A,B$。你可以令你的 $A$ 減去 $a_i$ 或 $B$ 減去 $b_i$ 來殺死怪物 $i$，你的 $A,B$ 不能變為負數。問 依次殺死怪物，你能殺死幾個呢？

特別提醒標黑部分（本蒟蒻讀錯題不會做卡了 20min。

考慮二分，二分一個怪物數量。對于前 $mid$ 個怪物，我們先把默認每個怪物都用 $A$ 殺，然后把 $b$ 作為代價， $a$ 作為價值，$B$ 為容量跑背包，跑出最大價值 $v$，發現如果 $(\sum a)?v\le A$，則有解。

其實不用二分也可以，但我賽時沒寫。

代碼：

#include <bits/stdc++.h>
using namespace std;
#define N 500000
int x[N],y[N],n,a,b,dp[N];
bool check(int mid){int sum=0;for (int i=1; i<=mid; i++) sum+=x[i];memset(dp,0,sizeof(dp));for (int i=1; i<=mid; i++){for (int j=b; j>=y[i]; j--){dp[j]=max(dp[j],dp[j-y[i]]+x[i]);}}return sum-dp[b]<=a;
}
int main(){ios::sync_with_stdio(0);cin.tie(0); cout.tie(0);cin>>n>>a>>b;for (int i=1; i<=n; i++){cin>>x[i]>>y[i];}int l=0,r=n;while (l<r-1){int mid=(l+r>>1);if (check(mid)) l=mid;else r=mid;}if (check(r)) cout<<r;else cout<<l;
} 

第 F 題 Balanced Rectangles

一句話題意，給你一個黑白網格，求多少子矩陣內黑白數量相等。

首先注意到 $H\times W\le 300000$，則 $H\times W\times \min (H,W)\le 300000\times \sqrt{300000}=164316767$，考慮這個時間復雜度。

首先你可以把黑設為 $1$，白為 $?1$，跑二維前綴和，那么假設 $H\le W$。

枚舉 $u,d$，滿足 $1\le u\le d\le H$，然后根據前綴和，我們可以求出每個紫矩陣的權值和，任選兩個（紅，綠）矩陣，如果它們權值相等，則構成一個可行答案（黑）。

那么請使用桶來統計答案，時間復雜度為上述值。

如果$H>W$，同理枚舉兩列即可。

代碼：

#include <bits/stdc++.h>
using namespace std;
#define K 500000
int cnt[K+K+K];
string s[K];
vector <int> sum[K];
int main(){ios::sync_with_stdio(0);cin.tie(0); cout.tie(0);int t; cin>>t;while (t--){int n,m; cin>>n>>m;for (int i=1; i<=n; i++) cin>>s[i],s[i]=" "+s[i];for (int i=0; i<=n; i++){sum[i].clear();for (int j=0; j<=m; j++){sum[i].push_back(((i==0||j==0)?0:(s[i][j]=='.'?1:-1)));}}for (int i=1; i<=n; i++){for (int j=1; j<=m; j++) sum[i][j]+=sum[i][j-1];}for (int i=1; i<=n; i++){for (int j=1; j<=m; j++) sum[i][j]+=sum[i-1][j];}if (n<=m){long long ans=0;for (int i=1; i<=n; i++){for (int j=i; j<=n; j++){cnt[K]++;for (int k=1; k<=m; k++){ans+=cnt[sum[j][k]-sum[i-1][k]+K];cnt[sum[j][k]-sum[i-1][k]+K]++;}for (int k=1; k<=m; k++){cnt[sum[j][k]-sum[i-1][k]+K]--;}cnt[K]--;}}cout<<ans<<"\n";}else{long long ans=0;for (int i=1; i<=m; i++){for (int j=i; j<=m; j++){cnt[K]++;for (int k=1; k<=n; k++){ans+=cnt[sum[k][j]-sum[k][i-1]+K];cnt[sum[k][j]-sum[k][i-1]+K]++;}for (int k=1; k<=n; k++){cnt[sum[k][j]-sum[k][i-1]+K]--;}cnt[K]--;}}cout<<ans<<"\n";}}
} 

第 G 題 Longest Chord Chain

一句話題意：一個圓上有一些弦，保留互不相交的一些弦，再畫一條弦，求問它們之間最多存在多少個交點。

猜結論：保留最多的弦，使得它們可以分成兩部分，每部分都依次包含，兩部分無交集。

看如下圖：

可以粗略證明上述結論。

現在考慮如何求解，首先假設 $a_i<b_i$（可以交換兩者），接下來把 $a$ 從大到小排序，設 $d{p}_i$ 為第 $i$ 個弦可以連套多少個區間，易得 $d{p}_i={\max }_{j\in [1,n]}^{j!=i,a_i<a_j<b_j<b_i}d{p}_j+1$，可以使用樹狀數組優化。

接下來有了 $dp$ 后，易得答案為 ${\max }_{i,j\in [1,n]}^{i!=j,b_j<a_i}d{p}_i+d{p}_j$ 和 $\max (d{p}_i)$ 求最大值，前者也用樹狀數組優化即可，具體實現請參考代碼。

代碼：

#include <bits/stdc++.h>
using namespace std;
#define N 500010
int n,dp[N];
struct edg{int x,y;
}a[N];
bool cmp(edg a,edg b){return a.x>b.x; 
}
struct node{int c[N];void update(int id,int mx){while (id<=n*2){c[id]=max(c[id],mx); id+=(id&-id);}}int query(int id){int ans=0;while (id>0){ans=max(ans,c[id]); id-=(id&-id);}return ans;}
}tr,tr2;
int main(){ios::sync_with_stdio(0);cin.tie(0); cout.tie(0);cin>>n;for (int i=1; i<=n; i++){cin>>a[i].x>>a[i].y;if (a[i].x>a[i].y) swap(a[i].x,a[i].y);}sort(a+1,a+n+1,cmp);for (int i=1; i<=n; i++){dp[i]=tr.query(a[i].y)+1;tr.update(a[i].y,dp[i]);}for (int i=1; i<=n; i++){tr2.update(a[i].y,dp[i]);}int ans=0;for (int i=1; i<=n; i++){ans=max(ans,tr2.query(a[i].x)+dp[i]);}cout<<ans;
} 

二、后記

本篇題解結束了，祝愿大家能夠在學習中實現一個一個小目標，在突破自我中成長。