当前位置：首页 > news >正文

洛谷9.16

news 来源：原创 2024/9/19 23:55:28

[HNOI2004] 打鼹鼠

题目描述

鼹鼠是一种很喜欢挖洞的动物，但每过一定的时间，它还是喜欢把头探出到地面上来透透气的。根据这个特点阿牛编写了一个打鼹鼠的游戏：在一个 $\times n$ 的网格中，在某些时刻鼹鼠会在某一个网格探出头来透透气。你可以控制一个机器人来打鼹鼠，如果 $i$ 时刻鼹鼠在某个网格中出现，而机器人也处于同一网格的话，那么这个鼹鼠就会被机器人打死。而机器人每一时刻只能够移动一格或停留在原地不动。机器人的移动是指从当前所处的网格移向相邻的网格，即从坐标为 $(i, j)$ 的网格移向 $(i - 1, j), (i + 1, j), (i, j - 1), (i, j + 1)$ 四个网格，机器人不能走出整个 $\times n$ 的网格。游戏开始时，你可以自由选定机器人的初始位置。

现在知道在一段时间内，鼹鼠出现的时间和地点，请编写一个程序使机器人在这一段时间内打死尽可能多的鼹鼠。

输入格式

第一行为 $n, m$ （ $\le 1000$ ， $\le {10}^4$ ），其中 $m$ 表示在这一段时间内出现的鼹鼠的个数，接下来的 $m$ 行中每行有三个数据 $\mathit{time}, x, y$ 表示在游戏开始后 $\mathit{time}$ 个时刻，在第 $x$ 行第 $y$ 个网格里出现了一只鼹鼠。 $\mathit{time}$ 按递增的顺序给出。注意同一时刻可能出现多只鼹鼠，但同一时刻同一地点只可能出现一只鼹鼠。

输出格式

仅包含一个正整数，表示被打死鼹鼠的最大数目。

样例 #1

样例输入 #1

2 2	         
1 1 1		
2 2 2

样例输出 #1

思路

设 $d p [i]$ 为地鼠序列中以下标为 $i$ 结尾的已打地鼠的数量，遍历其他的地鼠 $j$ ，若曼哈顿距离小于 $t_i-t_j$ ，则说明能打到下一个地鼠，状态转移

$if \ t_j-t_i>dis(i,j) \ then \ dp[i]=max(dp[i],dp[j]+1)$
为了防止重复遍历，令 $j$ 的下标小于 $i$

代码

#include<bits/stdc++.h>
using namespace std;
const int M = 10005;
int n, m;
struct node_ {int t, x, y;
}node[M];
int dp[M];
bool check(node_ a, node_ b) {int dis = abs(a.x - b.x) + abs(a.y - b.y);return dis <= b.t - a.t;
}
int main() {cin.tie(0);cout.tie(0);ios::sync_with_stdio(0);cin >> n >> m;for(int i = 1; i <= m; i ++ ) {cin >> node[i].t >> node[i].x >> node[i].y;dp[i] = 1;}for(int i = 1; i <= m; i ++ ) {for(int j = 1; j < i; j ++ ) {if(check(node[j], node[i])) dp[i] = max(dp[i], dp[j] + 1);}}int res = 1;for(int i = 1; i <= m; i ++ ) {res = max(res, dp[i]);}cout << res << endl;return 0;
}

[NOIP1999 提高组] 导弹拦截

题目描述

某国为了防御敌国的导弹袭击，发展出一种导弹拦截系统。但是这种导弹拦截系统有一个缺陷：虽然它的第一发炮弹能够到达任意的高度，但是以后每一发炮弹都不能高于前一发的高度。某天，雷达捕捉到敌国的导弹来袭。由于该系统还在试用阶段，所以只有一套系统，因此有可能不能拦截所有的导弹。

输入导弹依次飞来的高度，计算这套系统最多能拦截多少导弹，如果要拦截所有导弹最少要配备多少套这种导弹拦截系统。

输入格式

一行，若干个整数，中间由空格隔开。

输出格式

两行，每行一个整数，第一个数字表示这套系统最多能拦截多少导弹，第二个数字表示如果要拦截所有导弹最少要配备多少套这种导弹拦截系统。

样例 #1

样例输入 #1

389 207 155 300 299 170 158 65

样例输出 #1

6
2

提示

对于前 $50\%$ 数据（NOIP 原题数据），满足导弹的个数不超过 $10^4$ 个。该部分数据总分共 $100$ 分。可使用 $\mathcal O(n^2)$ 做法通过。
对于后 $50\%$ 的数据，满足导弹的个数不超过 $10^5$ 个。该部分数据总分也为 $100$ 分。请使用 $\mathcal O(n\log n)$ 做法通过。

对于全部数据，满足导弹的高度为正整数，且不超过 $5\times 10^4$ 。

此外本题开启 spj，每点两问，按问给分。

NOIP1999 提高组第一题

$\text{upd 2022.8.24}$ ：新增加一组 Hack 数据。

思路

求最多能拦截多少枚实际是求最长不上升子序列，求需要多少导弹系统实际是求最长上升子序列

对于 $i < j, d p [j] = d p [i] + 1, a [i] >= a [j]$ ，这是最长上升子序列的状态转移，最朴素的做法使用两重循环，此时复杂度为 $O(n^2)$ ，求最长上升子序列与这个类似，这样做只能过一半的数据，因此考虑优化
使用down[i]维护不上升子序列的状态，若 $a [i] <= d o w n . ba c k ()$ ，则将 $a [i]$ 加入到 $d o w n$ 中，否则找到第一个小于 $a [i]$ 的元素进行替换，为什么是小于不是小于等于呢，例如若 $\ down = [5, 3 ,2]$ 那么接下来 $d o w n$ 应该变成 $[5, 3, 3]$ 而不是 $[5, 3, 2]$ ，同理可以使用一个 $u p [i]$ 维护上升子序列的状态，完成最长上升子序列

代码

#include<bits/stdc++.h>
using namespace std;
const int N = 1e5 + 5;
int n, h[N];
int up[N], down[N];
int ttup = -1, ttdown = -1;int find1(int l, int r, int x) { // 降序，找第一个小于x元素，若x=3 down = 5 3 2 则应该变成 5 3 3 而不是 5 3 2 所以是找第一个小于xwhile(l < r) {int mid = (l + r) >> 1;if(down[mid] < x) r = mid;else l = mid + 1;}return l;
}
int find2(int l, int r, int x) { // 升序，找第一个大于等于x的元素  x = 4 up = 3 5 7 变成 3 4 7while(l < r) {int mid = (l + r) >> 1;if(up[mid] >= x) r = mid;else l = mid + 1;}return l;
}
void print() {cout << "up == ";for(int i = 0; i <= ttup; i ++ ) {cout << up[i] << " ";}cout << endl;cout << "down == ";for(int i = 0; i <= ttdown; i ++ ) {cout << down[i] << " ";}cout << endl;
}
int main() {cin.tie(0);cout.tie(0);ios::sync_with_stdio(0);while(cin >> h[n]) n ++ ;for(int i = 0; i < n; i ++ ) {if(ttdown == -1 || down[ttdown] >= h[i]) down[++ ttdown] = h[i];else {int pos = find1(0, ttdown, h[i]);down[pos] = h[i];}if(ttup == -1 || up[ttup] < h[i]) up[++ ttup] = h[i];else {int pos = find2(0, ttup, h[i]);up[pos] = h[i];}
//        print();}cout << ttdown + 1 << endl << ttup + 1 << endl;return 0;
}

kkksc03考前临时抱佛脚

题目背景

kkksc03 的大学生活非常的颓废，平时根本不学习。但是，临近期末考试，他必须要开始抱佛脚，以求不挂科。

题目描述

这次期末考试，kkksc03 需要考 $4$ 科。因此要开始刷习题集，每科都有一个习题集，分别有 $s_1,s_2,s_3,s_4$ 道题目，完成每道题目需要一些时间，可能不等（ $A_1,A_2,\ldots,A_{s_1}$ ， $B_1,B_2,\ldots,B_{s_2}$ ， $C_1,C_2,\ldots,C_{s_3}$ ， $D_1,D_2,\ldots,D_{s_4}$ ）。

kkksc03 有一个能力，他的左右两个大脑可以同时计算 $2$ 道不同的题目，但是仅限于同一科。因此，kkksc03 必须一科一科的复习。

由于 kkksc03 还急着去处理洛谷的 bug，因此他希望尽快把事情做完，所以他希望知道能够完成复习的最短时间。

输入格式

本题包含 $5$ 行数据：第 $1$ 行，为四个正整数 $s_1,s_2,s_3,s_4$ 。

第 $2$ 行，为 $A_1,A_2,\ldots,A_{s_1}$ 共 $s_1$ 个数，表示第一科习题集每道题目所消耗的时间。

第 $3$ 行，为 $B_1,B_2,\ldots,B_{s_2}$ 共 $s_2$ 个数。

第 $4$ 行，为 $C_1,C_2,\ldots,C_{s_3}$ 共 $s_3$ 个数。

第 $5$ 行，为 $D_1,D_2,\ldots,D_{s_4}$ 共 $s_4$ 个数，意思均同上。

输出格式

输出一行,为复习完毕最短时间。

样例 #1

样例输入 #1

样例输出 #1

提示

$1\leq s_1,s_2,s_3,s_4\leq 20$ 。

$1\leq A_1,A_2,\ldots,A_{s_1},B_1,B_2,\ldots,B_{s_2},C_1,C_2,\ldots,C_{s_3},D_1,D_2,\ldots,D_{s_4}\leq60$ 。

思路

贪心，由于只能同时完成同一科的两门课，因此对每一科单独分析，使每一科完成时间最短，最后相加即可，单科完成时间可以使用背包来做

代码

#include<bits/stdc++.h>
using namespace std;
int s[5][25];
int d[5];
int dp[5][2000];
int main() {for(int i = 1; i <= 4; i ++ ) cin >> s[i][0];for(int i = 1; i <= 4; i ++ ) {for(int j = 1; j <= s[i][0]; j ++ ) {cin >> s[i][j];d[i] += s[i][j];}}for(int i = 1; i <= 4; i ++ ) {for(int j = 1; j <= s[i][0]; j ++ ) {for(int k = d[i] / 2; k >= s[i][j]; k -- ) {dp[i][k] = max(dp[i][k], dp[i][k - s[i][j]] + s[i][j]);}}}int res = 0;for(int i = 1; i <= 4; i ++ ) {res += d[i] - dp[i][d[i]/2];}cout << res << endl;return 0;
}