GJOI 9.4 题解

1.CF1801B Buy Gifts / 洛谷 P13532 买礼物

题意

$n\le 2\times 10^5$。

思路

神秘卡常题，如果等待提交记录久一点就能知道自己 A 掉……

题目问 A 的最大值，减去 B 的最大值，求差值最小值。但是怎么选到两个最大值呢？

我们按照 $a$ 关键字排序得到从小到大有序的 $a_i$。不妨钦定 $a_i$ 为 A 能够选到的最大值，那么 $i+1\sim n$ 都不能选 $a$ 了，只能强制选 $b_{i+1\sim n}$。

于是 B 的最大值至少为 mx=max⁡{bi+1∼n}mx=\max\{b_{i+1\sim n}\}mx=max{bi+1∼n​}，容易预处理 $b$ 的后缀最大值。

那么 $1\sim i-1$ 的要怎么选出一个 $b_t,t\in [1,i)$，使得差值能够更小呢？当然是选一个和 $a_i$ 绝对值差值更接近的啦。

于是我们将 $b_{1\sim i-1}$ 压入 set 使其有序，然后在上面二分一个最靠近 $a_i$ 的 $b_x$。注意 $b_x$ 可以比 $a_i$ 小也可以比它大，还有一个前提就是 $b_x>mx$，否则选到的 $b_x$ 不是 B 的最大值。

这个 STL 真是个好东西，就是常数大了一些。

代码

#pragma GCC optimise(3,"Ofast","inline")
#include<bits/stdc++.h>
using namespace std;
#define ll int
const ll N=5e5+9,inf=1e9;
inline ll read()
{ll s=0,w=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();return s*w;
}
inline void write(ll x)
{ if(x==0){putchar('0');return;}ll len=0,k1=x,c[10005];if(k1<0)k1=-k1,putchar('-');while(k1)c[len++]=k1%10+'0',k1/=10;while(len--)putchar(c[len]);
}
ll T,n;
ll sfmx[N];
struct node
{ll a,b;
}p[N];
bool cmp(node x,node y)
{return x.a<y.a;//这里不对b特别排序，其实手玩一下发现是等价的
}
ll ans,tar;
multiset<ll>pre;//多重集可以把等于的算好
int main()
{freopen("gift.in","r",stdin);freopen("gift.out","w",stdout);T=read();while(T--){n=read();pre.clear();for(int i=1;i<=n;i++){ll a,b;a=read(),b=read();p[i]=(node){a,b};}sort(p+1,p+n+1,cmp);sfmx[n+1]=-inf;for(int i=n;i>=1;i--)sfmx[i]=max(sfmx[i+1],p[i].b);ans=inf;for(int i=1;i<=n;i++){tar=sfmx[i+1];if(tar>p[i].a)ans=min(ans,tar-p[i].a);else {ans=min(ans,p[i].a-tar);pre.insert(p[i].a);auto it=pre.find(p[i].a),End=pre.end();End--;if(it!=pre.begin()){it--;ans=min(ans,p[i].a-(*it));it++;}if(it!=End){it++;ans=min(ans,(*it)-p[i].a);it--;}pre.erase(it);}pre.insert(p[i].b);}write(ans);puts("");}return 0;
}

2.洛谷 P6583 回首过去

题意

给定正整数 $n$，求出有序整数对 $(i,j)$ 的个数，满足 $1\le i,j\le n$，且 $\frac{i}{j}$ 是十进制下的有限小数。

思路

根据小学数学知识，一个分数 $\frac{b}{x}$，如果 $x$ 的质因子只含有 $2,5$，计算结果就是有限小数。

考虑把原分数变成 $\frac{bt}{xt}$，$t$ 表示对原分数约分后的因子。于是 $bt,xt\in [1,n]$，那么 $b,x\in \left[1,\lfloor \frac{n}{t}\rfloor \right]$。其中，规定 $x$ 的质因子只含有 $2,5$。

如果强制规定，$\frac{b}{x}$ 是既约分数，即要讨论 $b$ 没有 $2,5$ 作为质因子、或者 $2,5$ 中只有一者作为质因子，首先这讨论很麻烦；其次 $t$ 就是全部的 $1\sim n$。假使把 $t$ 约分掉，$t$ 中含有 $2,5$ 作为因子：比如 $x=4,t=10$，那么在 $x=20,t=2$ 时就会出现算重的情况。

考虑怎么避免算重。不妨钦定 $t$ 不含有 $2,5$ 作为质因子，那么对于原分母 $j=xt$，我们发现 $j$ 被唯一分解——因此 $x,t$ 决定了 $j$ 不同的质因子。于是此时每个分母被唯一枚举，完全避免了算重的情况！

先考虑一个近似 $O(n)$ 的做法：先枚举 $x$，那么 $t\in \left[1,\lfloor \frac{n}{x}\rfloor \right]$，上面的 $b$ 的取值就有 $\lfloor \frac{n}{t}\rfloor$ 种。

在此先预处理所有质因子只有 $2,5$ 的数。

代码1（80pts）

#pragma GCC optimise(3,"Ofast","inline")
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const ll N=2e5+9,inf=1e9;
ll n;
vector<ll>num;
int main()
{freopen("recall.in","r",stdin);freopen("recall.out","w",stdout);scanf("%lld",&n);for(ll i=1;i<=n;i*=2)for(ll j=i;j<=n;j*=5)num.push_back(j);sort(num.begin(),num.end());ll ans=0;for(auto x:num){for(ll t=1;x*t<=n;t+=2){if(t%5==0)continue;ans+=n/t;}}printf("%lld",ans);return 0;
}

同样的，可以枚举 $t\in [1,n]$，那么就同时得到 $b,x$ 的范围（如上文所述）。容易知道 $b$ 的取值种树，我们只需要知道有多少合法的 $x\le \lfloor \frac{n}{t}\rfloor$。我们从小到大枚举 $t$，发现 $\lfloor \frac{n}{t}\rfloor$ 是单调递减的，因此对预处理数组排序之后用一个指针 $pos$ 维护最大的 $x\le \lfloor \frac{n}{t}\rfloor$ 即可，于是 $x$ 的个数恰为 $pos$。

代码2（80pts）

#pragma GCC optimise(3,"Ofast","inline")
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const ll N=2e5+9,inf=1e9;
ll n;
ll num[N],tot;
int main()
{freopen("recall.in","r",stdin);freopen("recall.out","w",stdout);scanf("%lld",&n);for(ll i=1;i<=n;i*=2)for(ll j=i;j<=n;j*=5)num[++tot]=j;sort(num+1,num+tot+1);ll ans=0,pos=tot;for(ll t=1;t<=n;t+=2){if(t%5==0)continue;ll b=n/t;while(pos>=1&&num[pos]>b)pos--;ans+=pos*b;}printf("%lld",ans);return 0;
}

我们发现 $b,x$ 的值域都是 $\left[1,\lfloor \frac{n}{t}\rfloor \right]$，右端点可以整除分块得到数值：

对于 $t\in [l,r]$ 可以取到同一个 $\lfloor \frac{n}{t}\rfloor$，我们用第二个方法计算 $b,x$ 的个数。在乘上 $[l,r]$ 中不是 $2,5$ 的倍数（即合法的 $t$）的个数就是答案了。

代码3（100pts）

#pragma GCC optimise(3,"Ofast","inline")
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const ll N=2e5+9,inf=1e9;
ll n;
ll num[N],tot;
ll cal(ll l,ll r)
{ll ret=r-l+1;ret-=r/2-(l-1)/2;ret-=r/5-(l-1)/5;ret+=r/10-(l-1)/10;return ret;
}
int main()
{freopen("recall.in","r",stdin);freopen("recall.out","w",stdout);scanf("%lld",&n);for(ll i=1;i<=n;i*=2)for(ll j=i;j<=n;j*=5)num[++tot]=j;sort(num+1,num+tot+1);ll ans=0,pos=tot;for(ll l=1,r;l<=n;l=r+1){ll b=n/l;if(!b)r=n;else r=n/b;while(pos>=1&&num[pos]>b)pos--;ans+=pos*b*cal(l,r);}printf("%lld",ans);return 0;
}

3.洛谷 P10207 马拉松比赛2（状元桥）

题意

P10207 [JOI 2024 Final] 马拉松比赛 2 / Marathon Race 2

题目描述

JOI 大道是一条东西向的长度为 $L$ 米的道路，地点 $l$ 位于从道路的西端走 $l(0\le l\le L)$ 米的地方。

今年 JOI 大道上第一次举办了马拉松大会。这个马拉松大会的规则和一般的不同，是按照以下的方式进行的：

• 道路上放了 $N$ 个球，第 $i(1\le i\le N)$ 个球放在地点 $X_i$。有些地方可能有多个球放在一起。
• 参加者从规定的起点出发，拿到所有 $N$ 个球后，如果在规定的时间内到达规定的终点，就算是完赛。但是，如果把拿到的球放在地上就会被取消资格。

这个大会的起点，终点和时间限制还没有公布，但是已经公布了 $Q$ 个可能的方案。第 $j(1\le j\le Q)$ 个方案的起点是地点 $S_j$，终点是地点 $G_j$，时间限制是 $T_j$ 秒。

理恵是马拉松大会的其中一名运动员。她拿起一个球要花 $1$ 秒，拿着 $x$ 个球在道路上跑 $1$ 米要花 $x+1$ 秒。

给出 JOI 大道，球，方案的信息。编写一个程序，对于每个方案判断理恵能不能完赛。可以则输出 Yes，否则输出 No。

$1\le N\le 5\times 10^5$，$1\le L\le 5\times 10^5$，$0\le X_i\le L$。

$1\le Q\le 5\times 10^5$，$0\le S_j,G_j\le L$，$1\le T_j\le 5\times 10^5$。

思路

这个数据范围看着就很无解捏！那就爆改数据范围

我们发现如果有连续 $1000$ 个不同的球，那么怎么捡耗时都至少为 1000×1001÷2=500500>max⁡{T}1000\times 1001\div 2=500500>\max \{T\}1000×1001÷2=500500>max{T}。

考虑将球离散化之后，有 $n$ 个位置放了球，若 $n\ge 1000$ 必然无解。

于是数据范围大幅缩小。但是 $Q$ 有 $5\times 10^5$，不能 $O(Qn)$，因此考虑在询问之外考虑 $O(n^2)$ 的做法。

有一个贪心的性质：若多次经过一个球，显然在最后一次经过时才拿这个球是最优的。因此在拿球的过程中，$n$ 个位置的球会是这样一个状态：位置编号为 $1\sim l-1$、$r+1\sim n$ 被拿掉了，剩下中间一段 $[l,r]$ 没有拿。

于是可以参考 Sue 的小球的做法，设 $f_{l,r,op}$ 表示，$[l,r]$ 还没有取（正准备取），且当前处于 $l/r$ 的最小步数。但是边界条件不同：根据上面的贪心，第一个拿球的位置，要么 $a_1$ 要么 $a_n$，如果直接让 $f_{1,n,0}=f_{1,n,1}=0$，相当于一开始两个位置的球同时被取。

因此改写状态 $f_{l,r,op1,op2}$ 表示，从 $a_1/a_n$ 出发，$[l,r]$ 还没有取（正准备取），且当前处于 $l/r$ 的最小步数。那么有正确的边界条件 $f_{1,n,0,0}=f_{1,n,1,1}=0$。

设已经在 $1\sim l-1$、$r+1\sim n$ 位置取到了 $ball$ 个球，容易用前缀和 $O(1)$ 算出。类似 Sue 的小球这一题，写出转移式子：

ll ball=pre[b[i]-1]+sum-pre[b[j]]+1;
//球数+1
//
f[i][j][op1][0]=min(f[i][j][op1][0],min(f[i-1][j][op1][0]+ball*(b[i]-b[i-1]),f[i][j+1][op1][1]+ball*(b[j+1]-b[i])));
f[i][j][op1][1]=min(f[i][j][op1][1],min(f[i-1][j][op1][0]+ball*(b[j]-b[i-1]),f[i][j+1][op1][1]+ball*(b[j+1]-b[j])));

考虑处理询问。设总共 $sum$ 个球，考虑到达终点坐标之前，拿完了所有的球。二分找一个终点左侧球放置位置 $Lid$ 和右侧位置 $Rid$。用状态 $f_{Lid,Lid,op1,0}$ 然后在取上自己，再走到终点。记得在开始时走到起点 $a_1$（$op1=0$）或者 $a_n$（$op2=1$）。

while(Q--)
{ll l,r,lim,ret=inf,id;scanf("%lld%lld%lld",&l,&r,&lim);id=lower_bound(b+1,b+n+1,r)-b;ret=min(ret,min(abs(l-b[1])+f[id][id][0][0],//走到相应起点，拿完sum-cnt[n]个球abs(l-b[n])+f[id][id][1][0])+abs(r-b[id])*(sum+1));//最后落点走回终点id=upper_bound(b+1,b+n+1,r)-b-1;ret=min(ret,min(abs(l-b[1])+f[id][id][0][0],abs(l-b[n])+f[id][id][1][0])+abs(r-b[id])*(sum+1));
//	cout<<ret<<endl;if(ret<=lim)puts("Yes");else puts("No");
}

代码

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const ll N=5e5+9,M=1003,inf=0x3f3f3f3f;
ll n,L,Q,sum;
ll b[N];
ll cnt[N],pre[N];
ll f[M][M][2][2];
int main()
{
//	freopen("run.in","r",stdin);
//	freopen("run.out","w",stdout);freopen("P10207_3.in","r",stdin);
//	freopen("P10207.out","w",stdout);scanf("%lld%lld",&n,&L);sum=n;L++;//下标整体+1，防止出现-1下标越界for(int i=1;i<=n;i++){scanf("%lld",&b[i]);cnt[++b[i]]++;}sort(b+1,b+n+1);n=unique(b+1,b+n+1)-b-1;pre[0]=cnt[0];for(int i=1;i<=L;i++)pre[i]=pre[i-1]+cnt[i];scanf("%lld",&Q);if(n>=1000){while(Q--)puts("No");return 0;}memset(f,inf,sizeof(f));f[1][n][0][0]=f[1][n][1][1]=0;for(int len=n-1;len>=1;len--){for(int i=1;i+len-1<=n;i++){ll j=i+len-1;ll ball=pre[b[i]-1]+sum-pre[b[j]]+1;//op1=0f[i][j][0][0]=min(f[i][j][0][0],min(f[i-1][j][0][0]+ball*(b[i]-b[i-1]),f[i][j+1][0][1]+ball*(b[j+1]-b[i])));f[i][j][0][1]=min(f[i][j][0][1],min(f[i-1][j][0][0]+ball*(b[j]-b[i-1]),f[i][j+1][0][1]+ball*(b[j+1]-b[j])));//op1=1f[i][j][1][0]=min(f[i][j][1][0],min(f[i-1][j][1][0]+ball*(b[i]-b[i-1]),f[i][j+1][1][1]+ball*(b[j+1]-b[i])));f[i][j][1][1]=min(f[i][j][1][1],min(f[i-1][j][1][0]+ball*(b[j]-b[i-1]),f[i][j+1][1][1]+ball*(b[j+1]-b[j])));}}for(int i=1;i<=n;i++)//最后拿上自己 {f[i][i][0][0]+=sum;//sum-1+1f[i][i][0][1]+=sum;f[i][i][1][0]+=sum;f[i][i][1][1]+=sum;}while(Q--){ll l,r,lim,ret=inf,id;scanf("%lld%lld%lld",&l,&r,&lim);l++,r++;id=lower_bound(b+1,b+n+1,r)-b;ret=min(ret,min(abs(l-b[1])+f[id][id][0][0],abs(l-b[n])+f[id][id][1][0])+abs(r-b[id])*(sum+1));id=upper_bound(b+1,b+n+1,r)-b-1;ret=min(ret,min(abs(l-b[1])+f[id][id][0][0],abs(l-b[n])+f[id][id][1][0])+abs(r-b[id])*(sum+1));//	cout<<ret<<endl;if(ret<=lim)puts("Yes");else puts("No");}return 0;
}