[PYTHON] AtCoder Beginner Contest 084 Rückblick auf frühere Fragen

Benötigte Zeit

Impressionen

FX ist heute besiegt und verwelkt. Der Markt erholt sich nicht und das Wochenende ist für Tokio geschlossen, was am schlimmsten ist. Diesmal ist es nicht schwierig, aber ich habe einen Fehler im Eratostenes-Sieb gemacht. Es ist schwer zu leben.

Problem A

Subtraktion, kein besonderer Eindruck.

answerA.py

print(48-int(input()))

B-Problem

Überprüfen Sie jeweils ein Zeichen. Ich habe eine Zeichenkette von 0 bis 9 erstellt und berechnet, ob sie darin enthalten ist, aber es scheint, dass sie in Ordnung ist, auch wenn sie "0" oder mehr und "9" oder weniger ist.

answerB.py

num=list("0123456789")
a,b=map(int,input().split())
s=input()

for i in range(a+b+1):
    if i!=a:
        if s[i] not in num:
            print("No")
            break
    else:
        if s[i]!="-":
            print("No")
            break
else:
    print("Yes")

C-Problem

Ich war zu schwach und habe viele Fehler gemacht. Notieren Sie in einer jetzt aufgerufenen Variablen, wann Sie an jeder Station ankommen. Berücksichtigen Sie dann für jede Station das kleinste Vielfache von f nach s und nach der Zeit, zu der Sie an dieser Station angekommen sind. Wenn Sie von dort aus mit c fortfahren, gelangen Sie zur nächsten Station. Kann mit gelöst werden. Ich konnte das nicht tun, weil ich zu viel über FX nachdachte. Wie verrückt!

answerC.py

import math
n=int(input())
csf=[list(map(int,input().split())) for i in range(n-1)]

for j in range(n-1):
    now=0
    for i in range(j,n-1):
        if csf[i][1]>=now:
            now=csf[i][1]+csf[i][0]
        else:
            now=csf[i][1]-((csf[i][1]-now)//csf[i][2])*csf[i][2]+csf[i][0]
    print(now)
print(0)

D Problem

Angesichts der Intervallabfrage ist es klar, den Unterschied in den kumulierten Summen zu berücksichtigen. Mit anderen Worten, Sie sollten zuerst nach "einer Zahl ähnlich 2017" fragen, bevor Sie die Abfrage ** Eratostenes 'Sieb ** berechnen (Anderer Artikel. Eingeführt in 0b49891986e8bb31e148)), zählen Sie die Primzahlen auf, aktivieren Sie "Zahlen ähnlich 2017" und berücksichtigen Sie die kumulative Summe. Das Eratostenes-Sieb war jedoch fehlerhaft und ich wollte "2017-ähnliche Zahlen" überprüfen, aber es dauerte lange, nur die Primzahlen zu überprüfen. Ich möchte solche ** nachlässigen Fehler ** beseitigen.

answerD.cc

#include<algorithm>//sort,Halbierungssuche,Eine solche
#include<bitset>//Bit mit fester Länge gesetzt
#include<cmath>//pow,Protokoll usw.
#include<complex>//Komplexe Zahl
#include<deque>//Double-Ended-Zugriffswarteschlange
#include<functional>//größer sortieren
#include<iomanip>//setprecision(Gleitkomma-Ausgabefehler)
#include<iostream>//Input-Output
#include<map>//map(Wörterbuch)
#include<numeric>//iota(Generierung einer Ganzzahlzeichenfolge),gcd und lcm(c++17)
#include<queue>//Warteschlange
#include<set>//einstellen
#include<stack>//Stapel
#include<string>//String
#include<unordered_map>//Karte mit Iterator, aber ohne Ordnung
#include<unordered_set>//Es gibt einen Iterator, aber die Reihenfolge wird nicht festgelegt
#include<utility>//pair
#include<vector>//Array mit variabler Länge

using namespace std;
typedef long long ll;

//Makro
#define REP(i,n) for(ll i=0;i<(ll)(n);i++)
#define REPD(i,n) for(ll i=(ll)(n)-1;i>=0;i--)
#define FOR(i,a,b) for(ll i=(a);i<=(b);i++)
#define FORD(i,a,b) for(ll i=(a);i>=(b);i--)
#define ALL(x) (x).begin(),(x).end() //Ich möchte Argumente wie sort weglassen
#define SIZE(x) ((ll)(x).size()) //Größe zu Größe_Wechseln Sie von t nach ll
#define MAX(x) *max_element(ALL(x))
#define INF 1000000000000
#define MOD 10000007
#define MA 100000
#define PB push_back
#define MP make_pair
#define F first
#define S second


ll sieve_check[MA+1];//i-th entspricht der ganzen Zahl i(1~100000)

//Implementieren Sie das Eratostenes-Sieb
void es(){
    FOR(i,2,MA)sieve_check[i]=1;
    //1 ist eine Primzahl, hier ist 0 keine Primzahl
    for(ll i=2;i<=1000;i++){
        if(sieve_check[i]==1){
            for(ll j=2;j<=ll(MA/i);j++){
                sieve_check[j*i]=0;
            }
        }
    }
}

signed main(){
    es();
    vector<ll> pre(MA+1);FOR(i,1,MA)pre[i]=(i%2==1&&sieve_check[i]&&sieve_check[(i+1)/2]);
    REP(i,MA)pre[i+1]+=pre[i];
    ll q;cin >> q;
    vector< pair<ll,ll> > ans(q);REP(i,q) cin >> ans[i].F >> ans[i].S;
    REP(i,q)cout << pre[ans[i].S]-pre[ans[i].F-1] << endl;
}