#C241008C. SolarPea与网格
标签（Label）
- 动态规划
网址（Website）
题解（Solution）
发现如果一个人在 $x$，另一个人在 $y$（$x < y$），在 $x$ 的人一定会把所有 $x < i < y$ 的 $i$ 全走一遍，走完之后会 $x + 1 = y$。
记 $f_i$ 表示一个人在 $i - 1$，一个人在 $i$，在 $i - 1$ 的人的得分减在 $i$ 的人的得分的最大值，答案即为 $f_2$。初值为 $f_{n-1} = a_n$。
记 $s$ 为 $a$ 的前缀和：
$f_i = \max_{j > i}(a_j - s_{j-1} + s_i - f_j) \\\quad= \max(f_{i+1} - a_{i+1}, a_{i+1} - f_{i+1}) \\\quad= |f_{i+1} - a_{i+1}|$
（第二行使用差分实现）
根据上文，我们可以推得最后的答案是 $\vert\vert\vert a_n-a_{n-1}\vert -a_{n-2}\vert-a_{n-3}\vert…$
考虑每次操作对答案的贡献，将 $a_n$ 看作 $x$ ，答案看作 $y$ 则有：$y = \vert\vert\vert x-a_{n-1}\vert -a_{n-2}\vert-a_{n-3}\vert…$ ，我们将函数的图像画出来，发现每加入一个点 $i$ 都是将原来的函数右移 $a_i$ 位，然后将其关于 $a_i$ 对称，最终询问的 $ans$ 便是输入的 $a_n$ 对应的 $x$ 的值。
发现 $a_n$ 的范围是 $[0,10^9]$ ，如果 $a_n$ 已经大于所有数的和了，直接选到 $a_n$ 即可（否则让 $\mathrm{PolarSea}$ 选到了 $a_n$ 贡献就是负的了）
时间复杂度为 $O(\sum a + q)$。
代码（Code）
直接对称
#include<bits/stdc++.h>
#include<vector>
#include<queue>
#include<list>
#define For(i,l,r) for(int i=l;i<=r;i++)
#define Rof(i,l,r) for(int i=l;i>=r;i--)
using namespace std;
#define P pair<int,int>
#define int long long
#define x first
#define y second
inline int rd(){
char c;bool f=false;while(!isdigit(c=getchar()))f=c=='-';int x=c^48;
while(isdigit(c=getchar())){x=(((x<<2)+x)<<1)+(c^48);}return f?-x:x;
}const int inf = 0x3f3f3f3f3f3f3f3f;
const int N = 2012345;
const int A = 1e6;
bool ST;
int n,q,len,a[N];
int res[N];
int f[N<<2|3];
inline void solve(){
n = rd(); For(i,1,n-1) a[i] = rd();
int s = 0; For(i,3,n-1) s+=a[i];//对未拿到的分数求和
For(i,0,s) f[i+A] = i;//复制一份？
int nw = 0;
For(i,3,n-1){
nw += a[i];//当前位置加上a[i]
For(j,0,a[i]-1) f[j+(A-nw)] = f[a[i]*2-j+(A-nw)];
}
q = rd();
while(q--){
int x = rd();
if(x<s) printf("%lld\n", f[x+(A-nw)]+a[1]-a[2]);
else printf("%lld\n", x-s+a[1]-a[2]);
}
}
bool ED;
signed main(){
cerr<<abs(&ST-&ED)/1024./1024.<<"MB\n";
freopen("game.in","r",stdin);
freopen("game.out","w",stdout);
int T = 1, Tim = clock();
while(T--) solve();
return cerr<<"TIME:"<<(clock()-Tim)/1000.,0;
}使用双端队列
#include<bits/stdc++.h>
#include<vector>
#include<queue>
#include<list>
#define For(i,l,r) for(int i=l;i<=r;i++)
#define Rof(i,l,r) for(int i=l;i>=r;i--)
using namespace std;
#define P pair<int,int>
#define int long long
#define x first
#define y second
inline int rd(){
char c;bool f=false;while(!isdigit(c=getchar()))f=c=='-';int x=c^48;
while(isdigit(c=getchar())){x=(((x<<2)+x)<<1)+(c^48);}return f?-x:x;
}const int inf = 0x3f3f3f3f3f3f3f3f;
const int N = 2012345;
bool ST;
int n,q,len,a[N];
int res[N];
list<int> f;
inline void solve(){
n = rd(); For(i,1,n-1) a[i] = rd();
int s = 0; For(i,3,n-1) s+=a[i];
For(i,0,s) f.push_back(i);
For(i,3,n-1){
auto it = f.begin();
For(j,1,a[i]) it++,f.push_front(*it);
}
len = 0;
for(auto x:f) res[len++] = x;
assert(len==s*2+1);
q = rd();
while(q--){
int x = rd();
if(x<len) printf("%lld\n", res[x]+a[1]-a[2]);
else printf("%lld\n", x-s+a[1]-a[2]);
}
}
bool ED;
signed main(){
cerr<<abs(&ST-&ED)/1024./1024.<<"MB\n";
// freopen("ex_game.in","r",stdin);
freopen("game.in","r",stdin);
freopen("game.out","w",stdout);
int T = 1, Tim = clock();
while(T--) solve();
return cerr<<"TIME:"<<(clock()-Tim)/1000.,0;
}
