À la lumière des résultats récents des malheureux professionnels de la compétition, j'ai décidé d'augmenter à nouveau le montant de la dévotion. Je voudrais me consacrer à la résolution de problèmes au-delà du différentiel d'eau dans le temps.
Pour le moment, je prévois de résoudre le problème des différences d'eau de 1AC ou plus chaque jour jusqu'à ce que tous les cours du semestre S soient terminés. Je ferai de mon mieux.
Environ une heure et demie (je vais mesurer le temps à partir de maintenant)
C'est $ O (NQ) $ lorsque chaque personne décide quelle construction de route sera fermée une fois, donc ** Il semble que cela puisse être fait efficacement si vous pensez à quelle personne chaque construction de route sera fermée à la circulation ** ..
Ici, la construction de la i-ième route ferme les personnes passant par la coordonnée $ X_i $ entre $ \ [S_i, T_i-1 ] $, mais les coordonnées peuvent être résumées dans le temps. En d'autres termes, marcher à la vitesse 1 peut être reformulé comme des personnes de fermeture qui partent entre $ \ [S_i-X_i, T_i-X_i-1 ] $.
La personne qui part à l'instant précédent peut être recherchée par la dichotomie, nous allons donc envisager de mettre à jour la section obtenue par la dichotomie $ N $ fois, mais il est nécessaire de mettre à jour la section efficacement. Il existe un arbre de segments de retard en tant que structure de données qui met à jour efficacement la section, et afin de trouver celle avec les coordonnées les plus proches dans la construction de la route qui est fermée à la circulation, ** la mise à jour doit être effectuée dans l'ordre de celle avec les coordonnées les plus éloignées **. J'ai pensé. Cependant, j'ai évité cette solution car je n'avais jamais utilisé d'arborescence de segments retardés et j'avais peur de la rendre boguée.
Ici, ** la chose importante dans la mise à jour de la section est de ne sauvegarder que les deux extrémités et de penser de manière cumulative à la fin ** (il en va de même pour la méthode imos et l'arbre de segment retardé). Par conséquent, ** ans_sectl [i]: deque ** qui stocke l'index de la section où la i-ème personne est à l'extrémité gauche, et ** ans_sectr [i]: l'index de la section où la i-ème personne est à l'extrémité droite. Préparez un deque ** pour enregistrer. (J'ai choisi $ \ parce que $ deque car il peut être récupéré avec $ O (1) $.)
De plus, bien qu'il soit réimprimé, ** celui avec les coordonnées les plus proches dans la construction de la route à fermer est en fait fermé **, donc lorsque vous recevez pour la première fois $ S_i, T_i, X_i $, la valeur de $ X_i $ est utilisée dans l'ordre croissant. Triez-le (xst). … ①
En dessous, un conteneur (ʻans) qui stocke le ** index de la section contenant l'heure de départ de chaque personne ** (= indice de construction de route qui peut être fermé à chaque personne) Si vous préparez et répétez ʻinsert s'il est inclus dans ʻans_sectl et ʻerase s'il est inclus dans ʻans_sectr dans l'ordre de la personne avec le plus petit nombre, ʻans accélérera le comportement souhaité. À
De plus, l'index de la section incluse dans ʻans est sauvegardé par ordre croissant s'il s'agit d'une ** carte ou d'un ensemble C ++ **, et il devrait être obtenu parce que la construction de la route a les coordonnées les plus proches incluses dans ʻans, donc le début du conteneur. Tout ce que vous avez à faire est de sortir la distance du point fermé correspondant à l'élément de ($ \ car $ ①).
De plus, lors de la recherche d'une personne dont l'heure de départ est incluse dans $ \ [S_i-X_i, T_i-X_i-1 ] $ dans une section fermée, l'extrémité gauche est L = (lower_bound (ALL (d), sx) - Vous devez trouver la bonne fin avec R = (upper_bound (ALL (d), tx-1) -d.begin ()) -1 avec d.begin (), mais $ \ [S_i-X_i, T_i S'il n'y a personne dont l'heure de départ est incluse dans -X_i-1 ] $, alors $ L> R $, vous devez donc exclure ce cas.
abc128e.cc
#include<algorithm>//sort,Recherche de bisection,Tel
#include<bitset>//Jeu de bits de longueur fixe
#include<cmath>//pow,journal etc.
#include<complex>//Nombre complexe
#include<deque>//File d'attente d'accès double
#include<functional>//trier plus
#include<iomanip>//setprecision(Erreur de sortie en virgule flottante)
#include<iostream>//Entrée sortie
#include<iterator>//Régler l'opération(Ensemble de produits,Ensemble de somme,Ensemble de différences, etc.)
#include<map>//map(dictionnaire)
#include<numeric>//iota(Génération d'une chaîne entière),pgcd et lcm(c++17)
#include<queue>//queue
#include<set>//ensemble
#include<stack>//empiler
#include<string>//Chaîne
#include<unordered_map>//Carte avec itérateur mais sans ordre
#include<unordered_set>//Il y a un itérateur mais l'ordre n'est pas maintenu défini
#include<utility>//pair
#include<vector>//Tableau de longueur variable
using namespace std;
typedef long long ll;
//macro
//pour la relation de 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.
#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--)
//x est un conteneur tel que vector
#define ALL(x) x.begin(),x.end() //Je souhaite omettre des arguments tels que le tri
#define SIZE(x) ll(x.size()) //taille à la taille_Changement de t à ll
//constant
#define INF 1000000000000 //10^12:Valeur extrêmement élevée,∞
#define MOD 1000000007 //10^9+7:Droit commun
#define MAXR 100000 //10^5:Portée maximale de la baie(Utilisé pour l'énumération des nombres premiers, etc.)
//Abréviation
#define PB push_back //Insérer dans le vecteur
#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
#define Umap unordered_map
#define Uset unordered_set
//Le traitement à la fin a été bâclé, ce genre d'implémentation lâche est inutile
signed main(){
//Code pour accélérer la saisie
ios::sync_with_stdio(false);
cin.tie(nullptr);
ll n,q;cin>>n>>q;
vector<vector<ll>> xst(n);
REP(i,n){
ll s,t,x;cin>>s>>t>>x;
xst[i]={x,s,t};
}
sort(ALL(xst));
vector<ll> d(q);
REP(i,q)cin>>d[i];
vector<deque<ll>> ans_sectl(q);
vector<deque<ll>> ans_sectr(q);
REP(i,n){
ll s,t,x;x=xst[i][0];s=xst[i][1];t=xst[i][2];
ll L=(lower_bound(ALL(d),s-x)-d.begin());
ll R=(upper_bound(ALL(d),t-x-1)-d.begin())-1;
//lower,soyez prudent supérieur
//2RE
if(L<=R){ans_sectl[L].PB(i);ans_sectr[R].PB(i);}
//cout << L << " " << R << endl;
}
map<ll,ll> ans;
REP(i,q){
ll sl=SIZE(ans_sectl[i]);
ll sr=SIZE(ans_sectr[i]);
REP(_,sl){
ans[*(ans_sectl[i].begin())]+=1;
ans_sectl[i].pop_front();
}
if(ans.empty()){
cout<<-1<<"\n";
}else{
cout<<xst[ans.begin()->F][0]<<"\n";
}
REP(_,sr){
ans[*(ans_sectr[i].begin())]-=1;
if(ans[*(ans_sectr[i].begin())]==0)ans.erase(*(ans_sectr[i].begin()));
ans_sectr[i].pop_front();
}
}
}
abc128e_set.cc
#include<algorithm>//sort,Recherche de bisection,Tel
#include<bitset>//Jeu de bits de longueur fixe
#include<cmath>//pow,journal etc.
#include<complex>//Nombre complexe
#include<deque>//File d'attente d'accès double
#include<functional>//trier plus
#include<iomanip>//setprecision(Erreur de sortie en virgule flottante)
#include<iostream>//Entrée sortie
#include<iterator>//Régler l'opération(Ensemble de produits,Ensemble de somme,Ensemble de différences, etc.)
#include<map>//map(dictionnaire)
#include<numeric>//iota(Génération d'une chaîne entière),pgcd et lcm(c++17)
#include<queue>//queue
#include<set>//ensemble
#include<stack>//empiler
#include<string>//Chaîne
#include<unordered_map>//Carte avec itérateur mais sans ordre
#include<unordered_set>//Il y a un itérateur mais l'ordre n'est pas maintenu défini
#include<utility>//pair
#include<vector>//Tableau de longueur variable
using namespace std;
typedef long long ll;
//macro
//pour la relation de 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.
#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--)
//x est un conteneur tel que vector
#define ALL(x) x.begin(),x.end() //Je souhaite omettre des arguments tels que le tri
#define SIZE(x) ll(x.size()) //taille à la taille_Changement de t à ll
//constant
#define INF 1000000000000 //10^12:Valeur extrêmement élevée,∞
#define MOD 1000000007 //10^9+7:Droit commun
#define MAXR 100000 //10^5:Portée maximale de la baie(Utilisé pour l'énumération des nombres premiers, etc.)
//Abréviation
#define PB push_back //Insérer dans le vecteur
#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
#define Umap unordered_map
#define Uset unordered_set
//Le traitement à la fin a été bâclé, ce genre d'implémentation lâche est inutile
signed main(){
//Code pour accélérer la saisie
ios::sync_with_stdio(false);
cin.tie(nullptr);
ll n,q;cin>>n>>q;
vector<vector<ll>> xst(n);
REP(i,n){
ll s,t,x;cin>>s>>t>>x;
xst[i]={x,s,t};
}
sort(ALL(xst));
vector<ll> d(q);
REP(i,q)cin>>d[i];
vector<deque<ll>> ans_sectl(q);
vector<deque<ll>> ans_sectr(q);
REP(i,n){
ll s,t,x;x=xst[i][0];s=xst[i][1];t=xst[i][2];
ll L=(lower_bound(ALL(d),s-x)-d.begin());
ll R=(upper_bound(ALL(d),t-x-1)-d.begin())-1;
//lower,soyez prudent supérieur
//2RE
if(L<=R){ans_sectl[L].PB(i);ans_sectr[R].PB(i);}
//cout << L << " " << R << endl;
}
set<ll> ans;
REP(i,q){
ll sl=SIZE(ans_sectl[i]);
ll sr=SIZE(ans_sectr[i]);
REP(_,sl){
ans.insert(*(ans_sectl[i].begin()));
ans_sectl[i].pop_front();
}
if(ans.empty()){
cout<<-1<<"\n";
}else{
cout<<xst[*ans.begin()][0]<<"\n";
}
REP(_,sr){
ans.erase(*(ans_sectr[i].begin()));
ans_sectr[i].pop_front();
}
}
}
Environ 1 heure (je mesurerai le temps à partir de maintenant)
Je résolvais un problème qui devenait plus difficile en ** mal interprétant ** "faire jusqu'à K fois" comme "juste faire K fois". Ce n'est pas bien ...
Tout d'abord, $ N $ et $ K $ ne sont pas très grands, vous devez donc comprendre qu'il semble y avoir une certaine marge dans le montant du calcul.
Ici, nous essayons d'abord la méthode de prélever avidement des bijoux extérieurs de grande valeur, mais la rejetons car ** il peut y avoir des bijoux de grande valeur à l'intérieur **. De plus, si vous effectuez l'opération de retrait du même côté après l'opération de compression **, les deux opérations sont inutiles , vous pouvez donc voir que vous devez effectuer l'opération de compression après avoir effectué l'opération de retrait ( opération Swap pour faciliter la réflexion! **).
Ici, si vous décidez du nombre de fois à retirer, le nombre de fois à emballer est également décidé, j'ai donc décidé de décider du nombre de fois à retirer $ i $ fois (la politique a commencé à s'égarer ici en raison de la première ** mauvaise lecture **, mais ** J'ai dû me calmer et lire l'énoncé du problème **.). Si $ i $ vaut 0, l'opération d'emballage ne peut pas être effectuée et la valeur totale maximale des bijoux après l'opération est de 0, donc $ i $ est considéré de 1 à $ min (k, n) $. De plus, même lorsque le nombre d'opérations à effectuer est de $ i $, je pensais que je prendrais avidement les bijoux avec la plus grande valeur à l'extérieur **, mais il peut y avoir des bijoux avec la plus grande valeur à l'intérieur **, donc cette politique Sera rejeté.
Par conséquent, en plus du fait qu'il y a encore de la place pour le calcul, j'ai essayé tout $ m $ lors de l'extraction de $ m $ de la gauche et de $ im $ de la droite ($ m = 0 $ ~ $ i). Découpez celui sorti avec $ et stockez-le dans le tableau $ s $). De plus, comme il est seulement nécessaire de conditionner les éléments extraits dans l'ordre de celui avec la valeur la plus basse (cependant, la valeur est 0 ou moins), triez $ s $ et emballez jusqu'à $ min (ki, i) $ fois. C'est bon. De plus, c'est un candidat pour la valeur maximale que la somme de $ s $ peut être calculée en définissant 0 comme article emballé.
Avec ce qui précède, le montant du calcul est $ O (X ^ 3 \ log {X}) $ avec $ X = min (N, K) $, et il n'est plus nécessaire d'accélérer, alors implémentez-le comme suit. ..
abc128d.py
import math
from collections import deque
n,k=map(int,input().split())
v=list(map(int,input().split()))
#C'était jusqu'à k fois mal lu
ans=0
for i in range(1,min(k,n)+1):
#Où prendre(N'est-ce pas toujours le plus gros?)
for m in range(i+1):
s=v[:m]+v[n-(i-m):]
s.sort()
#N'essayez pas d'emballer plus que ce que vous avez pris!
#K restant-je fois
for j in range(i,min(k,2*i)):#Si tu ne peux plus emballer
#Réécrire si moins de 0
if s[j-i]<0:s[j-i]=0
#Le plus gros que j'ai sorti(0 pour retourner)
ans=max(ans,sum(s))
#K restant-j fois(Je n'ai pas fait j au moment de la pause)
#À partir de là, répétez la mise en place et la mise en valeur(Si c'est pair, est-ce comme ça?)
#Tu n'en as même pas besoin, tu n'as pas besoin de consommer k fois
#print(sum(s))
print(ans)
Je n'ai pas eu beaucoup de temps cette fois, mais je l'ai résolu en environ une heure au total.
Parmi les deux conditions, j'ai considéré $ a + b = a \ oplus b $, ce à quoi il est facile de penser. Cela peut être compris avec un peu de réflexion, mais $ XOR $ est ** $ \ leftrightarrow $ ** où chaque bit peut être calculé indépendamment ** Il n'y a pas de report dans le calcul binaire **, donc a et b sont optionnels Vous pouvez voir qu'il n'y a que trois ensembles de (0,1), (1,0), (0,0) pour le bit de. … ①
Sous cela, la première condition, $ a + b \ leqq L $, est traitée, mais ici il faut penser que "si le premier chiffre est 0 ou 1, si le second chiffre est 0 ou 1, ..." Je pensais négligemment, "si elle tombe en dessous d'un chiffre, n'importe quel chiffre après ça va bien", mais cela fait longtemps que l'idée de ** chiffre DP ** s'applique aux problèmes avec de tels modèles. Je m'en suis souvenu après ça ...
<détails> Article d'ARMERIA et [Article de Kenchon](https://drken1215.hatenablog.com/entry/2019/ Si vous vous référez au 02/04/013700), il peut être généralisé que le chiffre DP peut être utilisé s'il existe les deux propriétés suivantes. 1: ** Je veux trouver le nombre de valeurs (valeurs maximum et minimum de XX) qui satisfont XX en dessous de la limite supérieure $ L $ ** (et $ L $ est grand)
2: Il y a une condition concernant les chiffres En vertu de cela, l'état de DP peut être déterminé comme suit.
$ DP [i] [plus petit]: = $ Une valeur lors de la détermination du chiffre du haut au chiffre $ i $
(Cependant, lorsque ** $ plus petit = 0 $, il y a des chiffres inférieurs à $ L $ jusqu'au chiffre $ i $, et lorsque $ plus petit = 1 $, tous les chiffres jusqu'au ième chiffre sont $ L $. On peut dire que c'est la même chose que **.) De plus, ** les transitions DP sont les suivantes à chaque fois **.
・ À partir de $ DP [i] [0] $, seul $ DP [i + 1] [0] $ peut être transféré, et tout chiffre $ i $ peut être sélectionné.
・ Lors de la transition de $ DP [i] [1] $ à $ DP [i + 1] [0] $, le chiffre $ i $ peut être sélectionné parmi tous les nombres inférieurs au chiffre $ i $ de $ L $. ça peut.
-Dans la transition de $ DP [i] [1] $ à $ DP [i + 1] [1] $, le chiffre $ i $ doit être le même que le chiffre $ i $ de $ L $. Si vous confirmez le mouvement du chiffre DP avec ce qui précède, ce problème est simple et vous pouvez déterminer l'état de DP comme suit. $ DP [i] [plus petit]: = $ Nombre de paires de $ (a, b) $ lors de la détermination du début au bit $ i $
(Cependant, lorsque $ plus petit $ vaut 0, les bits plus petits que $ L $ existent dans $ a + b $ du haut vers le bit $ i $, et lorsque $ plus petit $ vaut 1, le bit $ i $ du haut existe. Tous les bits jusqu'à l'œil sont égaux à $ L $) De plus, il existe trois types de transitions DP (\ car $ ① $). ・ $ DP [i + 1] [0] = 3 × DP [i] [0] \ ($ i $ bit de \ car a + b $ peut être 0 ou 1 $) $
・ Lorsque le chiffre $ i + 1 $ de $ L $ est 0
$ DP [i + 1] [1] = DP [i] [1] \ (\ car le bit $ i $ de a + b $ n'a que 0 $) $
・ Lorsque le chiffre $ i + 1 $ de $ L $ est 1.
$ DP [i + 1] [0] = DP [i] [1] \ (\ car a + b $ i-ème bit $ lorsque $ i $ bit th est 0 (a $ et $ b $ i-ème bit $ ) = (0,0)) $
$ DP [i + 1] [1] = 2 * DP [i] [1] \ (\ car a + b $ $ i $ bit Lorsque le premier est 1, $ (a $ et $ b $ i bit) Œil $) = (0,1), (1,0)) $ Le code ci-dessous implémente cette transition. Le jeu devait être en mesure de trouver immédiatement un DP numérique, donc j'aurais dû le résoudre un peu plus. C'est mortifiant.
Recommended Posts
code
abc129e.py
mod=10**9+7
l=input()
bit=[int(i) for i in l]
m=len(bit)
#J'en fais trop correctement, mais le chiffre DP
#Identique au plus petit
dp=[[0,0] for i in range(m)]
dp[0]=[1,2]
for i in range(m-1):
dp[i+1][0]=3*dp[i][0]%mod
if bit[i+1]==0:
dp[i+1][1]+=dp[i][1]
dp[i+1][1]%=mod
else:
dp[i+1][0]+=dp[i][1]
dp[i+1][1]+=(2*dp[i][1])
dp[i+1][0]%=mod
dp[i+1][1]%=mod
print(sum(dp[m-1])%mod)