Die Ergebnisse dieser Zeit

Eindrücke dieser Zeit

Ich habe die vergangenen Fragen bereits in Echtzeit gelöst, aber ich habe alle Probleme vergessen und sie mit einem Bacha gelöst. Ich konnte das E-Problem nicht lösen, als ich es in Echtzeit löste, aber diesmal konnte ich das E-Problem auch nicht lösen ... Ich habe keine andere Wahl, als es oft zu überprüfen ...

Problem A

Ruft den ASCII-Code (ord) ab und gibt das nächste Element aus.

`A.py`


print(chr(ord(input())+1))

B-Problem

Betrachten Sie die Punkte von 0 bis k, die erforderlich sind, um die Summe und den Durchschnitt bis zu diesem Punkt auf m Punkte oder mehr zu bringen.

`B.py`


n,k,m=map(int,input().split())
a=sum(list(map(int,input().split())))
if n*m-a>k:
    print(-1)
else:
    print(max(n*m-a,0))

C-Problem

** Zähle die Anzahl der Strafen bis zum Wechselstrom. Betrachten Sie jeden Fall abhängig davon, ob es sich um Wechselstrom handelt oder nicht.

`C.py`


n,m=map(int,input().split())
ps=[list(input().split()) for i in range(m)]
pen=[0]*n#Anzahl der Pena
rig=[0]*n#ACorWA

for i in range(m):
    if ps[i][1]=="AC":
        rig[int(ps[i][0])-1]=1
    else:
        if rig[int(ps[i][0])-1]==0:
            pen[int(ps[i][0])-1]+=1
cnt1,cnt2=0,0
for i in range(n):
    if rig[i]==1:
        cnt1+=rig[i]
        cnt2+=pen[i]

print(str(cnt1)+" "+str(cnt2))

D Problem

Rastersuche Ich verliere mich jedes Mal, wenn ich Code schreibe. Warum? (Es scheint keinen anderen Grund zu geben, als unbekannt zu sein). Das erste ist das in Echtzeit geschriebene BFS, und das zweite ist das im Bachacon geschriebene WF. Im Fall von BFS ist die Reihenfolge einer Suche O ($ HW ), und die Auswahl des Startknotens ist O ( HW ), sodass O ( H ^ 2W ^ 2 ) ausreicht. (Da es sich um ein einfaches BFS handelt, werde ich nur erklären, wie es gemacht wird, indem ich einen Kommentar in den Code schreibe. BFS ist das grundlegendste, wenn Sie die kürzeste Strecke zurücklegen.) Im Fall von WF (es wird nicht in Python übergeben, es wird in PyPy übergeben) behandelt es alle Gitter als Knoten und führt einfach die WF-Methode aus und findet schließlich den Wert des größten Elements (außer inf) ( O ( H ^ 3W ^ 3 $)). Das Gitter von i und j ist i * w + j im Array zum Aufzeichnen von WF (ich persönlich mag BFS, weil die Beurteilungsbedingungen kompliziert sind).

`answerD_BFS.py`


import queue
h,w=map(int,input().split())
s=[list(input()) for i in range(h)]

inf=100000000
ma=[]
for i in range(h):
    for j in range(w):
        if s[i][j]==".":
            x=[[inf for i_sub in range(w)] for j_sub in range(h)]
            #Das Gitter, das Sie betrachten
            q=queue.Queue()
            d=0
            #Erstes Gitter
            q.put([i,j])
            x[i][j]=0
            #Folgen Sie dem Gitter nacheinander, und wenn Sie allen Gittern folgen, sind Sie fertig
            while q.qsize()!=0:
                #Abstand hinzufügen
                d+=1
                l=q.qsize()
                #Zählen Sie die Anzahl der Gitter, die Sie haben
                for t in range(l):
                    I,J=q.get()
                    #Vom aktuellen Raster zum nächsten Raster
                    #Das Urteil ist"Gibt es dort ein Gitter?","Kannst du dem folgen?","Bist du schon gefolgt?"Dort sind drei.
                    if I-1>=0 and s[I-1][J]=="." and x[I-1][J]==inf:
                        q.put([I-1,J])
                        #Wenn diese Aktualisierung nicht in der if-Anweisung durchgeführt wird, wird das Raster genauer untersucht.
                        x[I-1][J]=d
                    if I+1<=h-1 and s[I+1][J]=="." and x[I+1][J]==inf:
                        q.put([I+1,J])
                        x[I+1][J]=d
                    if J-1>=0 and s[I][J-1]=="." and x[I][J-1]==inf:
                        q.put([I,J-1])
                        x[I][J-1]=d
                    if J+1<=w-1 and s[I][J+1]=="." and x[I][J+1]==inf:
                        q.put([I,J+1])
                        x[I][J+1]=d
            ma_sub=0
            for k in range(h):
                for l in range(w):
                    if x[k][l]!=inf:
                        ma_sub=max(ma_sub,x[k][l])
            ma.append(ma_sub)

print(max(ma))

`answerD_WF.py`


h,w=map(int,input().split())
s=[list(input()) for i in range(h)]
inf=1000000000
wf=[[inf]*(h*w) for i in range(h*w)]
for i in range(h*w):
    k,l=i//w,i%w
    #print(l)
    if s[k][l]=="#":
        continue
    if k!=0:
        if s[k-1][l]==".":
            wf[i][i-w]=1
    if k!=h-1:
        if s[k+1][l]==".":
            wf[i][i+w]=1
    if l!=0:
        if s[k][l-1]==".":
            wf[i][i-1]=1
    if l!=w-1:
        if s[k][l+1]==".":
            wf[i][i+1]=1
    wf[i][i]=0
for i in range(h*w):
    for j in range(h*w):
        for k in range(h*w):
            wf[j][k]=min(wf[j][k],wf[j][i]+wf[i][k])
ans=0
for i in range(h*w):
    for j in range(h*w):
        if wf[i][j]!=inf:
            ans=max(ans,wf[i][j])
print(ans)

E Problem

Ich habe mich gefragt, warum O ($ N ^ 2 $) passieren würde, selbst wenn N = $ 10 ^ 5 $. Es wurde TLE ohne zu vergehen.

Bei der Lösungsmethode, die zu O ($ N ^ 2 $) wird, werden max und min bestimmt und nur die erforderliche Anzahl von Elementen (k-2) zwischen ihnen ausgewählt, so dass ** max und min gleichzeitig eingestellt werden. Wenn Sie sich nicht entscheiden, werden Sie feststellen, dass Sie es mit O (N) ** lösen können. Mit anderen Worten, es kann leicht gelöst werden, indem die Summe von max und die Summe von min ermittelt und schließlich die Differenz zwischen den Summen ** berücksichtigt wird.

In Bezug auf die Lösung der richtigen Antwort sind das TLE-Muster und die Berechnung selbst nahezu identisch. Bereiten Sie zunächst Array A als Array vor, das Eingaben empfängt, und sortieren Sie es in aufsteigender Reihenfolge. Wenn Sie dann max finden, berücksichtigen Sie, wie viele Fälle jedes Element $ A_i $ zu max wird. In diesem Fall wählen Sie $ A_i $ und dann k-1 aus dem kleineren $ A_1 $ ~ $ A_ {i-1} $, also `COM (i, k-1) ) * a [i] . Fügen Sie dies zunächst zu ans hinzu (vergessen Sie nicht, es zum Rest des MOD zu machen). Wenn Sie min finden, wählen Sie als nächstes k-1 aus $ A_ {i + 1} $ ~ $ A_ {n-1} $ `` COM (ni-1, k-1). Sie können den Code als * a [i] `schreiben, also gehen wir zu ans. Wenn ans jedoch ist, müssen Sie mit dem MOD zu vorsichtig sein, um eine negative Division zu berücksichtigen, und dies mit `ans = MOD-abs (ans)% MOD``` vermeiden.

`answerE_TLE.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 INF 1000000000000
#define MOD 1000000007
#define PB push_back
#define MP make_pair
#define F first
#define S second
const ll MAX=200000;

ll fac[MAX], finv[MAX], inv[MAX];

//Vorbehandlung, um einen Tisch zu machen
void COMinit() {
    fac[0] = fac[1] = 1;
    finv[0] = finv[1] = 1;
    inv[1] = 1;
    for (ll i = 2; i < MAX; i++){
        fac[i] = fac[i - 1] * i % MOD;
        inv[i] = MOD - inv[MOD%i] * (MOD / i) % MOD;
        finv[i] = finv[i - 1] * inv[i] % MOD;
    }
}

//Berechnung des Binärkoeffizienten
ll COM(ll n,ll k){
    if (n < k) return 0;
    if (n < 0 || k < 0) return 0;
    return fac[n] * (finv[k] * finv[n - k] % MOD) % MOD;
}

signed main(){
    COMinit();
    ll n,k;cin >> n >> k;
    vector<ll> a(n);REP(i,n) cin >> a[i];
    sort(ALL(a));
    ll ans=0;
    if(k==1){
        cout << 0 << endl;
        return 0;
    }
    REP(i,n){
        FOR(j,i+1,n-1){
            ans+=((COM(j-i-1,k-2)*((a[j]-a[i])%MOD))%MOD);
            ans%=MOD;
        }
    }
    cout << ans << endl;
}

`answerE.cc`


//Referenz: http://ehafib.hatenablog.com/entry/2015/12/23/164517
//Einschließen
#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 INF 1000000000000
#define MOD 1000000007
#define PB push_back
#define MP make_pair
#define F first
#define S second
const ll MAX=200000;

ll fac[MAX], finv[MAX], inv[MAX];

//Vorbehandlung, um einen Tisch zu machen
void COMinit() {
    fac[0] = fac[1] = 1;
    finv[0] = finv[1] = 1;
    inv[1] = 1;
    for (ll i = 2; i < MAX; i++){
        fac[i] = fac[i - 1] * i % MOD;
        inv[i] = MOD - inv[MOD%i] * (MOD / i) % MOD;
        finv[i] = finv[i - 1] * inv[i] % MOD;
    }
}

//Berechnung des Binärkoeffizienten
ll COM(ll n,ll k){
    if (n < k) return 0;
    if (n < 0 || k < 0) return 0;
    return fac[n] * (finv[k] * finv[n - k] % MOD) % MOD;
}

signed main(){
    COMinit();
    ll n,k;cin >> n >> k;
    vector<ll> a(n);REP(i,n) cin >> a[i];
    sort(ALL(a));
    ll ans=0;
    if(k==1){cout << 0 << endl;return 0;}
    //Denken Sie zuerst an MAX
    REP(i,n){
        ans+=(COM(i,k-1)*a[i]);
        ans%=MOD;
    }
    REP(i,n){
        ans-=(COM(n-i-1,k-1)*a[i]);
        if(ans<0){
            ans=MOD-abs(ans)%MOD;
        }else{
            ans%=MOD;
        }
    }
    cout << ans << endl;
}

F Problem

Ich habe es noch nicht gelöst, tut mir leid. Löse, wenn du Zeit hast! Die Geometrie hat noch nicht viel von dem Problem gelöst, und ich bin nicht sehr gut darin ...

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

Die Ergebnisse dieser Zeit

Eindrücke dieser Zeit

Problem A

A.py

B-Problem

B.py

C-Problem

C.py