[PYTHON] Codeforces Round # 662 (Div.2) Critique Bacha (8/8)
Les résultats de cette fois
Impressions de cette époque
J'étais impatient avec le problème A et j'ai fait une erreur dans l'expérience et j'ai pris du temps. ** Si l'expérience est erronée ** Je n'ai pas pu m'en occuper jusqu'à présent, alors j'aimerais être prudent. J'ai passé environ une heure sur A, mais une telle ** ingéniosité qui ne rentre pas dans le marais ** (** loin du problème **, ** peut être fondamentalement mauvaise ou mauvaise mise en œuvre Je voudrais considérer **, etc.). Je pense que de tels modèles peuvent être collectés dans le passé Bachacon et les concours, alors j'aimerais le faire quand je pourrai faire un ** résumé de toutes les erreurs que j'ai faites jusqu'à présent **.
(De plus, l'examen a été retardé. Je voudrais être prudent, mais lorsque d'autres tâches se chevauchent ...)
Problème A
Tout d'abord, pensez à expérimenter des problèmes semblables à des casse-tête. Cependant, j'ai ** fait une erreur dans l'expérience de puzzle **. Tant que c'est embarrassant.
Si vous effectuez l'expérience avec précision, ce sera comme indiqué dans la figure ci-dessous.
Si vous pouvez faire cette expérience correctement, vous savez que $ [\ frac {n} {2}] $ est probablement la réponse, mais vous devez faire attention à la structure récursive. En d'autres termes, le cadre extérieur doit être considéré séparément, et cela devient comme suit.
A.py
def f(x):return x//2+1
for i in range(int(input())):
n=int(input())
print(f(n))
Problème B
Je pense qu'un problème de compatibilité descendante est apparu dans ABC.
Le problème est de combiner les planches, vous devez faire un carré et un rectangle. Cependant, les cartes ne peuvent pas être connectées ou coupées.
Ici, un carré peut être fait en utilisant ** 4 planches de même longueur **, et un rectangle peut être fait en utilisant ** 2 jeux de 2 planches de même longueur **. Par conséquent, il suffit d'enregistrer quatre cartes ou plus et deux cartes ou plus, respectivement, et d'avoir une ou plusieurs cartes avec quatre cartes ou plus et deux cartes ou plus avec deux cartes ou plus. Cependant, s'il y a ** 8 planches ou plus de même longueur **, vous pouvez créer un carré et un rectangle avec seulement ces planches, et s'il y a ** 6 planches ou plus de même longueur **, Vous pouvez créer deux côtés, carré et rectangulaire, vous devez donc également penser à ces cas.
Par conséquent, à partir de ce qui précède, 2 cartes ou plus, 4 cartes ou plus, 6 cartes ou plus et 8 cartes ou plus sont enregistrées en tant qu'ensembles («d2», «d4», «d6», «d8». Ce faisant, vous pouvez juger si vous pouvez créer un carré et un rectangle. De plus, pour le moment, je pense qu'il serait plus facile de mettre en œuvre ** si le tableau avait été défini comme un élément **, je voudrais donc essayer d'être prudent jusqu'à présent **.
B.py
n=int(input())
a=list(map(int,input().split()))
q=int(input())
d=dict()
for i in range(n):
if a[i] in d:
d[a[i]]+=1
else:
d[a[i]]=1
d2,d4,d6,d8=set(),set(),set(),set()
for i in d:
if d[i]>=8:
d8.add(i)
elif d[i]>=6:
d6.add(i)
elif d[i]>=4:
d4.add(i)
elif d[i]>=2:
d2.add(i)
for i in range(q):
s,x=input().split()
x=int(x)
if s=="+":
if x in d:
d[x]+=1
if d[x]==2:
d2.add(x)
elif d[x]==4:
d2.remove(x)
d4.add(x)
elif d[x]==6:
d4.remove(x)
d6.add(x)
elif d[x]==8:
d6.remove(x)
d8.add(x)
else:
d[x]=1
else:
d[x]-=1
if d[x]==1:
d2.remove(x)
elif d[x]==3:
d4.remove(x)
d2.add(x)
elif d[x]==5:
d6.remove(x)
d4.add(x)
elif d[x]==7:
d8.remove(x)
d6.add(x)
if len(d8)>0:
print("YES")
elif len(d6)>=2:
print("YES")
elif len(d6)==1 and len(d4)+len(d2)>0:
print("YES")
elif len(d4)>=2:
print("YES")
elif len(d4)==1 and len(d2)>=2:
print("YES")
else:
print("NO")
Problème C
(Les expériences et les illustrations étaient bien vivantes dans ce problème.)
Lorsque vous mangez des gâteaux en séquence, pensez à laisser le plus de temps possible pour manger le même gâteau.
Ici, ** un grand nombre de gâteaux a un intervalle de temps étroit **, c'est donc ce grand nombre de gâteaux qui ** régule la distance maximale que vous voulez trouver **. Par conséquent, j'ai pensé qu'il serait préférable de décider de la position dans l'ordre du gâteau avec le plus grand nombre. Sur la base de cette hypothèse, j'ai examiné le premier échantillon ci-dessous.
7
1 7 1 6 4 4 6
Dans l'exemple ci-dessus, les trois nombres 1, 4, 6 sont deux fois chacun, et 7 n'est qu'une fois, alors pensez à décider de l'emplacement de 1, 4, 6. À ce moment, la distance maximale de 3 peut être atteinte en agencant comme indiqué sur la figure ci-dessous.
Les points ici sont "pour placer 1-4-6 comme ** morceaux ** sans déplacer l'ordre" et "pour placer chaque morceau aux deux extrémités". Cela permet à chaque numéro d'être placé aussi loin que possible. J'ai également essayé de voir si la même chose était valable pour le deuxième échantillon ci-dessous.
8
1 1 4 6 4 6 4 7
Dans cet échantillon, les gâteaux les plus nombreux apparaissent dans 3 des 4 gâteaux. À ce stade, la distance maximale de 2 peut être atteinte en agencant comme indiqué sur la figure ci-dessous.
Ici, 4 est ** placé aux deux extrémités et entre eux aussi uniformément que possible **. De plus, en ajustant l'ordre des gâteaux restants (1 → 6 dans la figure ci-dessus), la distance maximale ne sera pas affectée. Par conséquent, vous devez considérer ** uniquement le gâteau avec le plus grand nombre **, et le type de gâteau avec le plus grand nombre est $ m $, et le nombre est $ k $, comme indiqué dans la figure ci-dessous.
Donc, puisque nous voulons trouver la distance dans ce problème, la réponse est (masse longueur-1) = $ [\ frac {n-m} {k-1}] -1 $.
C.py
from collections import Counter
for _ in range(int(input())):
n=int(input())
s=list(map(int,input().split()))
d=Counter(s)
d=list(d.items())
d.sort(reverse=True,key=lambda x:x[1])
l=len(d)
now=[1,d[0][1]]
for i in range(1,l):
if now[1]==d[i][1]:
now[0]+=1
else:
break
k=now[1]
m=now[0]
print((n-m)//(k-1)-1)
Problème D
Je n'ai pas pu le réussir pendant le concours, mais je suis content d'avoir pu le résoudre peu de temps après. ** Je me précipite à l'avant et je ne peux pas passer de temps sur les problèmes à l'arrière.
Tout d'abord, j'ai écrit le même chiffre ** que l'énoncé du problème. Dans la figure ci-dessus, vous pouvez voir que quatre modèles de robe ont été générés qui correspondent au thème, le centre étant une grille rouge. De plus, le nombre de modèles de vêtements centrés sur une certaine grille peut être compté dans quatre directions dans l'ordre, et peut être recherché sous la forme de BFS.
De plus, comme les robes ne contiennent que le même alphabet (lettres minuscules), il est possible de rechercher le nombre de patrons de robe centrés sur chaque grille pour chaque alphabet dans environ $ O ((n \ fois m) ^ 2) $. est. Cependant, si rien n'est fait, la recherche ne sera pas terminée dans le délai imparti et la zone de recherche sera évidemment couverte lors du comptage, alors réduisez le montant du calcul à environ ** $ O (n \ fois m) $ **. Penser à. De plus, je voulais permettre de ** rechercher chaque alphabet à la fois ** pour environ $ O (n \ fois m) $.
Dans ce qui précède, lors de la recherche, on considère que le nombre de motifs vestimentaires centrés sur chaque grille est ** enregistré sur la grille **, donc si l'enregistrement dans l'exemple suivant est fait à la main, l'enregistrement pour a sera Ce sera comme suit.
6 6
zbaagd
baaacd
aaaaae
eaaadc
cdafed
aecdae
| 0 | 0 | 1 | 1 | 0 | 0 |
|---|---|---|---|---|---|
| 0 | 1 | 2 | 1 | 0 | 0 |
| 1 | 2 | 3 | 2 | 1 | 0 |
| 0 | 1 | 2 | 1 | 0 | 0 |
| 0 | 0 | 1 | 0 | 0 | 0 |
| 1 | 0 | 0 | 0 | 1 | 0 |
Tout d'abord, tous les a sont ** 1 ou plus **. De plus, s'il y a un 0 dans l'une des quatre directions ** (ou si un a est à la toute fin), il peut être déterminé comme 1. Aussi, il semble difficile de décider immédiatement 2 ou 3, mais je me suis rendu compte qu'il semble que je puisse décider dans l'ordre de ** 1 → 2 → 3 →… **.
En d'autres termes, si les quatre directions sont ** 1, alors 2 et si les quatre directions sont 2, alors 3 ... En d'autres termes, après avoir décidé du point de départ pour devenir 1, vous pouvez effectuer une recherche avec le montant du calcul de $ O (N \ fois M) $ en utilisant BFS.
De plus, étant donné que les contraintes de temps sont assez strictes, il est nécessaire de concevoir des moyens tels que (1) utiliser C ++, (2) réutiliser le vecteur ** et (3) transmettre les informations de la grille dans ** paire au deque utilisé dans BFS.
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 100000 //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
//paire au lieu de vecteur
//Ne pas générer de vecteur à chaque fois
signed main(){
//Code pour accélérer la saisie
ios::sync_with_stdio(false);
cin.tie(nullptr);
ll ans=0;
ll n,m;cin>>n>>m;
vector<string> x(n);REP(i,n)cin>>x[i];
vector<char> alph(26);alph[0]='a';
for(ll i=1;i<26;i++){
alph[i]=alph[i-1];
alph[i]++;
}
vector<vector<ll>> y(n,vector<ll>(m,0));
vector<vector<bool>> check(n,vector<bool>(m,true));
FORA(i,alph){
REP(j,n)REP(k,m)y[j][k]=(x[j][k]==i);
REP(j,n)REP(k,m)check[j][k]=(x[j][k]!=i);
ll d=2;
deque<pair<ll,ll>> b;
REP(j,n){
REP(k,m){
if(j==0 or j==n-1 or k==0 or k==m-1){
if(y[j][k]){
check[j][k]=true;
b.PB(MP(j,k));
}
}else if(!(y[j-1][k] and y[j+1][k] and y[j][k-1] and y[j][k+1])){
if(y[j][k]){
check[j][k]=true;
b.PB(MP(j,k));
}
}
}
}
while(SIZE(b)){
ll l=SIZE(b);
REP(_,l){
pair<ll,ll> c=*(b.begin());b.pop_front();
if(c.F>0){
if(! check[c.F-1][c.S]){
check[c.F-1][c.S]=true;
y[c.F-1][c.S]=d;
b.PB(MP(c.F-1,c.S));
}
}
if(c.F<n-1){
if(! check[c.F+1][c.S]){
check[c.F+1][c.S]=true;
y[c.F+1][c.S]=d;
b.PB(MP(c.F+1,c.S));
}
}
if(c.S>0){
if(! check[c.F][c.S-1]){
check[c.F][c.S-1]=true;
y[c.F][c.S-1]=d;
b.PB(MP(c.F,c.S-1));
}
}
if(c.S<m-1){
if(! check[c.F][c.S+1]){
check[c.F][c.S+1]=true;
y[c.F][c.S+1]=d;
b.PB(MP(c.F,c.S+1));
}
}
}
d+=1;
}
REP(j,n)REP(k,m)ans+=y[j][k];
}
cout<<ans<<endl;
}
Après le problème E
Je vais sauter cette fois
Recommended Posts