9/21 越努力越幸运-思维赛(4.0)-蒲公英云

9/21 越努力越幸运-思维赛(4.0)

F.CodeForces - 1118D1

题意：有n杯咖啡，需要写m页作业；他每天可以喝不限量杯咖啡（1或者多杯）；每杯咖啡可以让他写ai页作业；在同一天里，他所喝的咖啡能让他写w页；

w=（第一杯+第二杯-1+第三杯-2……）；求最少喝几天能写完作业（这题意好像描述的不是很多，凑合~语文不好）

解：排序+二分答案，下限1天，上限n天，check的话直接看码；

O（nlogn）

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAXN=1e5+10;
int a[MAXN];
int n,m;
bool check(int mid){
    int ans=0;
    int i=1;
    int cnt=0;
    int k=mid;
    while(i<=n){
        for(;i<=min(k,n);i++){
            ans+=max(a[i]-cnt,0);
        }
        if(ans>=m)return true;
        k=k+=mid;
        cnt++;
    }
    return false;
}
bool cmp(int x,int y){
    return x>y;
}
int main(){
    ios::sync_with_stdio(false);
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        cin>>a[i];
    }
    sort(a+1,a+1+n,cmp);
    int ans=-1;
    int l=1,r=n,mid;
    while(l<=r){
        mid=(l+r)>>1;
        if(check(mid)){
            r=mid-1;
            ans=mid;
        }
        else l=mid+1;
    }
    cout<<ans<<endl;
    return 0;
}

E.CodeForces - 1221C

题意：acm组队，有a个代码手，b个数论king，c个闲人；

求最多能组多少队，每队至少要有1个代码手和一个数论king；

解：模拟？；easy

#include <bits/stdc++.h>
using namespace std;
const int MAXN=1e5+10;
typedef long long ll;
int main(){
    ios::sync_with_stdio(false);
    int T;
    cin>>T;
    while(T--){
        ll a,b,c,minn;
        cin>>a>>b>>c;
        minn=min(a,min(b,c));
        if(minn!=c){
            cout<<minn<<endl;
        }
        else{
            a-=c;b-=c;
            cout<<minn+min(a,min(b,(a+b)/3))<<endl;
        }
    }
    return 0;
}

D.CodeForces - 1221B

题意：给一个n，输出一个图（只含有W，B），使得每个W或B能攻击B或W的个数最多；

每个只能攻击日字对角线上的；W攻击B，B攻击W；

解：交叉输出BW就行了；

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAXN=2e5+10;
int main(){
    ios::sync_with_stdio(false);
    int n;
    cin>>n;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            if(i%2==j%2)cout<<'B';
            else cout<<'W';
        }
        cout<<endl;
    }
    return 0;
}

C.CodeForces - 1118B

题意：n个数，求去掉一个数，使得剩下数组中奇数项和等于偶数项和的个数；

解：先求出不去掉的奇数项和和偶数项和；

然后遍历数组；i代表去掉第i个数然后

奇数项和=（i之前的奇数项和+i之后的偶数项和）

偶数项和=（i之前的偶数项和+i之后的奇数项和）

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAXN=2e5+10;
int a[MAXN];
int main(){
    ios::sync_with_stdio(false);
    int n;
    cin>>n;
    int sum1=0;
    int sum2=0;
    for(int i=1;i<=n;i++){
        cin>>a[i];
        if(i%2)sum1+=a[i];
        else sum2+=a[i];
    }
    //cout<<"sum1="<<sum1<<' '<<"sum2="<<sum2<<endl;
    int ans=0;
    int newsum1=0;
    int newsum2=0;
    for(int i=1;i<=n;i++){
        if(i%2){
            sum1-=a[i];
            if(sum1+newsum2==sum2+newsum1)ans++;
            newsum1+=a[i];
        }
        else {
            sum2-=a[i];
            if(sum1+newsum2==sum2+newsum1)ans++;
            newsum2+=a[i];
        }
    }
    cout<<ans<<endl;
    return 0;
}

B.CodeForces - 1221A

题意：给你n个数，每两个一样的数可以合并成这个数的两倍，问能否合成2048；

2048游戏~；

解：桶排序；把小于等于2048的数进行桶排序，大于2048就不可能合成了；

然后从1开始遍历到2048（1024即可），num[i]>=2?num[i*2]+=num[i]/2:continue;

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAXN=1e3+10;
int a[MAXN];
int num[3000];
int main(){
    ios::sync_with_stdio(false);
    int T,n;
    cin>>T;
    while(T--){
        cin>>n;
        memset(num,0,sizeof(num));
        for(int i=1;i<=n;i++){
            cin>>a[i];
            if(a[i]<=2048){
                num[a[i]]++;
            }
        }
        for(int i=1;i<=2048;i++){
            if(num[i]>=2){
                num[i*2]+=num[i]/2;
            }
        }
        if(num[2048])cout<<"Yes"<<endl;
        else cout<<"No"<<endl;
    }
    return 0;
}

A.CodeForces - 1118A

题意：两种水瓶，1L a元，2L b元，问需要n L水最少需要花费多少；

解：直接比较1L和2L 的性价比，然后照着买；

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll n,a,b;
int main(){
    ios::sync_with_stdio(false);
    int T;
    cin>>T;
    while(T--){
        cin>>n>>a>>b;
        if(a*2<=b){
            cout<<n*a<<endl;
        }
        else{
            ll ans=0;
            ans+=n/2*b;
            if(n%2){
                ans+=a;
            }
            cout<<ans<<endl;
        }
    }
    return 0;
}