[PYTHON] Codeforces Round # 648 (Div.2) Critique Bacha (9/5)
Les résultats de cette fois
Impressions de cette époque
Cette fois, j'ai profité de ma réflexion habituelle et j'ai travaillé ** calmement **, mais j'ai pu obtenir des résultats relativement bons. Cependant, j'ai l'habitude de perdre temporairement ma concentration lorsque je rencontre un problème qui doit être pris en considération **, donc je veux pouvoir trop me concentrer là-bas.
Aussi, je sens que j'ai pu obtenir un peu plus de résultats, mais comme c'est probablement la première fois pour Gokan, j'aimerais l'utiliser comme source de motivation dans le futur.
(À part cet article, j'ai accumulé 3 critiques, donc je veux le digérer rapidement.)
Problème A
Vous ne pouvez pas sélectionner les lignes et les colonnes qui contiennent la cellule de craiming. Ici, le nombre de lignes et de colonnes qui ne contiennent pas de cellule de craiming de la première entrée peut être calculé comme mr, mc, respectivement ($ O (m \ times n) $).
À ce stade, chaque personne peut ** en sélectionner une parmi les lignes et colonnes qui ne sont pas incluses et sélectionner la cellule à l'intersection **, et la personne qui ne peut pas sélectionner en alternant cette opération perd. Je vais. En outre, le nombre d'opérations est «min (mr, mc)», et le gagnant est déterminé par l'étrangeté du nombre d'opérations.
A.py
for _ in range(int(input())):
n,m=map(int,input().split())
r,c=[False]*n,[False]*m
for i in range(n):
x=list(map(int,input().split()))
if not all(k==0 for k in x):
r[i]=True
for j in range(m):
if x[j]==1:
c[j]=True
z=min(r.count(False),c.count(False))
print(["Vivek","Ashish"][z%2])
Problème B
Notez qu'il s'agit d'un échange ** entre différents types, pas seulement le même type.
Ici, quand le $ i $ ème nombre doit être le $ j $ th après le tri, si $ i $ et $ j $ sont de types différents, il est réalisé en effectuant un échange entre $ i $ et $ j $. Est possible. En revanche, si $ i $ et $ j $ sont du même type, ** via swap entre différents $ k $ th nombres de types différents ** (swap à $ j $ et $ k $ → $ Ceci peut être réalisé en faisant le swap dans l'ordre de i $ et $ k $). Par conséquent, ** s'il y en a au moins un de chaque type **, il est possible de trier selon le sujet. De plus, même s'il n'y a qu'un seul type dans la colonne des nombres, il est possible de trier si la ** colonne des nombres est déjà triée **. Par conséquent, ces cas sont décrits comme suit.
B.py
for _ in range(int(input())):
n=int(input())
a=list(map(int,input().split()))
c=sorted(a)
b=list(map(int,input().split()))
if a==c:
print("Yes")
continue
if b.count(1)==n or b.count(0)==n:
print("No")
else:
print("Yes")
Problème C
Il est clair que le changement de cycle doit être ** au plus une fois **. Il est également clair qu'une recherche complète des rues $ n $ du changement de cycle aboutira à $ O (N ^ 2) $ ** et ne sera pas à temps. Par conséquent, au lieu de nous concentrer sur les changements, nous nous sommes concentrés sur ** le nombre de changements requis par chaque élément **. De plus, le nombre total d'éléments qui peuvent être décalés et mis en correspondance est limité à ** $ n $ en $ n $ décalages, alors j'ai eu l'idée que je devais faire attention aux éléments.
Une fois que vous avez une idée de prêter attention aux éléments, le reste n'est pas difficile. Vous pouvez facilement savoir combien il faut décaler chaque élément du tableau $ a $ et du tableau $ b $. De plus, à ce moment (index à $ b $) - (index à $ a $) peut être ** négatif **, alors ajoutez $ n $ dans ce cas. À partir de ce qui précède, nous avons pu enregistrer les équipes requises pour chaque élément, nous avons donc utilisé la classe Counter pour enregistrer le nombre d'éléments pour chaque équipe et calculé le nombre maximum d'éléments.
C.py
n=int(input())
a=list(map(int,input().split()))
b=list(map(int,input().split()))
#Position de chaque élément
ind=[0 for i in range(n)]
for i in range(n):
ind[a[i]-1]+=i
for i in range(n):
ind[b[i]-1]-=i
for i in range(n):
if ind[i]<0:
ind[i]+=n
from collections import Counter
c=Counter(ind)
ans=1
for i in c:
ans=max(ans,c[i])
print(ans)
Problème D
** J'ai fait une erreur dans le nom de la variable ** ou mis à -1 où j'ai ajouté +1 et j'étais impatient sans passer par l'exemple. La politique a été rapidement mise à la perfection, je voudrais donc travailler dur pour assurer une mise en œuvre stable. De plus, ** j'ai utilisé le rembourrage lors du traçage avec BFS ** J'ai pu écrire la partie du jugement proprement (par rapport à notre entreprise), donc j'aimerais l'utiliser à partir de maintenant.
Puisqu'il s'agit d'un déplacement vers une pièce qui partage un côté, envisagez de l'implémenter dans BFS ou DFS. De plus, G s'échappe et B ne s'échappe pas, mais ** B est plus restrictif **, pensez donc à remplir cette condition en premier. Lorsque B s'échappe, le motif est soit d'atteindre où se trouve G, soit d'atteindre directement $ (n, m) $. Par conséquent, dans l'un ou l'autre des cas, ** il est nécessaire de mettre un mur au milieu **. Vous pouvez également voir que plus la zone où le mur est placé est petite, plus il est susceptible d'atteindre $ (n, m) $ en ** G. En d'autres termes, quand il y a B, vous pouvez ** mettre des murs de tous les côtés **. De plus, si $ G $ est inclus de tous les côtés et que le mur ne peut pas être placé, le sujet ne peut pas être satisfait à ce point, et dans d'autres cas, le mur peut être entouré de tous les côtés. Par conséquent, pour la condition que B ne puisse pas s'échapper, ** placer des murs sur les quatre côtés est nécessaire et suffisant **.
Sur cette base, nous considérerons ** les conditions d'échappement G **, mais la condition que chaque G peut atteindre $ (n, m) $ par BFS ou DFS (utilisez le BFS que vous aimez ici). Ce n'est pas difficile à paraphraser. Cependant, si vous faites BFS sur chaque G, vous devez rechercher jusqu'à $ (50 \ fois 50) ^ 2 $ fois et il y a jusqu'à 100 cas de test, donc ce n'est évidemment pas à temps. Ici, en profitant du fait que la destination finale est la même que $ (n, m) $, ** à l'inverse, pouvons-nous atteindre chaque $ G $ à partir de $ (n, m) $? pense. Pour le moment, ** un BFS est requis **, donc la recherche est de 50 $ \ fois 50 $ fois et peut être implémentée dans un langage relativement lent tel que Python.
Lors de la mise en œuvre, vous pouvez le faire en deux étapes: (1) remplir la zone autour de B → (2) exécuter BFS. Cependant, veuillez noter qu'il existe les cas suivants.
(1) Lorsqu'il y a $ G $ de tous les côtés dans ① → Sortie Non (2) Lorsque $ (n, m) $ est un mur ou $ B $ et qu'il n'y a pas ** $ G $ ** → Oui est affiché (3) Lorsque $ (n, m) $ est un mur ou $ B $ et $ G $ existe → Sortie Non (4) Lorsqu'il y a $ G $ qui ne peut pas être recherché en cas de ② → Non est sorti (5) Lorsque $ G $ qui ne peut pas être recherché n'existe pas dans ② → Sortie Oui
D.py
from collections import deque
def bfs():
global n,m,s,d,check
#print(d)
while len(d):
l=len(d)
for i in range(l):
p=d.popleft()
for j in [[p[0],p[1]+1],[p[0],p[1]-1],[p[0]+1,p[1]],[p[0]-1,p[1]]]:
#print([[p[0],p[1]+1],[p[0],p[1]-1],[p[0]+1,p[1]],[p[0]-1,p[1]]])
#print(check[j[0]][j[1]])
if not check[j[0]][j[1]]:
check[j[0]][j[1]]=True
d.append(j)
#print(d)
for _ in range(int(input())):
n,m=map(int,input().split())
s=[["#" for i in range(m+2)]]+[list("#"+input()+"#") for i in range(n)]+[["#" for i in range(m+2)]]
f=False
#Remplissez autour de B
for i in range(1,n+1):
for j in range(1,m+1):
if s[i][j]=="B":
for k in [[i,j+1],[i,j-1],[i-1,j],[i+1,j]]:
if s[k[0]][k[1]]=="G":
f=True
elif s[k[0]][k[1]]==".":
s[k[0]][k[1]]="#"
#print(s)
if f:
print("No")
continue
#Rechercher avec bfs
if s[n][m]=="B" or s[n][m]=="#":
for i in range(1,n+1):
for j in range(1,m+1):
if s[i][j]=="G":
f=True
if not f:
print("Yes")
else:
print("No")
continue
d=deque()
d.append([n,m])
check=[[(s[i][j]=="B") or (s[i][j]=="#") for j in range(m+2)] for i in range(n+2)]
check[n][m]=True
#print(check)
bfs()
for i in range(1,n+1):
for j in range(1,m+1):
if s[i][j]=="G" and check[i][j]==False:
f=True
#if f:
#print(s)
#print(check)
#print(3)
if f:
print("No")
continue
print("Yes")
Problème E
L'implémentation n'avait pas besoin d'être C ++, mais j'ai choisi C ++ car je devais passer par un total d'environ 10 $ ^ 7 $ boucles.
Tout d'abord, l'énoncé du problème était difficile à lire, mais en résumé, le problème est le suivant (bien que mon résumé soit également difficile à lire ...).
"Lorsque $ k $ nombre est sélectionné dans la séquence de nombres $ a $ de longueur $ n $, $ max (1, k-2) $ ou plus représente le nombre sélectionné pour chaque bit. Trouve comment choisir le nombre qui maximise la réponse, y compris ce bit dans la réponse. "
Tout d'abord, ** chaque bit se déplace indépendamment **, il semble donc difficile de choisir goulûment un tel nombre **. Donc, pour le moment, j'ai réglé un peu correctement avec $ k = 1,2 $ et j'ai réfléchi. Ensuite, j'ai remarqué que $ k = 1,2,3 $ devrait être sélectionné afin que le plus de bits possible puissent être définis ** ($ \ car max (1, k-2) = 1 $). Cependant, lorsque $ k = 4 $, $ max (1, k-2) = 2 $, et même si un nombre est ajouté, le nombre de chaque bit augmentera d'au plus un, donc $ k = Il n'y a pas de nouveau bit inclus dans la réponse en augmentant de 3 $ à $ k = 4 $. La même chose peut être dite pour $ k \ geqq 5 $, donc ** $ k $ devrait être considéré jusqu'à 3 **.
À partir de ce qui précède, vous pouvez réfléchir à la façon de sélectionner 3 nombres, mais au plus $ _ {500} C_3 = 2.07085 \ times 10 ^ 7 $, et vous pouvez ** rechercher tout **. De plus, étant donné qu'il est seulement nécessaire qu'un nombre de bits reste lorsque trois nombres sont sélectionnés, il est seulement nécessaire de calculer avec le bit ou de trouver la valeur maximale. Cependant, lorsque $ n = 1,2 $, la solution est le bit ou de tous les éléments.
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
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];
ll ans=0;
REP(i,n){
FOR(j,i+1,n-1){
FOR(k,j+1,n-1){
ans=max(ans,a[i]|a[j]|a[k]);
}
}
}
if(n==1)cout<<a[0]<<endl;
else if(n==2)cout<<(a[0]|a[1])<<endl;
else cout<<ans<<endl;
}
Après problème F
Je vais sauter cette fois
Recommended Posts