[PYTHON] Codeforces Round # 606 (Div.3) Examen Bacha (10/13)
Les résultats de cette fois
Impressions de cette époque
Cette fois, j'ai dû résoudre le problème jusqu'à E, mais je n'ai pas pu le résoudre car j'avais perdu ma concentration. ** Vous devriez pouvoir résoudre le problème E en le paraphrasant un par un **, mais je suis très déçu car je n'ai pas pu le résoudre dans le cadre du concours.
Problème A
Puisqu'il s'agit d'un nombre positif qui répète le même nombre, considérez combien de façons il y a dans les neuf cas de 11 $ 11,22… 22,…, 99… 99 $. Ici, même si $ n = 10 ^ 9 $, il n'y a que 9 façons pour chacune, vous pouvez donc compter celles sous $ n $.
A.py
for _ in range(int(input())):
n=int(input())
ans=0
for i in range(1,10):
cand=[]
while True:
cand.append(str(i))
x=int("".join(cand))
if x<=n:
ans+=1
else:
break
print(ans)
Problème B
Tous les éléments pairs et égaux sont divisés par 2, donc si vous ne conservez que le type d'élément **, vous pouvez obtenir le nombre de simulations. Par conséquent, préparez $ a $ comme une structure $ set $ contenant les éléments (pairs) à manipuler.
Lorsque vous travaillez sur les éléments à l'intérieur de $ a $, l'opération réduit uniquement le nombre de chacun. Par conséquent, si vous effectuez l'opération ** qui divise par 2 dans l'ordre du plus grand nombre inclus dans ** $ a $, ce sera le nombre minimum d'opérations. De plus, si le résultat de la division par 2 est impair, il n'est pas nécessaire de le réinsérer dans $ a $. Par conséquent, le nombre minimum d'opérations dans le sujet est le nombre d'opérations jusqu'à ce que $ a $ devienne vide après avoir effectué ces opérations dans l'ordre.
B.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 t;cin>>t;
REP(i,t){
ll n;cin>>n;
set<ll> a;
REP(j,n){
ll x;cin>>x;
if(x%2==0)a.insert(x);
}
ll ans=0;
//cout<<SIZE(a)<<endl;
while(SIZE(a)>0){
ll y=*--a.end();a.erase(y);
y/=2;
if(y%2==0)a.insert(y);
ans++;
//cout<<SIZE(a)<<endl;
}
cout<<ans<<endl;
}
}
Problème C
Considérez une chaîne qui n'inclut pas un et deux à l'exception de quelques caractères. Ici, si ** un et deux existent sans chevauchement **, vous pouvez supprimer respectivement le n et le w du milieu afin que la chaîne de caractères après l'extraction n'inclut pas celui et le deux. Je vais. À l'heure actuelle, un et deux ne sont ** rien de nouveau **.
Le problème, c'est quand ** un et deux se chevauchent et deviennent deux **. À ce stade, en supprimant o, la chaîne de caractères twone devient twne, et ni un ni deux inclus dans cette chaîne de caractères ne sont inclus dans la chaîne de caractères après sa suppression. De plus, il n'y a rien de nouveau qu'un et deux peuvent faire comme avant.
De plus, ce qui devrait être affiché est le nombre de fois à exclure et l'index des caractères à exclure. Ici, ** l'index s'écarte de l'état initial lorsque le caractère est effectivement supprimé **, alors vérifiez-le comme le caractère à supprimer au lieu de le supprimer. Aussi, pour éviter ** le comptage en double ** dans le cas de deux et deux, un, scannez d'abord celui qui devient deux et vérifiez à l'avance, puis comptez celui qui devient deux, un. Fait.
C.py
import sys
input=sys.stdin.readline
for _ in range(int(input())):
s=input()
n=len(s)
check=[0]*n
ans=[]
for i in range(n):
if s[i:i+5]=="twone":
ans.append(str(i+3))
for j in range(i,i+5):
check[j]=1
for i in range(n):
if check[i]:
continue
if s[i:i+3]=="one":
ans.append(str(i+2))
if s[i:i+3]=="two":
ans.append(str(i+2))
print(s.count("one")+s.count("two")-s.count("twone"))
print(" ".join(ans))
Problème D
Malgré le fait que la considération et la mise en œuvre sont différentes **, j'étais impatient car il y avait un échantillon pour une raison quelconque car j'ai fait une erreur à deux endroits. C'est bien de pouvoir trouver les bugs après ça, mais je veux réduire ces erreurs pour ne pas m'impatienter.
En termes simples, il s'agit d'échanger des chaînes binaires. Considérez également le cas où les chaînes de caractères peuvent être inversées afin qu'elles ne correspondent pas, et le nombre d'inversions est aussi petit que possible alors que les caractères peuvent être pressés. Puisqu'il est inutile d'exécuter l'opération inverse sur la même chaîne de caractères plus d'une fois ici, considérez que l'opération inverse est effectuée au plus une fois pour chaque chaîne de caractères.
De plus, puisque seule l'opération inverse peut être effectuée, les caractères intermédiaires sont considérés comme un motif de ** 00,01,10,11 $, qu'ils puissent ou non être supprimés **. Ici, pour $ 00,11 $, l'opération de retournement n'affecte pas la compression, donc l'opération de retournement ** n'est effectuée qu'entre ** 01 $ et 10 $. De plus, si un seul de 00 $ et 11 $ est inclus ici, la compression ne peut pas être explicite, donc -1 est affiché.
Ici, supposons que $ 01 $ est $ a $ et $ 10 $ est $ b $, et $ a > b $ (la même chose est vraie pour $ a \ <b $, et $ a = b $ va de soi. Ça tiens). Ici, compte tenu des conditions qui peuvent être écrasées, c'est quand il est aligné avec $ 01 → 10 → 01 →… $ ou $ 10 → 01 → 01 →… $, et cela devrait être ** $ ab \ leqq 1 $ ** est. Pour ce faire, il vous suffit d'inverser $ [\ frac {a-b} {2}] $ sur ** $ 01 $ **, mais vous ne pouvez pas sélectionner des chaînes identiques lorsqu'elles sont inversées. De plus, le nombre de chaînes de caractères qui correspondent entre le modèle $ 01 $ et le modèle $ 10 $ par l'opération d'inversion est de $ l $ chacune ($ \ car $ ** l'inversion est une opération réversible **, donc $ l $ suffit. Je le ferai). Par conséquent, considérant que la différence est réduite de 2m $ lorsque le motif $ m $ de $ 01 $ est inversé, elle est inversée lorsque $ al \ <[\ frac {ab} {2}] \ times 2 $. Tu peux faire.
Par conséquent, il est possible de juger s'il sera possible ou non d'inverser et de supprimer, et à ce moment-là, le nombre d'éléments nécessitant une opération d'inversion peut également être obtenu, de sorte que vous pouvez sélectionner à partir de 01 $ pour ce nombre d'éléments. Pour le moment, veuillez noter que seuls ceux qui ne correspondent pas à ce qui est inclus dans ** 10 $ sont sélectionnés **.
D.py
for _ in range(int(input())):
n=int(input())
s=[input() for i in range(n)]
t=set(s)
a,b,c,d=set(),set(),set(),set()
for i in range(n):
if s[i][0]=="0":
if s[i][-1]=="0":
c.add(i)
else:
a.add(i)
else:
if s[i][-1]=="0":
b.add(i)
else:
d.add(i)
l=set()
for i in range(n):
if (i in a or i in b) and (s[i][::-1] in t):
l.add(i)
la,lb,lc,ld,ll=len(a),len(b),len(c),len(d),len(l)
#print(la,lb,lc,ld,ll)
if la==0 and lb==0:
if lc==0 or ld==0:
print(0)
else:
print(-1)
continue
if lb>la:
if lb-ll//2<(lb-la)//2*2:
print(-1)
continue
x=(lb-la)//2
print(x)
if x==0:
continue
ans=[]
for i in b:
if i not in l:
ans.append(str(i+1))
x-=1
if x==0:
break
print(" ".join(ans))
elif la>lb:
if la-ll//2<(la-lb)//2*2:
print(-1)
continue
x=(la-lb)//2
print(x)
if x==0:
continue
ans=[]
for i in a:
if i not in l:
ans.append(str(i+1))
x-=1
if x==0:
break
print(" ".join(ans))
else:
print(0)
E problème
Je suis très déçu car il semble être bientôt résolu. J'ai mis à jour en me référant à l'article de Hamayanhamayan.
Un tel problème ** a tendance à faire exploser la quantité de calcul lors de la recherche à partir de chaque sommet **, c'est donc un modèle typique à paraphraser en utilisant les caractéristiques du graphique.
Ici, en d'autres termes, vous devez passer à la fois par $ A et B $, en d'autres termes, si vous pouvez atteindre sans passer par $ A ou B $, ou si vous pouvez atteindre en utilisant uniquement $ A ou B $ * * Exclus ** en cas (** Considérez le refus de condition! **). Dans le premier cas, les sommets du composant de connexion lorsque tous les côtés connectés à ** $ A et B $ sont supprimés **, donc pour exclure le premier cas, ** les sommets contenus dans les différents composants de connexion ** Pensez-y.
Dans ce dernier cas, cela n'a pas fonctionné car j'ai pensé au composant de connexion lorsque j'ai utilisé le côté qui se connecte uniquement à $ A $ (ou $ B $), mais ** j'envisagerai d'utiliser le composant de connexion plus tôt ** Est bon (** Cohérence des considérations! **). Ici, le graphe lorsque tous les côtés connectés à $ A et B $ sont supprimés n'est pas connecté, mais chaque composant connecté est directement connecté à ** $ A ou B $ par sa définition **. Profitez-en. Pour le moment, il n'y a que trois modèles dans lesquels chaque composant de connexion est connecté à la fois à $ A et B $ (①), connecté uniquement à $ A $ (②), et connecté uniquement à $ B $ (③). Il n'y en a pas. Parmi ceux-ci, seuls les motifs (2) et (3) passent toujours par $ A et B $ pour les deux chemins reliant les deux points (vous pouvez facilement le découvrir en essayant les six méthodes).
Par conséquent, (le nombre de sommets inclus dans le composant concaténé du motif ②) $ \ times $ (le nombre de sommets inclus dans le composant concaténé du motif ③) renvoie ceci comme réponse.
E.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
//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,set<ll>> group; //Gérer par set(key:Représentant de l'ensemble, valeur:Un tableau d'éléments de l'ensemble)
ll n; //Nombre d'éléments
//constructeur
UnionFind(ll n_):n(n_),parent(n_),siz(n_,1){
//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]].insert(i);
}
//Supprimer le système prime set et initialiser
void clear(){
REP(i,n){parent[i]=i;}
siz=vector<ll>(n,1);
group.clear();
}
};
signed main(){
//Code pour accélérer la saisie
//ios::sync_with_stdio(false);
//cin.tie(nullptr);
ll t;cin>>t;
REP(_,t){
ll n,m,a,b;cin>>n>>m>>a>>b;a--;b--;
UnionFind uf(n);
set<ll> otheredgesA,otheredgesB;
REP(i,m){
ll u,v;cin>>u>>v;u--;v--;
if(u!=a and u!=b and v!=a and v!=b){
uf.unite(u,v);
}
if(u==a){
otheredgesA.insert(v);
}
if(v==a){
otheredgesA.insert(u);
}
if(u==b){
otheredgesB.insert(v);
}
if(v==b){
otheredgesB.insert(u);
}
}
uf.grouping();
ll countA=0;ll countB=0;
FORA(i,uf.group){
bool checkA=false;bool checkB=false;
if(i.F==a or i.F==b)continue;
FORA(j,i.S){
if(otheredgesA.find(j)!=otheredgesA.end()){
checkA=true;
}
if(otheredgesB.find(j)!=otheredgesB.end()){
checkB=true;
}
}
if(!checkB){
countA+=SIZE(i.S);
}
if(!checkA){
countB+=SIZE(i.S);
}
}
cout<<countA*countB<<endl;
}
}
Problème F
Je vais sauter cette fois.
Recommended Posts