Educational Codeforces Round 97 (Rated for Div. 2)A~D题解

发布于 2020-10-28  0 次阅读


A. Marketing Scheme

题目大意:

有顾客想购买x( l < = x < = r )包猫粮,你可以选择a包猫粮并且将其打包,顾客会首先买打包好的,而后剩余的x mod a包猫粮将会一包一包买,除非x mod a ≥   a / 2
你需要使得所有的顾客买的猫粮都高于想买的,即为( l < = x < = r )上所有的顾客都满足x   mod   a   ≥   a / 2

思路:

很明显重要的条件是满足x   mod   a   ≥   a / 2,即为使得等式左边大,右边小
x最大即为r,所有可以假设a=r+1,这样既可满足上述条件,再判断l是否满足即可

AC Code:

#pragma GCC optimize("-Ofast","-funroll-all-loops")
#include<cstdio>
#include<algorithm>
#include<iostream>
#include<cstring>
#include<math.h>
using namespace std;
#define endl '\n'
#define INF 0x3f3f3f3f
// #define int long long
#define debug(a) cout<<#a<<"="<<a<<endl;
typedef long long ll;
const double PI=acos(-1.0);
const double e=exp(1.0);
const int M=1e9+7;
const int N=2e5+7;
inline int mymax(int x,int y){return x>y?x:y;}
inline int mymin(int x,int y){return x<y?x:y;}
int l, r, a;
void solve(){
    cin>>l>>r;
    a=r+1;
    if(l%a >= (a+1)/2)  cout<<"YES"<<endl;
    else                cout<<"NO"<<endl;
	return ;
}

signed main(){
	ios::sync_with_stdio(false);
	cin.tie(0), cout.tie(0);
    int T;
    cin>>T;
    while(T--) solve();
    return 0;
}

B. Reverse Binary Strings

题目大意:

给你一个01字符串,你每次可以选择一个连续的子串进行左右翻转
求将其翻转成0,1交替出现的字符串的最小操作次数

思路:

显然每次翻转只能改变子串的两端的字符,所以每次翻转最多改变一个连续两个的1和一个连续的两个的0
即为每次操作可以使得连续的0和1的部分的连续长度减一
所以最小的操作次数即为连续的两个0和1的数量的最大值

AC Code:

#pragma GCC optimize("-Ofast","-funroll-all-loops")
#include<cstdio>
#include<algorithm>
#include<iostream>
#include<cstring>
#include<math.h>
using namespace std;
#define endl '\n'
#define INF 0x3f3f3f3f
// #define int long long
#define debug(a) cout<<#a<<"="<<a<<endl;
typedef long long ll;
const double PI=acos(-1.0);
const double e=exp(1.0);
const int M=1e9+7;
const int N=2e5+7;
inline int mymax(int x,int y){return x>y?x:y;}
inline int mymin(int x,int y){return x<y?x:y;}
int n;
 string s;
void solve(){
    cin>>n>>s;
    int ans1=0, ans0=0;
    for(int i=0; i<s.length()-1; i++){
        if(s[i]=='1' && s[i+1]=='1') ans1++;
        if(s[i]=='0' && s[i+1]=='0') ans0++;
    }
    cout<<mymax(ans1,ans0)<<endl;
	return ;
}

signed main(){
    int T;
    cin>>T;
    while(T--) solve();
    return 0;
}

C. Chef Monocarp(dp)

题目大意:

厨师刚刚把菜放进烤箱。他知道第i道菜的最佳烹饪时间是ti 分钟。在任何正整数分钟,厨师最多只能从烤箱中拿出一个盘子。如果第i盘在某一分钟被端出,那么它令人不快的值就是i 和ti之间的绝对差值。菜一出烤箱就放不进去了。厨师应该把所有的盘子从烤箱中拿出来。求厨师能获得的最小总不愉快值是多少

思路:

dp[i][j]表示在第i道菜在第j分钟被拿出的最小总不愉快值
注意点,n道菜最多2n时间被全部拿出

AC Code:

#pragma GCC optimize("-Ofast","-funroll-all-loops")
#include<cstdio>
#include<algorithm>
#include<iostream>
#include<cstring>
#include<math.h>
using namespace std;
#define endl '\n'
#define INF 0x3f3f3f3f
// #define int long long
#define debug(a) cout<<#a<<"="<<a<<endl;
typedef long long ll;
const double PI=acos(-1.0);
const double e=exp(1.0);
const int M=1e9+7;
const int N=209;
inline int mymax(int x,int y){return x>y?x:y;}
inline int mymin(int x,int y){return x<y?x:y;}
int n, a[N], dp[N][N*2];
void solve(){
    cin>>n;
    for(int i=1; i<=n; i++) cin>>a[i];
    sort(a+1, a+1+n);
    memset(dp, INF, sizeof(dp));
    for(int i=0; i<=n*2; i++) dp[0][i]=0; 
    for(int i=1; i<=n; i++)
        for(int j=1; j<=n*2; j++)
            dp[i][j]=min(dp[i][j-1], dp[i-1][j-1]+abs(a[i]-j));
    cout<<dp[n][n*2]<<endl;
	return ;
}

signed main(){
    int T;
    cin>>T;
    while(T--) solve();
    return 0;
}

D. Minimal Height Tree

题目大意:

已知一个BFS的遍历顺序,每个结点的子节点是按照升序从左到右排列的
求树的最少的层数

思路:

将每个升序的子序列接到树的目前的根结点,并且该子序列的长度即为下次可以接的子树的个数

AC Code:

#pragma GCC optimize("-Ofast","-funroll-all-loops")
#include<cstdio>
#include<algorithm>
#include<iostream>
#include<cstring>
#include<math.h>
using namespace std;
#define endl '\n'
#define INF 0x3f3f3f3f
// #define int long long
#define debug(a) cout<<#a<<"="<<a<<endl;
typedef long long ll;
const double PI=acos(-1.0);
const double e=exp(1.0);
const int M=1e9+7;
const int N=2e5+7;
inline int mymax(int x,int y){return x>y?x:y;}
inline int mymin(int x,int y){return x<y?x:y;}
int T, n, a[N];
int ans, now, cnt, sum;
void solve(){
	cin>>n;
    ans=sum=1;
    cnt=now=0;
    cin>>a[1];
    for(int i=2; i<=n; i++){
        cin>>a[i];
        if(a[i]>a[i-1]) now++;
        else{
            cnt++;
            if(cnt==sum){
                ans++;
                cnt=0;
                sum=now;
            }
        }
    }
    cout<<ans<<endl;		
	return ;
}

signed main(){
    int T;
    cin>>T;
    while(T--) solve();
    return 0;
}

平平无奇的大学在读本科生