Acwing match 56 Weekly

Table des matières

4482. Groupe

4483. Champ de bataille

4484. Décimales finies

---

4482. Groupe

4482. Groupe

Idées：

Nombre maximum de fois par nombre trouvé,Le nombre maximum de fois dans ces données est le nombre maximum de groupes

Les codes sont les suivants:：

#include <bits/stdc++.h>

#define fast ios::sync_with_stdio(false),cin.tie(0), cout.tie(0)

using namespace std;

typedef long long LL;
typedef pair<int, int> PII;

const int N = 2e5 + 10, mod = 1e9 + 7;

int n;
int st[N];

int main()
{
    //fast;
    //cin >> T;
    scanf("%d", &n);
    
    int x = 0, mx = 0;
    for(int i = 0; i < n; i ++ )
        scanf("%d", &x), st[x] ++, mx = max(mx, st[x]);
    
    printf("%d\n", mx);

    return 0;
}

4483. Champ de bataille

4483. Champ de bataille

Idées： Définit le tableau des éléments du tableau original et le tableau des quantités de cet élément , Trier les groupes d'éléments par ordre décroissant , Discrete dans le tableau original .

Clarifier quelques points ：

1） Il y a un nombre plus grand que le nombre de livres et il est conforme aux règles du sujet , Puis la quantité de ce numéro est effacée .

2） Quantité minimale à stocker , Supprimer tous les éléments qui peuvent être supprimés .C'est - à - dire:、 Supprimer tout nombre qui peut être supprimé pour chaque nombre , Après ce nombre K Nombre de plages, Peut être simplifié pour déterminer si deux numéros adjacents peuvent être supprimés .

Les codes sont les suivants:：

#include <bits/stdc++.h>

#define fast ios::sync_with_stdio(false),cin.tie(0), cout.tie(0)

using namespace std;

typedef long long LL;
typedef pair<int, int> PII;

const int N = 1e6 + 10, mod = 1e9 + 7;

int n, k;
int st[N];
int b[N];

int main()
{
    //fast;
    //cin >> T;
    scanf("%d %d", &n, &k);
    
    vector<int> a(n);
    
    int x = 0, res = 0;
    for(int i = 0; i < n; i ++ )
        scanf("%d", &a[i]), st[a[i]] ++;
    
    sort(a.begin(), a.end(), greater<int>());
    a.erase(unique(a.begin(), a.end()), a.end());
    
    res += st[a[0]];
    int t = a[0];
    for(int i = 1; i < a.size(); i ++ )
    {
        if(a[i-1] - a[i] <= k) st[a[i]] = 0;
    }
    
    int cnt = 0;
    for(int i = 0; i < a.size(); i ++ )
    {
        if(st[a[i]]) b[cnt++] = a[i];
    }
    
    for(int i = 1; i < cnt; i ++ )
    {
        if(t - b[i] > k)
        {
            t = b[i], res += st[b[i]];
        }
    }
    
    
    printf("%d\n", res);

    return 0;
}

4484. Décimales finies

4484. Décimales finies 

Idées： Jugement décimal fini , C'est - à - dire qu'il juge la partie décimale b Si la Sous - partie peut être ,C'est - à - dire le jugement p/q*b^nEst un entier,C'est - à - dire le jugementb^n/qEst un entier,Oui.qEtb Diviseur commun net ,Et jugerqOui Non1 , Pour1 Les délégués peuvent être divisés , Sinon, il ne peut pas être divisé.

Les codes sont les suivants:：

#include <bits/stdc++.h>

#define fast ios::sync_with_stdio(false),cin.tie(0), cout.tie(0)

using namespace std;

typedef long long LL;
typedef pair<int, int> PII;

const int N = 1e6 + 10, mod = 1e9 + 7;

int n;
LL p, q, b;

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

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