Die Ergebnisse dieser Zeit

スクリーンショット 2020-10-16 14.38.42.png

Eindrücke dieser Zeit

Dieses Mal konnte ich es lösen, ohne WA auszugeben (obwohl es einige Zeit dauerte), da ich bei der Organisation der Problemeinstellungen fortgefahren bin. Außerdem war das D-Problem mühsam, die Geschwindigkeit durch Sitzen zu erhöhen. Wenn ich es also als Set handhabte, wäre es gefährlich TLE (1996 ms / 2000 ms).

Es gab viele Leute, die C2 durch einen Blick auf die Rangliste des Freundes verbessert haben, aber ich fühlte mich nicht motiviert. Ich habe mich seit gestern zwei Tage hintereinander nicht mehr aufgelöst, also werde ich versuchen, mich nach morgen fest zu lösen, damit ich mich nicht an diese Gewohnheit gewöhne.

Problem A

Anzahl der Stürze mit BIT! ?? Dies war jedoch nicht der Fall. ** Der Maximalwert für die Anzahl der Stürze ** ist $ \ frac {n (n-1)} {2} $ nur, wenn die Elemente in absteigender Reihenfolge angeordnet sind **. Bestimmen Sie also, ob dies der Maximalwert ist. .. Beachten Sie auch, dass es bei mehreren identischen Elementen nicht $ \ frac {n (n-1)} {2} $ ist, aber es gibt freundlicherweise einen Fall in der Stichprobe.

`A.py`


for _ in range(int(input())):
    n=int(input())
    a=list(map(int,input().split()))
    if a==sorted(a,reverse=True) and len(set(a))==n:
        print("NO")
    else:
        print("YES")

B-Problem

Zuerst habe ich das Problem falsch verstanden und es war gefährlich (ich dachte, dass das gleiche Element, weil jedes bisschen das gleiche ist!).

Wenn die $ k $ -Bits von $ a \ _i und a \ _j $ $ a \ _ {ik} bzw. a \ _ {jk} $ sind, dann $ a \ _ {ik} $ & $ a \ _ { jk} $, $ a \ _ {ik} \ oplus a \ _ {jk} $ sieht folgendermaßen aus: (** Stück für Stück! **)

a\_{ik}	a\_{jk}	a\_{ik}&a\_{jk}	a\_{ik} \oplus a\_{jk}
0	0	0	0
0	1	0	1
1	0	0	1
1	1	1	0

Daher gilt $ a \ _i $ & $ a \ _ j \ geqq a \ _i \ oplus a \ _j $ für $ (a \ _ {ik}, a \ _ {jk}) = (0,0), Es wird (1,1) $ sein. Wenn es also ein Bit (MSB) ** gibt, das zum ersten Mal ab dem Bit ** von $ a \ _i $ steht, ist die Zahl, die $ a \ _i $ erfüllt, dieselbe Anzahl von MSBs ($ ). Da $ eine positive Zahl ist, steht das Bit immer).

Daher wird jedes $ a \ _ {i} $ von MSB klassifiziert, und wenn es $ x $ wie $ a \ _ {i} $ gibt, gibt es $ \ _x C \ _2 $ Kombinationen. Existiert. Die Antwort ist, die Summe davon zu finden.

`B.py`


from collections import Counter
for _ in range(int(input())):
    n=int(input())
    x=[0 for i in range(30)]
    l=list(map(int,input().split()))
    for i in l:
        for j in range(29,-1,-1):
            if (i>>j)&1:
                x[j]+=1
                break
    ans=0
    for i in x:
        if i>1:
            ans+=(i*(i-1)//2)
    print(ans)

C1-Problem

Es ist bereits in Kodofo erschienen. Ich habe jedoch einen Fehler im Index gemacht. Bist du dumm ...?

** Der Maximalwert der (speziellen) Summe der Unterspalten ** kann gefunden werden, so-oder + hängt vom-oder + des sofort ausgewählten Elements ab. Betrachten Sie daher den folgenden DP.

$ dp [i] [j]: = $ (Maximalwert der (speziellen) Summe von Unterspalten, die aus bis zur $ i $ -ten Zahl ausgewählt wurden, aber zuletzt ausgewählte Zahl, wenn $ j = 0 $ Wenn is-und $ j = 1 $ ist, ist die zuletzt ausgewählte Zahl +)

Der Übergang ist wie folgt. Es gibt ungefähr drei Möglichkeiten, die Unterspalte zu wechseln. Es ist notwendig, nur auf den Fall von -oder + zu achten.

(1) Wenn das $ i + 1 $ -te Element nicht ausgewählt ist dp[i+1][0]←dp[i][0] dp[i+1][1]←dp[i][1]

(2) Bei Auswahl des Elements $ i + 1 $ anstelle des ersten Males dp[i+1][0]←dp[i][1]-a[i+1] dp[i+1][1]←dp[i][0]+a[i+1]

(3) Bei der erstmaligen Auswahl des $ i + 1 $ -ten Elements

dp[i+1][1]←a[i+1]

Wenn Sie die obigen Maximalwerte in der richtigen Reihenfolge finden, ist $ max (dp [n-1]) $ die Antwort.

`C.py`


inf=10**12
import sys
input = sys.stdin.readline
for _ in range(int(input())):
    n,q=map(int,input().split())
    a=list(map(int,input().split()))
    dp=[[-inf,-inf] for i in range(n)]
    dp[0]=[-inf,a[0]]
    for i in range(n-1):
        dp[i+1][0]=dp[i][0]
        dp[i+1][1]=dp[i][1]
        dp[i+1][0]=max(dp[i+1][0],dp[i][1]-a[i+1])
        dp[i+1][1]=max(dp[i+1][1],dp[i][0]+a[i+1])
        dp[i+1][1]=max(dp[i+1][1],a[i+1])
    print(max(dp[n-1]))
    #print(dp)

C2-Problem

Ich werde diesmal überspringen.

D Problem

Ich bin der Meinung, dass es mit hoher Geschwindigkeit hätte gelöst werden müssen, deshalb möchte ich die Montageleistung verbessern.

Es gibt $ n $ geschlossene Abschnitte ** Sie können überprüfen, ob sich die Enden jedes Abschnitts überlappen . Mit anderen Worten, wenn Sie nur am Ende des Abschnitts ** sitzen, müssen Sie höchstens $ 2n $ -Koordinaten berücksichtigen. Daher können $ k $ Abschnitte, die mindestens eine Koordinate überlappen, als Betreffabschnitt ausgewählt werden ( Paraphrase des Betreffs! **).

Hier gibt es Zeiten, in denen Sie ** eine Kombination desselben Abschnitts mit mehreren Koordinaten ** (✳︎) auswählen können, daher müssen Sie vorsichtig sein. Zum Beispiel die roten und gelben Teile in der folgenden Abbildung ($ k = 3 $).

Außerdem möchte ich zunächst gierig denken, damit ich sie in aufsteigender Reihenfolge der Koordinaten betrachten kann. Unter der Annahme, dass an einer bestimmten Koordinate bereits $ x $ bereits ausgewählte Abschnitte und $ y $ Abschnitte zum ersten Mal ausgewählt wurden, wird "Auswählen eines noch nicht ausgewählten Abschnitts" von "Auswählen eines Abschnitts, der hier ausgewählt werden kann" in "geändert". Die Gesamtzahl beträgt $ _ {x + y} C_k-_xC_k $, ausgenommen "Wie man nur aus den bereits ausgewählten Abschnitten auswählt" (Es dauerte lange, bis man es bemerkte, aber ein einfaches ** Umhüllungsprinzip *). * ist). Wenn Sie also das Intervall verwalten, das jede Koordinate enthält, können Sie die Kombination mit $ O (1) $ berechnen (die Vorberechnung der Kombination ist $ O (n) $).

Daher ist die Implementierung wie folgt (** Fassen Sie die Implementierung zusammen! **).

nowseg: Set, das die Informationen des Abschnitts enthält, einschließlich der Koordinaten, als die Sie suchen (Koordinaten am rechten Ende des Abschnitts, Index) nexseg: Karte mit den Informationen des Abschnitts, die noch nicht gesehen wurden, mit dem linken Ende des Abschnitts als Schlüssel und (den Koordinaten des rechten Endes des Abschnitts, dem Index) als Wert Koordinaten: mit möglichen Intervallenden einstellen (weil ich es in aufsteigender Reihenfolge halten und die Implementierung des Sitzdrucks überspringen wollte)

Auf diese Weise wird an jeder Koordinate $ i $

(1) Setzen Sie die Größe von nowseg auf $ x $ und die Größe von nexseg [i] auf $ y $ und ermitteln Sie die Anzahl neuer Kombinationen von Abschnitten, die durch Kombinationsberechnung erstellt werden können. ② Fügen Sie alle Elemente von nexseg [i] zu nowseg hinzu ③ Löschen Sie nur diejenigen in nowseg, deren Koordinate ganz rechts im Abschnitt $ i $ ist (überprüfen Sie die Reihenfolge ab dem ersten Element von nowseg).

Es kann leicht implementiert werden, indem die Operationen in der Reihenfolge von ausgeführt werden.

`D.cc`


//Debug-Optionen:-fsanitize=undefined,address

//Compileroptimierung
#pragma GCC optimize("Ofast")

//Einschließen usw.
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;

//Makro
//für Schleife
//Das Argument ist(Variablen in der Schleife,Bewegungsumfang)Oder(Variablen in der Schleife,Erste Nummer,Anzahl der Enden)、のどちらOder
//Schleifenvariablen ohne D werden um 1 erhöht, und Schleifenvariablen mit D werden um 1 dekrementiert.
//FORA ist ein Bereich für Aussagen(Wenn es schwer zu bedienen ist, löschen Sie es)
#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--)
#define FORA(i,I) for(const auto& i:I)
//x ist ein Container wie ein Vektor
#define ALL(x) x.begin(),x.end() 
#define SIZE(x) ll(x.size()) 
//Konstante
#define INF 1000000000000 //10^12:∞
#define MOD 998244353 //10^9+7:Gemeinsames Recht
#define MAXR 300002 //10^5:Maximale Reichweite des Arrays
//Abkürzung
#define PB push_back //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 n,k;cin>>n>>k;
    map<ll,vector<pair<ll,ll>>> nexseg;
    set<pair<ll,ll>> nowseg;
    set<ll> coordinates;
    REP(i,n){
        ll l,r;cin>>l>>r;
        nexseg[l].PB(MP(r,i));
        coordinates.insert(l);
        coordinates.insert(r);
    }
    //Koordinaten von links scannen
    //Ursprünglich neu hinzugekommen(Überprüfen Sie die Nummer)→ Auf fehlende Gegenstände prüfen
    //Dann löschen
    mint ans=0;
    FORA(i,coordinates){
        //cout<<1<<endl;
        ll x,y;x=SIZE(nowseg);
        if(nexseg.find(i)==nexseg.end()){
            y=0;
            ans+=0;
        }else{
            y=SIZE(nexseg[i]);
            FORA(j,nexseg[i]){
                nowseg.insert(j);
            }
            ans+=(COM(x+y,k)-COM(x,k));
        }
        //cout<<x<<" "<<y<<" "<<ans<<endl;
        auto j=nowseg.begin();
        //cout<<j->F<<" "<<j->S<<endl;
        while(j!=nowseg.end()){
            //cout<<1<<endl;
            if(j->F==i){
                j=nowseg.erase(j);
            }else{
                break;
            }
        }
    }
    cout<<ans<<endl;
}

E Problem