AtCoder Beginner Contest 068 Revue des questions précédentes

Des questions passées que je n'ai jamais résolues, la première fois

Temps requis

スクリーンショット 2019-12-25 14.18.57.png

Impressions

J'ai compris le problème D en regardant la réponse, mais cela ne me semblait pas être une solution naturelle et il m'a fallu beaucoup de temps pour mâcher ...

Problème A

rien de spécial

answerA.py


print("ABC"+input())

Problème B

Il vous suffit de trouver le plus gros $ 2 ^ k $ qui remplit les conditions, alors connectez-vous et terminez

answerB.py


import math
n=int(input())
print(2**math.floor(math.log(n,2)))

Problème C

Puisque a →? → b, vous pouvez savoir ce que sont le nombre connecté à a et le nombre connecté à b. TLE s'est produit fréquemment parce que j'ai essayé de boucler dans la boucle où la première entrée a été reçue. (** Voir les contraintes même pour des problèmes simples **)

answerC.cc


#include<iostream>
#include<vector>
#include<set>
#include<algorithm>
using namespace std;

int main(){
  int n,m;cin >> n >> m;
  vector<int> x;
  bool f=false;
  for(int i=0;i<m;i++){
    int a,b;cin >> a >>b;
    if(a==1){
      x.push_back(b);
    }
    if(b==n){
      x.push_back(a);
    }
  }
  int l1=x.size();
  set<int> y(x.begin(),x.end());
  if(l1==y.size()){
    cout << "IMPOSSIBLE" << endl;
  }else{
    cout << "POSSIBLE" << endl;
  }
}

answerC.py


n,m=map(int,input().split())
x=[]
for i in range(m):
    a,b=map(int,input().split())
    if a==1:
        x.append(b)
    if b==n:
        x.append(a)
l=len(x)
if len(set(x))==l:
    print("IMPOSSIBLE")
else:
    print("POSSIBLE")

Problème D

answerD1.py、answerD2.py est$2$<=N<=$50$、$0$<=$a_i$<=$50 \times 10^{16}$Parce qu'il ne répond pas à chacun des critères ci-dessus, il est devenu TLE.


 Tout d'abord, en regardant les contraintes, nous pouvons voir qu'il semble préférable d'en faire autant de n que possible. Alors fixons ** n à 50 et ** y réfléchissons.
 Ici, il n'est pas possible de simuler l'opération entière en raison de la contrainte de $ 10 ^ {16} $, donc ** Est-il possible de restreindre les modèles qui peuvent être des contraintes pendant l'opération? ** ou ** Que se passe-t-il dans l'état final? Vous devez d'abord penser à ** (standard). Si vous faites une expérience ici, vous découvrirez quelque chose si vous la suivez à l'envers. Ensuite, dans ce problème, au contraire, vous pouvez découvrir le ** cycle ** en suivant ** avec précision **.
 Tout d'abord, concernant l'état final, il sera plus facile à comprendre si vous disposez de 0 à 49 de longueur 50 par ordre croissant. (L'expérience montre que la simulation inverse peut être fastidieuse s'il y a plusieurs nombres identiques.)
 Ensuite, si vous ajoutez 50 dans l'ordre du 1er au 50e et ajoutez -1 aux autres éléments, vous pouvez simuler exactement le contraire. De plus, puisque le total augmente de 1 pour chaque simulation inverse de la 1ère à la 50ème (de 50 $ + (-1) \ fois (50-1) $), pensez d'abord à k divisé par 50. Vous pouvez voir que vous devez simuler le nombre de fois restant, puis considérer combien le tout est ajouté dans le cycle restant.
 Lorsque ce qui précède est implémenté, il devient ```answerD3.py```.


#### **`answerD1.py`**
```python

k=int(input())
print(2)
if k%2==0:
    print(str(k//2)+" "+str(k//2+1))
else:
    print(str(k//2)+" "+str(k//2+2))

answerD2.py


k=int(input())
n=k+1
if n==1:
    print("2")
    print("0 1")
else:
    print(n-1+k*n,end="")
    for i in range(n-1):
        print(" 0",end="")
    print()

answerD3.py


k=int(input())
x=[0]*50
k1=k//50
k2=k%50
for i in range(k2):
    x[k2-i-1]=50-i
for i in range(k2+1,50):
    x[i]=i-k2
for i in range(50):
    x[i]+=k1
print(50)
print(" ".join(map(str,x)))

Recommended Posts

AtCoder Beginner Contest 102 Revue des questions précédentes
AtCoder Beginner Contest 085 Revue des questions précédentes
AtCoder Beginner Contest 062 Revue des questions précédentes
AtCoder Beginner Contest 113 Revue des questions précédentes
AtCoder Beginner Contest 074 Revue des questions précédentes
AtCoder Beginner Contest 051 Revue des questions précédentes
AtCoder Beginner Contest 119 Revue des questions précédentes
AtCoder Beginner Contest 151 Revue des questions précédentes
AtCoder Beginner Contest 075 Revue des questions précédentes
AtCoder Beginner Contest 054 Revue des questions précédentes
AtCoder Beginner Contest 110 Revue des questions précédentes
AtCoder Beginner Contest 117 Revue des questions précédentes
AtCoder Beginner Contest 070 Revue des questions précédentes
AtCoder Beginner Contest 105 Revue des questions précédentes
AtCoder Beginner Contest 112 Revue des questions précédentes
AtCoder Beginner Contest 076 Revue des questions précédentes
AtCoder Beginner Contest 089 Revue des questions précédentes
AtCoder Beginner Contest 069 Revue des questions précédentes
AtCoder Beginner Contest 079 Revue des questions précédentes
AtCoder Beginner Contest 056 Revue des questions précédentes
AtCoder Beginner Contest 087 Revue des questions précédentes
AtCoder Beginner Contest 093 Revue des questions précédentes
AtCoder Beginner Contest 046 Revue des questions précédentes
AtCoder Beginner Contest 123 Revue des questions précédentes
AtCoder Beginner Contest 049 Revue des questions précédentes
AtCoder Beginner Contest 078 Revue des questions précédentes
AtCoder Beginner Contest 047 Revue des questions précédentes
AtCoder Beginner Contest 104 Revue des questions précédentes
AtCoder Beginner Contest 057 Revue des questions précédentes
AtCoder Beginner Contest 121 Revue des questions précédentes
AtCoder Beginner Contest 090 Revue des questions précédentes
AtCoder Beginner Contest 103 Revue des questions précédentes
AtCoder Beginner Contest 061 Revue des questions précédentes
AtCoder Beginner Contest 083 Revue des questions précédentes
AtCoder Beginner Contest 124 Revue des questions précédentes
AtCoder Beginner Contest 116 Revue des questions précédentes
AtCoder Beginner Contest 097 Revue des questions précédentes
AtCoder Beginner Contest 092 Revue des questions précédentes
AtCoder Beginner Contest 099 Revue des questions précédentes
AtCoder Beginner Contest 065 Revue des questions précédentes
AtCoder Beginner Contest 053 Revue des questions précédentes
AtCoder Beginner Contest 094 Revue des questions précédentes
AtCoder Beginner Contest 063 Revue des questions précédentes
AtCoder Beginner Contest 107 Revue des questions précédentes
AtCoder Beginner Contest 071 Revue des questions précédentes
AtCoder Beginner Contest 064 Revue des questions précédentes
AtCoder Beginner Contest 082 Revue des questions précédentes
AtCoder Beginner Contest 084 Revue des questions précédentes
AtCoder Beginner Contest 068 Revue des questions précédentes
AtCoder Beginner Contest 058 Revue des questions précédentes
AtCoder Beginner Contest 043 Revue des questions précédentes
AtCoder Beginner Contest 098 Revue des questions précédentes
AtCoder Beginner Contest 114 Revue des questions précédentes
AtCoder Beginner Contest 045 Revue des questions précédentes
AtCoder Beginner Contest 120 Revue des questions précédentes
AtCoder Beginner Contest 108 Revue des questions précédentes
AtCoder Beginner Contest 106 Revue des questions précédentes
AtCoder Beginner Contest 122 Revue des questions précédentes
AtCoder Beginner Contest 125 Revue des questions précédentes
AtCoder Beginner Contest 109 Revue des questions précédentes
AtCoder Beginner Contest 118 Revue des questions précédentes