[PYTHON] AtCoder Beginner Contest 066 Überprüfen Sie frühere Fragen

Benötigte Zeit

Problem A

Wählen Sie einfach die beiden kleineren.

answerA.py

a,b,c=map(int,input().split())
x=[a,b,c]
print(sum(x)-max(x))

B-Problem

Löschen Sie einfach das Ende in der richtigen Reihenfolge und denken Sie darüber nach.

answerB.py

s=input()
l=len(s)
for i in range(1,l//2):
    k=(l-i*2)
    if s[:k//2]==s[k//2:k]:
        print(k)
        break

C-Problem

Wenn man bedenkt, wie ** tatsächlich drückt **, kann man sehen, dass die ungeraden und geraden Drücke unterschiedliche Anordnungen haben (siehe Beispiel). Wenn Sie die Anordnung also gehorsam implementieren, ist dies wie folgt. .. (Es ist auch zu beachten, dass es Fälle aufgrund der Gleichmäßigkeit von n gibt.)

answerC.py

n=int(input())
a=[i for i in input().split()]

b=[]
c=[]
if n%2==0:
    for i in range(n):
        if i%2==0:
            b.append(a[i])
        else:
            c.append(a[i])
else:
    for i in range(n):
        if i%2==0:
            c.append(a[i])
        else:
            b.append(a[i])
c=c[::-1]
print(" ".join(c)+" "+" ".join(b))

D Problem

Die Richtlinie wurde normal eingerichtet, die Implementierung konnte jedoch nicht abgeschlossen werden. (** Montagefähigkeit ** ist auch eines der Probleme, aber es scheint, dass es keine andere Wahl gibt, als mit der Menge umzugehen ...) Einige Stunden später stellte sich heraus, dass ich die grundlegenden Fehler in den Grundlagen nicht kannte.

Negative Reste verhalten sich ungewollt! !!

Wie Sie unter Bezugnahme auf diesen Artikel sehen können, scheint es für den Rest mehrere Definitionen zu geben, und jede Sprache verhält sich anders. Es scheint, dass. Um dies zu vermeiden, können Sie die negative Zahl in eine positive Zahl ändern, wie im Code geschrieben. (Ich denke, es ist einfach, aber ich wusste nichts über C ++, weil ich nicht viel darüber wusste. Ich sollte C ++ besser lernen ...)

In Bezug auf die Richtlinie ist, wenn Sie die Unterspalten der Länge k einschließlich der Duplizierung aus dem Ganzen zählen, $ _ {n + 1} C _k $, also ** Experimentieren Sie, ob es eine Duplizierung geben kann ** Machen. Gemäß dem Experiment sei x die Zahl, die in zwei existiert, und wenn x im Index i, j (0 <= i, j <= N) ist und beide in der Unterspalte enthalten sind, können sie sich überlappen. Wenn es nicht vorhanden ist und keine der beiden in der Unterspalte enthalten ist, können Sie sehen, dass es auch keine Duplizierung gibt. Betrachten Sie nun **, wenn Sie nur ein x in eine Unterspalte einfügen möchten **. Wenn man bedenkt, dass die Anzahl der Teile i + 1 bis j-1 enthalten ist, befindet sich die Nummer auf der rechten Seite für x in i und die Nummer auf der linken Seite für x in j, also die verschiedenen Teile Sie können sehen, dass es als Spalte unterteilt ist. Daher werden die Zahlen in ** 0 ~ i-1, j + 1 ~ N und die aus entweder x ausgewählten Unterspalten dupliziert ** und $ _ {i + (nj)} C _ {k -1} $ ist die Anzahl der doppelten Teilzeichenfolgen für Unterspalten der Länge k. Daher können Sie $ _ {n + 1} C k- {i + (nj)} C _ {k-1} $ finden, aber wie ich zuvor geschrieben habe, generieren Sie keinen negativen Rest. Bei einer negativen Zahl können Sie diese durch Hinzufügen von MODs auf einen positiven Überschuss reduzieren.

Darüber hinaus ist die Berechnung der Kombination von Herrn Kencho entlehnt. Weitere Informationen finden Sie in diesem Artikel.

answerD.cc

#include<iostream>
#include<vector>
#include<utility>
using namespace std;

const int MAX = 1000000;
const int MOD = 1000000007;

long long 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 (int 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
long long COM(int n, int k){
    if (n < k) return 0;
    if (n < 0 || k < 0) return 0;
    return fac[n] * (finv[k] * finv[n - k] % MOD) % MOD;
}

int main(){
  //Vorverarbeitung
  COMinit();
  int n;cin >> n;
  vector<int> a(n+1);for(int i=0;i<n+1;i++){cin >> a[i];a[i]-=1;}
  vector<bool> b(n,true);
  for(int i=0;i<n+1;i++){b[a[i]]=!b[a[i]];}
  pair<int,int> p=make_pair(-1,-1);
  for(int i=0;i<n+1;i++){
    if(b[a[i]]){
      if(p.first==-1){p.first=i;}
      else{p.second=i;break;}
    }
  }
  //Zuerst wurde c im folgenden Teil ausgegeben, aber c<Da die Möglichkeit 0 besteht, gibt es nicht genau den Rest des MOD
  for(int i=1;i<=n+1;i++){
    int c=COM(n+1,i)-COM(p.first+(n-p.second),i-1);
    while(c<0){
      c+=MOD;
    }
    cout << c%MOD << endl;
  }
}