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

Frühere Fragen, die ich beim ersten Mal nie gelöst habe

Benötigte Zeit

Impressionen

Ich verstand das D-Problem, indem ich mir die Antwort ansah, aber es schien keine natürliche Lösung für mich zu sein und ich brauchte lange, um zu kauen ...

Problem A

nichts Besonderes

answerA.py

print("ABC"+input())

B-Problem

Sie müssen nur die größten $ 2 ^ k $ finden, die die Bedingungen erfüllen, also protokollieren und beenden

answerB.py

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

C-Problem

Seit a →? → b können Sie herausfinden, wie die mit a verbundene Nummer und die mit b verbundene Nummer lauten. TLE trat häufig auf, weil ich versucht habe, die Schleife zu durchlaufen, in der die erste Eingabe empfangen wurde. (** Siehe die Einschränkungen auch für einfache Probleme **)

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

D Problem

answerD1.py、answerD2.py ist$2$<=N<=$50$、$0$<=$a_i$<=$50 \times 10^{16}$Da es nicht alle oben genannten Anforderungen erfüllt, ist es zu TLE geworden.

 Wenn wir uns die Einschränkungen ansehen, sehen wir zunächst, dass es besser erscheint, so viele n wie möglich zu machen. Also lasst uns ** n auf 50 fixieren und darüber nachdenken.
 Hier ist es aufgrund der Einschränkung von $ 10 ^ {16} $ nicht möglich, die gesamte Operation zu simulieren. ** Ist es möglich, die Muster einzugrenzen, die während der Operation Einschränkungen sein können? ** oder ** Was passiert im Endzustand? Sie müssen zuerst über ** nachdenken (Standard). Wenn Sie hier ein Experiment durchführen, werden Sie etwas herausfinden, wenn Sie es umgekehrt befolgen. In diesem Problem können Sie im Gegenteil den ** Zyklus ** entdecken, indem Sie ** genau ** folgen.
 In Bezug auf den Endzustand ist es zunächst einfacher zu verstehen, wenn Sie 0 bis 49 der Länge 50 in aufsteigender Reihenfolge anordnen. (Das Experiment zeigt, dass die umgekehrte Simulation mühsam sein kann, wenn mehrere identische Zahlen vorhanden sind.)
 Wenn Sie dann 50 in der Reihenfolge vom 1. bis zum 50. und -1 zu anderen Elementen hinzufügen, können Sie genau das Gegenteil simulieren. Da sich die Summe für jede umgekehrte Simulation von 1 auf 50 um 1 erhöht (von $ 50 + (-1) \ mal (50-1) $), denken Sie zuerst an k geteilt durch 50. Sie können sehen, dass nur die verbleibende Anzahl von Malen simuliert werden muss und dann berücksichtigt wird, wie viel das Ganze in den verbleibenden Zyklen hinzugefügt wird.
 Wenn das obige implementiert ist, wird es zu `` `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)))