Codeforces Round # 486 (Div.3) Examen Bacha (9/23)
Les résultats de cette fois
Impressions de cette époque
** J'ai perdu une heure et demie si j'avais corrigé le problème D pour toujours **. J'ai évité le problème E parce que je pensais que c'était gênant, mais en conséquence, j'ai pu le résoudre si je classais correctement les cas, donc je suis déçu. Je n'ai pas pu trouver de cas de coin ou de bogue dans les problèmes D et E parce que je n'ai pas pu utiliser mes réflexions jusqu'à présent, alors j'organiserai mon esprit pour pouvoir les utiliser la prochaine fois.
Problème A
Puisque nous voulons que les notes soient différentes, nous comptons le nombre de types de notes dans la structure ** set et déterminons si elle dépasse ** $ k $. Si c'est $ k $ ou plus, les morceaux $ k $ appropriés sont affichés. J'ai utilisé l'index ici pour le rendre plus facile à implémenter, mais une méthode différente est meilleure en termes de montant de calcul (je ne le montrerai pas ici, mais vous pouvez le faire avec $ O (k) $).
A.py
n,k=map(int,input().split())
a=list(map(int,input().split()))
b=list(set(a))
if len(b)>=k:
print("YES")
ans=[]
for i in range(k):
ans.append(a.index(b[i])+1)
print(" ".join(map(str,ans)))
else:
print("NO")
Problème B
Lorsqu'il y a un ordre de chaîne qui satisfait le sujet, toute chaîne (sauf la première chaîne) a la chaîne précédente comme sous-chaîne, donc ** cet ordre de chaîne est dans l'ordre croissant de longueur ** (Cela peut être montré par la méthode $ \ parce que $ absurdity).
Par conséquent, la chaîne de caractères donnée doit être corrigée par ordre croissant de longueur, et elle doit être jugée par si chacun est inclus dans la chaîne de caractères immédiatement précédente. À ce stade, le montant du calcul est de $ O (N ^ 2) $.
B.py
n=int(input())
a=[input() for i in range(n)]
a.sort(key=lambda x:len(x))
for i in range(n-1):
if a[i] not in a[i+1]:
print("NO")
break
else:
print("YES")
for i in range(n):
print(a[i])
Problème C
Sélectionnez deux séquences et extrayez un élément de chacune pour trouver celle avec la même somme. Ici, il y a des sommes $ n \ _i $ pour extraire un élément de la séquence de $ i $ e longueur $ n \ _i $ selon l'élément extrait. Aussi, à partir de la contrainte, $ \ sum \ _ {i = 1} ^ {k} {n \ _i} \ leqq 2 \ fois 10 ^ 5 $, donc ** cette somme peut être énumérée en entier **.
Ici, la somme lorsque le $ j $ ème élément de la séquence $ i $ th longueur $ n \ _i $ est extrait est (la somme de la $ i $ ème séquence) - (l'élément $ j $ ème). Value), et si la somme de chaque séquence est calculée à l'avance, elle peut être calculée par $ O (\ sum \ _ {i = 1} ^ {k} {n \ _ i}) $. De plus, si vous placez le dictionnaire $ m $ comme vecteur qui stocke la clé comme valeur somme de la séquence et la valeur comme "valeur (index de la séquence, index de l'élément extrait)", la somme des séquences obtenues précédemment peut être ordonnée dans l'ordre. Peut être stocké. En outre, à ce stade, s'il y a deux séquences ** ou plus avec la même clé mais des index différents **, elle peut être sortie en tant que réponse. Au contraire, s'il n'y en a pas avec deux ou plus, No doit être affiché.
(Je ne m'en suis pas rendu compte, mais je pouvais l'écrire en Python. Pourquoi l'ai-je écrit en C ++ ...?)
C.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
signed main(){
//Code pour accélérer la saisie
//ios::sync_with_stdio(false);
//cin.tie(nullptr);
ll k;cin>>k;
map<ll,vector<pair<ll,ll>>> m;
REP(i,k){
ll ni;cin>>ni;
vector<ll> a(ni);REP(j,ni)cin>>a[j];
ll s=0;REP(j,ni)s+=a[j];
REP(j,ni){
m[s-a[j]].PB(MP(i+1,j+1));
}
}
FORA(i,m){
if(SIZE(i.S)>1){
map<ll,ll> x;
//Élimine le même nombre de lignes
FORA(j,i.S){
x[j.F]=j.S;
}
if(SIZE(x)>1){
auto y=x.begin();
cout<<"YES"<<endl;
cout<<y->F<<" "<<y->S<<endl;
y++;
cout<<y->F<<" "<<y->S<<endl;
return 0;
}
}
}
cout<<"NO"<<endl;
}
Problème D
(Les opérations effectuées par Union Find sont considérées comme presque constantes et le montant du calcul est indiqué.)
Si vous le faites avec l'image de la sélection d'un sous-ensemble dans l'ensemble, vous pourriez être accro au marais. Notez que la distance entre les deux points est de 2 $ ^ d $ et le maximum est de 2 $ \ fois 10 ^ 9 $, il vous suffit donc de regarder ** $ d = $ 0 ~ 30 **.
À ce stade, envisagez de trouver le plus grand sous-ensemble ** pour chaque $ d $. De plus, en faisant attention à un certain point $ x $, les points séparés par $ 2 ^ d $ sont $ x-2 ^ d, x + 2 ^ d $, et si tous les points sont gérés par ensemble, ils sont ** séparés. Vous pouvez vérifier s'il y a un point avec $ O (\ log {n}) $ ** ($ O (n \ log {n}) $ si vous vérifiez à tout moment). Par conséquent, en utilisant ** Union Find pour connecter des points séparés de 2 ^ d $ **, vous pouvez créer des sous-ensembles de points comme indiqué ci-dessous.
De plus, je voudrais dire que tous les points inclus dans le sous-ensemble de la figure ci-dessus sont inclus dans le sous-ensemble qui satisfait le sujet, mais ** je ne peux inclure que 3 points **. En effet, si les points sont plus grands que 3, un ensemble de points dont la distance n'est pas la puissance de 2 est toujours inclus.
À partir de ce qui précède, Union Find est effectuée pour chacun des $ d = $ 0 à 30 (lorsque les éléments de l'ensemble sont disposés dans l'ordre croissant, l'espacement des coordonnées est $ 2 ^ d $), et un système d'ensembles premiers est obtenu. S'il y en a au moins un, ** affiche trois points adjacents ** lorsque l'ensemble est disposé par ordre croissant, et s'il y en a au moins un avec 2 éléments (qui ne remplit pas les conditions ci-dessus), l'ensemble Deux points inclus dans sont en sortie, et dans d'autres cas, un point approprié doit être produit.
De plus, comme je voulais spécifier l'index lors de l'union des points, j'ai préparé ʻindcomme une carte ** qui donne un index à la valeur, et j'ai changé l'index de la valeur de l'élément au moment de la sortie. J'ai préparé «val» comme vecteur. De plus, comme l'ensemble obtenu par UnionFind est dans l'ordre croissant d'index **, il est nécessaire de corriger **val dans l'ordre croissant et de le stocker dans ʻind ** pour correspondre à l'ordre croissant des valeurs **. il y a. (Je n'ai pas remarqué que je n'avais pas trié par ordre croissant, et cela m'a pris plusieurs heures pour déboguer ... C'était une erreur que j'ai remarquée au stade de la discussion, donc quand je suis impatient, je veux ** comparer avec mes propres pensées **. .)
9/25 post-scriptum
En fait, si vous faites attention uniquement au fait qu'il y en a au plus trois, vous pouvez l'implémenter légèrement et à grande vitesse simplement en regardant de côté. J'aurais aimé avoir remarqué cela. Voir le deuxième code Python.
D.cc
//Options de débogage:-fsani
//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
//Ci-dessous, l'ensemble premier et l'arbre représentent la même chose.
class UnionFind {
public:
vector<ll> parent; //parent[i]Est le parent de i
vector<ll> siz; //Un tableau représentant la taille de l'ensemble premier(Initialiser avec 1)
map<ll,vector<ll>> group;//Tableau associatif géré pour chaque ensemble premier(key est le parent de chaque ensemble premier, value est un tableau d'éléments de cet ensemble premier)
ll n;//Nombre d'éléments
//constructeur
UnionFind(ll n_):parent(n_),siz(n_,1),n(n_){
//Initialiser en tant que racine de tous les éléments est lui-même
for(ll i=0;i<n;i++){parent[i]=i;}
}
//Récupère la racine de l'arborescence à laquelle appartient la donnée x(Effectuer également la compression d'itinéraire)
ll root(ll x){
if(parent[x]==x) return x;
return parent[x]=root(parent[x]);//La valeur de l'expression d'affectation étant la valeur de la variable affectée, l'itinéraire peut être compressé.
}
//Fusionner les arbres x et y
void unite(ll x,ll y){
ll rx=root(x);//x racine
ll ry=root(y);//racine de y
if(rx==ry) return;//Quand dans le même arbre
//Fusionner un petit ensemble dans un grand ensemble(Fusionné de ry à rx)
if(siz[rx]<siz[ry]) swap(rx,ry);
siz[rx]+=siz[ry];
parent[ry]=rx;//Lorsque x et y ne sont pas dans le même arbre, attachez la racine y ry à la racine x rx
}
//Déterminer si l'arbre auquel appartiennent x et y est le même
bool same(ll x,ll y){
ll rx=root(x);
ll ry=root(y);
return rx==ry;
}
//Obtenez la taille de l'ensemble premier de x
ll size(ll x){
return siz[root(x)];
}
//Regroupez chaque ensemble principal
void grouping(){
//Effectuez d'abord la compression d'itinéraire
REP(i,n)root(i);
//Gérer avec la carte(Utiliser la version par défaut)
REP(i,n)group[parent[i]].PB(i);
}
void clear(){
for(ll i=0;i<n;i++){parent[i]=i;}
siz=vector<ll>(n,1);
group.clear();
}
};
signed main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
ll n;cin>>n;
set<ll> x;
//Ind pour valeur
map<ll,ll> ind;
//Valeur pour ind
vector<ll> val(n);
REP(i,n){
ll y;cin>>y;
x.insert(y);
val[i]=y;
}
sort(ALL(val));
REP(i,n){
ind[val[i]]=i;
}
vector<ll> v(1,0);
pair<ll,vector<ll>> ans=MP(1,v);
UnionFind uf(n);
REP(i,31){
uf.clear();
FORA(j,val){
if(x.find(j+(1LL<<i))!=x.end()){
uf.unite(ind[j],ind[j+(1LL<<i)]);
}
}
uf.grouping();
for(auto j=uf.group.begin();j!=uf.group.end();j++){
if(SIZE(j->S)>ans.F){
//Ne dépasse pas 3
//Non trié(val est)hein? ?? ?? ?? ?? ?? ??
if(ans.F==1){
if(SIZE(j->S)==2){
vector<ll> w(2);
w={j->S[0],j->S[1]};
ans=MP(2,w);
}else{
cout<<3<<endl;
cout<<val[j->S[0]]<<" "<<val[j->S[1]]<<" "<<val[j->S[2]]<<endl;
return 0;
}
}
if(ans.F==2){
if(SIZE(j->S)>2){
cout<<3<<endl;
cout<<val[j->S[0]]<<" "<<val[j->S[1]]<<" "<<val[j->S[2]]<<endl;
return 0;
}
}
}
}
}
cout<<ans.F<<endl;
REP(i,ans.F){
if(i==ans.F-1){
cout<<val[ans.S[i]]<<endl;
}else{
cout<<val[ans.S[i]]<<" ";
}
}
}
D.py
n=int(input())
x=list(map(int,input().split()))
y=set(x)
ans=[x[0]]
for d in range(31):
e=2**d
for i in range(n):
if x[i]-e in y and x[i]+e in y:
print(3)
print(x[i]-e,x[i],x[i]+e)
exit()
elif x[i]-e in y:
ans=[x[i],x[i]-e]
elif x[i]+e in y:
ans=[x[i],x[i]+e]
if len(ans)==2:
print(2)
print(ans[0],ans[1])
else:
print(1)
print(ans[0])
E problème
Ce n'est pas difficile à penser, mais j'ai pensé que c'était un problème gênant pour terminer la mise en œuvre.
Premièrement, la condition pour être un multiple de 25 est lorsque les deux derniers chiffres sont l'un de 00 $, 25, 50, 75 $. Il va de soi que vous devriez ** échanger et rapprocher les chiffres le plus possible **. Cependant, s'il y a un nombre donné dans le chiffre le plus significatif **, 0 peut venir dans le chiffre le plus significatif, il est donc nécessaire de séparer les cas à ce moment. De plus, dans le cas de 00 $, seuls deux du même nombre doivent être pris en compte et aucun numéro n'est attribué au chiffre le plus significatif, j'ai donc décidé de ** le considérer séparément des trois autres **.
Premièrement, s'il n'y a qu'un seul chiffre, il est difficile de faire la distinction entre les cas, donc -1 est émis à l'avance. Et même s'il se compose de deux chiffres, ** il était difficile de distinguer les cas ** (WA a également été émis), donc 0 est affiché pour 25,75,50 $ et 1 pour 52,57 $.
Sur cette base, trouvez le nombre minimum de swaps requis pour amener 25,50,75 $ au dernier chiffre. Ici, la fonction pour trouver le nombre minimum de fois est $ calc1 $, et les arguments sont $ x, y $ ($ (x, y) = (2,5), (5,0), (7,5) $) .. Tout d'abord, lors de l'échange, nous voulons savoir à quelle distance il est du chiffre le moins significatif, nous voyons donc le nombre donné comme un tableau de nombres et le retournons (appelons-le $ m $). Ici, si $ x et y $ ne sont pas inclus dans les chiffres, le nombre minimum de fois n'existe pas et $ inf $ est retourné. Sur cette base, l'indice de $ x, y $ en $ m $ est calculé comme étant $ ix, iy $. De plus, si aucun ** $ x, y $ n'est à l'extrême droite (chiffre le plus significatif) **, il est préférable d'échanger dans l'ordre du chiffre le plus proche du chiffre le moins significatif (le plus petit de $ ix, iy $). , Si $ ix <iy $, le chiffre le moins significatif est inversé tel quel, donc un échange supplémentaire est nécessaire.
Ensuite, considérez ** si l'un ou l'autre est à l'extrême droite **, mais puisque $ x et y $ sont la même opération à l'exception de l'échange entre les chiffres les moins significatifs, $ x $ est à l'extrême droite. L'heure de est considérée ci-dessous. Lorsque $ x $ est à l'extrême droite, regardez du chiffre le plus significatif au dernier chiffre, sélectionnez le premier élément qui n'est pas ** 0 et son index n'est pas $ iy $, et échangez avec le chiffre le plus significatif. Puisque ** est le nombre optimal de fois, échangez-le. De plus, s'il n'y a aucun élément qui n'est pas 0 et que son index n'est pas $ iy $, il renvoie $ inf $ ($ 25,75,50,52,57 $, qui a été initialement exclu comme cas, ** ne satisfait pas cela, donc d'abord L'affaire a été divisée en **.). Et si ce chiffre est $ i $, le nombre d'échanges avec le chiffre le plus significatif peut être facilement calculé. De plus, si ** $ i <iy $, $ iy- = 1 $ sera ajouté par swap lorsque vous portez $ i $ au chiffre supérieur **, alors soyez prudent. Par conséquent, si vous pouvez échanger avec le chiffre le plus significatif, vous pouvez échanger $ iy $ puis $ ix $, et compter le nombre total de swaps.
De plus, si vous souhaitez définir le chiffre le moins significatif sur 00 $, vous pouvez trouver l'index de 00 $ le plus proche du chiffre le moins significatif et le rapprocher du chiffre le moins significatif du chiffre le plus proche. Ce sera une mise en œuvre.
À partir de ce qui précède, le nombre minimum de fois pour chaque cas de 00 $, 25, 50, 75 $ peut être calculé, et le nombre minimum de fois peut être calculé, mais si le nombre minimum de fois est $ inf $, -1 est généré. besoin de le faire.
Étonnamment, c'était un problème qui n'était pas si lourd à mettre en œuvre. Je voudrais faire de mon mieux pour ** mettre en œuvre de tels problèmes ** involontairement.
E.py
n=[int(i) for i in input()]
l=len(n)
#Même si la longueur est de 2
if len(n)==1:
print(-1)
exit()
#Dans ce cas uniquement
if n in [[2,5],[7,5],[5,0]]:
print(0)
exit()
if n in [[5,2],[5,7]]:
print(1)
exit()
inf=10**12
#Si c'est à l'extrême gauche, c'est ennuyeux, alors je vais séparer les cas.(Inverser)
#00 est également divisé en cas
def calc1(x,y):
global n,l,inf
m=n[::-1]
if x not in n or y not in n:
#print(x,y,0)
return inf
ix,iy=m.index(x),m.index(y)
#Sinon à l'extrême droite
if max(ix,iy)<l-1:
if iy<ix:
#print(x,y,1)
return iy+(ix-1)
else:
#print(x,y,2)
return iy+(ix-1)+1
else:
ret=0
#print(ix,iy)
if ix==l-1:
#Regarde à droite et regarde à gauche(0 et pas l'autre à choisir)
for i in range(l-2,-1,-1):
if m[i]!=0 and i!=iy:
break
else:
#print(x,y,3)
return inf
if i<iy:
iy-=1
ret+=(l-1-i)
ix-=1
ret+=(iy+(ix-1))
#print(x,y,4,ret)
return ret
else:
ret+=iy
ret+=(l-1-i)
ix-=1
ret+=(ix-1)
#print(x,y,5,ret)
return ret
else:
#Regarde à droite et regarde à gauche(0 et pas l'autre à choisir)
#La seule possibilité pour l'autre de choisir(Éliminer en premier)
#Fais-le dehors
for i in range(l-2,-1,-1):
if m[i]!=0 and i!=ix:
break
else:
#print(x,y,6)
return inf
if i<ix:
iy-=1
ret+=(l-1-i)
ix-=1
ret+=(iy+(ix-1)+1)
#print(x,y,7,ret)
return ret
else:
ret+=iy
ret+=(l-1-i)
ix-=1
ret+=((ix-1)+1)
#print(x,y,8,ret)
return ret
#À 00
def calc2(x,y):
#Absolument pas à l'extrême droite
global n,l,inf
if n.count(0)<2:
return inf
m=[l-1-i for i in range(l) if n[i]==0][::-1]
return m[0]+m[1]-1
ans=min([calc1(2,5),calc1(7,5),calc1(5,0),calc2(0,0)])
#print([calc1(2,5),calc1(7,5),calc1(5,0),calc2(0,0)])
print(-1 if ans==inf else ans)
Problème F
Je vais sauter cette fois
Recommended Posts