Codeforces Round # 597 (Div.2) Examen Bacha (10/27)
Les résultats de cette fois
Impressions de cette époque
Je ne pouvais pas du tout résoudre D. Cela semble être un problème typique, alors je voudrais y réfléchir et l'utiliser la prochaine fois.
Problème A
Tout ce que vous avez à faire est de déterminer que $ a et b $ sont élémentaires l'un par rapport à l'autre. ** Tout ce que vous avez à faire est de vous souvenir du théorème chinois du reste **.
A.py
from math import gcd
for _ in range(int(input())):
a,b=map(int,input().split())
if gcd(a,b)==1:
print("Finite")
else:
print("Infinite")
Problème B
Si les variables suivantes $ r, p, s $ valent 0 ou plus, nous ne remplirons d'abord que les coups qui peuvent battre l'adversaire **. Si vous pouvez gagner avec plus de la moitié lorsque vous remplissez les coups gagnants, vous pouvez sortir après avoir décidé les coups restants de manière appropriée. Même si vous ne pouvez pas gagner plus de la moitié, NON est émis car le choix actuel est le meilleur choix.
Vous pouvez l'implémenter innocemment.
B.py
from collections import deque
for _ in range(int(input())):
n=int(input())
r,p,s=map(int,input().split())
t=input()
ans=["" for i in range(n)]
w=0
for i in range(n):
if t[i]=="R":
if p>0:
ans[i]="P"
p-=1
w+=1
elif t[i]=="P":
if s>0:
ans[i]="S"
s-=1
w+=1
else:
if r>0:
ans[i]="R"
r-=1
w+=1
if w<-(-n//2):
print("NO")
else:
ansp=deque()
for i in range(r):
ansp.append("R")
for i in range(p):
ansp.append("P")
for i in range(s):
ansp.append("S")
for i in range(n):
if ans[i]=="":
ans[i]=ansp.popleft()
print("YES")
print("".join(ans))
Problème C
J'ai oublié de diviser par ** 10 $ ^ 9 + 7 $ ** ...
Le problème du comptage de chaînes comme celui-ci est ** il vaut mieux compter dans un ordre fixe **. De plus, à ce moment-là, vous pouvez en faire un DP en définissant correctement l'état **. En d'autres termes, le DP suivant est défini.
$ dp [i]: = $ (nombre total de chaînes possibles jusqu'au $ i $ ème caractère (indexé en 1))
L'initialisation devrait être $ dp [0] = 1, dp [1] = 1 $, et à ce moment, compte tenu de la transition vers le caractère $ i $ ème, ce sera comme suit.
(1) Lorsque le caractère $ i $ ème n'est pas un caractère converti
Compte tenu des deux transitions ci-dessus, si vous n'oubliez pas de diviser par 10 $ ^ 9 + 7 $, la réponse sortira. De plus, puisque $ w et m $ changent toujours en ** $ uu et nn $ respectivement, il est nécessaire de sortir 0 si $ w $ ou $ m $ est inclus.
C.py
mod=10**9+7
s=input()
n=len(s)
dp=[0]*(n+1)
dp[0]=1
dp[1]=1
for i in range(2,n+1):
dp[i]+=dp[i-1]
dp[i]%=mod
#print(s[i-2:i])
if s[i-2:i]=="uu" or s[i-2:i]=="nn":
dp[i]+=dp[i-2]
dp[i]%=mod
#print(dp)
if ("w" in s)or("m" in s):
print(0)
else:
print(dp[n])
Problème D
Je pense qu'il est impossible de résoudre sans voir l'arbre de la superficie minimale. Je ne l'ai résolu qu'une fois il y a environ 9 mois, donc je n'y ai pas pensé du tout. Cependant, il a été beaucoup organisé cette fois-ci, donc je pense que cela sera résolu la prochaine fois.
** Pour maintenir les coûts aussi bas que possible ** Nous connecterons les zones entre les villes ou construirons une centrale électrique. À ce stade, il peut être considéré comme le problème de l'arbre de la superficie totale minimale ** car il vise à minimiser le coût lors de la connexion des bords entre les villes. Aussi, en ce qui concerne le coût de construction d'une centrale électrique, en introduisant un nouveau sommet (** super apex **) et en considérant le côté pondéré entre le sommet d'origine, il peut être réduit au problème de la résolution de l'arbre de la superficie totale minimale. Je peux.
En d'autres termes, ** vous pouvez créer le sommet de la centrale électrique et définir le coût de la i $ ème ville sur $ c \ _i $ **. De cette façon, la solution peut être trouvée simplement en considérant l'arbre global minimum aux sommets de $ n + 1 $. Il fournit également des informations sur la ville où se trouve la centrale électrique et la zone entre les villes connectées, mais cela peut être facilement mis en œuvre en divisant le cas lors de l'ajout de bords à l'aide de la méthode Clascal.
La discussion et l'implémentation ci-dessus sont bonnes, mais j'aimerais également mentionner que j'ai utilisé ** tuple pour la première fois ** parce que je voulais renvoyer plusieurs types de valeurs différents avec la méthode Clascal. Il est très confortable à utiliser, je vais donc continuer à l'utiliser (le document est ici).
(✳︎)… En ce qui concerne le plus petit arbre de la zone entière, j'ai posté la bibliothèque dans cet article.
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
//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; //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 car la racine de tous les éléments est elle-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]);//Puisque la valeur de l'expression d'affectation est 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éterminez 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);
}
//Supprimer le système prime set et initialiser
void clear(){
REP(i,n){parent[i]=i;}
siz=vector<ll>(n,1);
group.clear();
}
};
//Structure latérale
struct Edge{
ll u,v,cost;
//Mettez const sur le dos!
bool operator<(const Edge& e) const {return this->cost<e.cost;}
};
//Méthode Clascal
//ret:=Somme des poids de l'arbre de superficie totale minimale
//n:=Nombre total de sommets
//Montant du calcul:=O(|E|log|V|)
tuple<ll,vector<ll>,vector<pair<ll,ll>>> Kruskal(vector<Edge> &edges,ll n){
vector<ll> f1;vector<pair<ll,ll>> f2;
sort(ALL(edges));//Ordre croissant des poids latéraux
UnionFind uf=UnionFind(n);
ll ret=0;
FORA(e,edges){
//Avez-vous besoin d'ajouter ce côté(Centrale électrique ou côté)
if (!uf.same(e.u,e.v)){
uf.unite(e.u,e.v);
ret+=e.cost;
if(e.v==n-1){
f1.PB(e.u+1);
}else{
f2.PB(MP(e.u+1,e.v+1));
}
}
}
return {ret,f1,f2};
}
signed main(){
//Spécification de sortie du nombre de chiffres fractionnaires
//cout<<fixed<<setprecision(10);
//Code pour accélérer la saisie
//ios::sync_with_stdio(false);
//cin.tie(nullptr);
ll n;cin>>n;
vector<pair<ll,ll>> xy(n);REP(i,n)cin>>xy[i].F>>xy[i].S;
vector<ll> c(n);REP(i,n)cin>>c[i];
vector<ll> k(n);REP(i,n)cin>>k[i];
vector<Edge> edges;
REP(i,n){
FOR(j,i+1,n-1){
edges.PB({i,j,(abs(xy[i].F-xy[j].F)+abs(xy[i].S-xy[j].S))*(k[i]+k[j])});
}
}
REP(i,n)edges.PB({i,n,c[i]});
tuple<ll,vector<ll>,vector<pair<ll,ll>>> t=Kruskal(edges,n+1);
cout<<get<0>(t)<<endl;
cout<<SIZE(get<1>(t))<<endl;
REP(i,SIZE(get<1>(t))){
if(i==SIZE(get<1>(t))-1)cout<<get<1>(t)[i]<<endl;
else cout<<get<1>(t)[i]<<" ";
}
cout<<SIZE(get<2>(t))<<endl;
REP(i,SIZE(get<2>(t))){
cout<<get<2>(t)[i].F<<" "<<get<2>(t)[i].S<<endl;
}
}
Problème E
Je vais sauter cette fois.
Problème F
Considérons le chiffre DP en même temps pour chacun de $ a et b $, et quand on regarde le chiffre $ i $ du haut, est-il égal à $ l $ (①), est-il supérieur à $ l $ et inférieur à $ r $ (②), Quand j'ai essayé de penser à 3 façons d'égalité à $ r $ (③), l'implémentation a été ruinée (car il y a 27 façons de transitions de $ 3 \ fois 3 \ fois 3 $).
La politique était correcte, mais sauf quand $ a = b = 0 $, c'est $ a \ neq b $, donc si vous pensez dans l'ordre depuis le MSB de $ r $, $ a $ est is et ②, $ b $ est ② Vous pouvez voir que seul ③ est satisfait. Par conséquent, la transition sera de 2 $ \ fois 2 \ fois 3 $, ce qui peut être réduit à un montant suffisant pour être amorti.
Je ne vais pas améliorer cette fois, mais j'espère qu'il sera résolu la prochaine fois que je le verrai. Si vous y réfléchissez, c'est juste une question de se concentrer davantage sur sa résolution pendant le concours, donc je le regrette.
Recommended Posts