Code de l'éducation forces Round 89 Bacha Review (9/8)

Les résultats de cette fois

スクリーンショット 2020-09-09 8.10.24.png

Impressions de cette époque

Je n'ai pas fait très attention au problème D, mais je suis content d'avoir pu le récupérer plus tard. C'est bien de reconstruire, mais je suis loin d'avoir mis en place une politique très précise, ce qui est mon objectif, j'aimerais donc m'y consacrer.

Problème A

Si vous faites $ shovel $ de $ x $ et $ sword $ de $ y $, alors $ 0 \ leqq 2x + y \ leqq a $ et $ 0 \ leqq x + 2y \ leqq b $. A ce moment, la somme des deux équations donne $ 0 \ leqq x + y \ leqq \ frac {a + b} {3} $.

De plus, puisque je veux trouver $ x + y $, j'aimerais supposer que $ [\ frac {a + b} {3}] $ est la valeur maximale, mais ** $ [\ frac {a + b} {3 }] $ doit être inférieur ou égal à $ a $ et inférieur ou égal à $ b $ ** (car $ \ car x, y $ est supérieur ou égal à 0). On trouvera donc $ min ([\ frac {a + b} {3}], a, b) $.

A.py


for _ in range(int(input())):
    a,b=map(int,input().split())
    print(min((a+b)//3,a,b))

Problème B

C'était dangereux parce que je l'ai mal lu à mi-chemin. L'anglais de Kodofo a parfois un problème difficile à lire ...

Considérez combien d'index peuvent finalement être définis sur 1 lors de l'échange. En outre, vous pouvez permuter dans la plage de $ l \ _i $ à $ r \ _i $. Puisque nous voulons découvrir tous les index qui peuvent être 1, nous pouvons trouver la solution en trouvant la plage d'index qui peut être 1 au moment de $ i $ et en élargissant progressivement la plage.

En d'autres termes, commencez par $ [x, x] $ et commencez par le plus petit $ i $. Il est plus facile à comprendre si vous l'écrivez dans un diagramme, je vais donc l'expliquer dans un diagramme à partir d'ici.

IMG_0608.PNG

En conséquence, les sections qui peuvent être réglées à 1 sont obtenues dans l'ordre comme décrit ci-dessus, de sorte que la longueur de la section finalement obtenue peut être obtenue comme solution.

B.py


for _ in range(int(input())):
    n,x,m=map(int,input().split())
    ans=[x,x]
    for i in range(m):
        l,r=map(int,input().split())
        if r<ans[0] or l>ans[1]:
            continue
        else:
            ans=[min(ans[0],l),max(ans[1],r)]
    print(ans[1]-ans[0]+1)

Problème C

Codeforces semble avoir beaucoup de BFS et de DFS. Je suis content car je n'ai pas l'habitude de le mettre en œuvre personnellement. Si vous y réfléchissez, vous pouvez demander ce problème sans utiliser BFS.

(Pour faciliter l'explication, le carré est remplacé par un index 0.)

** Il devient symétrique ** lorsque les nombres écrits dans les carrés tracés pour n'importe quel chemin sont arrangés. Tout d'abord, à partir de la condition de ** pour tout chemin **, lors du traçage de $ (0,0) $ à $ (n-1, m-1) $, ** toutes les cellules à la même distance ont le même numéro. Il devient **. De plus, à partir de la condition de ** symétrie **, le nombre de carrés avec une distance de $ i $ et le nombre de carrés avec une distance de $ n + m-2-i $ sont les mêmes **. Par conséquent, pour chacune des cellules $ n \ times m $, ** recherchez les cellules avec la même distance ** avec BFS et stockez-les dans cand pour chaque cellule. En fait, quand elle est à $ (i, j) $, la distance est $ (i, j) $, donc elle peut être calculée sans utiliser BFS.

Après avoir trouvé par BFS, les cellules avec une distance de $ i $ et les cellules avec une distance de $ n + m-2-i $ sont ensuite combinées en une dans cand, et le nombre de 0 et de 1. Comptez et associez le plus petit au plus grand. De plus, quand $ (n + m) % 2 = 0 $, la cellule avec une distance de $ \ frac {n + m-2} {2} $ est ** le centre de n'importe quel chemin, alors de quelle cellule s'agit-il? Le nombre est également bon **.

La mise en œuvre n'est pas difficile si vous savez ** diviser la mise en œuvre en la partie qui divise la masse pour chaque profondeur et la partie qui calcule pour chaque profondeur **.

C.py


from collections import deque
def bfs(dep):
    global a,n,m,ans,d,check,cand
    while len(d):
        cand.append(list(d))
        l=len(d)
        for i in range(l):
            p=d.popleft()
            if p[1]<m-1:
                if not check[p[0]][p[1]+1]:
                    d.append([p[0],p[1]+1])
                    check[p[0]][p[1]+1]=True
            if p[0]<n-1:
                if not check[p[0]+1][p[1]]:
                    d.append([p[0]+1,p[1]])
                    check[p[0]+1][p[1]]=True


for _ in range(int(input())):
    n,m=map(int,input().split())
    a=[list(map(int,input().split())) for i in range(n)]

    d=deque([[0,0]])
    check=[[False]*m for i in range(n)]
    check[0][0]=True
    cand=[]
    bfs(0)

    ans=0
    for i in range((n+m-1)//2):
        x=[a[j[0]][j[1]] for j in cand[i]+cand[n+m-1-1-i]]
        ans+=min(x.count(0),x.count(1))
    print(ans)

Problème D

Cela a provoqué un miracle de dépassement de 2000 ms TL en 1949 ms. Je pensais que ça passerait, mais c'était dangereux.

Tout d'abord, considérez s'il existe $ d \ _1 $ et $ d \ _2 $ tels que $ gcd (d \ _1 + d \ _2, a \ _i) = 1 $. Ici, décomposé en facteurs premiers **, s'il n'y a qu'un seul nombre premier **, $ d \ _1 $ et $ d \ _2 $ sont tous deux des multiples de ce nombre premier, donc $ gcd (d \ _1 + d \ _2, Ce sera un \ _i) \ neq 1 $.

Par conséquent, dans ce qui suit, nous considérons les conditions lorsqu'il y a deux nombres premiers ou plus lorsque $ a \ _i $ est factorisé. À ce moment, j'ai pensé que ~~ ** devrait être ajouté en sélectionnant de manière appropriée des nombres premiers arbitraires ** ~~, mais c'est une erreur totale.

Ici, je suis venu avec la classification des cas par pair et bizarrerie, en faisant attention à ** addition . Premièrement, dans le cas d'un nombre impair, le plus petit $ a, b $ peut être sélectionné parmi les nombres premiers (impairs) inclus dans la factorisation première, et la somme est paire. De plus, ce nombre pair peut être exprimé comme $ \ frac {a + b} {2} \ fois 2 $, mais il est inférieur à $ \ frac {a + b} {2} $ et est inclus dans la factorisation première de $ a \ _i $. Il n'y a que $ a $ premiers, mais $ \ frac {a + b} {2} $ et $ a $ sont premiers l'un par rapport à l'autre, et 2 n'est pas inclus dans la factorisation première de $ a \ _i $, donc $ a, b $ est la solution $ d \ _1, d \ _2 $ ( attention au cas extrême des petits nombres! **).

Ensuite, dans le cas d'un nombre pair, si vous sélectionnez un nombre impair pour $ d \ _1 et d \ _2 $, la somme sera un nombre pair, donc $ d \ _1 $ vaut 2, $ d \ _2 $ est un nombre impair pratique. Doit être sélectionné. À ce stade, vous pouvez sélectionner $ d \ _2 $ (multiplié par tous les nombres impairs autres que 2) (** faites attention au cas extrême d'un grand nombre! **). En effet, pour le moment, $ d \ _1 + d \ _2 $ ne peut être divisé par aucun nombre premier inclus dans la factorisation première de $ a \ _i $.

(Il allait de soi s'il s'agissait d'un nombre impair, mais s'il s'agissait d'un nombre pair, il pourrait être difficile d'interpréter la condition selon laquelle il devrait être différent de tout nombre premier **. Cette zone semble familière.)

De ce qui précède, nous connaissons les cas de pair et impair, nous pouvons donc trouver la solution. En outre, bien que cela ne soit pas mentionné ci-dessus comme explicite, la vitesse est augmentée par le tamis Eratostenes afin de rendre logarithmique la quantité de calcul de la factorisation première.

D.cc


//Options de débogage:-fsanitize=undefined,address

//Optimisation du compilateur
#pragma GCC optimize("Ofast")

//Inclure etc.
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;

//macro
//pour boucle
//L'argument est(Variables dans la boucle,Amplitude de mouvement)Ou(Variables dans la boucle,Premier numéro,Nombre d'extrémités)、のどちらOu
//Les variables de boucle sans D sont incrémentées de 1 et les variables de boucle avec D sont décrémentées de 1.
//FORA est une gamme de déclaration(Si c'est difficile à utiliser, effacez-le)
#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 est un conteneur tel que vector
#define ALL(x) x.begin(),x.end() 
#define SIZE(x) ll(x.size()) 
//constant
#define INF 1000000000000 //10^12:∞
#define MOD 1000000007 //10^9+7:Droit commun
#define MAXR 10000000 //10^5:Portée maximale de la baie
//Abréviation
#define PB push_back //Insérer
#define MP make_pair //constructeur de paires
#define F first //Le premier élément de paire
#define S second //Le deuxième élément de paire

//MAXR=10^Notez que c'est 5
#define PN 1 //La marque du nombre premier est 1

vector<ll> PN_chk(MAXR+1,PN);//0-indexed(0~MAXR)

//Un ensemble qui stocke les nombres premiers inclus dans la factorisation première
set<ll> prime;

//O(MAXR)
void init_eratosthenes(){
    ll MAXRR=sqrt(MAXR)+1;
    //Il se décompose en facteurs premiers de 2 nombres ou plus, de sorte qu'il peut être ignoré.
    PN_chk[0]=0;PN_chk[1]=0;
    FOR(i,2,MAXRR){
        //Un nombre premier s'il est supposé être un nombre premier à votre arrivée
        //Marquer un multiple d'un nombre premier car il est divisible par ce nombre premier
        if(PN_chk[i]==1) FOR(j,i,ll(MAXR/i)){PN_chk[j*i]=i;}
    }
}

//O(logn)
//Puisqu'il s'agit d'une carte, le premier est déjà aligné
//Il n'y en a que deux
void prime_factorize(ll n){
    if(n<=1) return;
    //if(SIZE(prime)==2)return;
    //Si 1, n est un nombre premier
    if(PN_chk[n]==1){prime.insert(n);return;}
    //Les nombres marqués sont des nombres premiers
    prime.insert(PN_chk[n]);
    //Considérez le nombre de nombres marqués divisé par n
    prime_factorize(ll(n/PN_chk[n]));
}

signed main(){
    //Code pour accélérer la saisie
    //ios::sync_with_stdio(false);
    //cin.tie(nullptr);
    init_eratosthenes();
    ll n;cin>>n;
    vector<ll> a(n);REP(i,n)cin>>a[i];
    vector<ll> ans0(n,-1);
    vector<ll> ans1(n,-1);
    REP(i,n){
        if(a[i]%2==1){
            prime_factorize(a[i]);
            if(SIZE(prime)>1){
                ans0[i]=*prime.begin();
                ans1[i]=*++(prime.begin());
            }
            prime.clear();
        }else{
            prime_factorize(a[i]);
            if(SIZE(prime)>1){
                ans0[i]=2;ans1[i]=1;
                for(auto j=++prime.begin();j!=prime.end();j++){
                    ans1[i]*=(*j);
                }
            }
            prime.clear();
        }
    }
    REP(i,n){
        if(i==n-1)cout<<ans0[i]<<"\n";
        else cout<<ans0[i]<<" ";
    }
    REP(i,n){
        if(i==n-1)cout<<ans1[i]<<"\n";
        else cout<<ans1[i]<<" ";
    }
}

E problème

Je n'ai pas pu le résoudre dans le concours, alors j'y ai pensé après le concours. Ce n'était pas aussi difficile que ce à quoi je m'attendais, je veux donc pouvoir laisser beaucoup de temps avant le problème E.

Au cours de l'expérience, j'ai remarqué que ** la limite de la plage que peut prendre la fin de la section divisée est assez stricte **. De plus, comme il est difficile de penser où $ min $ apparaîtra en considérant le plus petit $ j $ de $ b \ _j $, nous avons décidé de considérer ** du plus grand $ j $ de ** $ b \ _ j $ . ( Scan de l'autre côté! **).

À ce stade, la plage possible de la valeur à l'extrémité gauche de l'intervalle peut être déterminée ** indépendamment et de manière unique **.

(1) Qu'y a-t-il à l'extrême droite? ** $ a \ _i = b \ _j $ tient, et le plus grand $ i $ ** est à l'extrême droite. De plus, lorsque $ a \ _i <b \ _j $ tient dans un endroit plus grand que $ i $, la condition de $ min $ n'est pas satisfaite, donc il y a 0 façons.

(2) Qu'y a-t-il à l'extrême gauche? (À la condition que ce soit le même que ou à gauche de l'extrême droite) ** $ a \ _i <b \ _j $ est +1 à $ i $ qui tient pour la première fois ** .. De plus, lorsque cela est vrai avec $ j = 0 $, la condition de $ min $ n'est pas satisfaite, il y a donc 0 façons.

Notez également que lorsque ** $ j = 0 , il n'y a qu'une seule extrémité gauche ( a \ _0 $) **. De plus, pour (1) et (2), l'instruction while est utilisée pour réduire $ i $ de $ a \ _i $ pour parcourir la plage la plus à gauche de la section, mais ** pendant le scan, $ j \ neq Si vous scannez tout $ a \ _i $ avec 0 $, il y a 0 façons car ** ne correspond pas au thème.

En faisant attention aux cas d'angle ci-dessus, si vous trouvez l'intervalle de la valeur la plus à gauche possible dans chaque $ j $, vous pouvez trouver la solution en la multipliant.

E.py


mod=998244353
n,m=map(int,input().split())
a=list(map(int,input().split()))
b=list(map(int,input().split()))
ans=1
i=n-1
for j in range(m-1,-1,-1):
    l,r=-1,-1
    while i!=-1:
        if a[i]<b[j]:
            print(0)
            exit()
        if a[i]==b[j]:
            r=i
            break
        i-=1
    else:
        print(0)
        exit()
    while i!=-1:
        if a[i]<b[j]:
            l=i+1
            if j==0:
                print(0)
                exit()
            break
        i-=1
    else:
        if j!=0:
            print(0)
            exit()
    if j!=0:
        ans*=(r-l+1)
        ans%=mod
    #print(l,r)
print(ans)

Après problème F

Je vais sauter cette fois

Recommended Posts

Code de l'éducation forces Round 93 Bacha Review (8/17)
Code de l'éducation forces Round 91 Bacha Review (7/28)
Code de l'éducation forces Round 88 Bacha Review (8/4)
Code de l'éducation forces Round 86 Bacha Review (9/17)
Code de l'éducation forces Round 89 Bacha Review (9/8)
Code de l'éducation forces Round 92 Bacha Review (7/30)
Code de l'éducation forces Round 90 Bacha Review (8/19)
Codeforces Round # 658 (Div.2) Examen Bacha (7/29)
Codeforces Round # 654 (Div.2) Critique Bacha (8/18)
Codeforces Round # 594 (Div.2) Examen Bacha (10/29)
Codeforces Round # 609 (Div.2) Critique Bacha (10/8)
Codeforces Round # 597 (Div.2) Examen Bacha (10/27)
Codeforces Round # 666 (Div.2) Examen Bacha (9/2)
Codeforces Round # 651 (Div.2) Critique Bacha (8/20)
Codeforces Round # 659 (Div.2) Critique Bacha (8/5)
Codeforces Round # 479 (Div.3) Examen Bacha (9/25)
Codeforces Round # 603 (Div.2) Examen Bacha (10/15)
Codeforces Round # 600 (Div.2) Examen Bacha (10/21)
Codeforces Round # 481 (Div.3) Examen Bacha (9/24)
Codeforces Round # 639 (Div.2) Examen Bacha (9/4)
Codeforces Round # 612 (Div.2) Examen Bacha (10/2)
Codeforces Round # 521 (Div.3) Examen Bacha (10/9)
Codeforces Round # 652 (Div.2) Examen Bacha (8/24)
Codeforces Round # 673 (Div.2) Examen Bacha (10/22)
Codeforces Round # 606 (Div.3) Examen Bacha (10/13)
Codeforces Round # 613 (Div.2) Examen Bacha (10/1)
Codeforces Round # 665 (Div.2) Examen Bacha (8/23)
Codeforces Round # 592 (Div.2) Examen Bacha (11/03)
Codeforces Round # 662 (Div.2) Critique Bacha (8/8)
Codeforces Round # 618 (Div.2) Examen Bacha (9/26)
Codeforces Round # 648 (Div.2) Critique Bacha (9/5)
Codeforces Round # 676 (Div.2) Examen Bacha (10/31)
Codeforces Round # 486 (Div.3) Examen Bacha (9/23)
Codeforces Round # 671 (Div.2) Examen Bacha (9/22)
Codeforces Round # 669 (Div.2) Examen Bacha (9/9)
Codeforces Round # 672 (Div.2) Examen Bacha (10/16)
Codeforces Round # 638 (Div.2) Examen Bacha (9/16)
Codeforces Round # 663 (Div.2) Examen Bacha (8/13)
Codeforces Round # 668 (Div.2) Examen Bacha (9/7)
Codeforces Round # 663 (Div.2) Examen Bacha (8/16)
Codeforces Round # 609 (Div.2) Examen Bacha (10/6)
Codeforces Round # 645 (Div.2) Critique Bacha (9/10)
Codeforces Round # 664 (Div.2) Examen Bacha (8/13)
Codeforces Round # 660 (Div.2) Critique Bacha (8/4)
Code de l'Éducation Forces Round 87
Codeforces Round # 643 (Div.2) Révision
Codeforces Round # 679 (Div.2) Révision (10/25)
Codeforces Round # 657 (Div.2) Révision
Codeforces Beta Round # 13
Codeforces Beta Round # 1
Codeforces Beta Round # 2
DP100 Question Bacha Review 1 ~ 10 (8 / 26,27)
Codeforces Round # 626 B.Compte des sous-rectangles
Codeforces Round # 609 (Div.2) (jusqu'à B)