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

 代码：#include<bits/stdc++.h>usingnamespacestd;inta[100005];boola1[100005];intmain(){inti=1;while(cin>>a[i]){a1[i]=false;i++;}i--;intant=0,x=a[1],j=2,sum=1;a1[1]=true;

题意：求出一个最长单调不增子序列和最少的个数的单调不加的子序列的个数。根据dilworth:最少的全集个数等于最大的反链的元素个数。可以将求最少的个数的单调不加的子序列的个数转化为求最长上升子序列的长度。于是用二分+贪心来写点击查看代码#include<iostream>#include

C++[NOIP1999提高组]邮票面值设计详解题目背景题目描述输入格式输出格式样例#1样例输入#1样例输出#1完整代码（你们最想要的):[NOIP1999提高组]邮票面值设计题目背景除直接打表外，本题不保证存在正确且时间复杂度可以通过全部数据做法。由于测试数据过水，部

P1020[NOIP1999提高组]导弹拦截参考材料需要抽象一下，第一问就可以抽象为最长不上升子序列，第二问可以抽象为最长上升子序列长度。就如下图的情况：然后可以先\(n^2\)做法做，因为\(n\ge100000\)所以要滚动数组，求最长不上升子序列可以反向从n开始递推。我是n^2我不好

#include<bits/stdc++.h>usingnamespacestd;#defineintlonglongconstintN=1e5+10;intn;inta[N];intq[N];signedmain(){ ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); intx; while(cin>>x)a[++n]=x; intlen

前置：二分查找，最长单调不升子序列，最长单调不降子序列（dilworth）。题解：可以用来练习手写二分，二分优化的最长上升子序列时间复杂度O(nlogn)。但是坑是非常多的。代码：#include<bits/stdc++.h>usingnamespacestd;typedeflonglongll;constintN=1e5+10;inta[N],n,

传送门：P1020[NOIP1999提高组]导弹拦截题目大意：一个拦截导弹的系统，每次只能拦截高度不超过上一个的导弹求出：一个系统最多能拦截的导弹数量；要拦截所有导弹最少需要的该系统的数量。思路：第一问：一眼就是最长单调不上升子序列，朴素DP求解，复杂度为O(n^2)；请参考，能过掉50%

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

原题链接：https://www.luogu.com.cn/problem/P1016题意解读：用最少的加油费用到达另一个城市，中间有若干加油点，起点也可加油。解题思路：本题是一个贪心策略题：枚举每一个加油点i：1、初始加油点是起点2、汽车能跑的最大距离范围内，找到下一个更便宜的加油点的位置3、如果能找到更便

原题链接：https://www.luogu.com.cn/problem/P1015题意解读：一个N进制数M，把M正序和M逆序相加，几次之后得到是数是回文数，如果超过30次还无法得到回文数，输出Impossible!。解题思路：M最长100位，因此需要高精度，定义数组vector<int>m来存储整数M注意：16进制中可能存在'a~f''A~F'等字母，需

原题链接：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

原题链接：https://www.luogu.com.cn/problem/P1020题意解读：拦截系统发射导弹的高度依次不增，计算能拦截的最大导弹数以及需要几套拦截系统。解题思路：问题1：最多能拦截多少导弹？由于发射导弹高度不增，所以求一个最长不增子序列即可得到最大拦截数。方法一、O(n^2)做法：动态规划。采

链接：https://www.luogu.com.cn/problem/P1020这个题目一分为二：首先就是LIS：改下，改成最长不升子序列，复杂度：nlogn;然后用vector的贪心，复杂度：n^2(这里似乎可以二分降到nlogn，不过反正过了OwO!)被这个输入卡的好难受，建议用getline读取不确定的数题目：代码：#include<iostream>#incl

贪心、分治与倍增魔法+正妹吃月饼+修改+[JSOI2007]建筑抢修+[POI2012]HUR-WarehouseStore；[USACO17JAN]SecretCowCodeS+Moo+[NOIP2004普及组]FBI树+地毯填补问题+逆序对；【国家集训队】种树+哈希冲突；还有\(8\)题未研究。动态规划基础[USACO08MA

题目链接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

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

P1015[NOIP1999普及组]回文数https://www.luogu.com.cn/problem/P1015 思路将字符串m转换为10进制的值翻转m，也转换为10进制值，后运用10进制加这两个数转换为对

problemsolutioncodes#include<iostream>usingnamespacestd;intmain(){intn,k=1;cin>>n;//1.第n个数在第k条斜线上（前k条斜线的数的个数为等差数列）while(

[NOIP1999普及组]导弹拦截题目描述某国为了防御敌国的导弹袭击，发展出一种导弹拦截系统。但是这种导弹拦截系统有一个缺陷：虽然它的第一发炮弹能够到达任意的高度，但是以

题目链接：https://www.luogu.com.cn/problem/P1014有理数可枚举In1873Cantorprovedtherationalnumberscountable,i.e.theymaybeplacedinone-onecorrespon

https://www.luogu.com.cn/problem/P1014详解见代码内部注释部分#include<bits/stdc++.h>usingnamespacestd;typedeflonglongLL;typedefpair<LL,LL>PII;cons

题目传送门分析 1e5的数据，要nlogn才能过 第一问求的是 最长不上升序列,第二问求的是 最少的不上升子列个数第一问：传统的dp求LIS是\(n^2\)的复杂度，事实上第二层

[NOIP1999普及组]回文数题目描述若一个数（首位不为零）从左向右读与从右向左读都一样，我们就将其称之为回文数。例如：给定一个十进制数\(56\)，将\(56\)加\(65\)（即把\(5

题目链接：​​Cantor表​​这道题很水，但有的人没看懂题意，这不怪大家，怪题目没说清楚。给张图：看到这，你应该明白题目意思了。先看看有什么规律。我把这个数列写出来：