[PYTHON] concours yukicoder 266 avis

résultat

Impressions

J'étais impatient parce que je ne pouvais pas résoudre D, mais si j'y pense, je peux le résoudre simplement en transformant la formule. Aussi, même si j'ai eu l'idée du problème E, je n'ai pas pu analyser la quantité de calcul. ** Gardez à l'esprit que l'analyse utilisant des séries harmoniques est importante **.

Récemment, l'examen a été négligé et diverses choses ont été retardées, je voudrais donc ajuster le rythme de l'examen.

Problème A

Essayez jusqu'à $ [\ frac {n} {5}] $ fois, conversion jusqu'à $ [\ frac {n} {2}] $, objectif de pénalité jusqu'à $ [\ frac {n} {3} ] $ Fois. De plus, puisque $ N $ est égal ou inférieur à 100, vous pouvez tout rechercher. Cependant, gardez à l'esprit que c'est le nombre de conversions $ \ leqq $ le nombre d'essais.

A.py

n=int(input())
ans=0
for i in range(n//5+1):
    for j in range(n//2+1):
        for k in range(n//3+1):
            ans+=(i*5+j*2+k*3==n and i>=j)
print(ans)

Problème B

Premièrement, les probabilités du coffre au trésor n'ont rien à voir avec la réponse, alors disons $ p \ leqq q \ leqq r $.

À ce moment, marquez un coffre au trésor et ** RESTER ou CHANGER **. Lorsque vous sélectionnez SEJOUR, ** RESTEZ au coffre au trésor avec la probabilité la plus élevée est le maximum **, donc la probabilité d'obtenir un diamant est égale à la probabilité d'avoir un diamant dans le coffre au trésor sélectionné $ r / (p + q + r) C'est $. Si vous sélectionnez CHANGER, ** la probabilité maximale est de changer du coffre au trésor avec la probabilité la plus faible **, donc la probabilité d'obtenir un diamant est égale à la probabilité qu'il y ait un diamant dans le coffre au trésor non sélectionné $ (q + r) / ( p + q + r) $.

Par conséquent, la réponse est $ max (r / (p + q + r), (q + r) / (p + q + r)) = (q + r) / (p + q + r) $.

B.py

p,q,r=sorted(list(map(int,input().split())))
print((q+r)/(p+q+r))

Problème C

Tout d'abord, il est important d'être un multiple de 10, alors prenez $ mod \ 10 $ pour chaque carte. De plus, en choisissant une carte, la valeur de $ mod \ 10 $ changera, et ** considérez le DP que vous pouvez avoir avec le nombre maximum de cartes que vous pouvez choisir. À ce stade, réglez DP comme suit.

$ dp [i]: = $ (nombre maximum de feuilles lorsque le reste est $ i $)

De plus, la transition sera la suivante lors de la sélection de la carte $ A \ _j $.

dp[(i+A\_j)\%10]+=dp[i]

De plus, ** la transition n'est pas à sens unique **, vous devez donc mettre à jour ** $ dp $ collectivement ** lorsque vous sélectionnez la carte $ A \ _j $. Par conséquent, chaque carte $ A \ _j $ mise à jour doit être sauvegardée dans $ dp \ _sub $ et enregistrée dans $ dp $ après que la carte $ A \ _j $ a été sélectionnée.

C.py

ans=0
n=int(input())
check=[0 for i in range(10)]
a=list(map(int,input().split()))
for i in a:
    check[i%10]+=1
dp=[0 for i in range(10)]
for i in range(10):
    for j in range(check[i]):
        dp_sub=[0]*10
        for k in range(10):
            if k==0:
                dp_sub[(i+k)%10]=dp[k]+1
            elif dp[k]!=0:
                dp_sub[(i+k)%10]=dp[k]+1
        for k in range(10):
            dp[k]=max(dp[k],dp_sub[k])
        #print(dp_sub)
#print(dp)
print(dp[0])

Problème D

J'y ai pensé pendant un moment pendant et après le concours, mais je n'ai pas compris. Cela aurait pu être résolu si j'avais eu une tête.

Il est difficile de penser à des règles évidentes et à des solutions typiques, mais comme il s'agit d'un ** problème de relation entre les nombres premiers et les puissances **, nous le considérerons en utilisant le ** petit théorème de Fermat **. Le théorème de Fermat est le suivant.

Lorsque p est un nombre premier et a est un entier premier avec p, a^{p-1} = 1\ (mod \ p) \\
Pour le montrer, à partir du théorème binomial a^{p} = a\ (mod \ p)Montre juste.

Premièrement, si vous substituez la valeur dans le théorème de Fermat telle quelle, $ 2 ^ {p \ _ i-1} = 1 \ (mod \ p \ _ i) $… ① est valable, alors considérez ** transformer cette formule ** Je vais. De plus, ** 2 et $ p \ _i $ doivent être premiers l'un par rapport à l'autre **, mais ce n'est que lorsque $ p \ _i = 2 $, soit $ x = 2 $. Ici, en prenant la puissance des deux côtés ** de ** ①, la valeur du côté droit ne change pas, mais la valeur du côté gauche change. En d'autres termes, si vous prenez les puissances $ t $ des deux côtés de ①, $ 2 ^ {t (p \ _ i-1)} = 1 \ \ (mod \ p \ _i) $ tient. Aussi, ce que vous voulez trouver, c'est quand $ 2 ^ {t (p \ _ i-1)} = t (p \ _ i-1) \ \ (mod \ p \ _i) $. Par conséquent, si ** deux côtés sont combinés **, $ t (p \ _ i-1) = 1 \ \ (mod \ p \ _ i) $ est établi. En transformant ceci, si $ t = p \ _i-1 $ est défini à partir de $ p \ _i-t = 1 \ \ (mod \ p \ _i) $, cela est satisfait, et $ x = (p \ _ i-1) ) ^ 2 $ est inférieur à 10 $ ^ {18} $, donc il répond certainement aux critères en question.

D'après ce qui précède, le sujet est satisfait par $ x = 2 $ lorsque $ p \ _i = 2 $ et $ x = (p \ _ i-1) ^ 2 $ lorsque $ p \ neq 2 $.

D.py

for i in range(int(input())):
    n=int(input())
    print(2 if n==2 else (n-1)**2)

E problème

J'ai beaucoup appris car ** l'analyse computationnelle par séries harmoniques ** a été le premier type de problème à résoudre un problème important. Cet article peut être utilisé comme référence pour la série harmonisée.

Tout d'abord, trouvez la somme des valeurs de $ A \ _i % A \ _j $ pour tout $ i, j $. Dans un tel ** problème global, il est bon de faire attention à chaque valeur **, mais c'est difficile si cela reste trop, alors considérez ** paraphraser **. En d'autres termes, $ A \ _i % A \ _j = A \ _i - [\ frac {A \ _i} {A \ _ j}] \ fois A \ _j $. À ce stade, $ A \ i $ est $ n \ sum {i = 1} ^ {n} A \ _i $, donc il peut être calculé par $ O (N) $, mais $ [\ frac {A \ _i} {A \ _ j}] \ times A \ _ j $ n'est pas facile à trouver.

Ici, si vous corrigez $ A \ _j $, il peut y avoir $ i $ qui correspond à ** $ [\ frac {A \ _i} {A \ _j}] \ times A \ _j $ ** Parce qu'il y en a, $ A \ _j $ est fixe (car si $ \ parce que $ correspond, ** peut être calculé collectivement ** dans la plupart des cas). De plus, lorsque les valeurs correspondent et $ [\ frac {A \ _i} {A \ _j}] = k $, $ A \ _j \ times k \ leqq A \ i <A \ j \ times (k + 1) Puisque ce sera $, nous le compterons avec l'image de la ** distribution de fréquence **. À ce stade, si les colonnes numériques $ A $ sont disposées par ordre croissant, il est possible ** d'utiliser la dichotomie pour savoir combien de nombres correspondent à un certain $ k $ **. Aussi. Pour améliorer l'efficacité du calcul, la somme fixée à un certain $ A \ j $ est sauvegardée dans le dictionnaire, et si le même nombre apparaît, le nombre sauvegardé dans le dictionnaire est utilisé. De plus, chaque $ A \ j $ a un maximum de $ [\ frac {A \ _ {max}} {A \ _ j}] $, et chaque recherche coûte $ O (\ log {n}) $. , Le montant total du calcul est de $ O (\ sum \ _ {j = 1} ^ {n} [\ frac {A \ _ {max}} {A \ _ j}] \ log {n}) = O (A { max} \ log {n} \ sum \ _ {j = 1} ^ {n} [\ frac {1} {A \ _ j}]) $. Aussi, ici de ** Concept de série harmonique ** (✳︎), $ O (\ sum \ _ {j = 1} ^ {n} [\ frac {1} {A \ _ j}]) = O (\ log Depuis {A {max}}) $, le montant total du calcul est $ O (A {max} \ log {n} \ log {A {max}}) $.

(✳︎)… ** Je veux faire en sorte que lorsque je vois la forme somme des fractions, je puisse la réduire à une série d'harmonie **!

E.py

n=int(input())
a=list(map(int,input().split()))
a.sort()
from bisect import bisect_left,bisect_right
ans=0
d=dict()
for i in range(n):
    if a[i] in d:
        ans+=d[a[i]]
        continue
    ans_sub=0
    j=i
    while j!=n:
        x=a[j]//a[i]
        b=bisect_left(a,(x+1)*a[i],lo=j)-1
        ans_sub+=(x*(b-j+1)*a[i])
        j=b+1
    d[a[i]]=ans_sub
    ans+=ans_sub
print(sum(a)*n-ans)

Problème F

J'ai copié le code dans cet article. Si c'est un problème simple, vous pouvez utiliser une autre bibliothèque, mais c'est un problème difficile et vous ne pouvez pas faire de même, donc j'aimerais ** créer une bibliothèque d'arbre de segments dès que possible **.

F.cc

//Options de débogage:-fsanitize=undefined,address

//Optimisation du compilateur
#pragma GCC optimize("Ofast")

//Inclure etc.
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;

//macro
//pour boucle
//L'argument est(Variables dans la boucle,Amplitude de mouvement)Ou(Variables dans la boucle,Premier numéro,Nombre d'extrémités)、のどちらOu
//Les variables de boucle sans D sont incrémentées de 1 et les variables de boucle avec D sont décrémentées de 1.
//FORA est une gamme de déclaration(Si c'est difficile à utiliser, effacez-le)
#define REP(i,n) for(ll i=0;i<ll(n);i++)
#define REPD(i,n) for(ll i=n-1;i>=0;i--)
#define FOR(i,a,b) for(ll i=a;i<=ll(b);i++)
#define FORD(i,a,b) for(ll i=a;i>=ll(b);i--)
#define FORA(i,I) for(const auto& i:I)
//x est un conteneur tel que vector
#define ALL(x) x.begin(),x.end() 
#define SIZE(x) ll(x.size()) 
//constant
#define MOD 1000000007 //10^9+7:Droit commun
#define MAXR 100000 //10^5:Portée maximale de la baie
//Abréviation
#define PB push_back //Insérer
#define MP make_pair //constructeur de paires
#define F first //Le premier élément de paire
#define S second //Le deuxième élément de paire

/* RMQ：[0,n-1]Structure qui gère la valeur minimale pour chaque section
    set(i,x), build():Définissez le i-ème élément sur x. Construisez ensemble un arbre seg. O(n)
    add(a,b,x):section[a,b)Ajoutez x à l'élément de. O(log(n))
    query(a,b):section[a,b)Obtenez le plus petit élément. O(log(n))
    find_rightest(a,b,x): [a,b)Trouvez la position la plus à droite avec des éléments inférieurs ou égaux à x. O(log(n))
    find_leftest(a,b,x): [a,b)Trouvez la position la plus à gauche avec des éléments inférieurs ou égaux à x. O(log(n))
*/
template <typename T>
struct RMQ {
    const T INF = numeric_limits<T>::max();
    int n;
    vector<T> dat, lazy;
    RMQ(int n_) : n(), dat(n_ * 4, INF), lazy(n_ * 4, 0) {
        int x = 1;
        while (n_ > x) x *= 2;
        n = x;
    }

    void set(int i, T x) { dat[i + n - 1] = x; }
    void build() {
        for (int k = n - 2; k >= 0; k--) dat[k] = min(dat[2 * k + 1], dat[2 * k + 2]);
    }

    /* lazy eval */
    void eval(int k) {
        if (lazy[k] == 0) return;  //Quitter s'il n'y a rien à mettre à jour
        if (k < n - 1) {           //Si ce n'est pas une feuille, elle se propage à l'enfant
            lazy[k * 2 + 1] += lazy[k];
            lazy[k * 2 + 2] += lazy[k];
        }
        //Mettez-vous à jour
        dat[k] += lazy[k];
        lazy[k] = 0;
    }

    void add(int a, int b, T x, int k, int l, int r) {
        eval(k);
        if (a <= l && r <= b) {  //Quand complètement à l'intérieur
            lazy[k] += x;
            eval(k);
        } else if (a < r && l < b) {                  //Lorsque certaines sections sont couvertes
            add(a, b, x, k * 2 + 1, l, (l + r) / 2);  //Enfant de gauche
            add(a, b, x, k * 2 + 2, (l + r) / 2, r);  //Bon enfant
            dat[k] = min(dat[k * 2 + 1], dat[k * 2 + 2]);
        }
    }
    void add(int a, int b, T x) { add(a, b, x, 0, 0, n); }

    T query_sub(int a, int b, int k, int l, int r) {
        eval(k);
        if (r <= a || b <= l) {  //Quand complètement dehors
            return INF;
        } else if (a <= l && r <= b) {  //Quand complètement à l'intérieur
            return dat[k];
        } else {  //Lorsque certaines sections sont couvertes
            T vl = query_sub(a, b, k * 2 + 1, l, (l + r) / 2);
            T vr = query_sub(a, b, k * 2 + 2, (l + r) / 2, r);
            return min(vl, vr);
        }
    }
    T query(int a, int b) { return query_sub(a, b, 0, 0, n); }

    T find_rightest(int a, int b, int x) { return find_rightest_sub(a, b, x, 0, 0, n); }  //S'il n'existe pas un-1
    T find_leftest(int a, int b, int x) { return find_leftest_sub(a, b, x, 0, 0, n); }    //S'il n'existe pas b
    T find_rightest_sub(int a, int b, int x, int k, int l, int r) {
        eval(k);
        if (dat[k] > x || r <= a || b <= l) {  //Votre valeur est supérieure à x ou[a,b)Mais[l,r)S'il est hors de la plage de, renvoyez un-1
            return a - 1;
        } else if (k >= n - 1) {  //Si vous êtes une feuille, retournez cette position
            return (k - (n - 1));
        } else {
            int vr = find_rightest_sub(a, b, x, 2 * k + 2, (l + r) / 2, r);
            if (vr != a - 1) {  //Regardez le sous-arbre sur la droite un-Si différent de 1, retournez
                return vr;
            } else {  //Regardez le sous-arbre sur la gauche et renvoyez la valeur
                return find_rightest_sub(a, b, x, 2 * k + 1, l, (l + r) / 2);
            }
        }
    }
    T find_leftest_sub(int a, int b, int x, int k, int l, int r) {
        eval(k);
        if (dat[k] > x || r <= a || b <= l) {  //Votre valeur est supérieure à x ou[a,b)Mais[l,r)S'il est hors de portée de, retournez b
            return b;
        } else if (k >= n - 1) {  //Si vous êtes une feuille, retournez cette position
            return (k - (n - 1));
        } else {
            int vl = find_leftest_sub(a, b, x, 2 * k + 1, l, (l + r) / 2);
            if (vl != b) {  //Regardez le sous-arbre sur la gauche et revenez s'il est autre que b
                return vl;
            } else {  //Regardez le sous-arbre à droite et renvoyez la valeur
                return find_leftest_sub(a, b, x, 2 * k + 2, (l + r) / 2, r);
            }
        }
    }

    /* debug */
    inline T operator[](inta){returnquery(a,a+1); }
    void print() {
        for (int i = 0; i < n; ++i) {
            cout << (*this)[i];
            if (i != n) cout << ",";
        }
        cout << endl;
    }
};

signed main(){
    //Code pour accélérer la saisie
    //ios::sync_with_stdio(false);
    //cin.tie(nullptr);
    ll n;cin>>n;
    RMQ<ll> x(n);
    REP(i,n){
        ll y;cin>>y;
        x.set(i,y);
    }
    x.build();
    ll q;cin>>q;
    REP(i,q){
        ll k,l,r,c;cin>>k>>l>>r>>c;
        if(k==1){
            x.add(l-1,r,c);
        }else{
            cout<<x.query(l-1,r)<<endl;
        }
    }
    //x.print();
}