[PYTHON] Codeforces Round # 613 (Div.2) Examen Bacha (10/1)
Les résultats de cette fois
Impressions de cette époque
Est-ce que c'est OK comme note? ** J'ai pu résoudre les problèmes de gamme de niveaux que je devais résoudre **, ce qui est très apprécié par moi. Cependant, je regrette de ne pas avoir pu pleinement considérer le problème E simplement en chauffant la chaise dans l'heure restante **.
(Je vais sauter le problème E cette fois car la politique n'est pas sortie immédiatement.)
Problème A
Si vous voulez aller le plus possible vers la gauche, vous atteindrez les coordonnées de - (le nombre de $ L $ dans la chaîne), et si vous voulez aller le plus possible vers la droite, vous atteindrez les coordonnées (le nombre de $ R $ dans la chaîne). De plus, ** toutes les coordonnées intermédiaires peuvent être atteintes **, donc la réponse est (le nombre de $ R $ dans la chaîne) + (le nombre de $ L $ dans la chaîne) + 1.
(** Vérifiez uniquement les deux extrémités de la plage! **)
A.py
n=int(input())
s=input()
print(s.count("L")+s.count("R")+1)
Problème B
J'ai raté plusieurs phrases problématiques. C'est une réflexion. Plus précisément, il convient de noter qu'Adel peut sélectionner des ** sous-colonnes continues ** et ** ne peut pas sélectionner l'ensemble **.
Ici, le caractère délicieux du gâteau sélectionné par Yasser n'est calculé que par $ O (N) $, donc ** Adel trouve la valeur maximale ** (✳︎) dans la sous-chaîne continue qui peut être sélectionnée et cette valeur est S'il est inférieur au total, "OUI" doit être affiché, sinon "NON" doit être émis.
Si la valeur maximale dans une sous-colonne continue est $ dp [i]: = $ (la valeur maximale de la somme partielle des sous-colonnes continues se terminant par $ i $ th), alors ** $ i-1 $ th est la fin. Il peut être calculé par DP simplement en considérant s'il faut ou non l'attacher à la sous-chaîne continue qui a comme **. Cependant, lors de l'exécution d'un DP normal sur un nombre donné de colonnes, il ne remplit pas la condition que ** l'ensemble ne peut pas être sélectionné **.
Donc, en d'autres termes, vous pouvez répondre en disant ** vous n'avez pas à sélectionner le premier et le dernier élément en même temps **. Par conséquent, $ dp1 $ effectue DP pour trouver la valeur maximale de la somme lorsqu'une sous-colonne continue est sélectionnée parmi $ n $ -1er élément du 1er élément, et $ dp2 $ est $ du 2ème élément. Exécute DP pour trouver la valeur maximale de la somme lorsqu'une sous-colonne continue est sélectionnée à partir du n $ ème élément. La valeur maximale obtenue par ces deux DP est la valeur maximale en (✳︎).
B.py
for _ in range(int(input())):
n=int(input())
a=list(map(int,input().split()))
inf=10**15
dp1=[-inf]*(n-1)
dp1[0]=a[0]
for i in range(1,n-1):
dp1[i]=max(dp1[i-1]+a[i],a[i])
dp2=[-inf]*(n-1)
dp2[0]=a[1]
for i in range(2,n):
dp2[i-1]=max(dp2[i-2]+a[i],a[i])
if max(dp1+dp2)<sum(a):
print("YES")
else:
print("NO")
Problème C
Premièrement, à partir de la condition que $ LCM (a, b) = X $, ** $ a et b $ sont chacun une fraction de $ X $ **. De plus, en raison des contraintes du problème, ** toutes les fractions peuvent être recherchées **, donc $ a $ est utilisé comme une fraction de $ X $ et toutes les recherches sont effectuées.
Considérez le plus petit $ b $, ** $ a $ étant fixe **. A ce moment, si $ GCD (a, b) = 1 $, $ b = \ frac {X} {a} $ sera le minimum $ b $. Dans le cas de $ GCD (a, b) \ neq 1 $, si $ LCM (a, b) = X $ est transformé, $ b = \ frac {X} {\ frac {a} {GCD (a, b)}} Ce sera $, mais $ \ frac {a} {GCD (a, b)} $ est aussi une fraction de $ X $, vous n'avez donc pas besoin de le rechercher ** (). Par conséquent, vous pouvez trouver celui avec le plus petit $ max (a, b) $ dans tout $ a $.
✳︎… Je n'ai pas fait la preuve de $ GCD (a, b) \ neq 1 $ pendant que je le résolvais. Je ne peux pas m'en empêcher parce que j'étais impatient, mais ce n'est pas évident, alors je vais essayer de ** le prouver dans ma tête **.
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
vector<ll> divisors;//Un tableau qui stocke les fractions
void make_divisors(ll n){
FOR(i,1,sqrt(n)){
if(n%i==0){
divisors.PB(i);
if(i!=n/i){
divisors.PB(n/i);
}
}
}
}
signed main(){
//Code pour accélérer la saisie
//ios::sync_with_stdio(false);
//cin.tie(nullptr);
ll x;cin>>x;
make_divisors(x);
//Agrandissez le premier élément
pair<ll,ll> ans=MP(INF,INF);
FORA(a,divisors){
if(gcd(a,x/a)!=1)continue;
pair<ll,ll> ans_sub;
if(a>x/a){
ans_sub=MP(a,x/a);
}else{
ans_sub=MP(x/a,a);
}
if(ans_sub.F<ans.F){
ans=ans_sub;
}
}
cout<<ans.F<<" "<<ans.S<<endl;
}
Problème D
J'ai été déçu de ne pas pouvoir résoudre un problème similaire avec HUPC, donc je suis très heureux de pouvoir me venger cette fois.
Premièrement, j'ai eu du mal à choisir parmi les bits ci-dessus ** et à le réduire avec gourmandise **. Cependant, dans la discussion ** considérez la valeur maximale pour chaque bit ** et découvrez que ($ \ car $$ $ \ oplus $ est calculé petit à petit indépendamment). Autrement dit, lorsque le bit $ i $ de $ X $ est 0, le $ (a \ _i \ oplus X) \ _ {max} $ du bit $ i $ est le bit $ i $ de ** $ a $. Lorsque le nombre à 1 et le xor de $ X $ sont pris, il devient $ 2 ^ i $, et lorsque le bit $ i $ de $ X $ est 1, la relation inverse est obtenue.
Par conséquent, ** divisez le nombre qui maximise le $ i $ ème bit de $ X $ vu du bit supérieur ** par 0 ou 1, et récursivement $ i-1 même pour l'ensemble des nombres divisés. Regardez simplement le bit $ et divisez-le. Aussi, puisque ce que nous voulons finalement trouver est le minimum $ (a \ _i \ oplus X) \ _ {max} $, la valeur de retour de la fonction récursive est $ min $ ($ i $ ensemble de nombres dont les bits sont 0). Suite au calcul du bit $ i-1 $ et après, résultat du calcul du bit $ i-1 $ et après pour un ensemble de nombres dont le bit $ i $ est 0) + $ 2 ^ i $ C'est bon. De plus, si les ** $ i $ bits de l'ensemble des nombres donnés à la fonction récursive sont tous les mêmes **, en donnant les mêmes bits que ce bit, le maximum $ (a \ _ i \ oplus X) des $ i $ bits ) \ _ {Max} $ sera égal à 0, et vous pouvez renvoyer le résultat du calcul de $ i-1 $ et des bits suivants sans division. De plus, si $ i = 0 $, la récurrence est terminée.
En implémentant la fonction récursive ci-dessus, le minimum $ (a \ _ i \ oplus X) \ _ {max} $ peut être obtenu et affiché. De plus, je m'inquiétais de la quantité de calcul de la fonction récursive, mais comme chaque élément est divisé à chaque récurrence, chaque élément n'est appelé qu'une seule fois au ** $ i $ bit **, $ O (\ log {a \ \ Il peut être supprimé par _ {max}} n) $ et fonctionne assez rapidement.
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
ll rec(vector<ll> vec,ll ind){
ll ret=0;
vector<ll> vec0,vec1;
FORA(i,vec){
if((i>>ind)&1){
vec0.PB(i);
}else{
vec1.PB(i);
}
}
if(SIZE(vec0)==0){
if(ind==0)return 0;
return rec(vec1,ind-1);
}
if(SIZE(vec1)==0){
if(ind==0)return 0;
return rec(vec0,ind-1);
}
//Ni est 0(Retournez le plus petit)
//+2^je
if(ind==0)return 1;
return min(rec(vec0,ind-1),rec(vec1,ind-1))+(1<<ind);
}
signed main(){
//Code pour accélérer la saisie
//ios::sync_with_stdio(false);
//cin.tie(nullptr);
ll n;cin>>n;
vector<ll> a(n);REP(i,n)cin>>a[i];
cout<<rec(a,31)<<endl;
}
Après le problème E
Je vais sauter cette fois.
Recommended Posts