如何运用区间分块和二分思想解决CF-E. Holes问题？
- 内容介绍
- 文章标签
- 相关推荐
本文共计1197个文字，预计阅读时间需要5分钟。
C.+Holes+时间限制+每测试+内存限制+每测试+输入+输出+小佩蒂亚喜欢玩很多。最爱的游戏是洞。这是一个单人游戏，规则如下：有N个洞排列成一行，每个洞有一个编号a+1，a+2，…，a+N。游戏的目标是找到所有相邻的洞，它们的编号之差为2。例如，如果洞的编号是1，2，3，4，那么相邻的洞1和3就是一个符合条件的对。你的任务是编写一个程序，找出所有符合条件的相邻洞对，并计算它们的数量。
输入：第一行包含一个整数N，表示洞的数量（1≤N≤100）。接下来的一行包含N个整数，表示洞的编号。
输出：输出一个整数，表示符合条件的相邻洞对的数量。
E. Holes
time limit per test
memory limit per test
input
output
Little Petya likes to play a lot. Most of all he likes to play a game «Holes». This is a game for one person with following rules:
There are N holes located in a single row and numbered from left to right with numbers from 1 to N. Each hole has it's own power (hole number i has the power ai). If you throw a ball into hole i it will immediately jump to hole i + ai, then it will jump out of it and so on. If there is no hole with such number, the ball will just jump out of the row. On each of the M
- Set the power of the hole a to value b.
- Throw a ball into the hole a
Petya is not good at math, so, as you have already guessed, you are to perform all computations.
Input
The first line contains two integers N and M (1 ≤ N ≤ 105, 1 ≤ M ≤ 105) — the number of holes in a row and the number of moves. The second line contains N positive integers not exceeding N — initial values of holes power. The following M
- 0 a b
- 1 a
Type
0 means that it is required to set the power of hole a to
b, and type
1 means that it is required to throw a ball into the a-th hole. Numbers
a and
b are positive integers do not exceeding
N.
Output
For each move of the type 1
Sample test(s)
Input
8 51 1 1 1 1 2 8 21 10 1 31 10 3 41 2
Output
8 78 57 3
思路：直接模拟询问次数乘以询问代价，更新代价为O（1）最坏N*N ，N<10^5有最坏数据直接爆了。
所以应该分用区间，分多少区间呢？多少都行，但一般选择sqrt(N)比较合适。
这样挑出大区间的值，就等于调出sqrt(N)个小区间的值之和。
这样更新代价为O(sqrt(N)),询问代价也为O(sqrt(N)),总代价最坏为O(N*sqrt(N))可以差不多险过。
哎！当时比赛怎么没去看这题，一直第二道抠几何题，解决方法很简单就是向量的一些基本知识，可惜代码敲半死没敲出来。
->最后的题不一定是最难的题。
TLE代码:
#include<iostream>using namespace std;const int mm=100100;int f[mm],s[mm];int main(){ int m,n; int a,b,c; while(cin>>m>>n) { for(int i=1;i<=m;i++) cin>>f[i]; int num,last; for(int i=0;i<n;i++) { cin>>a>>b; if(a) { num=0; while(b<=m) { last=b; b+=f[b]; num++; } cout<<last<<" "<<num<<"\n"; } else { cin>>c;f[b]=c; } } }}
优化完的代码
#include<iostream>#include<cmath>using namespace std;const int mm=100100;int f[mm],num[mm],last[mm];int k,m,n;void fen(int x)///区间值更新{ if(x+f[x]>m||x/k!=(x+f[x])/k)///挑出区间了 last[x]=x,num[x]=0; else last[x]=last[f[x]+x],num[x]=num[x+f[x]]+1;///在去间内正常模拟}int main(){ int a,b,c; while(cin>>m>>n) { for(int i=1;i<=m;i++) cin>>f[i]; for(int i=1;i*i<m;i++)///分sqrt(m)个区间 k=i; for(int i=m;i>0;i--)///预处理 fen(i); for(int i=0;i<n;i++) { cin>>a>>b; if(a) { int _num=0,_last; while(b<=m)///模拟区间跳 { _last=last[b]; _num+=num[b]+1; b=_last+f[_last]; } cout<<_last<<" "<<_num<<"\n"; } else { cin>>c;f[b]=c; for(int i=b;i>0&&i/k==b/k;i--)///区间更新 fen(i); } } }}
本文共计1197个文字，预计阅读时间需要5分钟。
C.+Holes+时间限制+每测试+内存限制+每测试+输入+输出+小佩蒂亚喜欢玩很多。最爱的游戏是洞。这是一个单人游戏，规则如下：有N个洞排列成一行，每个洞有一个编号a+1，a+2，…，a+N。游戏的目标是找到所有相邻的洞，它们的编号之差为2。例如，如果洞的编号是1，2，3，4，那么相邻的洞1和3就是一个符合条件的对。你的任务是编写一个程序，找出所有符合条件的相邻洞对，并计算它们的数量。
输入：第一行包含一个整数N，表示洞的数量（1≤N≤100）。接下来的一行包含N个整数，表示洞的编号。
输出：输出一个整数，表示符合条件的相邻洞对的数量。
E. Holes
time limit per test
memory limit per test
input
output
Little Petya likes to play a lot. Most of all he likes to play a game «Holes». This is a game for one person with following rules:
There are N holes located in a single row and numbered from left to right with numbers from 1 to N. Each hole has it's own power (hole number i has the power ai). If you throw a ball into hole i it will immediately jump to hole i + ai, then it will jump out of it and so on. If there is no hole with such number, the ball will just jump out of the row. On each of the M
- Set the power of the hole a to value b.
- Throw a ball into the hole a
Petya is not good at math, so, as you have already guessed, you are to perform all computations.
Input
The first line contains two integers N and M (1 ≤ N ≤ 105, 1 ≤ M ≤ 105) — the number of holes in a row and the number of moves. The second line contains N positive integers not exceeding N — initial values of holes power. The following M
- 0 a b
- 1 a
Type
0 means that it is required to set the power of hole a to
b, and type
1 means that it is required to throw a ball into the a-th hole. Numbers
a and
b are positive integers do not exceeding
N.
Output
For each move of the type 1
Sample test(s)
Input
8 51 1 1 1 1 2 8 21 10 1 31 10 3 41 2
Output
8 78 57 3
思路：直接模拟询问次数乘以询问代价，更新代价为O（1）最坏N*N ，N<10^5有最坏数据直接爆了。
所以应该分用区间，分多少区间呢？多少都行，但一般选择sqrt(N)比较合适。
这样挑出大区间的值，就等于调出sqrt(N)个小区间的值之和。
这样更新代价为O(sqrt(N)),询问代价也为O(sqrt(N)),总代价最坏为O(N*sqrt(N))可以差不多险过。
哎！当时比赛怎么没去看这题，一直第二道抠几何题，解决方法很简单就是向量的一些基本知识，可惜代码敲半死没敲出来。
->最后的题不一定是最难的题。
TLE代码:
#include<iostream>using namespace std;const int mm=100100;int f[mm],s[mm];int main(){ int m,n; int a,b,c; while(cin>>m>>n) { for(int i=1;i<=m;i++) cin>>f[i]; int num,last; for(int i=0;i<n;i++) { cin>>a>>b; if(a) { num=0; while(b<=m) { last=b; b+=f[b]; num++; } cout<<last<<" "<<num<<"\n"; } else { cin>>c;f[b]=c; } } }}
优化完的代码
#include<iostream>#include<cmath>using namespace std;const int mm=100100;int f[mm],num[mm],last[mm];int k,m,n;void fen(int x)///区间值更新{ if(x+f[x]>m||x/k!=(x+f[x])/k)///挑出区间了 last[x]=x,num[x]=0; else last[x]=last[f[x]+x],num[x]=num[x+f[x]]+1;///在去间内正常模拟}int main(){ int a,b,c; while(cin>>m>>n) { for(int i=1;i<=m;i++) cin>>f[i]; for(int i=1;i*i<m;i++)///分sqrt(m)个区间 k=i; for(int i=m;i>0;i--)///预处理 fen(i); for(int i=0;i<n;i++) { cin>>a>>b; if(a) { int _num=0,_last; while(b<=m)///模拟区间跳 { _last=last[b]; _num+=num[b]+1; b=_last+f[_last]; } cout<<_last<<" "<<_num<<"\n"; } else { cin>>c;f[b]=c; for(int i=b;i>0&&i/k==b/k;i--)///区间更新 fen(i); } } }}