AtCoder Beginner Contest 374 (A-E)

比赛链接

A - Takahashi san 2

#include<bits/stdc++.h>

using namespace std;

using i64=long long;

void Showball(){
     string s;
     cin>>s;
     int n=s.size();
     cout<<(s.substr(n-3)=="san"?"Yes\n":"No\n"); 
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int t=1;
    //cin>>t;

    while(t--){
      Showball();
    }

    return 0;
}

B - Unvarnished Report

#include<bits/stdc++.h>

using namespace std;

using i64=long long;

void Showball(){
     string s,t;
     cin>>s>>t;
     if(s==t) return cout<<"0",void();
     int n=min(s.size(),t.size());
     for(int i=0;i<n;i++){
        if(s[i]!=t[i]) return cout<<i+1,void();
     } 
     cout<<n+1;
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int t=1;
    //cin>>t;

    while(t--){
      Showball();
    }

    return 0;
}

C - Separated Lunch

\(2\le n \le 20\) ，二进制暴力枚举即可。

#include<bits/stdc++.h>

using namespace std;

using i64=long long;

void Showball(){
     int n;
     cin>>n;
     vector<int> a(n);
     int sum=0;
     for(int i=0;i<n;i++){
        cin>>a[i];
        sum+=a[i];
     }
     int ans=sum;
     for(int i=0;i<(1<<n);i++){
        int res=0;
        for(int j=0;j<n;j++){
            if(i>>j&1){
                res+=a[j];
            }
        }
        ans=min(ans,max(res,sum-res));
     }
     cout<<ans;
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int t=1;
    //cin>>t;

    while(t--){
      Showball();
    }

    return 0;
}

D - Laser Marking 几何

思路：

全排列枚举线段的顺序，二进制枚举左右端点即可。

#include<bits/stdc++.h>

using namespace std;

using i64=long long;

struct Point{
    int x,y;
};

double dis(Point a,Point b){
    return hypot(a.x-b.x,a.y-b.y);
}

void Showball(){
    int n,s,t;
    cin>>n>>s>>t;
    vector<array<Point,2>> a(n);
    for(int i=0;i<n;i++){
        cin>>a[i][0].x>>a[i][0].y>>a[i][1].x>>a[i][1].y;
    }
    vector<int> p(n);
    iota(p.begin(),p.end(),0);

    double ans=1e9;
    do{ 
        for(int i=0;i<(1<<n);i++){
            Point pre={0,0};
            double res=0.0;
            for(int j=0;j<n;j++){
                int u=i>>j&1;
                res+=dis(a[p[j]][0],a[p[j]][1])/(t*1.0);
                res+=dis(a[p[j]][u],pre)/(s*1.0);
                pre=a[p[j]][!u];
            }
            ans=min(ans,res);
        }
    }while(next_permutation(p.begin(),p.end()));

    cout<<fixed<<setprecision(9)<<ans<<"\n";
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int t=1;
    //cin>>t;

    while(t--){
      Showball();
    }

    return 0;
}

E - Sensor Optimization Dilemma 2 二分答案

思路：

考虑二分，发现 \(A_i\) 和 \(B_i\) 的最大值都为100， 有一个显然的性质，机器 \(S_i\) 不会买超过 \(B_i\) 个或者机器 \(T_i\) 不会买超过 \(A_i\) 个，因为如果超过了，那么他们产生的产品数量一定大于等于 \(A_i*B_i\)，那么就可以作为一个整体，然后用更便宜的替换它即可。因此，我们直接枚举选的少的机器数量，求出另一种机器数量进行 \(check\) 即可。

#include<bits/stdc++.h>

using namespace std;

using i64=long long;

void Showball(){
     int n,x;
     cin>>n>>x;
     vector<array<i64,4>> v(n);
     for(int i=0;i<n;i++){
        for(int j=0;j<4;j++){
            cin>>v[i][j];
        }
     }

     auto check=[&](i64 w){
        i64 sum=0;
        for(int i=0;i<n;i++){
            i64 minn=1e18;
            auto [a,p,b,q]=v[i];
            for(int j=0;j<b;j++){   
                minn=min(minn,j*p+max(0LL,w-j*a+b-1)/b*q);
            }
            for(int j=0;j<a;j++){
                minn=min(minn,j*q+max(0LL,w-j*b+a-1)/a*p);
            }
            sum+=minn;
        }
        return sum<=x;
     };
     int l=0,r=1e9;
     while(l<r){
        i64 mid=l+r+1>>1;
        if(check(mid)) l=mid;
        else r=mid-1;
     }
     cout<<l<<"\n";
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int t=1;
    //cin>>t;

    while(t--){
      Showball();
    }

    return 0;
}