[PYTHON] Code de l'éducation forces Round 89 Bacha Review (9/8)
Les résultats de cette fois
Impressions de cette époque
Je n'ai pas fait très attention au problème D, mais je suis content d'avoir pu le récupérer plus tard. C'est bien de reconstruire, mais je suis loin d'avoir mis en place une politique très précise, ce qui est mon objectif, j'aimerais donc m'y consacrer.
Problème A
Si vous faites $ shovel $ de $ x $ et $ sword $ de $ y $, alors $ 0 \ leqq 2x + y \ leqq a $ et $ 0 \ leqq x + 2y \ leqq b $. A ce moment, la somme des deux équations donne $ 0 \ leqq x + y \ leqq \ frac {a + b} {3} $.
De plus, puisque je veux trouver $ x + y $, j'aimerais supposer que $ [\ frac {a + b} {3}] $ est la valeur maximale, mais ** $ [\ frac {a + b} {3 }] $ doit être inférieur ou égal à $ a $ et inférieur ou égal à $ b $ ** (car $ \ car x, y $ est supérieur ou égal à 0). On trouvera donc $ min ([\ frac {a + b} {3}], a, b) $.
A.py
for _ in range(int(input())):
a,b=map(int,input().split())
print(min((a+b)//3,a,b))
Problème B
C'était dangereux parce que je l'ai mal lu à mi-chemin. L'anglais de Kodofo a parfois un problème difficile à lire ...
Considérez combien d'index peuvent finalement être définis sur 1 lors de l'échange. En outre, vous pouvez permuter dans la plage de $ l \ _i $ à $ r \ _i $. Puisque nous voulons découvrir tous les index qui peuvent être 1, nous pouvons trouver la solution en trouvant la plage d'index qui peut être 1 au moment de $ i $ et en élargissant progressivement la plage.
En d'autres termes, commencez par $ [x, x] $ et commencez par le plus petit $ i $. Il est plus facile à comprendre si vous l'écrivez dans un diagramme, je vais donc l'expliquer dans un diagramme à partir d'ici.
En conséquence, les sections qui peuvent être réglées à 1 sont obtenues dans l'ordre comme décrit ci-dessus, de sorte que la longueur de la section finalement obtenue peut être obtenue comme solution.
B.py
for _ in range(int(input())):
n,x,m=map(int,input().split())
ans=[x,x]
for i in range(m):
l,r=map(int,input().split())
if r<ans[0] or l>ans[1]:
continue
else:
ans=[min(ans[0],l),max(ans[1],r)]
print(ans[1]-ans[0]+1)
Problème C
Codeforces semble avoir beaucoup de BFS et de DFS. Je suis content car je n'ai pas l'habitude de le mettre en œuvre personnellement. Si vous y réfléchissez, vous pouvez demander ce problème sans utiliser BFS.
(Pour faciliter l'explication, le carré est remplacé par un index 0.)
** Il devient symétrique ** lorsque les nombres écrits dans les carrés tracés pour n'importe quel chemin sont arrangés. Tout d'abord, à partir de la condition de ** pour tout chemin **, lors du traçage de $ (0,0) $ à $ (n-1, m-1) $, ** toutes les cellules à la même distance ont le même numéro. Il devient **. De plus, à partir de la condition de ** symétrie **, le nombre de carrés avec une distance de $ i $ et le nombre de carrés avec une distance de $ n + m-2-i $ sont les mêmes **. Par conséquent, pour chacune des cellules $ n \ times m $, ** recherchez les cellules avec la même distance ** avec BFS et stockez-les dans cand pour chaque cellule. En fait, quand elle est à $ (i, j) $, la distance est $ (i, j) $, donc elle peut être calculée sans utiliser BFS.
Après avoir trouvé par BFS, les cellules avec une distance de $ i $ et les cellules avec une distance de $ n + m-2-i $ sont ensuite combinées en une dans cand, et le nombre de 0 et de 1. Comptez et associez le plus petit au plus grand. De plus, quand $ (n + m) % 2 = 0 $, la cellule avec une distance de $ \ frac {n + m-2} {2} $ est ** le centre de n'importe quel chemin, alors de quelle cellule s'agit-il? Le nombre est également bon **.
La mise en œuvre n'est pas difficile si vous savez ** diviser la mise en œuvre en la partie qui divise la masse pour chaque profondeur et la partie qui calcule pour chaque profondeur **.
C.py
from collections import deque
def bfs(dep):
global a,n,m,ans,d,check,cand
while len(d):
cand.append(list(d))
l=len(d)
for i in range(l):
p=d.popleft()
if p[1]<m-1:
if not check[p[0]][p[1]+1]:
d.append([p[0],p[1]+1])
check[p[0]][p[1]+1]=True
if p[0]<n-1:
if not check[p[0]+1][p[1]]:
d.append([p[0]+1,p[1]])
check[p[0]+1][p[1]]=True
for _ in range(int(input())):
n,m=map(int,input().split())
a=[list(map(int,input().split())) for i in range(n)]
d=deque([[0,0]])
check=[[False]*m for i in range(n)]
check[0][0]=True
cand=[]
bfs(0)
ans=0
for i in range((n+m-1)//2):
x=[a[j[0]][j[1]] for j in cand[i]+cand[n+m-1-1-i]]
ans+=min(x.count(0),x.count(1))
print(ans)
Problème D
Cela a provoqué un miracle de dépassement de 2000 ms TL en 1949 ms. Je pensais que ça passerait, mais c'était dangereux.
Tout d'abord, considérez s'il existe $ d \ _1 $ et $ d \ _2 $ tels que $ gcd (d \ _1 + d \ _2, a \ _i) = 1 $. Ici, décomposé en facteurs premiers **, s'il n'y a qu'un seul nombre premier **, $ d \ _1 $ et $ d \ _2 $ sont tous deux des multiples de ce nombre premier, donc $ gcd (d \ _1 + d \ _2, Ce sera un \ _i) \ neq 1 $.
Par conséquent, dans ce qui suit, nous considérons les conditions lorsqu'il y a deux nombres premiers ou plus lorsque $ a \ _i $ est factorisé. À ce moment, j'ai pensé que ~~ ** devrait être ajouté en sélectionnant de manière appropriée des nombres premiers arbitraires ** ~~, mais c'est une erreur totale.
Ici, je suis venu avec la classification des cas par pair et bizarrerie, en faisant attention à ** addition . Premièrement, dans le cas d'un nombre impair, le plus petit $ a, b $ peut être sélectionné parmi les nombres premiers (impairs) inclus dans la factorisation première, et la somme est paire. De plus, ce nombre pair peut être exprimé comme $ \ frac {a + b} {2} \ fois 2 $, mais il est inférieur à $ \ frac {a + b} {2} $ et est inclus dans la factorisation première de $ a \ _i $. Il n'y a que $ a $ premiers, mais $ \ frac {a + b} {2} $ et $ a $ sont premiers l'un par rapport à l'autre, et 2 n'est pas inclus dans la factorisation première de $ a \ _i $, donc $ a, b $ est la solution $ d \ _1, d \ _2 $ ( attention au cas extrême des petits nombres! **).
Ensuite, dans le cas d'un nombre pair, si vous sélectionnez un nombre impair pour $ d \ _1 et d \ _2 $, la somme sera un nombre pair, donc $ d \ _1 $ vaut 2, $ d \ _2 $ est un nombre impair pratique. Doit être sélectionné. À ce stade, vous pouvez sélectionner $ d \ _2 $ (multiplié par tous les nombres impairs autres que 2) (** faites attention au cas extrême d'un grand nombre! **). En effet, pour le moment, $ d \ _1 + d \ _2 $ ne peut être divisé par aucun nombre premier inclus dans la factorisation première de $ a \ _i $.
(Il allait de soi s'il s'agissait d'un nombre impair, mais s'il s'agissait d'un nombre pair, il pourrait être difficile d'interpréter la condition selon laquelle il devrait être différent de tout nombre premier **. Cette zone semble familière.)
De ce qui précède, nous connaissons les cas de pair et impair, nous pouvons donc trouver la solution. En outre, bien que cela ne soit pas mentionné ci-dessus comme explicite, la vitesse est augmentée par le tamis Eratostenes afin de rendre logarithmique la quantité de calcul de la factorisation première.
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 10000000 //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
//MAXR=10^Notez que c'est 5
#define PN 1 //La marque du nombre premier est 1
vector<ll> PN_chk(MAXR+1,PN);//0-indexed(0~MAXR)
//Un ensemble qui stocke les nombres premiers inclus dans la factorisation première
set<ll> prime;
//O(MAXR)
void init_eratosthenes(){
ll MAXRR=sqrt(MAXR)+1;
//Il se décompose en facteurs premiers de 2 nombres ou plus, de sorte qu'il peut être ignoré.
PN_chk[0]=0;PN_chk[1]=0;
FOR(i,2,MAXRR){
//Un nombre premier s'il est supposé être un nombre premier à votre arrivée
//Marquer un multiple d'un nombre premier car il est divisible par ce nombre premier
if(PN_chk[i]==1) FOR(j,i,ll(MAXR/i)){PN_chk[j*i]=i;}
}
}
//O(logn)
//Puisqu'il s'agit d'une carte, le premier est déjà aligné
//Il n'y en a que deux
void prime_factorize(ll n){
if(n<=1) return;
//if(SIZE(prime)==2)return;
//Si 1, n est un nombre premier
if(PN_chk[n]==1){prime.insert(n);return;}
//Les nombres marqués sont des nombres premiers
prime.insert(PN_chk[n]);
//Considérez le nombre de nombres marqués divisé par n
prime_factorize(ll(n/PN_chk[n]));
}
signed main(){
//Code pour accélérer la saisie
//ios::sync_with_stdio(false);
//cin.tie(nullptr);
init_eratosthenes();
ll n;cin>>n;
vector<ll> a(n);REP(i,n)cin>>a[i];
vector<ll> ans0(n,-1);
vector<ll> ans1(n,-1);
REP(i,n){
if(a[i]%2==1){
prime_factorize(a[i]);
if(SIZE(prime)>1){
ans0[i]=*prime.begin();
ans1[i]=*++(prime.begin());
}
prime.clear();
}else{
prime_factorize(a[i]);
if(SIZE(prime)>1){
ans0[i]=2;ans1[i]=1;
for(auto j=++prime.begin();j!=prime.end();j++){
ans1[i]*=(*j);
}
}
prime.clear();
}
}
REP(i,n){
if(i==n-1)cout<<ans0[i]<<"\n";
else cout<<ans0[i]<<" ";
}
REP(i,n){
if(i==n-1)cout<<ans1[i]<<"\n";
else cout<<ans1[i]<<" ";
}
}
E problème
Je n'ai pas pu le résoudre dans le concours, alors j'y ai pensé après le concours. Ce n'était pas aussi difficile que ce à quoi je m'attendais, je veux donc pouvoir laisser beaucoup de temps avant le problème E.
Au cours de l'expérience, j'ai remarqué que ** la limite de la plage que peut prendre la fin de la section divisée est assez stricte **. De plus, comme il est difficile de penser où $ min $ apparaîtra en considérant le plus petit $ j $ de $ b \ _j $, nous avons décidé de considérer ** du plus grand $ j $ de ** $ b \ _ j $ . ( Scan de l'autre côté! **).
À ce stade, la plage possible de la valeur à l'extrémité gauche de l'intervalle peut être déterminée ** indépendamment et de manière unique **.
(1) Qu'y a-t-il à l'extrême droite? ** $ a \ _i = b \ _j $ tient, et le plus grand $ i $ ** est à l'extrême droite. De plus, lorsque $ a \ _i <b \ _j $ tient dans un endroit plus grand que $ i $, la condition de $ min $ n'est pas satisfaite, donc il y a 0 façons.
(2) Qu'y a-t-il à l'extrême gauche? (À la condition que ce soit le même que ou à gauche de l'extrême droite) ** $ a \ _i <b \ _j $ est +1 à $ i $ qui tient pour la première fois ** .. De plus, lorsque cela est vrai avec $ j = 0 $, la condition de $ min $ n'est pas satisfaite, il y a donc 0 façons.
Notez également que lorsque ** $ j = 0
En faisant attention aux cas d'angle ci-dessus, si vous trouvez l'intervalle de la valeur la plus à gauche possible dans chaque $ j $, vous pouvez trouver la solution en la multipliant.
E.py
mod=998244353
n,m=map(int,input().split())
a=list(map(int,input().split()))
b=list(map(int,input().split()))
ans=1
i=n-1
for j in range(m-1,-1,-1):
l,r=-1,-1
while i!=-1:
if a[i]<b[j]:
print(0)
exit()
if a[i]==b[j]:
r=i
break
i-=1
else:
print(0)
exit()
while i!=-1:
if a[i]<b[j]:
l=i+1
if j==0:
print(0)
exit()
break
i-=1
else:
if j!=0:
print(0)
exit()
if j!=0:
ans*=(r-l+1)
ans%=mod
#print(l,r)
print(ans)
Après problème F
Je vais sauter cette fois
Recommended Posts