AtCoder Beginner Contest 106 Revue des questions précédentes

Temps requis

スクリーンショット 2020-04-29 14.37.25.png

Impressions

Je l'ai fait dans un ordre supérieur à la solution principale dans le problème D et je suis devenu TLE en Python, alors je l'ai fait C ++ et je l'ai accéléré. Cette solution est également une idée importante, je voudrais donc l'apprendre.

Problème A

Tout ce que vous avez à faire est d'avancer la route jusqu'au bout.

answerA.py


a,b=map(int,input().split())
print((a-1)*(b-1))

Problème B

Puisqu'il y a 8 réductions, nous les compterons en utilisant la fonction de l'énumération des réductions dans cet article. Si vous n'en avez que combien, vous pouvez calculer sans préparer de tableau.

answerB.py


def make_divisors(n):
    divisors=[]
    for i in range(1,int(n**0.5)+1):
        if n%i==0:
            divisors.append(i)
            if i!=n//i:
                divisors.append(n//i)
    return divisors

ans=0
n=int(input())
for i in range(1,n+1):
    ans+=(len(make_divisors(i))==8 and i%2==1)
print(ans)

Problème C

Puisque le sujet est opéré sur la chaîne de caractères 5000 billions de fois, chaque nombre $ x (\ neq1) $ contenu dans la chaîne de caractères devient $ x ^ {5000000000000000} $ après 5000 billions de fois, donc ** $ Vous pouvez voir qu'il est clairement plus long que K $ **. Par conséquent, si le premier caractère est un caractère autre que 1, vous pouvez voir que le caractère $ K $ est $ x $. De même, en supposant que les 1 sont consécutifs du 1er caractère au caractère $ l $, s'il s'agit de $ l \ geqq K $, le Kème caractère sera 1. Inversement, si $ l <K $, le Kème caractère est le l + 1er numéro de caractère.

answerC.py


s=input()
k=int(input())
l=0
for i in s:
    if i=="1":
        l+=1
    else:
        break
print("1" if k<=l else s[l])

Problème D

Étant donné que la requête de question pose à plusieurs reprises des questions sur l'intervalle (jusqu'à 10 $ ^ 5 $ fois), vous pouvez voir que vous souhaitez accélérer le calcul de l'intervalle ici **. Par conséquent, nous examinerons comment calculer jusqu'à 10 $ ^ 3 $ pour chaque requête.

Ici, lorsque le nombre de trains passant par le tronçon [$ l, r $] est $ x_ {l, r} $, les trains passant par le tronçon de ville $ p_i $ à ville $ q_i $. Le nombre de est $ (x_ {p_i, p_i} + x_ {p_i, p_i + 1} +… + x_ {p_i, q_i}) + (x_ {p_i + 1, p_i + 1} +… + x_ {p_i + 1 , q_i}) +… + (x_ {q_i, q_i}) = \ Sigma_ {k = p_i} ^ {q_i} {(\ Sigma_ {l = k} ^ {q_i} {x_ {k, l}})} Puisque ce sera $ (✳︎), j'ai pensé que $ k $ (** extrémité gauche de la section **) devrait être corrigé.

Par conséquent, lorsque la section par laquelle passe chaque train est d'abord donnée sous la forme de [$ L_i, R_i $], préparez un train de tableau à deux dimensions dans lequel l'extrémité gauche de la section est divisée par quelle ville, et le $ L_i $ th Insérez la valeur la plus à droite $ R_i $ dans le tableau de. Ensuite, après avoir effectué toutes les insertions, triez chaque tableau. En vertu de cela, lorsque $ p_i $ et $ q_i $ sont donnés dans chaque question, ** $ p_i $ th tableau à $ q_i $ th tableau (jusqu'à N façons) **, respectivement ** Il suffit de compter le nombre d'éléments sous $ q_i $ ** (∵ (✳︎)). Vous pouvez compter le nombre d'éléments ** par dichotomie ($ O (\ log {M}) $) pour chaque tableau ** (trié). Par conséquent, le montant total du calcul est de $ O (log QN {M}) $. (Premier et deuxième code, AC pour C ++, TLE pour Python et PyPy)

Aussi, si le train de tableau bidimensionnel à préparer est ** train [$ i ] [ j ]: le nombre de trains dont la section est [ i, j ] **, alors [ L_i, R_i ] ], En ajoutant +1 pour former [ L_i ] [ R_i $] et en considérant la somme cumulée, la requête de question ne dichotomise pas le nombre d'éléments sous $ q_i $. Puisqu'il peut être calculé par ** $ O (1) $ **, le montant du calcul est O ($ QN + N ^ 2 $). (Troisième code, AC avec PyPy)

De plus, bisect_right est utilisé dans le code suivant pour la dichotomie. Voir cet article pour plus d'informations.

answerD_TLE.py


import bisect
n,m,q=map(int,input().split())
train=[[] for i in range(n)]
for i in range(m):
    l,r=map(int,input().split())
    train[l-1].append(r-1)
for i in range(n):
    train[i].sort()
for i in range(q):
    p,q=map(int,input().split())
    ans=0
    for i in range(p-1,q):
        ans+=bisect.bisect_right(train[i],q-1)
    print(ans)

answerD.cc


//Référence: http://ehafib.hatenablog.com/entry/2015/12/23/164517
//Comprendre(Ordre alphabétique,bits/stdc++.Une faction qui n'utilise pas h)
#include<algorithm>//sort,Recherche de bisection,Tel
#include<bitset>//Jeu de bits de longueur fixe
#include<cmath>//pow,journal etc.
#include<complex>//Nombre complexe
#include<deque>//File d'attente d'accès double
#include<functional>//trier plus
#include<iomanip>//setprecision(Erreur de sortie en virgule flottante)
#include<iostream>//Entrée sortie
#include<iterator>//Régler l'opération(Ensemble de produits,Ensemble de somme,Ensemble de différences, etc.)
#include<map>//map(dictionnaire)
#include<numeric>//iota(Génération d'une chaîne entière),pgcd et lcm(c++17)
#include<queue>//queue
#include<set>//ensemble
#include<stack>//empiler
#include<string>//Chaîne
#include<unordered_map>//Carte avec itérateur mais sans ordre
#include<unordered_set>//Il y a un itérateur mais l'ordre n'est pas maintenu défini
#include<utility>//pair
#include<vector>//Tableau de longueur variable

using namespace std;
typedef long long ll;

//macro
//pour la relation de 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.
#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--)
//x est un conteneur tel que vector
#define ALL(x) (x).begin(),(x).end() //Je souhaite omettre des arguments tels que le tri
#define SIZE(x) ((ll)(x).size()) //taille à la taille_Changement de t à ll
#define MAX(x) *max_element(ALL(x)) //Trouvez la valeur maximale
#define MIN(x) *min_element(ALL(x)) //Trouvez la valeur minimale
#define D()
//constant
#define INF 1000000000000 //10^12:Valeur extrêmement élevée,∞
#define MOD 10000007 //10^9+7:Droit commun
#define MAXR 100000 //10^5:Portée maximale de la baie(Utilisé pour l'énumération des nombres premiers, etc.)
//Abréviation
#define PB push_back //Insérer dans le vecteur
#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

//↑ A partir de là, le modèle

signed main(){
    ll n,m,q;cin >> n >> m >> q;
    vector<vector<ll>> train(n);
    REP(i,m){
        ll l,r;cin >> l >> r;
        train[l-1].PB(r-1);
    }
    REP(i,n){
        sort(ALL(train[i]));
    }
    REP(i,q){
        ll p,q_;cin >> p >> q_;
        ll ans=0;
        FOR(j,p-1,q_-1){
            ans+=ll(upper_bound(ALL(train[j]),q_-1)-train[j].begin());
        }
        cout << ans << endl;
    }
}

answerD.py


n,m,q=map(int,input().split())
train=[[0]*n for i in range(n)]
for i in range(m):
    l,r=map(int,input().split())
    train[l-1][r-1]+=1
for i in range(n):
    for j in range(n-1):
        train[i][j+1]+=train[i][j]
for i in range(q):
    p,q_=map(int,input().split())
    ans=0
    for j in range(p-1,q_):
        ans+=train[j][q_-1]
    print(ans)

Recommended Posts

AtCoder Beginner Contest 102 Revue des questions précédentes
AtCoder Beginner Contest 085 Revue des questions précédentes
AtCoder Beginner Contest 062 Revue des questions précédentes
AtCoder Beginner Contest 113 Revue des questions précédentes
AtCoder Beginner Contest 074 Revue des questions précédentes
AtCoder Beginner Contest 051 Revue des questions précédentes
AtCoder Beginner Contest 119 Revue des questions précédentes
AtCoder Beginner Contest 151 Revue des questions précédentes
AtCoder Beginner Contest 075 Revue des questions précédentes
AtCoder Beginner Contest 054 Revue des questions précédentes
AtCoder Beginner Contest 110 Revue des questions précédentes
AtCoder Beginner Contest 117 Revue des questions précédentes
AtCoder Beginner Contest 070 Revue des questions précédentes
AtCoder Beginner Contest 105 Revue des questions précédentes
AtCoder Beginner Contest 112 Revue des questions précédentes
AtCoder Beginner Contest 076 Revue des questions précédentes
AtCoder Beginner Contest 089 Revue des questions précédentes
AtCoder Beginner Contest 069 Revue des questions précédentes
AtCoder Beginner Contest 079 Revue des questions précédentes
AtCoder Beginner Contest 056 Revue des questions précédentes
AtCoder Beginner Contest 087 Revue des questions précédentes
AtCoder Beginner Contest 093 Revue des questions précédentes
AtCoder Beginner Contest 046 Revue des questions précédentes
AtCoder Beginner Contest 123 Revue des questions précédentes
AtCoder Beginner Contest 049 Revue des questions précédentes
AtCoder Beginner Contest 078 Revue des questions précédentes
AtCoder Beginner Contest 047 Revue des questions précédentes
AtCoder Beginner Contest 104 Revue des questions précédentes
AtCoder Beginner Contest 057 Revue des questions précédentes
AtCoder Beginner Contest 121 Revue des questions précédentes
AtCoder Beginner Contest 090 Revue des questions précédentes
AtCoder Beginner Contest 103 Revue des questions précédentes
AtCoder Beginner Contest 061 Revue des questions précédentes
AtCoder Beginner Contest 083 Revue des questions précédentes
AtCoder Beginner Contest 124 Revue des questions précédentes
AtCoder Beginner Contest 116 Revue des questions précédentes
AtCoder Beginner Contest 097 Revue des questions précédentes
AtCoder Beginner Contest 092 Revue des questions précédentes
AtCoder Beginner Contest 099 Revue des questions précédentes
AtCoder Beginner Contest 065 Revue des questions précédentes
AtCoder Beginner Contest 053 Revue des questions précédentes
AtCoder Beginner Contest 094 Revue des questions précédentes
AtCoder Beginner Contest 063 Revue des questions précédentes
AtCoder Beginner Contest 107 Revue des questions précédentes
AtCoder Beginner Contest 071 Revue des questions précédentes
AtCoder Beginner Contest 064 Revue des questions précédentes
AtCoder Beginner Contest 082 Revue des questions précédentes
AtCoder Beginner Contest 084 Revue des questions précédentes
AtCoder Beginner Contest 058 Revue des questions précédentes
AtCoder Beginner Contest 043 Revue des questions précédentes
AtCoder Beginner Contest 098 Revue des questions précédentes
AtCoder Beginner Contest 114 Revue des questions précédentes
AtCoder Beginner Contest 045 Revue des questions précédentes
AtCoder Beginner Contest 120 Revue des questions précédentes
AtCoder Beginner Contest 106 Revue des questions précédentes
AtCoder Beginner Contest 122 Revue des questions précédentes
AtCoder Beginner Contest 125 Revue des questions précédentes
AtCoder Beginner Contest 109 Revue des questions précédentes
AtCoder Beginner Contest 118 Revue des questions précédentes
AtCoder Beginner Contest 080 Revue des questions précédentes
AtCoder Beginner Contest 073 Revue des questions précédentes