一道很不错的思维题，没啥算法基础。
场上离做出来就差最后一步。
题目链接。
题意
在一个坐标轴上有 个棋子，第
个棋子的坐标是 。
现在将每一个棋子移动
次，移动规则是这样的：
对于第
次移动，如果某个棋子坐标大于 ，将它向左移 ；如果坐标小于 ，将它向右移 ；坐标为 则不变。
对于每一个棋子，按照规则移动完这 次以后，输出以下值：
如果这个棋子的坐标最后不是 ，输出坐标，否则输出这个棋子在第几次移动后到达坐标
。
题解
首先我们观察范围，会发现 ，值域非常小。
这提示我们不妨假设
范围内，每一个地方都有一个棋子。如果我们能把这些答案都求出来，那么题目中所给的
个坐标肯定也没问题。
然后我们会发现一个性质。
假如有两个棋子在第
次操作后坐标互为相反数/相等。
那么它们在第
次操作之后，坐标肯定也互为相反数/相等。
这个性质很显然。
然后我们再来想，对于一段棋子 ，如果我们进行一次操作，里面的棋子最多有三个结果：落在原点，或者原点左边/右边。
落在原点的棋子我们不用看，以后无论怎么操作，它肯定都在原点。
现在假如有一部分棋子落在原点左边，有一部分棋子落在原点右边。
结合一些上面的性质。
我们会发现有一些棋子会”结合“起来，它们的坐标以后都互为相反数，这个时候我们只需要计算它们其中的一部分。
举一个例子：
现在
上各有一个棋子，我们现在进行操作 。
所有棋子向左移 格，坐标为
的棋子到了原点，棋子 到了原点左边，棋子 到了原点右边。
不难发现，棋子 现在坐标为
，棋子 坐标为 ，它们的坐标现在互为相反数，所以以后它们的坐标都会互为相反数。我们只要知道了棋子
之后某一时刻的坐标，就能知道棋子
在那个时候的坐标。
同理，棋子 ，棋子 ，棋子 都有这样的关系。
所以在之后的某一个时刻中，我们如果知道了棋子 的坐标，我们就能知道棋子 的坐标。
现在回到原来的问题：坐标 上各有一个棋子，经过若干次操作，求它们的最终位置。
这告诉我们，每一次操作之后，如果整个序列被分成了两段，那么我们只需要计算出长的那一段的最终位置，并且记录短的那一段与长的那一段，坐标的关系即可。
假如我们称每一次操作后，被分成的两段中，较长的一段为”关键段“。
那么我们只需要在每一次操作后维护，当前关键段的位置，以及关键段由哪些棋子组成。然后记录”关键段“与较短段的关系。
上面的这两个东西都可以直接递推。
记录关系可以直接进行建边。我们将”关键段“里的棋子连一条边向较短段里的对应棋子，表示后者的坐标是前者的相反数。
例如，在上面那个例子中，我们就可以从 ，……
处理到最后一个询问时，我们就知道关键段中点的答案（以及其中一些算出的，到达原点的棋子编号），这个时候我们就可以通过之前连的有向边，求出
中所有点的答案。
可以看一看官方题解中的图，假设记忆。
代码
细节还是比较多的。
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
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
| #include<algorithm>
#include<assert.h>
#include<cstring>
#include<cstdio>
#include<vector>
#include<queue>
#include<map>
using namespace std;
using ll=long long;
using pli=pair<ll,int>;
using pi=pair<int,int>;
template<typename A>
using vc=vector<A>;
inline int read()
{
int s=0,w=1;char ch;
while((ch=getchar())>'9'||ch<'0') if(ch=='-') w=-1;
while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();
return s*w;
}
vc<int>t[1000001];
bool t0[1000001];
int ans[1000001];
int x[1000001];
int d[1000001];
vc<int>a0;
int l,r;
int n,m;
int sum;
void dfs(int num)
{
for(int p:t[num])
{
t0[p]=t0[num],ans[p]=ans[num];
if(!t0[p]) ans[p]=-ans[p];
dfs(p);
}
}
int main()
{
n=read(),m=read(),l=1,r=1000000;
for(int i=1;i<=n;i++) x[i]=read();
for(int i=1;i<=m;i++) d[i]=read();
for(int i=1;i<=m;i++)
{
if(l>r) break;
if(l>0)
{
if(l>d[i]||r<d[i])
{
l-=d[i],r-=d[i],sum-=d[i];
continue;
}
t0[d[i]-sum]=1,ans[d[i]-sum]=i;
a0.push_back(d[i]-sum);
int l1=l,r1=d[i]-1;
int l2=d[i]+1,r2=r;
if(r1-l1>=r2-l2)
{
for(int i=0;i<=r2-l2;i++) t[r1-i-sum].push_back(l2+i-sum);
l=l1-d[i],r=r1-d[i],sum-=d[i];
}
else
{
for(int i=0;i<=r1-l1;i++) t[l2+i-sum].push_back(r1-i-sum);
l=l2-d[i],r=r2-d[i],sum-=d[i];
}
}
else
{
if(-r>d[i]||-l<d[i])
{
l+=d[i],r+=d[i],sum+=d[i];
continue;
}
t0[-d[i]-sum]=1,ans[-d[i]-sum]=i;
a0.push_back(-d[i]-sum);
int l1=l,r1=-d[i]-1;
int l2=-d[i]+1,r2=r;
if(r1-l1>=r2-l2)
{
for(int i=0;i<=r2-l2;i++) t[r1-i-sum].push_back(l2+i-sum);
l=l1+d[i],r=r1+d[i],sum+=d[i];
}
else
{
for(int i=0;i<=r1-l1;i++) t[l2+i-sum].push_back(r1-i-sum);
l=l2+d[i],r=r2+d[i],sum+=d[i];
}
}
}
for(int i=l;i<=r;i++) ans[i-sum]=i,dfs(i-sum);
for(int i:a0) dfs(i);
for(int i=1;i<=n;i++)
{
if(t0[x[i]]) printf("Yes %d\n",ans[x[i]]);
else printf("No %d\n",ans[x[i]]);
}
return 0;
}
|
感谢观看！