【BZOJ4282】慎二的随机数列 乱搞
2024-09-21 13:22:36
【BZOJ4282】慎二的随机数列
Description
间桐慎二是间桐家著名的废柴,有一天,他在学校随机了一组随机数列, 准备使用他那强大的人工智能求出其最长上升子序列,但是天有不测风云,人有旦夕祸福,柳洞一成路过时把间桐慎二的水杯打翻了……
现在给你一个长度为 n 的整数序列,其中有一些数已经模糊不清了,现在请你任意确定这些整数的值,使得最长上升子序列最长(为何最长呢?因为间桐慎二向来对自己的人品很有信心) 。
Input
第一行一个正整数 n。
接下来 n 行,第 i 行若为“K x” ,则表示第 i 个数可以辨认且这个数为 x;
若为“N” ,则表示第i 个数已经辨认不清了。
Output
第一行一个整数,表示最长的最长上升子序列长度。
Sample Input
4
K 1
N
K 2
K 3
K 1
N
K 2
K 3
Sample Output
3
HINT
对于100%的数据,n ≤ 100000,|x| ≤ 10^9
题解:一开始想得极其复杂,看了Claris的题解后也觉得极不可做,然而直到看到了这个做法:
先统计有多少个N,然后将N去掉,然后对于每个k,我们令它的值-=它前面N的个数,最后跑最长上升子序列即可。
不要问我为什么是正确的。。。如果两个K之间N的个数比这两个数的差要多,那么为什么不直接将这个K扔掉呢。。。
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int maxn=100010;
int n,m,sum;
int s[maxn];
char str[5];
inline int rd()
{
int ret=0,f=1; char gc=getchar();
while(gc<'0'||gc>'9') {if(gc=='-') f=-f; gc=getchar();}
while(gc>='0'&&gc<='9') ret=ret*10+(gc^'0'),gc=getchar();
return ret*f;
}
int main()
{
n=rd();
int i,v,l,r,mid;
for(i=1;i<=n;i++)
{
scanf("%s",str);
if(str[0]=='K')
{
v=rd()-sum;
l=1,r=m+1;
while(l<r)
{
mid=(l+r)>>1;
if(s[mid]<v) l=mid+1;
else r=mid;
}
if(l>m) m++;
s[l]=v;
}
else sum++;
}
printf("%d",m+sum);
return 0;
}
最新文章
- Android 使用 DownloadManager 管理系统下载任务的方法,android管理系统
- Ubuntu 16.04 nvidia安装
- glsl计算sprite的亮度饱和度对比度
- Winform---文件夹操作
- Android bluetooth low energy (ble) writeCharacteristic delay callback
- jsp无法支持el标签及jstl标签
- 哈希表的C++实现(转)
- 在安装ISE的情况下,充分利用ISE的安装目录,查找资料
- SqlServer2005安装错误解决方法
- 开源控件ViewPagerIndicator学习
- 总结NHibernate 中删除数据的几种方法
- mysql添加远程用户
- DataTabel DataSet 对象 转换成json
- web前端开发面试题(未完待续)
- [转载] 基于Redis实现分布式消息队列
- mysql视图定义、原理、创建、使用
- Android广播接收器Broadcast Receiver-android学习之旅(十二)
- 【jQuery】(5)---jQuery CSS
- java 双因素认证(2FA)TOTP demo
- (转)winform之ListView