AtCoder Beginner Contest 315

https://atcoder.jp/contests/abc315

F - Shortcuts

题意

有一场比赛，$n$ 个点标。参赛者需要按序通过这些点标，但可以选择跳过这些点标。点标 $1$ 和点标 $n$ 不能被跳过，此外，若跳过了 $c$ 个点标，则需要增加 $2^{c-1}$ 罚时（$c>0$）。参赛者的比赛用时为行走路径距离加上罚时，求最小用时。

数据范围：$2\leq n\leq 10^4$。

题解

赛时没看到是按序通过的…

其实这题是很简单的：由于罚时是指数级别的，所以最终跳过的点数一定不会太多，找一个比较合适的上界，比如说 $30$。那么，我们令 $f_{i,j}$ 表示走到 $i$ 跳过了 $j$ 个点的距离，有转移：

$$f_{i,j}\leftarrow f_{k,j-(i-k-1)}$$

其中 $k$ 也只需要枚举前面 $30$ 个就可以了。

代码

#include <bits/stdc++.h>
using namespace std;
const int N=1e4+5;
int x[N],y[N];
double f[N][35];
double dis(int i,int j)
{
    int xx=x[j]-x[i],yy=y[j]-y[i];
    return sqrt(xx*xx+yy*yy);
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;cin>>n;
    for(int i=1;i<=n;i++) cin>>x[i]>>y[i];
    for(int i=1;i<=n;i++)
        for(int j=0;j<=30;j++) f[i][j]=1e18;
    f[1][0]=0;
    for(int i=2;i<=n;i++)
        for(int j=0;j<=30;j++)  
            for(int k=i-1;k>=max(1,i-j-1);k--)
                f[i][j]=min(f[i][j],f[k][j-(i-k-1)]+dis(k,i));
    double ans=f[n][0];
    for(int j=1;j<=30;j++) ans=min(ans,f[n][j]+pow(2,j-1));
    cout<<fixed<<setprecision(20)<<ans<<'\n';
    return 0;
}

G - Ai + Bj + Ck = X (1 <= i, j, k <= N)

题意

求符合条件的 $(i,j,k)$ 数量，满足

• $1\leq i,j,k\leq n$
• $ai+bj+ck=x$

数据范围：$1\leq n\leq 10^6,1\leq a,b,c\leq 10^9,1\leq x\leq 3\times 10^{15}$。

题解

并不困难的一道题目。我们枚举 $i$，问题就变成了求解 $bj+ck=n-a\times i$ 的解 $(j,k)$ 的组数。这可以用 exgcd 完成。求出一组特解 $(x_0,y_0)$ 后，我们考虑求待定系数 $k$ 的范围。这里以 $x_0$ 为例：方程的通解可以写成 $x=x_0+k\times dx$ 的形式（$x_0,dx$ 都可以用 exgcd 求出），那么我们只需要让 $x$ 落在区间 $[1,n]$ 内即可。分三种情况讨论：

• $x<1$ 时，$l=\lceil\dfrac{1-x}{dx}\rceil,r=\lfloor\dfrac{n-x}{dx}\rfloor$；
• $1\leq x\leq n$ 时，$l=-\lfloor\dfrac{x-1}{dx}\rfloor,r=\lfloor\dfrac{n-x}{dx}\rfloor$；
• $x\geq n$ 时，$l=-\lfloor\dfrac{x-1}{dx}\rfloor,r=-\lceil\dfrac{x-n}{dx}\rceil$。

其中 $k\in[l,r]$。我们再类似地解出由 $y$ 确定的 $k$ 的取值区间，两个求交集就得到了结果。

代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef __int128 i128;
void exgcd(i128 a,i128 b,i128 &x,i128 &y)
{
    if(b==0)
    {
        x=1,y=0;
        return;
    }
    exgcd(b,a%b,y,x);
    y-=a/b*x;
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    ll n,a,b,c,x;cin>>n>>a>>b>>c>>x;
    ll ans=0;
    for(int i=1;i<=n;i++)
    {
        ll m=x-a*i;
        if(m<=0) break;
        ll g=__gcd(b,c);
        if(m%g) continue;
        i128 x,y;
        exgcd(b,c,x,y);
        i128 x0=x*m/g,y0=y*m/g;ll dx=c/g,dy=b/g;//dx为增加量,dy为减少量
        ll l1,r1,l2,r2;
        if(x0<1) l1=(1-x0-1)/dx+1,r1=(n-x0)/dx;
        else if(x0>=1&&x0<=n) 
        {
            l1=(x0-1)/dx,r1=(n-x0)/dx;
            l1=-l1;
        }
        else 
        {
            l1=(x0-1)/dx,r1=(x0-n-1)/dx+1;
            l1=-l1,r1=-r1;
        }
        if(y0>n) l2=(y0-n-1)/dy+1,r2=(y0-1)/dy;
        else if(y0>=1&&y0<=n) 
        {
            l2=(n-y0)/dy,r2=(y0-1)/dy;
            l2=-l2;
        }
        else
        {
            l2=(n-y0)/dy,r2=(1-y0-1)/dy+1;
            l2=-l2,r2=-r2;
        }
        ans+=max(0ll,min(r1,r2)-max(l1,l2)+1);
    }
    cout<<ans<<'\n';
    return 0;
}