Code de l'éducation forces Round 93 Bacha Review (8/17)
Les résultats de cette fois
Impressions de cette époque
J'ai toujours le sentiment que l'endroit où D ne peut pas passer n'est pas stable. Je suis resté coincé à essayer de le faire avec une solution non supposée. Même si vous essayez de devenir fou, ** assurez-vous d'avoir une bonne perspective avant de l'implémenter **.
Problème A
J'ai presque mal lu le problème. Le problème est de répondre à un ensemble de trois nombres qui ne forment pas un triangle, et comme la séquence $ a $ a été triée par ordre croissant, $ a \ _i + a \ _j <a \ _k (i <j <k) $ Assurez-vous qu'il existe. Cela peut être fait en envisageant de rendre $ a \ _i + a \ _j $ plus petit et $ a \ _k $ plus grand, alors assurez-vous que $ (i, j, k) = (1,2, n) $ tient. Simplement fais-le.
A.py
for _ in range(int(input())):
n=int(input())
a=list(map(int,input().split()))
if a[0]+a[1]<=a[-1]:
print(f"1 2 {n}")
else:
print(-1)
Problème B
Cela a semblé difficile pendant un moment, mais c'était facile.
Les deux visent à maximiser le nombre de 1 à choisir, alors ** alternez à partir des sous-colonnes continues les plus longues **. Par conséquent, après avoir stocké la longueur de la sous-chaîne continue de 1 contenue dans la chaîne $ S $ dans ʻans, elle est triée par ordre décroissant des valeurs, et la somme des valeurs impaires devient la valeur maximale du score d'Alice. C'est très pratique en Python car vous pouvez écrire avec juste ʻans [:: 2] pour choisir d'en sauter deux.
B.py
for _ in range(int(input())):
s=input()
n=len(s)
ans=[0]
for i in range(n):
if s[i]=="1":
ans[-1]+=1
else:
if ans[-1]!=0:
ans.append(0)
ans.sort(reverse=True)
print(sum(ans[::2]))
Problème C
Je soupçonnais DP car c'était facile à gérer comme transition d'ajout, mais c'est difficile ** car je ne peux pas gérer l'état ** (du coup, le problème D était DP. Je suis déçu).
Ici, nous traitons ** intervalles, nous avons donc décidé de considérer la différence des sommes cumulées **. Par conséquent, la somme jusqu'à $ x $ th est définie comme $ S \ _x $. A ce moment, la condition du sujet est $ S \ _r- S \ _ {l-1} = r-l + 1 \ leftrightarrow S \ _ r-r = S \ _ {l-1} - (l-1) $ Je vais. Par conséquent, si $ S \ _0-0 = 0 $, alors tout $ i (0 \ leqq i \ leqq n) $ avec le même $ S \ _i-i $ sera apparié. Par conséquent, celui-ci est divisé en ceux qui sont identiques en utilisant un dictionnaire tel que Counter, et lorsqu'il y a $ l $ $ i $ tel que $ S \ _i-i = k $, $ \ _l C \ _2 $ Est le nombre de ces combinaisons $ i $. Faites ce calcul pour chaque $ k $, et la somme est la réponse.
AtCoder semble également être sorti récemment, j'ai donc pu le résoudre à grande vitesse. Cela a probablement pris environ 30 minutes il y a un mois, alors j'ai senti l'importance et la croissance de la dévotion.
C.py
for _ in range(int(input())):
n=int(input())
a=list(map(int,input().split()))
if a==[i+1 for i in range(n)]:
print(0)
continue
#Hors les bords
for i in range(n):
if a[i]!=i+1:
break
for j in range(n-1,-1,-1):
if a[j]!=j+1:
break
#Erreur d'index
for k in range(i,j+1):
if a[k]==k+1:
print(2)
break
else:
print(1)
Problème D
** J'ai senti qu'une lacune dans une considération faisait une grande différence **. Je voudrais faire une considération plus précise.
La première politique que vous pouvez facilement trouver est ** de combiner avidement celles qui ont les plus grandes valeurs **. En d'autres termes, les paires de côtés de $ r, g et b $ sont mises en priorité \ _queue dans l'ordre du plus long, et les paires sont faites à partir du plus long. Cependant, si cette méthode est utilisée, il ne restera qu'un seul côté de couleur . Que dois-je faire dans ce cas? La première méthode consiste à moderniser les côtés supplémentaires. Cependant, étant donné que la méthode gourmande est utilisée ( je décide arbitrairement l'ordre de sélection **), il est possible que la méthode gourmande soit interrompue par la ** mise à niveau **. Je pensais que je ne le casserais pas, mais je ne pouvais pas le mettre en œuvre parce que j'étais sur le point de marcher sur le cas d'angle. De cette façon, ** il est difficile de penser dans une certaine mesure, et si d'autres politiques peuvent être établies, vous devriez envisager une autre méthode **.
Ici, la méthode gourmande mentionnée ci-dessus a une ** marge considérable pour le temps d'exécution **, vous pouvez donc y penser sans être particulier sur la méthode gourmande. La méthode suivante à laquelle je peux penser est DP. En plus de considérer la ** transition du choix **, $ r, g, b $ vaut au plus 200, il n'y a donc que des ** états ** d'environ $ R \ fois G \ fois B = 8 \ fois 10 ^ 6 $. De ce point de vue, il semble que DP soit un moyen très efficace.
Le PDD considéré ici est le suivant. De plus, comme il est préférable de sélectionner $ r, g et b $ parmi les plus grands, nous allons poursuivre la discussion en supposant qu'ils sont triés par ordre décroissant.
$ dp [i] [j] [k]: = $ ($ i $ morceaux de $ r $, $ j $ morceaux de $ g $, $ k $ morceaux de $ b $, le plus grand rectangulaire Superficie totale)
De plus, dans une transition normale, nous envisagerons d'ajouter des éléments un par un, mais cette fois nous pouvons faire un rectangle en faisant une paire, nous allons donc considérer une transition qui ajoute des ** paires **. Donc ça ressemble à ça:
(1) Lorsque $ i <R $ et $ j <G $
Vous pouvez choisir une paire entre $ r $ et $ g $, alors choisissez les plus grands $ r [i] $ et $ g [j] $ que vous pouvez choisir ($ i, j $ sont indexés à 0). Veuillez noter que.).
(2) Lorsque $ i <R $ et $ k <B $
Vous pouvez choisir une paire entre $ r $ et $ b $, alors choisissez les plus gros $ r [i] $ et $ b [k] $ que vous pouvez choisir ($ i, k $ sont indexés à 0). Veuillez noter que.).
(3) Lorsque $ j <G $ et $ k <B $
Vous pouvez choisir une paire entre $ g $ et $ b $, alors choisissez les plus gros $ g [j] $ et $ b [k] $ que vous pouvez choisir ($ j, k $ sont indexés à 0). Veuillez noter que.).
(4) À d'autres moments Puisqu'il n'y a rien à choisir en tant que groupe, voici les réponses. [1] Lorsque $ i <R $, $ dp [i + 1] [j] [k] = max (dp [i + 1] [j] [k], dp [i] [j] [k] ) $ [2] Lorsque $ j <G $, $ dp [i] [j + 1] [k] = max (dp [i] [j + 1] [k], dp [i] [j] [k] ) $ [3] Lorsque $ k <B $, $ dp [i] [j] [k + 1] = max (dp [i] [j] [k + 1], dp [i] [j] [k] ) $
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
signed main(){
//Code pour accélérer la saisie
//ios::sync_with_stdio(false);
//cin.tie(nullptr);
ll R,G,B;cin>>R>>G>>B;
vector<ll> r(R);REP(i,R)cin>>r[i];sort(ALL(r),greater<ll>());
vector<ll> g(G);REP(i,G)cin>>g[i];sort(ALL(g),greater<ll>());
vector<ll> b(B);REP(i,B)cin>>b[i];sort(ALL(b),greater<ll>());
vector<vector<vector<ll>>> dp(R+1,vector<vector<ll>>(G+1,vector<ll>(B+1,0)));
REP(i,R+1){
REP(j,G+1){
REP(k,B+1){
//DP à choisir et à distribuer pour chaque paire
//C'est facile si tu y penses
//dp[i][j][k]:=Lorsque les i-ème j-ème et k-ème sont appariés
bool f=false;
if(i<R and j<G){
dp[i+1][j+1][k]=max(dp[i+1][j+1][k],dp[i][j][k]+r[i]*g[j]);
f=true;
}
if(i<R and k<B){
dp[i+1][j][k+1]=max(dp[i+1][j][k+1],dp[i][j][k]+r[i]*b[k]);
f=true;
}
if(j<G and k<B){
dp[i][j+1][k+1]=max(dp[i][j+1][k+1],dp[i][j][k]+g[j]*b[k]);
f=true;
}
if(!f){
if(i<R)dp[i+1][j][k]=max(dp[i+1][j][k],dp[i][j][k]);
if(j<G)dp[i][j+1][k]=max(dp[i][j+1][k],dp[i][j][k]);
if(k<B)dp[i][j][k+1]=max(dp[i][j][k+1],dp[i][j][k]);
}
}
}
}
cout<<dp[R][G][B]<<endl;
}
Après le problème E
Je vais sauter cette fois
Recommended Posts