Die Ergebnisse dieser Zeit

Eindrücke dieser Zeit

Ich bin nicht gut darin, schnell zu lösen, aber ich denke, er hat gute Arbeit geleistet. Ich möchte das F-Problem rechtzeitig lösen können. Ich möchte in der Lage sein, logisch mit einem Spielraum zu denken, auch wenn die Überlegung kompliziert wird. Zu diesem Zweck denke ich, ich sollte das Memo etwas schöner schreiben. Ich habe den Wettbewerb kürzlich überprüft, daher möchte ich diesen Punkt selbst bewerten. Ich hoffe, dass die Ergebnisse bald zum Tragen kommen.

Problem A

Ob es sich um Großbuchstaben handelt oder nicht, kann durch die Isupper-Funktion bestimmt werden.

`A.py`


a=input()
print("A" if a.isupper() else "a")

B-Problem

Ich habe das Gefühl, dass das Problem dieses Musters in AtCoder auftritt. Da K Elemente in aufsteigender Reihenfolge ausgewählt sind, können Sie sie in aufsteigender Reihenfolge sortieren und die Summe der 1. bis K. Elemente im Array berücksichtigen.

`B.py`


n,k=map(int,input().split())
p=list(map(int,input().split()))
p.sort()
print(sum(p[:k]))

C-Problem

Wie beim letzten Mal erwartet, können Sie sehen, dass wir versuchen, mit C eine Klippe zu machen. Ich denke, der Prozess ist mühsam, aber ich bin überrascht, dass eine beträchtliche Anzahl von Menschen durchkommt.

Erstens, wenn die Länge des Hundenamens $ l $ beträgt, ist es klar, dass es $ 26 ^ l $ Möglichkeiten gibt, den Hund zu benennen. Von hier aus können Sie auch sehen, dass es bequem ist, sich eine Zahl von 26 Jahren vorzustellen. ** Wenn Sie die Länge des Namens festlegen, können Sie sich dies als den Prozess der Bestimmung der n-stelligen Ziffern vorstellen **. Daher habe ich mich entschlossen, die Länge des Namens zuerst mit der Funktion n_len zu ermitteln.

Hier kann die Länge des Namens erhalten werden, indem $ 26,26 ^ 2,… $ von dem gegebenen N subtrahiert wird, so dass es nicht 0 oder weniger wird, also unter diesem Prozess ** Namenslänge Es enthält die Informationen $ l $ ** und die Nummer $ N $ ** im Namen dieser Länge (in lexikalischer Reihenfolge).

Wenn Sie der Meinung sind, dass die Verarbeitung der 26-stelligen Zahl von der unteren Ziffer abhängt, können Sie das Alphabet dieser Ziffer mit "n% 26" finden und diese Ziffer mit "n // = 26" verwerfen. Nennen Sie dies also Alles was Sie tun müssen, ist für die Länge $ l $.

`C.py`


n=int(input())-1
def n_len():
    global n
    i=1
    while n>=26**i:
        n-=26**i
        i+=1
    return i
l=n_len()
alp=[chr(i) for i in range(97, 97+26)]
ans=""
for i in range(l):
    k=n%26
    ans=alp[k]+ans
    n//=26
print(ans)

D Problem

Wenn Sie die Zahlenspalte als Array speichern und eine Abfrageberechnung durchführen, müssen Sie alle Elemente des Arrays überprüfen. Der Berechnungsbetrag beträgt $ O (QN) $, was zu spät ist.

Bei der Abfrageverarbeitung werden alle Zahlen mit dem Wert $ B_i $ in $ C_i $ umgeschrieben. Wenn Sie speichern, wie viele Zahlen sich in der Zahlenspalte des Wörterbuchs befinden, lautet diese Verarbeitung $ O (1) $ Du kannst es schaffen.

Wenn Sie also eine Variable vorbereiten, um die Summe der Elemente zu speichern, und die Möglichkeit berücksichtigen, dass $ B_i und C_i $ in der Sequenz nicht vorhanden sind, können Sie ein Programm mit einem Berechnungsbetrag von $ O (Q) $ implementieren. Ich kann es schaffen

`D.py`


n=int(input())
a=dict()
ans=0
for i in map(int,input().split()):
    ans+=i
    if i in a:
        a[i]+=1
    else:
        a[i]=1
q=int(input())
for i in range(q):
    b,c=map(int,input().split())
    if c not in a:
        a[c]=0
    if b not in a:
        a[b]=0
    ans=ans-b*a[b]+c*a[b]
    a[c]+=a[b]
    a[b]=0
    print(ans)

E Problem

Wie Sie aus hamayanhamayans Artikel sehen können, gibt es drei häufig verwendete Eigenschaften von XOR ($ a). $ Ist eine ganze Zahl größer oder gleich 0).

1: Börsen- und Verbindungsrecht 2:$a \oplus a=0$ 3:$2a \oplus (2a+1)=1 \leftrightarrow 4a \oplus (4a+1) \oplus (4a+2) \oplus (4a+3)=0$

Zusätzlich eine ganze Zahl, die den Vektorraum $ F ^ n $ so betrachtet, dass $ F = \ {0,1 \} $, (Anzahl der Bits) = $ n $ und $ \ oplus $ als lineare Verbindung. Es gibt auch ein Problem (AGC045 Ein Problem), das lineare Unabhängigkeit und lineare Abhängigkeit ausdrückt und beurteilt, aber für Details hamayanhamayan Bitte beachten Sie den Artikel etc.

In diesem Problem verwenden wir hauptsächlich die obige Eigenschaft 2 und gehen davon aus, dass sie mit einem guten Gefühl gelöscht werden kann, da sie 0 ist, wenn eine Abdeckung auftritt **, und sie wird wie in der folgenden Abbildung gezeigt. (Verwenden Sie implizit auch Eigenschaft 1.)

In Anbetracht des XOR von $ a_1, a_2,…, a_n $ ist klar, dass $ b_1, b_2,…, b_n $ jedes Mal $ n-1 $ erscheinen. Konzentrieren Sie sich außerdem auf $ a_i $, um ** $ b_i $ ** und XOR $ a_i $ erneut zu finden, um $ b_1,…, b_ {i-1}, b_ {i + 1} zu erhalten Sie können sehen, dass…, b_n $ jeweils $ n $ mal und $ b_i $ jeweils $ n-1 $ mal erscheint. Aufgrund der Einschränkung des Problems ist $ n $ gerade, sodass alle XORs von $ b_1,…, b_ {i-1}, b_ {i + 1},…, b_n $ 0 sind und nur $ b_i $ übrig bleibt. Ich verstehe.

Finden Sie aus dem Obigen das XOR von $ a_1, a_2,…, a_n $ als Vorberechnung und die Nummer und das XOR von $ a_1, a_2,…, a_n $ als Antwort. ..

`E.py`


n=int(input())
a=list(map(int,input().split()))
b=0
for i in range(n):
    b^=a[i]
ans=[0]*n
for i in range(n):
    ans[i]=a[i]^b
print(" ".join(map(str,ans)))

F Problem

Es schien mit etwas mehr Kopfdrehung gelöst zu werden ... Blue Diff hat viele Probleme wie dieses ...

(Im Folgenden wird die ursprüngliche Zeichenfolge als $ S $ ausgedrückt, ihre Länge als $ N $, das Zeichen $ i $ als $ S_i $ und die schließlich generierte Zeichenfolge als $ S ^ {'} $. )

Zunächst bezweifelte ich DP, weil es ** eine Zeichenkette ist und die Reihenfolge in Beziehung zu stehen scheint **, aber es ist eindeutig nicht rechtzeitig für die Berechnung. Da es den Anschein hat, dass aufgrund des Experiments mit dem Beispiel und der Begrenzung des Problems viele Zeichenketten dargestellt werden können, dachte ich, dass ** ich es durch Kombinationsberechnung in etwa $ O (K + N) $ belassen möchte **. Da der Freiheitsgrad der später hinzuzufügenden Zeichen hoch ist, haben wir die Methode übernommen, die Position der in ** $ S $ enthaltenen Zeichen zu bestimmen und dann die Gesamtzahl der später hinzuzufügenden Zeichenkombinationen zu berücksichtigen **.

Wenn Sie jedoch entscheiden, welche Zeichen in $ S $ enthalten sein sollen, und dann nach der Kombination fragen, vorausgesetzt, dass jeweils 26 andere Zeichen vorhanden sind, besteht die Möglichkeit, dass in ** $ S ^ {'} $ ** eine doppelte Zeichenfolge auftritt. .. Wenn Sie es mit der Richtlinie kombinieren, die Position der in $ S $ enthaltenen Zeichen zu bestimmen, wird die Entscheidung, wie $ S ^ {'} $ erstellt werden soll, eindeutig anhand der Position der in ** $ S $ enthaltenen Zeichen entschieden. Fragen Sie einfach nach der Methode **. Mit anderen Worten, diese Methode kann umformuliert werden, indem eine Methode ** (✳︎) gefunden wird, die die Position der in $ S $ enthaltenen Zeichen für ** $ S ^ {'} $ eindeutig bestimmt.

(↑ ** Die Antwort wird eindeutig durch eine bestimmte Methode bestimmt. Zählen von $ \ leftrightarrow $ Eine bestimmte Methode wird eindeutig durch das Zählen bestimmt **. Es gibt viele Probleme mit dem Thema Eindeutigkeit, daher möchte ich es lösen können. ist.)

In Bezug auf (✳︎) kann hier eindeutig bestimmt werden, ob es ** die Position ist, an der das in $ S $ enthaltene Zeichen zuerst erscheint, wenn $ S ^ {'} $ von vorne betrachtet wird **. Ich werde. Darunter auch von der Position von $ S \ _ {i-1} $ von $ S ^ {'} $ zur Position von $ S \ _ {i} $ ** $ S \ _ {i} $ Sie können alle Alphabete ** außer verwenden. Daher gibt es 25 (= 26-1) Zeichen, die vor der Position von $ S \ _ {N} $ nicht in $ S $ enthalten sind. Für die Zeichenfolge nach der Position von $ S \ _ {N} $ kann ein beliebiges Alphabet verwendet werden. Es gibt also 26 Möglichkeiten.

Wenn Sie oben die Position von $ S \ _ {N} $ festlegen, die die Grenze zwischen dem Fall von 26 Wegen und dem Fall von 25 Wegen darstellt, geben 26 und 25 an, wie viele Positionen von Zeichen in den verbleibenden $ S $ enthalten sind. Die folgende Implementierung kann erhalten werden, indem die Anzahl der Befugnisse ermittelt wird. Darüber hinaus wird im Folgenden die Modint-Struktur verwendet, die Ganzzahlen immer durch Modding verwaltet.

`F.cc`


//Einschließen(Alphabetischer Reihenfolge)
#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<iterator>//Betrieb einstellen(Produktset,Summensatz,Differenzsatz etc.)
#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
//für Schleifenbeziehung
//Das Argument ist(Variablen in der Schleife,Bewegungsumfang)Oder(Variablen in der Schleife,Erste Nummer,Anzahl der Endungen)、のどちらOder
//Wenn es kein D gibt, wird die Schleifenvariable um 1 erhöht, und wenn es ein D gibt, wird die Schleifenvariable um 1 dekrementiert.
#define REP(i,n) for(ll i=0;i<(ll)(n);i++)
#define REPD(i,n) for(ll i=n-1;i>=0;i--)
#define FOR(i,a,b) for(ll i=a;i<=(ll)(b);i++)
#define FORD(i,a,b) for(ll i=a;i>=(ll)(b);i--)
//x ist ein Container wie ein Vektor
#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
//Konstante
#define INF 1000000000000 //10^12:Extrem großer Wert,∞
#define MOD 1000000007 //10^9+7:Gemeinsames Recht
#define MAXR 3000000 //10^5:Maximale Reichweite des Arrays(Wird für die Aufzählung von Primzahlen usw. verwendet.)
//Abkürzung
#define PB push_back //In Vektor einfügen
#define MP make_pair //Paarkonstruktor
#define F first //Das erste Element des Paares
#define S second //Das zweite Element des Paares

template<ll mod> class modint{
public:
    ll val=0;
    //Konstrukteur
    modint(ll x=0){while(x<0)x+=mod;val=x%mod;}
    //Konstruktor kopieren
    modint(const modint &r){val=r.val;}
    //Arithmetischer Operator
    modint operator -(){return modint(-val);} //einstellig
    modint operator +(const modint &r){return modint(*this)+=r;}
    modint operator -(const modint &r){return modint(*this)-=r;}
    modint operator *(const modint &r){return modint(*this)*=r;}
    modint operator /(const modint &r){return modint(*this)/=r;}
    //Aufgabenverwalter
    modint &operator +=(const modint &r){
        val+=r.val;
        if(val>=mod)val-=mod;
        return *this;
    }
    modint &operator -=(const modint &r){
        if(val<r.val)val+=mod;
        val-=r.val;
        return *this;
    }
    modint &operator *=(const modint &r){
        val=val*r.val%mod;
        return *this;
    }
    modint &operator /=(const modint &r){
        ll a=r.val,b=mod,u=1,v=0;
        while(b){
            ll t=a/b;
            a-=t*b;swap(a,b);
            u-=t*v;swap(u,v);
        }
        val=val*u%mod;
        if(val<0)val+=mod;
        return *this;
    }
    //Äquivalenzvergleichsoperator
    bool operator ==(const modint& r){return this->val==r.val;}
    bool operator <(const modint& r){return this->val<r.val;}
    bool operator !=(const modint& r){return this->val!=r.val;}
};

using mint = modint<MOD>;

//E / A-Stream
istream &operator >>(istream &is,mint& x){//Fügen Sie x nicht const hinzu
    ll t;is >> t;
    x=t;
    return (is);
}
ostream &operator <<(ostream &os,const mint& x){
    return os<<x.val;
}

//Leistung
mint modpow(const mint &a,ll n){
    if(n==0)return 1;
    mint t=modpow(a,n/2);
    t=t*t;
    if(n&1)t=t*a;
    return t;
}

//Berechnung des Binomialkoeffizienten
mint fac[MAXR+1],finv[MAXR+1],inv[MAXR+1];
//Eine Tabelle erstellen
void COMinit() {
    fac[0]=fac[1]=1;
    finv[0]=finv[1]=1;
    inv[1]=1;
    FOR(i,2,MAXR){
        fac[i]=fac[i-1]*mint(i);
        inv[i]=-inv[MOD%i]*mint(MOD/i);
        finv[i]=finv[i-1]*inv[i];
    }
}
//Berechnungsteil
mint 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];
}

signed main(){
    //Code zur Beschleunigung der Eingabe
    //ios::sync_with_stdio(false);
    //cin.tie(nullptr);
    COMinit();
    ll k,l;cin>>k;
    string s;cin>>s;n=SIZE(s);
    mint ans=0;
    FOR(i,n,k+n){
        ans+=(modpow(25,i-n)*modpow(26,k+n-i)*COM(i-1,n-1));
    }
    cout<<ans<<endl;
}

[PYTHON] AtCoder Beginner Contest 171 Bewertung