Temps requis

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)

[PYTHON] AtCoder Beginner Contest 106 Revue des questions précédentes

Temps requis

Impressions

Problème A

answerA.py

Problème B

answerB.py

Problème C

answerC.py