- 2024-08-18洛谷P1020 [NOIP1999 提高组] 导弹拦截(未完)
传送门:P1020[NOIP1999提高组]导弹拦截题目大意:一个拦截导弹的系统,每次只能拦截高度不超过上一个的导弹求出:一个系统最多能拦截的导弹数量;要拦截所有导弹最少需要的该系统的数量。思路:第一问:一眼就是最长单调不上升子序列,朴素DP求解,复杂度为O(n^2);请参考,能过掉50%
- 2024-07-04洛谷 P1020 [NOIP1999 提高组] 导弹拦截
题目描述某国为了防御敌国的导弹袭击,发展出一种导弹拦截系统。但是这种导弹拦截系统有一个缺陷:虽然它的第一发炮弹能够到达任意的高度,但是以后每一发炮弹都不能高于前一发的高度。某天,雷达捕捉到敌国的导弹来袭。由于该系统还在试用阶段,所以只有一套系统,因此有可能不能拦截所
- 2024-05-21CSP历年复赛题-P1016 [NOIP1999 提高组] 旅行家的预算
原题链接:https://www.luogu.com.cn/problem/P1016题意解读:用最少的加油费用到达另一个城市,中间有若干加油点,起点也可加油。解题思路:本题是一个贪心策略题:枚举每一个加油点i:1、初始加油点是起点2、汽车能跑的最大距离范围内,找到下一个更便宜的加油点的位置3、如果能找到更便
- 2024-05-20CSP历年复赛题-P1015 [NOIP1999 普及组] 回文数
原题链接:https://www.luogu.com.cn/problem/P1015题意解读:一个N进制数M,把M正序和M逆序相加,几次之后得到是数是回文数,如果超过30次还无法得到回文数,输出Impossible!。解题思路:M最长100位,因此需要高精度,定义数组vector<int>m来存储整数M注意:16进制中可能存在'a~f''A~F'等字母,需
- 2024-05-20CSP历年复赛题-P1014 [NOIP1999 普及组] Cantor 表
原题链接:https://www.luogu.com.cn/problem/P1014题意解读:根据z字形遍历,求第n个数。解题思路:根据题意,遍历顺序如下图所示观察得知,第i层的x/y的x+y=i+1,并且如果i是偶数,x从1开始枚举;如果i是奇数,x从i开始枚举100分代码:#include<bits/stdc++.h>usingnamespacestd;in
- 2024-04-23洛谷题单指南-动态规划2-P1020 [NOIP1999 提高组] 导弹拦截
原题链接:https://www.luogu.com.cn/problem/P1020题意解读:拦截系统发射导弹的高度依次不增,计算能拦截的最大导弹数以及需要几套拦截系统。解题思路:问题1:最多能拦截多少导弹?由于发射导弹高度不增,所以求一个最长不增子序列即可得到最大拦截数。方法一、O(n^2)做法:动态规划。采
- 2024-04-05P1020 [NOIP1999 提高组] 导弹拦截
链接:https://www.luogu.com.cn/problem/P1020这个题目一分为二:首先就是LIS:改下,改成最长不升子序列,复杂度:nlogn;然后用vector的贪心,复杂度:n^2(这里似乎可以二分降到nlogn,不过反正过了OwO!)被这个输入卡的好难受,建议用getline读取不确定的数题目:代码:#include<iostream>#incl
- 2024-03-31上课笔记大全
贪心、分治与倍增魔法+正妹吃月饼+修改+[JSOI2007]建筑抢修+[POI2012]HUR-WarehouseStore;[USACO17JAN]SecretCowCodeS+Moo+[NOIP2004普及组]FBI树+地毯填补问题+逆序对;【国家集训队】种树+哈希冲突;还有\(8\)题未研究。动态规划基础[USACO08MA
- 2023-06-03算法刷题记录:[NOIP1999]回文数
题目链接https://ac.nowcoder.com/acm/contest/19859/G题目分析高精度相加+进制转换+判断回文的模拟题。AC代码//Problem:[NOIP1999]回文数//Contest:NowCoder//URL:https://ac.nowcoder.com/acm/contest/19859/G//MemoryLimit:262144MB//TimeLimit:20
- 2023-05-18 [NOIP1999 普及组] 导弹拦截
[NOIP1999普及组]导弹拦截题目描述某国为了防御敌国的导弹袭击,发展出一种导弹拦截系统。但是这种导弹拦截系统有一个缺陷:虽然它的第一发炮弹能够到达任意的高度,但是以后每一发炮弹都不能高于前一发的高度。某天,雷达捕捉到敌国的导弹来袭。由于该系统还在试用阶段,所以只有一套
- 2023-02-11P1015 [NOIP1999 普及组] 回文数
P1015[NOIP1999普及组]回文数https://www.luogu.com.cn/problem/P1015 思路将字符串m转换为10进制的值翻转m,也转换为10进制值,后运用10进制加这两个数转换为对
- 2023-02-08【NOIP1999】【codevs1083】Cantor表(找规律)
problemsolutioncodes#include<iostream>usingnamespacestd;intmain(){intn,k=1;cin>>n;//1.第n个数在第k条斜线上(前k条斜线的数的个数为等差数列)while(
- 2023-01-31P1020 [NOIP1999 普及组] 导弹拦截
[NOIP1999普及组]导弹拦截题目描述某国为了防御敌国的导弹袭击,发展出一种导弹拦截系统。但是这种导弹拦截系统有一个缺陷:虽然它的第一发炮弹能够到达任意的高度,但是以
- 2023-01-29P1014 [NOIP1999 普及组] Cantor 表
题目链接:https://www.luogu.com.cn/problem/P1014有理数可枚举In1873Cantorprovedtherationalnumberscountable,i.e.theymaybeplacedinone-onecorrespon
- 2023-01-19P1014 [NOIP1999 普及组] Cantor 表(模拟/枚举)
https://www.luogu.com.cn/problem/P1014详解见代码内部注释部分#include<bits/stdc++.h>usingnamespacestd;typedeflonglongLL;typedefpair<LL,LL>PII;cons
- 2023-01-08[NOIP1999 普及组] 导弹拦截
题目传送门分析 1e5的数据,要nlogn才能过 第一问求的是 最长不上升序列,第二问求的是 最少的不上升子列个数第一问:传统的dp求LIS是\(n^2\)的复杂度,事实上第二层
- 2022-11-28p1015 [NOIP1999 普及组] 回文数
[NOIP1999普及组]回文数题目描述若一个数(首位不为零)从左向右读与从右向左读都一样,我们就将其称之为回文数。例如:给定一个十进制数\(56\),将\(56\)加\(65\)(即把\(5
- 2022-11-18Cantor表(NOIP1999)
题目链接:Cantor表这道题很水,但有的人没看懂题意,这不怪大家,怪题目没说清楚。给张图:看到这,你应该明白题目意思了。先看看有什么规律。我把这个数列写出来:
- 2022-09-03信息学一本通 1309:【例1.6】回文数(Noip1999)
时间限制:1000ms 内存限制:65536KB提交数:17647 通过数:7270【题目描述】若一个数(首位不为零)从左向右读与从右向左读都是一样,我们就将其