• 欢迎光临~

cf

开发技术 开发技术 2022-10-30 次浏览

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;
}

 

程序员灯塔
转载请注明原文链接:cf
喜欢 (0)