2023ICPC亞洲區域賽(合肥)VP補題題解記錄

寫在前面

已更新 E F G J，待更新 B I C

F and E(簽到題和簡單題)

F直接計數即可

ac代碼參考(FastIO已省略)

def solve():n = I()dic = {}for i in range(n):c = S()dic[c] = dic.get(c,0) + 1mx = 0ans = ''su = 0for k,v in dic.items():su += vif v > mx:mx = vans = kprint1(ans if mx > su/2 else "uh-oh")solve()

E 分離 x 和 y。

ac代碼參考

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e3+5;int n,m;
map<int,int> mp;
int cnt;
int a[N][N];
vector<int> nx[1000005];
vector<int> ny[1000005];
void solve()
{cin>>n>>m;for(int i=1;i<=n;++i)for(int j=1;j<=m;++j){cin>>a[i][j]; }for(int i=1;i<=n;++i) for(int j=1;j<=m;++j){int x=a[i][j];if(!mp[x])mp[x]=++cnt;int idx=mp[x];nx[idx].push_back(i);ny[idx].push_back(j);}ll ans=0;for(int i=1;i<=cnt;++i){ll sum=0;for(int j=0;j<nx[i].size();++j){ans-=sum;ans+=j*1ll*nx[i][j]; sum+=nx[i][j];}sum=0;sort(ny[i].begin(),ny[i].end());for(int j=0;j<ny[i].size();++j){ans-=sum;ans+=j*1ll*ny[i][j];sum+=ny[i][j];}}cout<<ans*2ll<<'\n';
}
int main()
{ios::sync_with_stdio(false);cin.tie(0);int t=1;
//	cin>>t;while(t--)solve();return 0;
} 

G. Streak Manipulation

題目大意

給你一個01串，告訴你串的長度 $n\in [1,2\times 10^5]$，最多可操作次數 $m\in [1,n]$, 以及 $k\in \min (n,5)$。每次操作可將一個 $0$ 變為 $1$。要我們求，在不超過 $m$ 次操作時，第 $k$ 長的連續為 $1$ 的串最長是多少。

題目分析

• 我們考慮二分答案，即二分在最多 $m$ 次操作后，第 $k$ 長的最小是多少(看到這個最大值最小的是不是很容易想到二分)。
• 想想check函數怎么實現，注意到 $k\in \min (n,5)$。
• 我們考慮dp，以當前是考慮前幾個字符為階段，與 前面有 $j$ 個長度大于 $mid$ 的連續 $1$ 串和當前字符是0還是1共同構成狀態。
• 對于當前的 $mid$, 設 $dp[i][j][0/1]$ 為前 $i$ 個字符，有 $j$ 段長度大于等于 $mid$ 的連續 $1$ 串，且當前字符是否位于第 $j$ 段連續 $1$ 串的末尾（0為假1為真）所需的最少操作次數。
• 考慮狀態轉移：
  • 如果 $s[i]={=}^{\prime }{0}^{\prime }$
    • $dp[i][j][0]=min(dp[i][j][0],dp[i?1][j][0],dp[i?1][j][1])$
    • $dp[i][j][1]=min(dp[i][j][1],dp[i?1][j][1]+1)$
  • 否則：
    • $dp[i][j][0]=min(dp[i][j][0],dp[i?1][j][0])$
    • $dp[i][j][1]=min(dp[i][j][1],dp[i?1][j][1])$
  • 此外在 $i\ge midandj\ge 0$ 時
    • $dp[i][j][1]=min(dp[i][j][1],dp[i?mid][j?1][0]+pre[i]?pre[i?mid])$
• $pre$ 記錄的是前綴中 $0$ 的數量。總的時間復雜度為 $O(kn\log (n))$

ac代碼參考

#include <bits/stdc++.h>
using namespace std;
const int N = 2e5+5;
int dp[N][6][2], pre[N];
int n,m,k;
string s;void solve(){auto check = [&](int mid){for (int i = 0; i <= n; i++)for(int j = 0; j <= k; j++)dp[i][j][0] = dp[i][j][1] = 0x3f3f3f3f;dp[0][0][0] = 0;for (int i = 1; i <= n; i++){for(int j = 0; j <= k; j++){if(s[i]=='0'){dp[i][j][0] = min({dp[i][j][0], dp[i-1][j][0], dp[i-1][j][1]});dp[i][j][1] = min({dp[i][j][1], dp[i-1][j][1] + 1});}else{dp[i][j][0] = min(dp[i][j][0], dp[i-1][j][0]);dp[i][j][1] = min(dp[i][j][1], dp[i-1][j][1]);}if (i >= mid && j >= 1)dp[i][j][1] = min(dp[i][j][1], dp[i-mid][j-1][0] + pre[i] - pre[i-mid]);}}return min(dp[n][k][0], dp[n][k][1]) <= m;};cin>>n>>m>>k>>s;s = "@" + s;for(int i = 1; i<=n; i++){pre[i] += pre[i-1] + (s[i] == '0');}int l = 0, r = 2e5;while (l < r){int mid = (l + r + 1) >> 1;if (check(mid)) l = mid;else r = mid - 1;}if(l)cout<<l<<'\n';else cout << "-1\n";}int main() {ios::sync_with_stdio(false);cin.tie(0);int t = 1;while (t--)solve();return 0;
}

J. Takeout Delivering

題目大意

給你一個無向連通圖，定義最短路為 path 中最貴的兩條邊之和，只有一條邊時就是邊權。求1到n的最短路。

$n\in [2,3\times 10^5],m\in [\max (1,n?1),10^6]$

題目分析

• 我們考慮枚舉每條邊 $Edge(x,y,z)$ 以該條邊作為路徑上的最大邊權的邊。
• 考慮第二大邊權的邊在哪？
• 一定在 $path(1,x),path(y,n)$ 或 $path(1,y),path(x,n)$
• 對于第二大邊權的邊，我們只需要預處理出從 $1$ 和從 $n$ 到各個點的最大邊權即可。
• 具體實現見代碼，總的時間復雜度為 $O(m\log m)$

ac代碼參考

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=3e5+5;
const int M=1e6+5;
struct Edge{int x,y,z;
}; int n,m,tot;
int ver[M+M],head[N],edge[M+M],nxt[M+M];
int d1[N],d2[N];
bool vis[N];
Edge ls[M];void solve()
{auto add = [&](int x,int y,int z){ver[++tot]=y,edge[tot]=z;nxt[tot]=head[x],head[x]=tot;};auto dijkstra = [&](int st,int *dist){priority_queue<pair<int, int> > q;memset(vis,0,sizeof(vis));for(int i=1;i<=n;++i)dist[i]=1e9+7;dist[st]=0;q.push({-0,st});while(!q.empty()){pair<int, int> tmp = q.top();q.pop();int x = tmp.second;if(vis[x]) continue;  vis[x] = 1;for(int i=head[x];i;i=nxt[i]){int y=ver[i];int w=edge[i];if (dist[y] > max(dist[x], w)){dist[y] = max(dist[x], w);q.push({-dist[y], y});}}}};cin>>n>>m;for(int i=1;i<=m;++i){int u,v,w;cin>>u>>v>>w;add(u,v,w);add(v,u,w);ls[i]={u,v,w};}dijkstra(1,d1);dijkstra(n,d2);int ans=2e9;for(int i=1;i<=m;++i){int x=ls[i].x,y=ls[i].y,z=ls[i].z;int tmp = min(max(d1[x],d2[y]), max(d1[y],d2[x]));if(tmp<=z)ans=min(ans,tmp+z);}cout<<ans<<'\n';
}
int main()
{ios::sync_with_stdio(false);cin.tie(0);int t=1;while(t--)solve(); return 0;
}