AtCoder Beginner Contest 126 Revue des questions précédentes
Les résultats de cette fois
Impressions de cette époque
A partir d'aujourd'hui, pour le moment, je voudrais passer à ABC (6 questions) après 126. Personnellement, je pense que le problème est devenu plus sophistiqué ces jours-ci, alors assurez-vous de le porter. Je voudrais le joindre. De plus, cette fois, j'ai pu le terminer complètement. J'ai passé le problème F sans beaucoup de preuves, donc je voudrais le revoir fermement.
Problème A
J'ai oublié la fonction de conversion en minuscules, j'ai donc divisé les cas par A, B ou C. De plus, c'est la fonction inférieure qui se convertit en minuscules, ce qui vous permet d'écrire du beau code (le deuxième code). N'est-ce pas difficile pour un problème?
A.py
n,k=map(int,input().split())
s=input()
if s[k-1]=="A":
print(s[:k-1]+"a"+s[k:])
elif s[k-1]=="B":
print(s[:k-1]+"b"+s[k:])
else:
print(s[:k-1]+"c"+s[k:])
A_shorter.py
n,k=map(int,input().split())
s=input()
print(s[:k-1]+s[k-1].lower()+s[k:])
Problème B
Le mois possible (MM) est 00-12, alors gardez ceci comme candidat pour le mois (cand)
B.py
s=input()
cand={"0"+str(i) if i<10 else str(i) for i in range(1,13)}
if s[:2] in cand and s[2:] in cand:
print("AMBIGUOUS")
elif s[:2] in cand:
print("MMYY")
elif s[2:] in cand:
print("YYMM")
else:
print("NA")
Problème C
J'ai pensé prendre le plafond de log, mais je l'ai évité cette fois car il y a une erreur dans la fraction. Le seul moyen pour Sunuke de gagner est de se présenter jusqu'à ce qu'il soit ** K ou supérieur ** (car si vous le retournez $ \ parce que $, ce sera 0 et vous perdrez). Par conséquent, il suffit de compter le nombre de fois jusqu'à ce qu'il devienne K ou plus, mais comme la valeur des premiers dés peut être de 1 à N, la solution peut être trouvée par $ O (N \ log N) $.
C.py
n,k=map(int,input().split())
ans=0
for i in range(1,n+1):
j,now=0,i
while now<k:
j+=1
now*=2
ans+=(2**(-j))
print(ans/n)
Problème D
Ce n'est pas parce que c'est un arbre que vous devez être prêt, vous devez donc être calme. Sous les contraintes de ce problème, il y a toujours ** une manière de peindre qui rencontre le sujet. Maintenant, concentrons-nous sur un certain pic. A ce moment, on peut dire que les sommets connectés aux sommets sont ** de la même couleur si la longueur du côté reliant les deux sommets est paire, et de couleurs différentes ** si la longueur est impaire. Cela peut être dit à n'importe quel sommet, donc si vous décidez correctement du point de départ et que vous le suivez avec une recherche de priorité de profondeur, vous pouvez trouver la solution avec $ O (M + N) $.
(Le but est de le mettre dans la simple question de ** ce qui se passe à un certain pic **.)
answerD.py
import sys
sys.setrecursionlimit(10**6)
n=int(input())
path=[[] for i in range(n)]
for i in range(n-1):
u,v,w=map(int,input().split())
path[u-1].append((v-1,w%2))
path[v-1].append((u-1,w%2))
ans=[0]+[-1]*(n-1)
def dfs(i):
global n,path,ans
for j in path[i]:
if ans[j[0]]==-1:
if j[1]:
ans[j[0]]=1-ans[i]
dfs(j[0])
else:
ans[j[0]]=ans[i]
dfs(j[0])
dfs(0)
print("\n".join(map(str,ans)))
E problème
C'est beaucoup plus facile à résoudre car il dit qu'il n'y a pas de contradiction dans les conditions données. De plus, comme il n'y a que deux types de chaque carte, je considérerai d'abord la ** recherche complète **, mais je rejetterai cette politique car c'est évidemment impossible.
Ici, il suffit de déterminer si $ A_ {x_i} + A_ {y_i} + Z_i $ est pair, et comme $ Z_i $ est connu, l'un des ** $ A_ {x_i} $ et $ A_ {y_i} $ est Si vous le savez, l'autre sera définitivement décidé **. On voit donc que le numéro de chaque carte est ** déterminé dans une chaîne par les informations connues $ A_ {x_i} + A_ {y_i} + Z_i $ **, donc ** les cartes déterminées dans une chaîne sont du même ensemble. Vous pouvez utiliser Union Find Tree (forêt élémentaire d'ensemble) pour gérer en tant que **. Bien sûr, vous pouvez penser à $ A_ {x_i} + A_ {y_i} + Z_i $ comme unissant $ A_ {x_i} $ et $ A_ {y_i} $.
Aussi, je veux savoir combien d'ensembles premiers il y a dans la ** forêt d'ensembles premiers, donc après avoir utilisé la fonction de regroupement dans Union Find Library Trouvez simplement la taille du groupe.
La mise en œuvre de ceci ressemble à ceci:
De plus, ** combien d'ensembles élémentaires sont dans la forêt ** est, en termes généraux, ** des composants connectés (le plus grand des graphes partiels où il y a un chemin entre deux sommets quelconques). C'est la même valeur que le nombre **, et s'écrit dans cette solution comme cette dernière.
E.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
//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)
//Du constructeur:Initialiser les variables membres après
UnionFind(ll n):parent(n),siz(n,1){
//Initialement initialisé comme la racine de tous les éléments est lui-même
for(ll i=0;i<n;i++){parent[i]=i;}
}
ll root(ll x){ //Récupère la racine de l'arborescence à laquelle appartient la donnée x
if(parent[x]==x) return x;
return parent[x]=root(parent[x]);
//La valeur de l'expression d'affectation sera la valeur de la variable affectée
//Compression de chemin(Rationalisez les calculs en connectant les éléments directement à la racine)Il est réalisé
}
void unite(ll x,ll y){ //Fusionner les arbres x et y
ll rx=root(x);//La racine de x est rx
ll ry=root(y);//y root ry
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
}
bool same(ll x,ll y){//Déterminer si l'arbre auquel appartiennent x et y est le même
ll rx=root(x);
ll ry=root(y);
return rx==ry;
}
ll size(ll x){ //Obtenez la taille de l'ensemble premier de x
return siz[root(x)];
}
//↓ Fonctions qui ne sont pas dans les bibliothèques d'autres personnes mais qui sont utiles
//O(n)Notez que
void grouping(ll n){//Ensembles élémentaires de groupe
REP(i,n){
if(group.find(parent[i])==group.end()){
group[parent[i]]={i};
}else{
group[parent[i]].PB(i);
}
}
}
};
signed main(){
//Code pour accélérer la saisie
//ios::sync_with_stdio(false);
//cin.tie(nullptr);
ll n,m;cin >> n >> m;
UnionFind uf(n);
REP(i,m){
ll x,y,z;cin >> x >> y >> z;
uf.unite(x-1,y-1);
}
REP(i,n)uf.root(i);
uf.grouping(n);
cout << SIZE(uf.group) << endl;
}
Problème F
J'ai fait un modèle pratique et donné une réponse appropriée, donc Answer et [le blog d'ARMERIA](https: // betrue12. Je l'ai examiné en référence à hateblo.jp/entry/2019/05/20/213302). (Cependant, je pense qu'il n'y a pas beaucoup de gens qui ca font des preuves pendant le concours ...?)
Tout d'abord, c'était un problème de $ xor $, j'ai donc décidé d'en décider un pour chaque bit, mais ** j'ai remarqué qu'il y avait trop de motifs et j'ai abandonné ** (si ce n'est pas possible, abandonnez une fois!).
Alors ensuite, j'ai décidé de ** me concentrer sur deux des mêmes entiers **. Ici, ** $ xor $ entre les mêmes entiers devient $ 0 $ **, donc si vous les arrangez pour qu'ils soient appariés les uns aux autres comme indiqué dans la figure ci-dessous, $ xor $ de $ a_i $ à $ a_j $ changera. C'est égal à $ x ou $ de $ a_ {i + 1} $ à $ a_ {j-1} $, et j'ai pensé que ce serait pratique.
De plus, quand $ j-i + 1 $ est même ici, tous les entiers peuvent être regroupés pour faire le $ x ou $ 0 $ entier, donc quand $ K $ est $ 0 $, Construisez comme indiqué ci-dessus avec $ i = 1, j = 2 ^ {M + 1} $.
Je l'ai soumis parce que je pensais qu'il n'y avait que ce modèle, donc il est devenu WA, mais lorsque je ** change et continue à considérer **, j'ai trouvé qu'il y avait aussi un modèle où $ j-i + 1 $ devenait étrange comme le montre la figure ci-dessous. J'ai fait.
À ce stade, en insérant $ K $ entre les deux, comme indiqué dans la figure ci-dessus, il est possible de créer une paire qui satisfait les conditions pour des entiers autres que $ K $ (puisqu'elle est prise en sandwich entre eux, ** $ K $ vaut 0 $ ou plus. Doit être inférieur à 2 $ ^ M $ **.). Ce modèle existe également si le XOR de tous les entiers autres que $ K $ inclus dans la partie entre $ K $ est calculé et devient $ K $.
De plus, il était difficile de penser qu'il existait autre chose que ce motif à symétrie élevée (** ← trop grossier **), j'ai donc pu AC lorsque je l'ai mis à -1 sauf pour les deux motifs ci-dessus. En fait, il peut être prouvé qu'il n'y a pas d'autre modèle, donc il est montré ci-dessous.
<détails> Jusqu'à ce qui précède, nous avons montré qu'il existe une séquence de nombres qui satisfait la condition lorsque $ k = 0 $ ((1)) (le modèle de la première figure). Ici, "Quand $ 0 \ leqq K <2 ^ M $, $ xor $ obtenu en soustrayant $ K $ du nombre de $ 0 $ ou plus et moins de $ 2 ^ M $ devient $ K $. "Exists" (②) est affiché en premier (le modèle dans la deuxième figure), puis il n'y a pas de séquence de nombres qui satisfait la condition lorsque $ k \ geqq 2 ^ M $ (③). Ici, en utilisant que ** $ xor $ de deux entiers consécutifs $ 2a, 2a + 1 $ ($ a $ est un entier) devient 1, ** le nombre entier de $ 0 $ ou plus et moins de $ 2 ^ M $ Pour $ x ou $ de $ M \ geqq 2 $, vous pouvez créer un nombre pair de paires de deux entiers consécutifs $ 2a, 2a + 1 $ ($ a $ est un entier) **. Par conséquent, le total $ xor $ est $ 0 $ car il y a un nombre pair de paires où $ xor $ est $ 1 $ ($ \ car $$ xor $ théorème d'addition). De plus, lorsque le total $ xor $ du nombre de $ 0 $ ou plus et inférieur à 2 $ ^ M $ est de 0 $, $ xor $ excluant $ K $ devient $ K $ **, donc ($ \ parce que $$) On montre que le modèle ci-dessus est valable pour K \ xor \ K = 0 $) et $ M \ geqq 2 $. De plus, lorsque $ M = 0 $ et $ M = 1 $, le nombre de ** total $ xor $ qui est supérieur ou égal à 0 $ $ et inférieur à 2 $ ^ M $ n'est pas 0 $, donc $ xor $ excluant $ K $ est Cela ne devient pas $ K $, et même si vous écrivez des cas possibles, vous ne pouvez pas créer une séquence de nombres qui remplit les conditions. Par conséquent, ② a été affiché. De plus, dans le cas de $ k \ geqq 2 ^ m $, certains bits sont $ M $ ou plus et deviennent 1, mais le nombre de $ 0 $ ou plus et inférieur à $ 2 ^ M $ est de $ M $ ou plus. Il n'y a rien qui devient 1, donc cela n'existe pas non plus dans ce cas. Par conséquent, ③ a été affiché. À partir de (1), (2) et (3) ci-dessus, vous pouvez montrer que votre solution est nécessaire et suffisante.
Recommended Posts
F.py
from itertools import chain
m,k=map(int,input().split())
if k==0:
print(" ".join([str(i) for i in chain(range(0,2**m),range(2**m-1,-1,-1))]))
elif 0<k<2**m:
s=0
for i in range(0,2**m):
if i!=k:
s^=i
if s==k:
print(" ".join([str(i) for i in chain(range(0,k),range(k+1,2**m),[k],range(2**m-1,k,-1),range(k-1,-1,-1),[k])]))
else:
print(-1)
else:
print(-1)
F_shortest.py
m,k=map(int,input().split());x=list(range(2**m));print(*x[::-1]+x if k<1 else x[:k:-1]+x[k-1::-1]+[k]+x[:k]+x[k+1:]+[k]if(k<2**m)&(m>1)else[-1])