orz教主的算法太强大了！

orz!orz!orz!orz!orz!orz!orz!orz!orz!orz!orz!

orz!orz!orz!orz!orz!orz!orz!orz!orz!orz!orz!

orz!orz!orz!orz!orz!orz!orz!orz!orz!orz!orz!

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：0ms

秒杀

LS的LS:"而为什么那种扫来扫去的算法为什么能过....只能说数据不够强大了.."

这说明你根本没弄清楚这题

扫2次的算法在理论上是完美的，不是数据弱的问题。

我觉得用最短路能做的啊，为什么只有50分呢？

为什么？？

小的写了线段树dp，从右往左。应该是O(nlogn)啊，怎么只过6个点呢？？

查询O(lgn)，修改我也用了信息传递的小优化，纯色结点不向下修改，只在询问时向下修改（传递信息）。可是用Cena一测发现比不优化还慢呢！why??

希望各位大牛帮忙看看，指点迷津！

#include

int n,nn,m,a[100011],f[262150],ask[50011],min[262150],loc[262150],L,R,X,pure[262150];

void build(int i,int l,int r)

{

f[i]=999999;

if(l==r) {loc[l]=i;return;}

build(i*2,l,(l+r)/2);

build(i*2+1,(l+r)/2+1,r);

}

void editdown(int i,int l,int r)

{int a,b;

if(LX){pure[i]=1;f[i]=X;return;}//叶子都是纯色结点

if(l==r){if(f[i]>X)f[i]=X; return; }

if(f[i]>X)f[i]=X;

if(L

看来我编程功底有待提高......

第一次竟然把堆给打错了..

我用的dijstra过了6个点.....

极端数据就不行了阿

然后某牡牛（我同学）就说....从后面扫一遍...在从前面扫一遍......就能过了....

可惜急躁的我...硬是少写了一句话...结果wa...过了4个点.....

第二次dragon无情地最后一个点超时.....

第三次puppy终于让我AC了...

不过个人觉得....dijstra是可以的....只不过在这道题目预处理的话就用了很多时间了

而为什么那种扫来扫去的算法为什么能过....只能说数据不够强大了..

桥牛这实力啊，全部秒杀，Orz

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：0ms

Orz教主无敌的O（N）算法。。

教主实力在的 Orz Orz Orz Orz Orz Orz Orz Orz Orz Orz Orz Orz

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 103ms

├ 测试数据 10：答案正确... 603ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：706ms

想出来方法就很简单了，从后往前扫一次，再从前往后扫一次，基本上平均情况O(n)

最后那两个点数据大，感觉慢了点儿，不过还是可以了

对vj的评测机真的无语了~~

同样的程序，在自己的机子上ac的~~

第一次交，

在vj上竟然后三个点‘运行超时|格式错误...’得了unaccepted；

同样的程序，我在第二次交（啥都没改）；

只有一个点‘运行超时|格式错误...’显示90分，

但是！！！！这时候神奇的事情发生了，一看‘Flag 　　Accepted ’竟然ac了！！！！！！！！！！！！！！！！！！！1

…………………………………………

dp+奇怪的优化

居然过了,果然没有卡我那个优化的数据

第4题在1422

我用贪心的才对3个`\唯一不同的是我没排序``

昨天想说只要从F[1]拓展到F[2]一直拓展下去便可``

不知道为什么会有错解不只是超时`\

今天排序一下就AC了`

无限鄙视这次的测评...今天用一摸一样的程序提交前两道,ac,昨天测出来是0分...

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 0ms

设置一个上限max，一开始max=n+1，然后找出一个i使得min(i)且i+a[i]>=max，则sum[i]（表示第I个数所需要移动次数）=重新设置上限的次数+1，i～max之间的数j：若j+a[j]>=max 则sum[j]=sum[i] 否则sum[j]=sum[i]+1;重复做即可

找I的时候需要用到RMQ，具体如下：

先预处理出一个数组a，存i+a[i]，从小到大排序一下。要找i的时候，二分查找max，假设a中第一个>=max的值在第k个，则a数组中k～n内所有的数所代表的数都可以一步到达max，所以我们找出一个i～n中所代表的数的最小值，即为所

求I.

算法复杂度O(nlogn)

类似区间覆盖...

编了个极其猥琐的heap+dijkstra，vijos竟然说我编译不过，lazarus上很稳的……

不过，又试了试也就得60分，太不好了！

用暴力搜的……居然除了第八个点都秒杀……

#include

#define maxn 100000

#define INF 20000000

long n,m,a[maxn+10],f[maxn+10],g[maxn+10];

int main()

{

long i,j,up,tmp,ans;

scanf("%ld%ld",&n,&m);

for(i=1;i=1;--i)

{

f[i]=INF;

up=i+a[i];

if(up>n) {f[i]=1;continue;}

for(j=up;j>i;--j)

if(f[j]+1

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 9ms

├ 测试数据 09：答案正确... 25ms

├ 测试数据 10：答案正确... 9ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：43ms

从后往前DP，利用RMQ优化到NlogN