2023ICPC亚洲区域赛(合肥)VP补题题解(48th)

2023ICPC亚洲区域赛(合肥)VP补题题解记录。已更新 E F G J，待更新 B I C。

smile是对你的礼貌~

3963人浏览 · 2024-07-03 13:28:42

smile是对你的礼貌~ · 2024-07-03 13:28:42 发布

2023ICPC亚洲区域赛(合肥)VP补题题解记录

文章目录

2023ICPC亚洲区域赛(合肥)VP补题题解记录

写在前面

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

比赛补题链接：Dashboard - The 2023 ICPC Asia Hefei Regional Contest (The 2nd Universal Cup. Stage 12: Hefei) - Codeforces

F and E(签到题和简单题)

F直接计数即可

ac代码参考(FastIO已省略)

def solve():
    n = I()
    dic = {}
    for i in range(n):
        c = S()
        dic[c] = dic.get(c,0) + 1
    mx = 0
    ans = ''
    su = 0
    for k,v in dic.items():
        su += v
        if v > mx:
            mx = v
            ans = k

    print1(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\times10^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$ 个长度大于 $mi d$ 的连续 $1$ 串和当前字符是0还是1共同构成状态。
对于当前的 $mi d$ , 设 $d p [i] [j] [0/1]$ 为前 $i$ 个字符，有 $j$ 段长度大于等于 $mi d$ 的连续 $1$ 串，且当前字符是否位于第 $j$ 段连续 $1$ 串的末尾（0为假1为真）所需的最少操作次数。
考虑状态转移：
- 如果 $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})$
- 否则：
  - $d p [i] [j] [0] = min (d p [i] [j] [0], d p [i - 1] [j] [0])$
  - $d p [i] [j] [1] = min (d p [i] [j] [1], d p [i - 1] [j] [1])$
- 此外在 $i\ge mid\ and \ j \ge0$ 时
  - $d p [i] [j] [1] = min (d p [i] [j] [1], d p [i - mi d] [j - 1] [0] + p re [i] - p re [i - mi d])$
$p re$ 记录的是前缀中 $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\times10^5],m\in[\max(1,n-1),10^6]$

题目分析

我们考虑枚举每条边 $E d g e (x, y, z)$ 以该条边作为路径上的最大边权的边。
考虑第二大边权的边在哪？
一定在 $p a t h (1, x), p a t h (y, n)$ 或 $p a t h (1, y), p a t h (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;
}

B. Queue Sorting

题目大意

给一个可重数集， $n$ $(1 \leq n \leq 500)$ 有 $a_i$ $a_i≤500)$ 个，问有多少序列符合能拆成最多两个不降子序列。

题目分析

根据 Dilworth 定理，最小链分解数等于最长反链长度，即最长下降子序列长度不能超过 2 。(类似比较经典的题目有如拦截导弹)
我们现在问题变成了：有多少种不同的序列，它的最长下降子序列长度不能超过 2 。
考虑计数 DP 的方法，一开始构造一个空序列，接着将数字按从小到大的顺序插入到序列之中。
对于每次加入的数字 $i$ ，只要不是最后一个，必定形成一个长度为 2 的下降子序列。
设 $d p (i, j)$ 表示，数字 $1$ ∼ $i$ 已经全部插入，最后一个长度为 2 的下降子序列靠前前的那个数字的位置是 $j$ 。
令 $sum_x=∑_{y≤x}a_y$ ，每次 $i + 1$ 插入的时候是不能放到位置 $j$ 前面的，插在后面不改变最长下降子序列的长度，所以相当于对 $j+1,sum_i]$ 和 $a_{i+1}$ 个位置的组合。
状态转移要考虑新的 $j'$ 的位置，所以枚举有 $x$ 个 $i + 1$ 直接加到最后了，第一个不是最后的位置是 $k$ ，转移是:
$dp(i+1,k)=\sum_{j,x}{dp(i,j)\times{\left( \begin{aligned} &\ \ \ k-j-1 \\ &a_{i+1}-x-1 \\ \end{aligned} \right)}}$

ac代码参考

#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> pii;
const int N = 507, mod = 998244353;


int a[N], sum[N], dp[N][N], c[N][N];
int n;

void solve(){
	cin >> n;
	for(int i = 1; i <= n; i++) {
		cin>>a[i];
		sum[i] = sum[i - 1] + a[i];
	}

	c[0][0] = 1;
	for(int i = 1; i <= sum[n]; i++) {
		c[i][0] = 1;
		for(int j = 1; j <= i; j++) 
			c[i][j] = (c[i][j] + c[i - 1][j - 1] + c[i - 1][j]) % mod;
	}

	dp[0][0] = 1;
	for(int i = 0; i < n; i++) 
		for(int j = 0; j <= sum[i]; j++) if (dp[i][j]) {
			dp[i + 1][j] = (dp[i + 1][j] + dp[i][j]) % mod;
			for (int k = j + 1; k < sum[i + 1]; k++) { 
				//  如果边界比较复杂，可以使用if 代替直接计算
				int lb = max(0, a[i + 1] - (k - j));
				int ub = min(a[i + 1] - 1, sum[i + 1] - k - 1);
				for(int x = lb; x <= ub; x++) 
					dp[i + 1][k] = (dp[i+1][k] + (1ll * dp[i][j] * c[k - j - 1][a[i + 1] - x - 1] % mod)) % mod;
			}
		}

	int ans = 0;
	for(int i = 0; i <= sum[n]; i++) ans = (ans + dp[n][i]) % mod;
	cout<<ans<<'\n';
}


int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	int t = 1;
	while(t--)
		solve();
	return 0;
}