Codeforces Round #681 A~C题解

发布于 2020-11-04  0 次阅读


A. Kids Seating

题目大意:

给你一个n,从1~4n中选出n个数字使得数字两两gcd≠1并且不能互相整除

思路:

考虑从4n往前取,每次减少2,即可使得两两之间的gcd=2
同时,由4n取到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=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;
void solve(){
    cin>>n;
    for(int i=4*n; i>2*n; i-=2)cout<<i<<" ";
    putchar('\n');
	return ;
}

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

B. Saving the City

题目大意:

给你一个01字符串s,消除其中连续的1耗费a,将一个0变为1耗费b,求将整个字符串s全部变成0所消耗的最小值

思路:

取将不相连的两段相连与否的最小值即可,即为
第一个连续的1直接耗费a,后面记录到下一段的1的距离(即为中间0的个数),然后m i n ( s u m ∗ b , a ) min(sum*b,a)min(sum∗b,a)即可

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 a, b, ans;
string s;
void solve(){
    cin>>a>>b;
    cin>>s;
    ans=0;
    int flag=0, sum=0;
    for(int i=0; i<s.length(); i++){
        if(s[i]=='1'){
            if(!flag) flag=1, ans=a;
            else      ans+=min(a,sum*b);
            sum=0;
        }
        if(s[i]=='0') sum++;
    }
    cout<<ans<<endl;
	return ;
}

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

C. The Delivery Dilemma(贪心|二分)

题目大意:

共有n道菜,餐厅给你送过来的时间为ai ,你自己去餐厅拿的时间为bi ,不同的餐厅可以同时送餐,但在一段时间内你只能去一家餐厅
求n道菜全部到家的最小时间

思路1:

考虑二分答案,首先假设自己去所有的餐厅取餐,然后二分答案,当前时间大于mid时,自己去取餐,小于mid的让餐厅送过来,算出自己去拿的时间然后与当前的时间mid作判断

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, a[N], b[N];
int l, r, mid, sum;

bool check(int x){
    sum=0;
    for(int i=1; i<=n; i++)
        if(a[i]>x)
            sum+=b[i];
    return sum<=x;
}

void solve(){
    l=r=0;
    cin>>n;
    for(int i=1; i<=n; i++) cin>>a[i];
    for(int i=1; i<=n; i++) cin>>b[i], r+=b[i];
    while(l<r){
        mid=(l+r)>>1;
        if(check(mid))  r=mid;
        else            l=mid+1;
    }
    cout<<r<<endl;
	return ;
}

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

思路2:

考虑将各个菜的时间按照a aa非递增排序,然后前缀和维护b bb的送餐时间,然后a n s = m i n ( a n s , m a x ( s u m [ i − 1 ] , a [ i ] ) ) ans=min(ans,max(sum[i-1], a[i]))ans=min(ans,max(sum[i−1],a[i]))
很好理解的思路,就不说了

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 0x3f3f3f3f3f3f
#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, sum[N];
struct node
{
    int a, b;
}tim[N];

bool cmp(node a, node b){
    if(a.a==b.a) a.b<a.b;
    return a.a>b.a;
}

void solve(){
    cin>>n;
    for(int i=1; i<=n; i++) cin>>tim[i].a;
    for(int i=1; i<=n; i++) cin>>tim[i].b;
    sort(tim+1,tim+1+n,cmp);
    for(int i=1; i<=n; i++) sum[i]=sum[i-1]+tim[i].b;
    int ans=INF;
    tim[n+1].a=0;
    for(int i=n+1; i>=1; i--){
        ans=mymin(ans,max(sum[i-1], tim[i].a));
    }
    cout<<ans<<endl;
	return ;
}

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

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