2023ICPC亚洲区域赛(合肥)VP补题题解(48th)
Mister.Yu 2024-10-27 10:05:01 阅读 86
2023ICPC亚洲区域赛(合肥)VP补题题解记录
文章目录
2023ICPC亚洲区域赛(合肥)VP补题题解记录写在前面已更新 E F G J B，待更新 I C
F and E(签到题和简单题)G. Streak Manipulation题目大意题目分析ac代码参考
J. Takeout Delivering题目大意题目分析ac代码参考
B. Queue Sorting题目大意题目分析ac代码参考
写在前面
已更新 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已省略)
<code>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
∈
[
1
,
2
×
1
0
5
]
n\in[1,2\times10^5]
n∈[1,2×105]，最多可操作次数
m
∈
[
1
,
n
]
m\in[1,n]
m∈[1,n], 以及
k
∈
min
(
n
,
5
)
k\in\min(n,5)
k∈min(n,5)。每次操作可将一个
0
0
0 变为
1
1
1。要我们求，在不超过
m
m
m 次操作时，第
k
k
k 长的连续为
1
1
1 的串最长是多少。
题目分析
我们考虑二分答案，即二分在最多
m
m
m 次操作后，第
k
k
k 长的最小是多少(看到这个最大值最小的是不是很容易想到二分)。想想check函数怎么实现，注意到
k
∈
min
(
n
,
5
)
k\in\min(n,5)
k∈min(n,5)。我们考虑dp，以当前是考虑前几个字符为阶段，与 前面有
j
j
j 个长度大于
m
i
d
mid
mid 的连续
1
1
1 串和当前字符是0还是1共同构成状态。对于当前的
m
i
d
mid
mid, 设
d
p
[
i
]
[
j
]
[
0
/
1
]
dp[i][j][0/1]
dp[i][j][0/1] 为前
i
i
i 个字符，有
j
j
j 段长度大于等于
m
i
d
mid
mid 的连续
1
1
1 串，且当前字符是否位于第
j
j
j 段连续
1
1
1 串的末尾（0为假1为真）所需的最少操作次数。考虑状态转移：
如果
s
[
i
]
=
=
′
0
′
s[i] == '0'
s[i]==′0′
d
p
[
i
]
[
j
]
[
0
]
=
m
i
n
(
d
p
[
i
]
[
j
]
[
0
]
,
d
p
[
i
−
1
]
[
j
]
[
0
]
,
d
p
[
i
−
1
]
[
j
]
[
1
]
)
dp[i][j][0] = min({dp[i][j][0], dp[i-1][j][0], dp[i-1][j][1]})
dp[i][j][0]=min(dp[i][j][0],dp[i−1][j][0],dp[i−1][j][1])
d
p
[
i
]
[
j
]
[
1
]
=
m
i
n
(
d
p
[
i
]
[
j
]
[
1
]
,
d
p
[
i
−
1
]
[
j
]
[
1
]
+
1
)
dp[i][j][1] = min({dp[i][j][1], dp[i-1][j][1] + 1})
dp[i][j][1]=min(dp[i][j][1],dp[i−1][j][1]+1) 否则：
d
p
[
i
]
[
j
]
[
0
]
=
m
i
n
(
d
p
[
i
]
[
j
]
[
0
]
,
d
p
[
i
−
1
]
[
j
]
[
0
]
)
dp[i][j][0] = min(dp[i][j][0], dp[i-1][j][0])
dp[i][j][0]=min(dp[i][j][0],dp[i−1][j][0])
d
p
[
i
]
[
j
]
[
1
]
=
m
i
n
(
d
p
[
i
]
[
j
]
[
1
]
,
d
p
[
i
−
1
]
[
j
]
[
1
]
)
dp[i][j][1] = min(dp[i][j][1], dp[i-1][j][1])
dp[i][j][1]=min(dp[i][j][1],dp[i−1][j][1]) 此外在
i
≥
m
i
d
a
n
d
j
≥
0
i\ge mid\ and \ j \ge0
i≥mid and j≥0 时
d
p
[
i
]
[
j
]
[
1
]
=
m
i
n
(
d
p
[
i
]
[
j
]
[
1
]
,
d
p
[
i
−
m
i
d
]
[
j
−
1
]
[
0
]
+
p
r
e
[
i
]
−
p
r
e
[
i
−
m
i
d
]
)
dp[i][j][1] = min(dp[i][j][1], dp[i-mid][j-1][0] + pre[i] - pre[i-mid])
dp[i][j][1]=min(dp[i][j][1],dp[i−mid][j−1][0]+pre[i]−pre[i−mid])
p
r
e
pre
pre 记录的是前缀中
0
0
0 的数量。总的时间复杂度为
O
(
k
n
log
(
n
)
)
O(\ kn\log(n)\ )
O( knlog(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
∈
[
2
,
3
×
1
0
5
]
,
m
∈
[
max
(
1
,
n
−
1
)
,
1
0
6
]
n\in[2,3\times10^5],m\in[\max(1,n-1),10^6]
n∈[2,3×105],m∈[max(1,n−1),106]
题目分析
我们考虑枚举每条边
E
d
g
e
(
x
,
y
,
z
)
Edge(x,y,z)
Edge(x,y,z) 以该条边作为路径上的最大边权的边。考虑第二大边权的边在哪？一定在
p
a
t
h
(
1
,
x
)
,
p
a
t
h
(
y
,
n
)
path(1,x),path(y,n)
path(1,x),path(y,n) 或
p
a
t
h
(
1
,
y
)
,
p
a
t
h
(
x
,
n
)
path(1,y),path(x,n)
path(1,y),path(x,n)对于第二大边权的边，我们只需要预处理出从
1
1
1 和从
n
n
n 到各个点的最大边权即可。具体实现见代码，总的时间复杂度为
O
(
m
log
m
)
O(m\log m)
O(mlogm)
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
n
n
(
1
≤
n
≤
500
)
(1≤n≤500)
(1≤n≤500) 有
a
i
a_i
ai
(
∑
a
i
≤
500
)
(∑a_i≤500)
(∑ai≤500) 个，问有多少序列符合能拆成最多两个不降子序列。
题目分析
根据 Dilworth 定理，最小链分解数等于最长反链长度，即最长下降子序列长度不能超过 2 。(类似比较经典的题目有如 拦截导弹)
我们现在问题变成了：有多少种不同的序列，它的最长下降子序列长度不能超过 2 。
考虑计数 DP 的方法，一开始构造一个空序列，接着将数字按从小到大的顺序插入到序列之中。
对于每次加入的数字
i
i
i ，只要不是最后一个，必定形成一个长度为 2 的下降子序列。
设
d
p
(
i
,
j
)
dp(i,j)
dp(i,j) 表示，数字
1
1
1∼
i
i
i 已经全部插入，最后一个长度为 2 的下降子序列靠前前的那个数字的位置是
j
j
j 。
令
s
u
m
x
=
∑
y
≤
x
a
y
sum_x=∑_{y≤x}a_y
sumx=∑y≤xay，每次
i
+
1
i+1
i+1 插入的时候是不能放到位置
j
j
j 前面的，插在后面不改变最长下降子序列的长度，所以相当于对
[
j
+
1
,
s
u
m
i
]
[j+1,sum_i]
[j+1,sumi] 和
a
i
+
1
a_{i+1}
ai+1 个位置的组合。
状态转移要考虑新的
j
′
j′
j′ 的位置，所以枚举有
x
x
x 个
i
+
1
i+1
i+1 直接加到最后了，第一个不是最后的位置是
k
k
k ，转移是:
d
p
(
i
+
1
,
k
)
=
∑
j
,
x
d
p
(
i
,
j
)
×
(
k
−
j
−
1
a
i
+
1
−
x
−
1
)
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)}}
dp(i+1,k)=j,x∑dp(i,j)×( k−j−1ai+1−x−1)
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;
}
声明
本文内容仅代表作者观点，或转载于其他网站，本站不以此文作为商业用途
如有涉及侵权，请联系本站进行删除
转载本站原创文章，请注明来源及作者。