对一些题目的思考

对一些题目的思考

洛谷 P3203 [HNOI2010]弹飞绵羊

题目

这道题我用的是分块,但一开始 WA 了,改了几遍都还是只有 50pts,后来看题解,发现题解说的是在更新的时候要整个块全部重构,而我只重构了块内在被更新位置之前的那些位置的值,直接用 i+aii+a_i 是否等于 xx 来判断要不要更新这个值,然而在同一块中,绵羊可能从一个位置跳很多次都跳不出这个块,也就是说,有可能它无法一次性跳到从 ii 跳到 xx,而要经过几次跳跃才行,所以不能这样判断,但如果直接根据弹力系数一个一个暴力跳来判断能否到达 xx,那单次修改复杂度最坏可能会达到接近 O(n)O(n),还不如直接整个块重构,这样复杂度是 O(n)O(\sqrt n) 的。同时,在一开始初始化和重构时,不必每个位置都暴力跳一遍,可以从后往前循环,用后面的位置来更新前面的位置,也就是说,对于每个位置,判断是否能一次性跳出这个块,如果可以,直接给这个位置赋值就行了,如果不行,那它必定是跳到了后面的某个位置,由于它后面的值已经全部更新过了,所以直接在跳到的那个位置的基础上加一就可以了。

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
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
#include<bits/stdc++.h>
#define N 200010
#define pii pair<int,int>
#define mp make_pair
using namespace std;
int n,m,len,num,a[N],l[1010],r[1010],belong[N];
pii g[N];
void update(int x,int k)
{
a[x]=k;
for(int i=r[belong[x]];i>=l[belong[x]];i--)
{
g[i].first=i+a[i];
g[i].second=1;
if(g[i].first<=r[belong[x]])
{
g[i].second=g[g[i].first].second+1;
g[i].first=g[g[i].first].first;
}
}
}
int query(int x)
{
int j=x,sum=0;
while(j<=n)
{
sum+=g[j].second;
j=g[j].first;
}
return sum;
}
int main()
{
scanf("%d",&n);
len=sqrt(n);
num=(n-1)/len+1;
for(int i=1;i<=n;i++)
{
scanf("%d",&a[i]);
belong[i]=(i-1)/len+1;
}
for(int i=1;i<=num;i++)
{
l[i]=r[i-1]+1;
r[i]=min(i*len,n);
}
for(int i=n;i>=1;i--)
{
g[i].first=i+a[i];
g[i].second=1;
if(g[i].first<=r[belong[i]])
{
g[i].second=g[g[i].first].second+1;
g[i].first=g[g[i].first].first;
}
}
scanf("%d",&m);
for(int i=1;i<=m;i++)
{
int op,x,k;
scanf("%d%d",&op,&x);
if(op==1)
printf("%d\n",query(x+1));
else
{
scanf("%d",&k);
update(x+1,k);
}
}
return 0;
}

另外,CF13E 跟这道题几乎一模一样,但有一个坑点在于它还要求最后一次落在哪个洞里,一开始我是直接用一个变量来存储 jj 上一次到达的位置,但在第三个测试点里 WA 了,后来才发现这里的 jj 是直接从块中跳出去的,所以可能会从当前位置跳多次才能跳出这个块,但上面这个方法就只统计了当前位置,没有管后面是否中转,所以会出错。解决方法是再把最后的答案进行暴力跳转,直到找到一个能把球弹出的位置,这个位置才是答案。

1
2
3
4
5
6
7
8
9
10
11
12
13
int query(int x)
{
int j=x,b,sum=0;
while(j<=n)
{
sum+=g[j].second;
b=j;
j=g[j].first;
}
while(b+a[b]<=n)
b+=a[b];
printf("%d %d\n",b,sum);
}

洛谷 P1171 售货员的难题

这道题算是状压的一道经典题型,一开始我是 WA 了,只得了 1010 分,调了一会不知道哪里出问题了,看了一下题解才发现自己在算 dpdp 数组的时候,是把起点放在最外层循环,到过的城镇的状态放在中间循环,终点放在内层循环。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
for(int i=1;i<=n;i++)
{
for(int j=1;j<=(1<<n)-1;j++)
{
if(!(j&(1<<(i-1))))
continue;
for(int k=1;k<=n;k++)
{
if(j&(1<<(k-1)))
continue;
dp[k][j|(1<<(k-1))]=min(dp[k][j|(1<<(k-1))],dp[i][j]+dis[i][k]);
}
}
}

这样就相当于我是人为地把这个顺序给固定下来了,必须是从编号小的点走到大的点,因为如果最佳顺序是 15231\to 5 \to 2\to 3 这样一个序列的话,那我虽然可以用 55 去更新 22 的距离,但从 2233 的距离已经定了,不能改变了,所以最后求出来的答案就是错误的,解决方法是把到过城镇的状态放在第一层循环,然后去枚举起点和终点(事实上,据旁边的 xfy 巨佬说,状压 DP 都应该是把状态放在最外层,这样才能保证你用来更新其他点的这个值是已经被计算完的)。

1
2
3
4
5
6
7
8
9
10
11
12
for(register int j=1;j<=(1<<n)-1;j++)
for(register int i=1;i<=n;i++)
{
if(!(j&(1<<(i-1))))
continue;
for(register int k=1;k<=n;k++)
{
if(!(j&(1<<(k-1))))
continue;
dp[j][k]=min(dp[j][k],dp[j^(1<<(k-1))][i]+dis[i][k]);
}
}

另外,这道题有一点点卡常,亲测不加 register 的话第 1010 个点会 T 掉(也有可能是我人傻常数大),把表示状态的较大的一维放在最外层,也可以少个几毫秒的样子(其实更有可能是评测机波动)。

作者

AzuSemisa

发布于

2020-10-24

更新于

2020-11-22

许可协议

评论