我是靠谱客的博主 任性小松鼠,最近开发中收集的这篇文章主要介绍Codeforces Round #551 (Div. 2) 题解,觉得挺不错的,现在分享给大家,希望可以做个参考。

概述

题目链接:http://codeforces.com/contest/1153

 

A. Serval and Bus

计算每一班车到达车站的时间超过m,并且离m最近的时间去最小就好了。

#include <bits/stdc++.h>
using namespace std;
const int mx = 1e2 + 10;
int main(){
int n,m;
scanf("%d%d",&n,&m);
int u,v,ma = 1e9,p = 1;
for(int i=1;i<=n;i++){
scanf("%d%d",&u,&v);
if(u>=m){
if(ma>u) p = i,ma = u;
}else{
int c = m - u;
u += ((c-1)/v + 1)*v;
if(ma>u) p = i,ma = u;
}
}
printf("%dn",p);
return 0;
} 

B. Serval and Toy Bricks

对于这样的一个构造题,首先让其满足一个条件,然后再用第二个条件进行筛选。也就是将第i行的数都先变为b[i],这样就满足了第二个条件,然后再将现在的值和第一个条件的值取一个min就好了,至于俯看就更好判断了。

#include <bits/stdc++.h>
using namespace std;
const int mx = 1e2 + 10;
int ans[mx][mx],a[mx],b[mx];
bool top[mx][mx];
int main(){
int n,m,h;
scanf("%d%d%d",&n,&m,&h);
for(int i=1;i<=m;i++) scanf("%d",a+i);
for(int i=1;i<=n;i++) scanf("%d",b+i);
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
scanf("%d",top[i]+j);
ans[i][j] = b[i];
if(!top[i][j]) ans[i][j] = 0;
}
}
for(int j=1;j<=m;j++){
for(int i=1;i<=n;i++){
ans[i][j] = min(a[j],ans[i][j]);
}
}
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++)
printf("%d ",ans[i][j]);
puts("");
}
return 0;
} 

C. Serval and Parenthesis Sequence

很明显的一个贪心,对于左括号放左边最好,对于右括号放右边最好。然后最后去看一下是否有前缀可以完全括号匹配。

#include <bits/stdc++.h>
using namespace std;
const int mx = 3e5 + 10;
char s[mx];
int main(){
int n,hd = 0;
int a = 0,b = 0;
scanf("%d",&n);
scanf("%s",s+1);
for(int i=n;i>=1;i--){
if(s[i]=='(') a++;
if(s[i]==')') b++;
}
if((n&1)||s[n]=='(') return 0*puts(":(");
if(max(a,b)>n/2) return 0*puts(":(");
int d = n/2 - a;
for(int i=1;i<=n;i++){
if(s[i]=='?'){
if(d>0) s[i] = '(',d--;
else s[i] = ')';
}
}
for(int i=1;i<n;i++){
if(s[i]=='(') hd++;
else{
hd--;
if(hd<=0) return 0*puts(":(");
}
}
puts(s+1);
return 0;
} 

 

D. Serval and Rooted Tree

对于这题来说,我们可以做一个dp,dp[x]表示x节点可以获得的最大值与最大值(叶子节点数)的差+1,那么对于节点u来说,如果是取max,那么dp[u]就等于u的子节点v的max{dp[v]}。如果是取min,那么dp[u] = sum dp[v]。因为数字是不能重复的,所以只能去下顺,所以取min的最大值就是所有子节点的dp值之和。最后的答案就是最大值-dp[1]+1。

#include <bits/stdc++.h>
using namespace std;
const int mx = 3e5 + 10;
int n,ty[mx],out[mx],siz;
int cnt[mx];
vector <int> g[mx];
void dfs(int u){
cnt[u] = 1e9;
int sum = 0;
for(int v:g[u]){
dfs(v);
if(ty[u])
cnt[u] = min(cnt[v],cnt[u]);
sum += cnt[v];
}
if(!ty[u]) cnt[u] = sum;
if(!out[u]) cnt[u] = 1;
}
int main(){
scanf("%d",&n);
for(int i=1;i<=n;i++) scanf("%d",ty+i);
int v;
for(int i=2;i<=n;i++){
scanf("%d",&v);
g[v].push_back(i);
out[v]++;
}
for(int i=1;i<=n;i++)
if(!out[i]) siz++;
dfs(1);
printf("%dn",siz-cnt[1]+1);
return 0;
} 

E. Serval and Snake

 对于查询的一个矩形值来说,如果它是奇数,说明矩形内肯定有且只有一个点是头或者尾。如果是偶数,那么说明矩形内头和尾都在矩形内或者都不在矩形内。

因此我们可以通过查询前i行是奇数还是偶数,可以得到头和尾在第几行。用相同的方法查询前j列也可以得到头和尾在第几列,这样最后在通过一次查询确定头尾位置示意总共花费2*n - 1次。

但是还有一种情况是无法都得到两种位置的,也就是头和尾在同一行或者同一列。这个时候的查询就查不到奇数,也就无法判断它在第几行(第几列),但是我们知道头和尾在第几列(第几行)。根据前面讲到的矩形值得奇偶性可以对该列(行)进行奇偶性二分查询,从而找到它在第几行(列)。所以这种情况最后查询要再加log(n)次。

所以总共的查询不会超过2008次。

#include <bits/stdc++.h>
using namespace std;
const int mx = 1e3 + 10;
int main(){
int n,v;
scanf("%d",&n);
int u,d,l,r;
l = u = 1e9,r = d = 0;
for(int i=1;i<n;i++){
printf("? %d %d %d %dn",1,1,n,i);
fflush(stdout);
scanf("%d",&v);
if(v&1){
l = min(l,i);
r = max(r,i+1);
}
}
for(int i=1;i<n;i++){
printf("? %d %d %d %dn",1,1,i,n);
fflush(stdout);
scanf("%d",&v);
if(v&1){
u = min(u,i);
d = max(d,i+1);
}
}
if(!r){
int L = 1,R = n;
while(L<R){
int mid = (L+R)>>1;
printf("? %d %d %d %dn",u,1,u,mid);fflush(stdout);
scanf("%d",&v);
if(v&1) R = mid; else L = mid+1;
}
printf("! %d %d %d %dn",u,L,d,L);fflush(stdout);
}else if(!d){
int L = 1,R = n;
while(L<R){
int mid = (L+R)>>1;
printf("? %d %d %d %dn",1,l,mid,l);fflush(stdout);
scanf("%d",&v);
if(v&1) R = mid; else L = mid+1;
}
printf("! %d %d %d %dn",L,l,L,r);fflush(stdout);
}else{
printf("? %d %d %d %dn",u,l,u,l);
fflush(stdout);
scanf("%d",&v);
printf("! %d %d %d %dn",u,v==1?l:r,d,v==1?r:l);
fflush(stdout);
}
return 0;
} 

F. Serval and Bonus Problem

我们可以把区间长度看做1,然后最后再将结果扩大L倍,显然答案是一样的。

对于原来的问题求被至少k条线段覆盖区间和的期望,我们可以转化成随机一个点x,求x在至少k条线段内的概率,这也是等价的,已知n条线段就会有2*n个点,再加上x就有2*n+1个点。

然后就有dp[i][j][0/1]表示前i个点中还有j个点还有没有匹配成线段,0/1表示x点放了还是没放。那么就有如下转移方程:

                                               dp[i][j][k] -> dp[i+1][j+1][k]     该点作为左端点

                                               dp[i][j][k] -> dp[i+1][j-1][k]     该点作为右端点

                                               dp[i][j][0] -> dp[i+1][j][1](j>=k)  该点作为x,保证至少被K条线段覆盖

这是我们求得的可行方案数,所以最后要除以总的方案数才是概率,总的方案数可以看做(2*n+1)!,但是线段的端点并不用考虑顺序,n条线段也不需要有顺序之分,所以最后答案还要乘以2^{n} * n!

(本蒟蒻还是对期望dp有点迷糊)

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mx = 4e3 + 10;
const int mod = 998244353;
ll fac[mx];
int dp[mx][mx][2];
void add(int &x,int y){ x = (x+y)%mod; }
ll qpow(ll x,ll y){
ll ans = 1;
while(y){
if(y&1) ans = ans*x%mod;
y >>= 1;
x = x*x%mod;
}
return ans;
}
int main(){
int n,L,K;
scanf("%d%d%d",&n,&K,&L);
fac[0] = dp[0][0][0] = 1;
for(int i=1;i<mx;i++) fac[i] = fac[i-1]*i%mod;
int c = 2*n + 1;
for(int i=0;i<c;i++){
for(int j=0;j<=i;j++){
add(dp[i+1][j+1][0],dp[i][j][0]);
add(dp[i+1][j+1][1],dp[i][j][1]);
if(j){
add(dp[i+1][j-1][0],1ll*dp[i][j][0]*j%mod);
add(dp[i+1][j-1][1],1ll*dp[i][j][1]*j%mod);
}
if(j>=K) add(dp[i+1][j][1],dp[i][j][0]);
}
}
ll ans = fac[n]*qpow(2,n)%mod*dp[c][0][1]%mod*L%mod;
printf("%lldn",ans*qpow(fac[c],mod-2)%mod);
return 0;
} 

 

最后

以上就是任性小松鼠为你收集整理的Codeforces Round #551 (Div. 2) 题解的全部内容,希望文章能够帮你解决Codeforces Round #551 (Div. 2) 题解所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错,欢迎将靠谱客网站推荐给程序员好友。

本图文内容来源于网友提供,作为学习参考使用,或来自网络收集整理,版权属于原作者所有。
点赞(70)

评论列表共有 0 条评论

立即
投稿
返回
顶部