Codeforces Round # 672 (Div.2) Examen Bacha (10/16)
Les résultats de cette fois
Impressions de cette époque
Cette fois, j'ai pu le résoudre sans émettre WA (même si cela a pris du temps), grâce au fait que j'ai procédé en organisant les paramètres du problème. De plus, le problème D était gênant d'augmenter la vitesse en s'asseyant, donc si je le manipulais comme un ensemble, ce serait dangereusement TLE (1996ms / 2000ms).
Il y avait beaucoup de gens qui ont amélioré C2 en regardant le classement de l'ami, mais je ne me sentais pas motivé. Je n'ai pas évolué pendant deux jours de suite depuis hier, alors je vais essayer de résoudre fermement après demain pour ne pas prendre cette habitude.
Problème A
Nombre de chutes avec BIT! ?? Cependant, ce n’était pas le cas. ** La valeur maximale du nombre de chutes ** est $ \ frac {n (n-1)} {2} $ uniquement lorsque les éléments sont disposés par ordre décroissant **, alors déterminez si ce sera la valeur maximale. .. Notez également que lorsqu'il y a plusieurs éléments identiques, ce ne sera pas $ \ frac {n (n-1)} {2} $, mais gentiment il y a un cas dans l'exemple.
A.py
for _ in range(int(input())):
n=int(input())
a=list(map(int,input().split()))
if a==sorted(a,reverse=True) and len(set(a))==n:
print("NO")
else:
print("YES")
Problème B
Au début, j'ai mal compris le problème et c'était dangereux (je pensais que le même élément parce que tout est le même!).
Si les $ k $ bits de $ a \ _i et a \ _j $ sont respectivement $ a \ _ {ik} et a \ _ {jk} $, alors $ a \ _ {ik} $ & $ a \ _ { jk} $, $ a \ _ {ik} \ oplus a \ _ {jk} $ ressemble à ceci: (** petit à petit! **)
| 0 | 0 | 0 | 0 |
| 0 | 1 | 0 | 1 |
| 1 | 0 | 0 | 1 |
| 1 | 1 | 1 | 0 |
Par conséquent, $ a \ _i $ & $ a \ _ j \ geqq a \ _i \ oplus a \ _j $ vaut pour $ (a \ _ {ik}, a \ _ {jk}) = (0,0), Ce sera (1,1) $. Par conséquent, quand il y a un bit (MSB) ** qui représente la première fois à partir du bit on ** de $ a \ _i $, le nombre qui satisfait $ a \ _i $ est le même nombre de MSB ($ ). Parce que $ est un nombre positif, le bit tient toujours).
Par conséquent, chaque $ a \ _ {i} $ est classé par MSB, et quand il y a $ x $ tel $ a \ _ {i} $, il y a des combinaisons $ \ _x C \ _2 $. Existe. La réponse est de trouver la somme de ceux-ci.
B.py
from collections import Counter
for _ in range(int(input())):
n=int(input())
x=[0 for i in range(30)]
l=list(map(int,input().split()))
for i in l:
for j in range(29,-1,-1):
if (i>>j)&1:
x[j]+=1
break
ans=0
for i in x:
if i>1:
ans+=(i*(i-1)//2)
print(ans)
Problème C1
Il est déjà apparu dans Kodofo. Cependant, j'ai fait une erreur dans l'indice. Es-tu stupide ...?
** La valeur maximale de la somme (spéciale) des sous-colonnes ** peut être trouvée, so-or + dépend du-or + de l'élément immédiatement sélectionné. Par conséquent, considérez le DP suivant.
$ dp [i] [j]: = $ (valeur maximale de la somme (spéciale) des sous-colonnes sélectionnées jusqu'à $ i $ e nombre, mais dernier nombre sélectionné lorsque $ j = 0 $ Quand est-et $ j = 1 $, le dernier nombre sélectionné est +)
La transition est la suivante. Il existe environ trois façons de faire la transition de la sous-colonne. Il faut prêter attention uniquement au cas de-ou +.
(1) Lorsque $ i + 1 $ e élément n'est pas sélectionné
(2) Lors de la sélection de l'élément $ i + 1 $ ème au lieu de la première fois
(3) Lors de la sélection de l'élément $ i + 1 $ ème pour la première fois
Si vous trouvez les valeurs maximales ci-dessus dans l'ordre, $ max (dp [n-1]) $ est la réponse.
C.py
inf=10**12
import sys
input = sys.stdin.readline
for _ in range(int(input())):
n,q=map(int,input().split())
a=list(map(int,input().split()))
dp=[[-inf,-inf] for i in range(n)]
dp[0]=[-inf,a[0]]
for i in range(n-1):
dp[i+1][0]=dp[i][0]
dp[i+1][1]=dp[i][1]
dp[i+1][0]=max(dp[i+1][0],dp[i][1]-a[i+1])
dp[i+1][1]=max(dp[i+1][1],dp[i][0]+a[i+1])
dp[i+1][1]=max(dp[i+1][1],a[i+1])
print(max(dp[n-1]))
#print(dp)
Problème C2
Je vais sauter cette fois.
Problème D
Je pense que cela aurait dû être résolu à grande vitesse, je voudrais donc améliorer la puissance de montage.
Il y a des sections fermées $ n $ ** Vous pouvez vérifier si les extrémités de chaque section se chevauchent **. En d'autres termes, en ne vous installant qu'à la fin de la section , vous n'avez besoin de considérer que les coordonnées $ 2n $ au maximum. Par conséquent, les sections $ k $ qui chevauchent au moins une coordonnée peuvent être sélectionnées comme section sujet ( Paraphrase du sujet! **).
Ici, il y a des moments où vous pouvez sélectionner ** une combinaison de la même section avec plusieurs coordonnées ** (✳︎), vous devez donc faire attention. Par exemple, les parties rouges et jaunes de la figure ci-dessous ($ k = 3 $).
Aussi, ** Tout d'abord, je veux penser avidement **, donc je vais les regarder dans l'ordre croissant des coordonnées. Ici, en supposant qu'il y a $ x $ déjà sélectionnés sections et $ y $ sections sélectionnées pour la première fois à une certaine coordonnée, "comment sélectionner une section qui n'a pas encore été sélectionnée" est changé de "comment sélectionner toute section qui peut être sélectionnée ici" à ". Le nombre total est $ _ {x + y} C_k-_xC_k $, à l'exclusion de "Comment choisir uniquement parmi les sections déjà sélectionnées" (Il a fallu beaucoup de temps pour le remarquer, mais un simple ** principe d'encapsulation * *est). Par conséquent, si vous gérez l'intervalle contenant chaque coordonnée, vous pouvez calculer la combinaison avec $ O (1) $ (le pré-calcul de la combinaison est $ O (n) $).
Par conséquent, l'implémentation est la suivante (** Résumez l'implémentation! **).
nowseg: ensemble contenant les informations de la section, y compris les coordonnées que vous recherchez (coordonnées à l'extrémité droite de la section, index) nexseg: Carte qui contient les informations de la section qui n'a pas encore été vue, avec l'extrémité gauche de la section comme clé et (les coordonnées de l'extrémité droite de la section, l'index) comme valeur coordonnées: défini avec des fins d'intervalle possibles (car je voulais le garder dans l'ordre croissant et ignorer la mise en œuvre de la pression assise)
De cette façon, à chaque coordonnée $ i $
(1) Définissez la taille de nowseg sur $ x $ et la taille de nexseg [i] sur $ y $. ② Ajoutez tous les éléments de nexseg [i] à nowseg ③ Supprimez uniquement ceux de nowseg dont la coordonnée la plus à droite de la section est $ i $ (vérifiez dans l'ordre à partir du premier élément de nowseg)
Il peut être facilement implémenté en effectuant les opérations dans l'ordre de.
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 998244353 //10^9+7:Droit commun
#define MAXR 300002 //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
template<ll mod> class modint{
public:
ll val=0;
//constructeur
modint(ll x=0){while(x<0)x+=mod;val=x%mod;}
//Copier le constructeur
modint(const modint &r){val=r.val;}
//Opérateur arithmétique
modint operator -(){return modint(-val);} //unaire
modint operator +(const modint &r){return modint(*this)+=r;}
modint operator -(const modint &r){return modint(*this)-=r;}
modint operator *(const modint &r){return modint(*this)*=r;}
modint operator /(const modint &r){return modint(*this)/=r;}
//Opérateur d'assignation
modint &operator +=(const modint &r){
val+=r.val;
if(val>=mod)val-=mod;
return *this;
}
modint &operator -=(const modint &r){
if(val<r.val)val+=mod;
val-=r.val;
return *this;
}
modint &operator *=(const modint &r){
val=val*r.val%mod;
return *this;
}
modint &operator /=(const modint &r){
ll a=r.val,b=mod,u=1,v=0;
while(b){
ll t=a/b;
a-=t*b;swap(a,b);
u-=t*v;swap(u,v);
}
val=val*u%mod;
if(val<0)val+=mod;
return *this;
}
//Opérateur de comparaison d'équivalence
bool operator ==(const modint& r){return this->val==r.val;}
bool operator <(const modint& r){return this->val<r.val;}
bool operator !=(const modint& r){return this->val!=r.val;}
};
using mint = modint<MOD>;
//Flux d'E / S
istream &operator >>(istream &is,mint& x){//N'ajoutez pas de const à x
ll t;is >> t;
x=t;
return (is);
}
ostream &operator <<(ostream &os,const mint& x){
return os<<x.val;
}
//Puissance
mint modpow(const mint &a,ll n){
if(n==0)return 1;
mint t=modpow(a,n/2);
t=t*t;
if(n&1)t=t*a;
return t;
}
//Calcul du coefficient binomial
mint fac[MAXR+1],finv[MAXR+1],inv[MAXR+1];
//Créer une table
void COMinit() {
fac[0]=fac[1]=1;
finv[0]=finv[1]=1;
inv[1]=1;
FOR(i,2,MAXR){
fac[i]=fac[i-1]*mint(i);
inv[i]=-inv[MOD%i]*mint(MOD/i);
finv[i]=finv[i-1]*inv[i];
}
}
//Partie calcul
mint COM(ll n,ll k){
if(n<k)return 0;
if(n<0 || k<0)return 0;
return fac[n]*finv[k]*finv[n-k];
}
signed main(){
//Code pour accélérer la saisie
//ios::sync_with_stdio(false);
//cin.tie(nullptr);
COMinit();
ll n,k;cin>>n>>k;
map<ll,vector<pair<ll,ll>>> nexseg;
set<pair<ll,ll>> nowseg;
set<ll> coordinates;
REP(i,n){
ll l,r;cin>>l>>r;
nexseg[l].PB(MP(r,i));
coordinates.insert(l);
coordinates.insert(r);
}
//Scanner les coordonnées de gauche
//Nouveauté à l'origine(Vérifiez le numéro)→ Vérifier les éléments manquants
//Puis supprimez
mint ans=0;
FORA(i,coordinates){
//cout<<1<<endl;
ll x,y;x=SIZE(nowseg);
if(nexseg.find(i)==nexseg.end()){
y=0;
ans+=0;
}else{
y=SIZE(nexseg[i]);
FORA(j,nexseg[i]){
nowseg.insert(j);
}
ans+=(COM(x+y,k)-COM(x,k));
}
//cout<<x<<" "<<y<<" "<<ans<<endl;
auto j=nowseg.begin();
//cout<<j->F<<" "<<j->S<<endl;
while(j!=nowseg.end()){
//cout<<1<<endl;
if(j->F==i){
j=nowseg.erase(j);
}else{
break;
}
}
}
cout<<ans<<endl;
}
Problème E
Je vais sauter cette fois.
Recommended Posts