[PYTHON] Codeforces Round # 657 (Div.2) Révision
Les résultats de cette fois
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.
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
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