【Acwing】第56场周赛 题解

 所有数出现次数的最大值就是分组数的下界值（贪心思路）

#include 
#include 

using namespace std;

int num[200];

int main()
{
    int n;
    int a[10000];
    cin >> n;
    int m = 0;
    for(int i = 0; i < n; i ++ )
    {
        cin >> a[i];
        num[a[i]] ++ ;
        m = max(num[a[i]], m);
    }
    cout << m << endl;
    return 0;
}

先按找战斗力从小到大排序

一个战士是否能被淘汰，取决于他后面战士的战斗力和他战斗力的差值是否小于 k 

如果小于 k 的话，则能被淘汰。前面被淘汰的战士不会影响到后面被淘汰的战士。

而且战斗力最大的那个战士最后一定会保留下来。

#include 
#include 
#include 
using namespace std;

const int N = 1e6 + 10;

int cnt[N];
int q[N];
vector v;

int main()
{
    int n, k;
    cin >> n >> k;
    
    for(int i = 0; i < n; i ++ ) 
    {
        scanf("%d", &q[i]); cnt[q[i]] ++ ;
        if(cnt[q[i]] == 1) v.push_back(q[i]);
    }
    
    sort(v.begin(), v.end());
    
    int res = 0;
    res += cnt[v[v.size() - 1]];
    for(int i = 0; i < v.size() - 1; i ++ )
    {
        if(v[i + 1] - v[i] > k) res += cnt[v[i]];
    }
        
    
    cout << res << endl;
    
    return 0;
}

整数部分只需要考虑 p 和 q 能否构成一个整数即可，因为整数都能由 p 进制的数来表示出来

小数的进制转换：

以 123.375为例，整数部分是 111101，得到小数部分的流程如下1：

0.375 * 2 = 0.75

0.75 * 2 = 1.5  0.5

0.5 * 2 = 1  最终得到小数部分是 011，所以最后的表达式是 111101.011

所以，对于上述问题，每次  取整，依次把十分位，百分位，千分位等的数取出来，如果在 b 进制下是一个有限小数位，那么在经过有限次的操作后最终取整完为0

 等价于以下性质   （ 整除 ）

#include 
using namespace std;

typedef long long LL;

LL p, q, b;

LL gcd(LL a, LL b)
{
    return b ? gcd(b, a % b) : a;
}

int main()
{
    int T; cin >> T;
    while(T -- )
    {
        scanf("%lld%lld%lld", &p, &q, &b);
        LL d = gcd(p, q);
        q /= d;
        while(q > 1)
        {
            d = gcd(q, b);
            if(d == 1) break;
            while(q % d == 0) q /= d;
        }
        
        if(q == 1) puts("YES");
        else puts("NO");
    }
    return 0;
}