[PYTHON] Codeforces Round # 643 (Div.2) Révision
Les résultats de cette fois
Impressions de cette époque
J'ai commencé AtCoder il y a environ un an, mais j'ai décidé d'apparaître dans Kodofo, qui a entendu dire qu'il y avait de nombreux concours. Je ne vais pas le faire pour le moment car il y a trop de problèmes pour répondre aux questions du passé, mais je reviendrai à chaque fois quand le temps n'est pas trop tard. C'est la deuxième fois, et je ne suis pas habitué au format Kodofo et aux phrases de questions en anglais, mais je pense que j'obtiens de bonnes notes. De plus, ABC fournit essentiellement une explication AC toutes questions, mais Kodofo essaiera d'expliquer à la légère uniquement les problèmes qui peuvent être résolus et les problèmes susceptibles d'être résolus bientôt.
Problème A
Quand je l'ai vu pour la première fois ** j'étais impatient parce que je ne pouvais pas du tout comprendre la loi **.
Cependant, si même un 0 est mélangé dans le chiffre lorsqu'il est converti en décimal, $ minDigit (a_n) = 0 $, et $ k \ geqq n $ ne change pas la valeur de $ a_k $. .. De plus, il est prédit que $ minDigit (a_n) = 0 $ sera bientôt atteint ($ \ car $ ne sera probablement pas $ minDigit (a_n) \ neq0 $ à n'importe quel n), donc $ minDigit (a_n) = 0 Quand il est devenu $, $ a_k $ à ce moment-là était sorti et cassé.
Puisqu'il s'agit d'un problème de programmation de compétition, il y a un certain nombre de problèmes qui peuvent être résolus sans preuve rigoureuse, alors j'aimerais le résoudre. (Bien que cela doive être prouvé dans ma tête)
A.py
t=int(input())
for i in range(t):
a,k=map(int,input().split())
for i in range(k-1):
ax=str(a)
l,r=int(min(ax)),int(max(ax))
if l==0:
print(a)
break
else:
a+=(l*r)
else:
print(a)
Problème B
J'ai mal compris que je devais inclure tout le monde dans le groupe ... Puisqu'il n'est pas nécessaire d'inclure tout le monde dans le groupe, sélectionnez dans l'ordre les personnes ayant le plus petit "nombre de personnes requises pour le groupe". À ce stade, le nombre de personnes sélectionnées en tant que groupe doit être égal ou supérieur au "nombre requis de personnes dans le groupe" de chaque personne, donc s'il n'est pas supérieur au "nombre requis de personnes dans le groupe", ajoutez autant de personnes que nécessaire au groupe. Faire. Et si le groupe remplit les conditions, il peut être ajouté au nombre de groupes du sujet. En Python, j'ai réussi le prétest, donc j'ai fait attention, mais c'est devenu TLE. Il peut être plus fiable de lancer C ++ pour une quantité aussi marginale de calcul.
B.py
t=int(input())
for i in range(t):
n=int(input())
e=sorted(list(map(int,input().split())))
ans,now=0,0
while True:
nowx=now+e[now]
while nowx<n:
if nowx-now<e[nowx-1]:
nowx=now+e[nowx-1]
else:
break
if nowx>=n:
if nowx==n:
if nowx-now>=e[nowx-1]:
ans+=1
break
else:
ans+=1
now=nowx
print(ans)
answerB.cc
//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
#define MAX(x) *max_element(ALL(x)) //Trouvez la valeur maximale
#define MIN(x) *min_element(ALL(x)) //Trouvez la valeur minimale
//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
signed main(){
ll t;cin >> t;
vector<ll> answers(t);
REP(i,t){
ll n;cin >> n;
vector<ll> e(n);REP(j,n)cin >> e[j];
sort(ALL(e));
ll ans=0;ll now=0;
while(true){
ll nowx=now+e[now];
while(nowx<n){
if(nowx-now<e[nowx-1]){
nowx=now+e[nowx-1];
}else{
break;
}
}
if(nowx>=n){
if(nowx==n){
if(nowx-now>=e[nowx-1]){
ans++;
}
}
break;
}else{
ans++;
now=nowx;
}
}
answers[i]=ans;
}
REP(i,t){
cout << answers[i] << endl;
}
}
Problème C
Je suis heureux d'avoir pu réfléchir correctement à ce problème. Premièrement, pour être considéré comme un triangle, (somme des deux plus petits côtés)> (côté le plus grand) doit tenir.
De plus, $ A \ leqq x \ leqq B \ leqq y \ leqq C \ leqq z \ leqq D $ tient entre les trois côtés du triangle $ x, y, z $, donc $ x + y> z $ J'en ai juste besoin. De plus, $ A + B \ leqq x + y \ leqq B + C $ tient, et il est clair que ce candidat x + y est de l'ordre d'environ $ 10 ^ 5 $, donc c'est l'original que x + y est décidé. J'ai pensé que je devrais trouver le candidat pour z par $ O (1) $ (** Il est naturel de penser que je veux en corriger un car il y a trois inconnues **, si x est fixe, si z est fixe À la suite d'expériences telles que, nous sommes arrivés au résultat qu'il est préférable de fixer avec x + y.).
Si vous y réfléchissez, vous pouvez savoir combien de z sont plus petits que x + y, mais il y a un piège ici. Les candidats pour la valeur de x + y sont de l'ordre d'environ 10 $ ^ 5 $, mais il existe plusieurs paires de x et y pour la valeur de x + y. Le traitement de ces multiples choses peut être bien pensé en dessinant la figure ci-dessous. (Je suis content d'avoir pu calmer cette considération. J'ai déjà eu un problème similaire avec AtCoder et je n'ai pas pu le résoudre ...)
Par conséquent, les candidats pour la paire (x, y) lorsque $ x + y = k $ peuvent être trouvés, et le candidat pour z à ce moment est comme indiqué dans l'image ci-dessous.
Par conséquent, la réponse est la somme du produit du nombre de paires de (x, y) lorsque $ x + y = k $ et du nombre de candidats pour z.
C.py
a,b,c,d=map(int,input().split())
xy=dict()
for i in range(a+b,b+c+1):
f=min(i-a-b+1,b+c-i+1)
f=min(f,b-a+1,c-b+1)
xy[i]=f
ans=0
for i in range(a+b,b+c+1):
if i>d:
ans+=(xy[i]*(d-c+1))
elif i<=c:
continue
else:
ans+=(xy[i]*(i-c))
print(ans)
Problème D
Je ne suis pas sûr de la preuve car j'ai sauté le processus de réflexion et résolu le problème.
Cependant, Petya peut ** créer une séquence pratique **, ce qui conduit à l'idée que Petya veut ** créer une séquence pratique pour gagner. Aussi, c'est bien s'il n'y a pas de total de k ou Sk pour le tableau partiel, donc si vous faites attention à sa symétrie, ** le sous-tableau dont le total est proche de 0 et le total est proche de S J'ai pensé qu'il serait bon de supposer un tableau ** dans lequel seul un tableau partiel existe.
Un tel tableau ressemblerait à la figure ci-dessous (n en majuscules et minuscules), en notant que tous les éléments du tableau sont supérieurs ou égaux à 1 et inférieurs ou égaux à S-1 et que la somme de tous les éléments est S. Ne vous inquiétez pas de sa fermeture.)
En supposant un tableau comme celui montré ci-dessus, la somme des sous-tableaux peut être $ 1 $ à $ n-1, S- (n-1) $ à $ S $, et ** la symétrie peut également être considérée. J'ai pensé que ce serait pratique parce que c'est **. Aussi, pour faire cette séquence commode (Petya gagne), il suffit qu'il y ait un k qui satisfait $ n-1 <k <S- (n-1) $, et qu'un tel k existe. La condition pour est $ n-1 <S- (n-1) $, et une fois implémentée, elle devient comme suit (quand $ \ parce que $ k satisfait cela, il est clair que Sk satisfait également cela. ).
answerD.py
n,s=map(int,input().split())
if n<s-(n-1):
print("YES")
print(" ".join(map(str,[1 if i!=n-1 else s-(n-1) for i in range(n)])))
print(n)
else:
print("NO")
Problème E
J'ai vu des solutions pour la recherche de trois minutes, mais je n'ai pas encore fait la recherche de trois minutes, donc je vais sauter cette fois.
Problème F
Comme pour le problème E, je pense que je manque encore de capacités, alors je vais sauter cette fois.
Recommended Posts