Codeforces Round # 657 (Div.2) Révision

Les résultats de cette fois

スクリーンショット 2020-07-20 7.53.01.png

Impressions de cette époque

J'ai rejoint codeforces pour la première fois en 2 mois. R J'étais préparé pour un temps froid car je n'ai pas pu résoudre le problème pendant longtemps, mais pour une raison quelconque, il a fait assez chaud. Il est peut-être venu au sol.

Quoi qu'il en soit, il a changé de couleur pour la première fois depuis longtemps, donc je pense que c'était une bonne expérience. Je ferai de mon mieux pour viser AtCoder: Blue, Coderforces: Purple.

Problème A

J'ai été placé dans le problème A, donc j'ai perdu mon calme et je n'ai pas pu le résoudre. En principe, rien n'est difficile ...

Ce n'est pas trop difficile car le montant de calcul de $ O (t \ times n ^ 2) $ est autorisé. Tout d'abord, vérifiez quelle partie de la chaîne "abacaba" (ci-après appelée la chaîne S) est susceptible d'apparaître. Si la chaîne de caractères S apparaît plus d'une fois lorsqu'elle est cochée, "Non" est affiché, et si la chaîne de caractères S n'apparaît qu'une seule fois, remplacez "?" Par "d ~ z" et sortez. C'est bon. Dans d'autres cas, nous vérifierons s'il y a quelque chose qui peut être une chaîne de caractères S en changeant le "?", Ce qui ne créera qu'une ** chaîne de caractères S **.

De plus, il sera facile de comprendre si vous séparez le contrôle de la sous-chaîne qui peut être la chaîne de caractères S et s'il n'y a qu'une ** chaîne de caractères S **.

A.py


#Vérifiez où il y a une possibilité d'abaca
#Étrange
#Erreurs d'index ...
a=["a","b","a","c","a","b","a"]
t=int(input())
for _ in range(t):
    n=int(input())
    s=list(input())
    check=[0]*(n-6)            
    for i in range(n-6):
        for j in range(i,i+7):
            if s[j]!=a[j-i] and s[j]!="?":
                break
        else:
            if s[i:i+7]==a:
                check[i]=2
            else:
                check[i]=1
    if check.count(2)>1:
        print("No")
        continue
    elif check.count(2)==1:
        print("Yes")
        print(("".join(s)).replace("?","z"))
        continue
    #?Changement et un seul modèle
    g=False
    for i in range(n-6):
        if check[i]==1:
            f=False
            cand=[a[j-i] if i<=j<=i+6 else s[j] if s[j]!="?" else "z" for j in range(n)]
            for j in range(n-6):
                if i!=j:
                    for k in range(j,j+7):
                        if cand[k]!=a[k-j]:
                            break
                    else:
                        f=True
            if not f:
                print("Yes")
                print("".join(cand))
                g=True
                break
    if not g:print("No")

Problème B

Tout d'abord, considérons la plage qui peut être exprimée par $ a, b, c $. C'est plus de $ l $ et moins de $ r $, appliquons donc chacun à la formule donnée. Ensuite, cela devient comme suit.

スクリーンショット 2020-07-20 8.50.57.png

Sur cette base, envisagez de fixer l'un de ① et ②. ** ② est continu et facile à penser **, alors pensez à réparer ①.

Alors, ① est idéalement proche de m, donc il devient $ ceil (\ frac {m} {a}) \ fois un $ ou $ floor (\ frac {m} {a}) \ fois un $.

Par conséquent, si la différence entre cette valeur et la valeur absolue de $ m $ est $ r-l $, alors $ b et c $ existent également et la réponse est.

Vous pouvez rechercher ceci pour n'importe quel $ a $ et trouver la réponse.

De plus, le montant du calcul est $ O (t \ times (r-l)) $, et il est écrit dans la phrase de question que la réponse est toujours obtenue, alors écrivez le code comme suit.

B.py


t=int(input())
for _ in range(t):
    l,r,m=map(int,input().split())
    f=False
    for a in range(l,r+1):
        n1,n2=m//a,-((-m)//a)
        if l-r<=m-n1*a<=r-l:
            for c in range(l,r+1):
                b=m-n1*a+c
                if l<=b<=r:
                    if m+c-b!=0:
                        print(a,b,c)
                        f=True
                        break
        if f:break
        if l-r<=m-n2*a<=r-l:
            for c in range(l,r+1):
                b=m-n2*a+c
                if l<=b<=r:
                    if m+c-b!=0:
                        print(a,b,c)
                        f=True
                        break
        if f:break

Problème C

Je ne pense pas que la politique soit difficile, mais est-ce à peine en Python? ?? J'ai peur, alors j'ai utilisé C ++.

Je ne peux pas tout essayer car $ n $ est gros. Cependant, après un certain nombre d'essais, il vous suffit de ** sélectionner un certain $ b_i $ **. J'ai pensé qu'il serait préférable de prendre le maximum $ b_i $, mais l'échantillon ne correspondait pas. Si vous y réfléchissez bien, vous devez sélectionner $ a_i $ lorsque vous sélectionnez ** $ b_i $ **, et selon la valeur, il n'est pas optimal de prendre le maximum $ b_i . Par conséquent, j'ai décidé d'essayer toutes les façons ( m $ façons) de continuer à prendre quel $ b_i $.

De plus, lorsque ** $ b_i $ n'est pas pris **, $ n \ leqq m $ tient, et dans ce cas, vous pouvez sélectionner $ n $ à partir du plus grand de $ a $. De plus, $ a_i $ doit être organisé par ordre croissant, mais comme $ a_i $ correspondant à ** $ b_i $ sera requis plus tard **, préparez un tableau $ c $ dans lequel $ a_i $ est organisé par ordre croissant. Faire.

Ici, lors de la sélection de $ b_i $, ceux qui sont plus grands que $ b_i $ dans $ a $ sont également les meilleurs pour maximiser la somme, et les éléments du tableau $ c $ sont plus que les éléments recherchés par upper_bound. Tout ce que vous avez à faire est de sélectionner. À ce stade, il est inefficace de calculer la somme de ces éléments à chaque fois, elle est donc calculée par la somme cumulée **.

De plus, vous devez sélectionner $ a_i $ en même temps que $ b_i $, et ** $ a_i $ sera classé selon qu'il a été sélectionné plus tôt. Vous pouvez répéter ce qui précède et trouver la réponse maximale.

C.cc


//Pour l'optimisation du compilateur
#pragma GCC optimize("Ofast")
//Comprendre(Ordre alphabétique)
#include<algorithm>//sort,Recherche de bisection,Tel
#include<bitset>//Jeu de bits de longueur fixe
#include<cmath>//pow,journal etc.
#include<complex>//Nombre complexe
#include<deque>//File d'attente d'accès double
#include<functional>//trier plus
#include<iomanip>//setprecision(Erreur de sortie en virgule flottante)
#include<iostream>//Entrée sortie
#include<iterator>//Régler l'opération(Ensemble de produits,Ensemble de somme,Ensemble de différences, etc.)
#include<map>//map(dictionnaire)
#include<numeric>//iota(Génération d'une chaîne entière),pgcd et lcm(c++17)
#include<queue>//queue
#include<set>//ensemble
#include<stack>//empiler
#include<string>//Chaîne
#include<unordered_map>//Carte avec itérateur mais sans ordre
#include<unordered_set>//Il y a un itérateur mais l'ordre n'est pas maintenu défini
#include<utility>//pair
#include<vector>//Tableau de longueur variable

using namespace std;
typedef long long ll;

//macro
//pour la relation de 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.
#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 est un conteneur tel que vector
#define ALL(x) x.begin(),x.end() //Je souhaite omettre des arguments tels que le tri
#define SIZE(x) ll(x.size()) //taille à la taille_Changement de t à ll
//constant
#define INF 1000000000000 //10^12:Valeur extrêmement élevée,∞
#define MOD 1000000007 //10^9+7:Droit commun
#define MAXR 100000 //10^5:Portée maximale de la baie(Utilisé pour l'énumération des nombres premiers, etc.)
//Abréviation
#define PB push_back //Insérer dans le vecteur
#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
#define Umap unordered_map
#define Uset unordered_set

signed main(){
    //Code pour accélérer la saisie
    //ios::sync_with_stdio(false);
    //cin.tie(nullptr);
    ll t;cin>>t;
    while(t--){
        ll n,m;cin>>n>>m;
        vector<ll> a(m);
        vector<ll> b(m);
        vector<ll> c(m);
        REP(i,m){cin>>a[i]>>b[i];c[i]=a[i];}
        //Type trié dans un
        sort(ALL(c));
        //Trouvez la somme cumulée de c(De la direction opposée)
        vector<ll> d(m+1);d[m]=0;
        REPD(i,m)d[i]=c[i]+d[i+1];
        ll ans=0;
        //Lors du choix d'un seul
        if(n<=m)ans=max(ans,d[m-n]);
        //Quel élément b choisir
        REP(i,m){
            auto as=upper_bound(ALL(c),b[i]);
            ll anum=distance(c.begin(),as);
            if(a[i]>b[i] and m-anum<=n)ans=max(d[anum]+b[i]*(n-(m-anum)),ans);
            if(a[i]<=b[i] and m-anum<=n-1)ans=max(d[anum]+b[i]*(n-(m-anum)-1)+a[i],ans);
        }
        cout<<ans<<endl;
    }
}

Problème après D

Je vais sauter cette fois

Recommended Posts

Codeforces Round # 643 (Div.2) Révision
Codeforces Round # 679 (Div.2) Révision (10/25)
Codeforces Round # 657 (Div.2) Révision
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 # 610 (Div.2) Critique Bacha (10/5)
Codeforces Round # 479 (Div.3) Examen Bacha (9/25)
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 # 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 # 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 # 675 (Div.2) Examen Bacha (10/30)
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 93 Bacha Review (8/17)
Code de l'éducation forces Round 94 Bacha Review (9/3)
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 # 609 (Div.2) (jusqu'à B)
Code de l'Éducation Forces Round 87
Codeforces Beta Round # 13
Codeforces Beta Round # 1
Codeforces Beta Round # 2
Codeforces Round # 626 B.Compte des sous-rectangles