codeforces 514d R2D2 and Droid Army (RMQ+二分)
Jun 07, 2016 pm 03:00 PM题意: 有n*m的矩阵,然后你有k发子弹。现在你可以朝着任意列发射子弹,每一发子弹都会使该列上的数-1,最小减少到0。 现在问你连续最长的行数,在k发子弹内,使得这些行上的数全部为0. 思路: 看了别人代码,其实RMQ不是必要的,开m个双端队列也可以。因此
题意:
有n*m的矩阵,然后你有k发子弹。现在你可以朝着任意列发射子弹,每一发子弹都会使该列上的数值-1,最小减少到0。
现在问你连续最长的行数,在k发子弹内,使得这些行上的数值全部为0.
思路:
看了别人代码,其实RMQ不是必要的,开m个双端队列也可以。因此每次要问一段范围内的最大值都是按顺序下去的,队列可以解决。
二分长度len,枚举n行是否存在这样的i~i+len-1,所需要的子弹数
code:
#include <bits> using namespace std; typedef long long LL; const int MAXN = 1e5+5; const int MAXM = 5; int a[MAXN][5]; int dp[5][MAXN][20]; //five RMQ int res[MAXM], tres[MAXM]; int n, m, k; void RMQ(int t) { for(int i = 0;i <br> <br> </bits>

Article chaud

Outils chauds Tags

Article chaud

Tags d'article chaud

Bloc-notes++7.3.1
Éditeur de code facile à utiliser et gratuit

SublimeText3 version chinoise
Version chinoise, très simple à utiliser

Envoyer Studio 13.0.1
Puissant environnement de développement intégré PHP

Dreamweaver CS6
Outils de développement Web visuel

SublimeText3 version Mac
Logiciel d'édition de code au niveau de Dieu (SublimeText3)

Sujets chauds

Réduisez l'utilisation de la mémoire MySQL dans Docker

Comment modifier une table dans MySQL en utilisant l'instruction ALTER TABLE?

Comment résoudre le problème de MySQL ne peut pas ouvrir la bibliothèque partagée

Exécutez MySQL dans Linux (avec / sans conteneur Podman avec phpmyadmin)

Exécuter plusieurs versions MySQL sur macOS: un guide étape par étape

Comment configurer le cryptage SSL / TLS pour les connexions MySQL?

Comment sécuriser MySQL contre les vulnérabilités communes (injection SQL, attaques par force brute)?
