图床推荐

十分推荐这个图床 https://sm.ms

  • 当你想在洛谷讨论中分享图片,却发现图片被打上水印?
  • 当你想上传高清图片时,却发现因为图片太大无法上传?

没关系!来 sm.ms 轻松解决!

好了不废话了以下进入正题


sm.ms 使用方法:

  1. 在浏览器中输入 sm.ms ,界面如图 TIM截图20190723203517.png
  2. 将要上传的图片拖入中央写有“Drag & drop files here”字样的矩形,或直接在单击底部蓝色“browse”按钮后在对话框中选择图片
  3. 选择好图片后,单击upload按钮完成上传 TIM截图20190723204329.png
  4. 等待上传完毕后,即可在底部的“URL”中复制链接,或在“Markdown”和“Markdown with link”中复制Markdown版链接 TIM截图20190723204829.png

注:图床外链为一次性生成,但可永久使用


分享一个快读

如题

1
2
3
4
5
6
7
8
9
10
11
12
13
14
inline int read()
{
int s=0,w=1;
char ch=getchar();
while(ch<'0' || ch>'9'){
if(ch=='-') w=-1;
ch=getchar();
}
while(ch>='0' && ch<='9'){
s=(s<<3)+(s<<1)+(ch^48);//精华
ch=getchar();
}
return s*w;
}

题解 P2782 【友好城市】

题解

条件分析

首先,我们分析一下航道不交叉的条件。

如果有一条已经被批准的航道,南北坐标为N1,S1;

则第二条N2<N1,S2>S1(或恰好相反)的航道将不能被批准,因为他们发生了交叉。


参照此图:

1
2
3
4
5
6
7
8
9
.N   .N
\ |
\ |
\ |
\|
|
|\
| \
.S .S

因此,要满足题目中的条件,需要保证南岸序列和北岸序列单调上升(题目中交代了坐标不会重合)。

我们可以按北岸坐标大小对城市进行排序,来保证北岸序列单调上升;

然后,南岸序列的最长上升子序列长度就是能够批准的航线条数。

最长上升子序列

如何求出最长上升子序列的长度?

不难看出,这个问题用动态规划解决会很简单,

边界为f(1)=1

状态转移方程为f(i)=max{f(i),f(j)+1|S(i)>s(j)} (i=1,i<=n) (j=i+1,j<=n)

然而 这题的数据规模。。。 n<=200000;

n方的动态规划肯定TLE,我们得想点别的办法。

假设有一个序列 100 389 207 99 300,从前往后扫描;

  1. 扫描到100,将100加入序列
  2. 扫描到389,将389加入序列尾部
  3. 扫描到207,将207替换掉389(因为它更小,可以让更多数插进来)
  4. 扫描到99,将99替换掉100(这不会使结果变差)
  5. 扫描到300,加入序列尾部(可以看出,如果不执行第三步的替换,这里会漏过最优解)

因此,我们的策略是:如果当前数比序列尾更大,直接将其插入尾部,序列长度+1;

否则用它替换掉序列中比它大但又最小的一个(保持单调性)。

对于情况一,可在常数时间内完成;

对于情况二,STL中有现成的函数——lower_bound(这题upper_bound也可以),他的时间复杂度是logn,效率很高(其实就是二分查找)。


贴代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44

#include<iostream>
#include<algorithm>
using namespace std;
struct city{
//方便排序
int north;//北岸
int south;//南岸
};
struct cmp{
bool operator () (city& a,city& b)
{
return a.north<b.north;
}
};
city c[200005];
int lis[200005];//LIS序列
int ans=0;//LIS长度
int n;
int main()
{
ios::sync_with_stdio(false);//流式I/O加速
cin.tie(0);
cin>>n;
for(int i=1;i<=n;++i)
{
cin>>c[i].north>>c[i].south;
}
sort(c+1,c+n+1,cmp());//将城市按北岸排序,之后就没北岸什么事了
for(int i=1;i<=n;i++)
{
if(c[i].south>lis[ans])//如果能插入
{
lis[++ans]=c[i].south;//插入至末尾
}
else
{
//否则二分查找出序列中比它大但又最小的一个并替换
*lower_bound(lis+1,lis+ans+1,c[i].south)= (c[i].south);
}
}
cout<<ans<<endl;
return 0;
}

————写小白也能看懂的题解!

【置顶】Crash Report

由于某些乱七八糟的原因,电脑上的博客文件夹没了。。。

搞得我又用Hexo搭了一遍(这可真糟糕)

新的Blog加装了一个Live2D模型(没错,就是你在右下角看到的东西)

正在加入统计和PWA功能

(To Be Continued)