[PYTHON] AtCoder Beginner Contest 066 Revoir les questions précédentes

Temps requis

Problème A

Choisissez simplement les deux plus petits.

answerA.py

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

Problème B

Effacez simplement la fin dans l'ordre et pensez-y.

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

Problème C

Si vous pensez à ** comment vous poussez réellement **, vous pouvez voir que l'arrangement est différent pour les poussées impaires et paires (voir exemple), donc si vous implémentez cet arrangement avec obéissance, ce sera comme suit. .. (Il est également nécessaire de noter qu'il existe des cas dus à la régularité de n.)

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))

Problème D

La politique a été établie normalement, mais la mise en œuvre n'a pas pu être achevée. (** La capacité de montage ** est également l'un des problèmes, mais il semble qu'il n'y ait pas d'autre choix que de gérer le montant ...) On a découvert quelques heures plus tard que je n'étais pas au courant des erreurs de base dans les bases.

Les restes négatifs se comportent involontairement! !!

Comme vous pouvez le voir en vous référant à cet article, il semble qu'il existe plusieurs définitions pour le reste, et chaque langue se comporte différemment. Il semble. Pour éviter cela, vous pouvez changer le nombre négatif en un nombre positif tel qu'écrit dans le code. (Je pense que c'est basique, mais je ne connaissais pas le C ++ parce que je n'en savais pas grand chose. Je devrais étudier le C ++ plus correctement ...)

En ce qui concerne la politique, si vous comptez la sous-colonne de longueur k à partir du tout, y compris la duplication, ce sera $ _ {n + 1} C _k $, donc ** Expérimentez pour déterminer s'il peut y avoir duplication ** Faire. Selon l'expérience, soit x le nombre qui existe dans deux, et lorsque x est dans l'indice i, j (0 <= i, j <= N), lorsque les deux sont inclus dans la sous-colonne, ils peuvent se chevaucher. Vous pouvez également voir qu'il n'y a pas de doublons lorsqu'ils n'existent pas et qu'aucun des deux n'est inclus dans la sous-colonne. Considérez maintenant ** lorsque vous souhaitez inclure un seul x dans une sous-colonne **. Compte tenu du fait que le nombre de parties i + 1 à j-1 est inclus, le nombre est situé sur le côté droit pour x dans i et le nombre est situé sur le côté gauche pour x dans j, donc les différentes parties Vous pouvez voir qu'il est divisé en colonne. Par conséquent, les nombres dans ** 0 ~ i-1, j + 1 ~ N et les sous-colonnes sélectionnées parmi x sont des doublons **, et $ _ {i + (nj)} C _ {k -1} $ est le nombre de sous-chaînes dupliquées pour les sous-colonnes de longueur k. Par conséquent, vous pouvez trouver $ _ {n + 1} C k- {i + (nj)} C _ {k-1} $, mais comme je l'ai écrit plus tôt, ne générez pas de reste négatif. Dans le cas d'un nombre négatif, vous pouvez le réduire à un surplus positif en ajoutant des MOD.

De plus, le calcul du regroupement est emprunté à M. Kencho. Pour plus de détails, veuillez consulter cet article.

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];

//Prétraitement pour faire une table
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;
    }
}

//Calcul du coefficient binaire
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(){
  //Prétraitement
  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;}
    }
  }
  //Au début, c était sorti dans la partie suivante, mais c<Puisqu'il y a une possibilité de 0, il n'y a pas exactement le reste du 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;
  }
}