cf

10.31

Divisibility by Eight（1500）

题目大意：
给你一个不包含前导0的整数，位数100位，问是否可以在通过删除一些位数，且不能改变原有位置的情况下整除8？

解题思路：
我们可以发现1000正好是8的倍数，所以我们只需要枚举是否存在1位数，2位数，3位数可以整除8即可，至于为什么不用枚举4位数及更高的位数呢？我们来分析一下，对于任意一个4位数及更高位数的整数 x 都可以表示为 x = 1000 * n + k 的形式，而1000是8的倍数，那么自然1000 * n 也是8的倍数，所以我们可以通过判断k是否能整除8进而来判断x是否能整除8，又因为k可能是1位数，2位数，3位数，所以正好可以应证前面的结论。

#include<bits/stdc++.h>
using namespace std;
string s;

int main(){
    cin>>s;
    for(int i=0;i<s.size();i++){
        if((s[i]-'0')%8==0){
            cout<<"YES"<<endl;
            cout<<s[i]<<endl;
            return 0;
        }
    }
    for(int i=0;i<s.size();i++){
        for(int j=i+1;j<s.size();j++){
            if(((s[i]-'0')*10+(s[j]-'0'))%8==0){
                cout<<"YES"<<endl;
                cout<<s[i]<<s[j]<<endl;
                return 0;
            }
        }
    }
    for(int i=0;i<s.size();i++){
        for(int j=i+1;j<s.size();j++){
            for(int k=j+1;k<s.size();k++){
                if(((s[i]-'0')*100+(s[j]-'0')*10+s[k]-'0')%8==0){
                    cout<<"YES"<<endl;
                    cout<<s[i]<<s[j]<<s[k]<<endl;
                    return 0;
                }
            }
        }
    }
    cout<<"NO"<<endl;
    return 0;
}

Gift Set（2100）

题意

有x个红糖,y个蓝糖。每一个礼包里面要么有a个红糖+ b个蓝糖，要么是a个蓝糖+ b个红糖。
问最多能打多少份礼包。
T ≤104组数据，1 ≤x, y,a, b ≤10°。

题解

不难发现答案具有包含性，能打n份就─定能打n —1份。
交换，令a >b，那么每打包一份礼包，x和y都至少会减少b。
直接二分答案s，那么在x, y ≥S · b的前提下，再把x和y都减去s · b后，相当于在x, y中只用找单独的s个ab就行了({x. y}变成了{x - sb, y - sb}， {a, b}变成了{a - b, 0}，其中一个为0了，两种糖果不再绑定)，这等价于此时a = b或者 x/(a-b) + y/(a-b) >= s

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int t;
ll x,y,a,b;

bool check(ll k){
    ll X=x,Y=y,A=a,B=b;
    if(X<k*B||Y<k*B) return false;
    X-=k*B,Y-=k*B;
    A=A-B;
    if(A==0) return true;
    return X/A+Y/A>=k;
}

void solve(){
    cin>>x>>y>>a>>b;
    if(x<y)swap(x,y);
    if(a<b)swap(a,b);
    ll l=0,r=1e9+10;
    for(int i=1;i<=200;i++){
        ll mid=(l+r)>>1;
        if(check(mid)) l=mid;
        else r=mid;
    }
    cout<<l<<endl;
}

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