8.30 下午训练

· · 算法·理论

T1 A T2 B T3 C T4 D
100 0 100 40

T1 A

两分钟就可以 AC 的入门题，依题意直接写就行

注：一开始题目看错，所以 a\text{ 和 }b 是反的

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int maxn();
double a,b;
int main(){
    cin>>b>>a;
    while(b>=a){
        b-=a;
    }
    printf("%.2lf",b);
    return 0;
}

T2 B

通过推出第四种情况我们可以发现 dp_4=dp_1+dp_2+dp_3+方案数 由此可得 dp_i=dp_{i-1}+dp_{i-2}+dp_{i-3}+f_i ，dp_i 为长度为 i 时所需要的个数 ，f_i 为长度为 i 时有多少种方案数。

注意到不取模见祖宗

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int mod(99824353);
const int maxn(1e6+10);
int dp1[maxn],dp[maxn];
int T,n;
int main(){
    cin>>T;
    dp[1]=1;
    dp[2]=2;
    dp[3]=4;
    for(int i(4);i<=1e6;i++){
        dp[i]=dp[i-1]+dp[i-2]+dp[i-3];
        dp[i]%=mod;    //取mod
    }
    dp1[1]=1;
    dp1[2]=3;
    dp1[3]=8;
    for(int i(4);i<=1e6;i++){
        dp1[i]=dp1[i-1]+dp1[i-3]+dp1[i-2]+dp[i];
        dp1[i]%=mod;   //取mod
    }
    while(T--){
        cin>>n;
        cout<<dp1[n]<<'\n';
    }
    return 0;
}

T3 C

第一眼看到无法到达输出 -1 于是直接 cout<<-1 拿到 10 分，然后我们想如何可以在正常情况下拿到这 10 分（正常情况指写的是暴力或正解的情况），注意到鱼大大每个城市都要游玩至少一天的时间 1\le x ，且在路上耗费的天数要向上取整: \lceil \frac{d}{v}\rceil（两个城市之间的距离为 d，而速度为 v），也就是说在每两个城市之间在路上至少要花费一天赶路，所以如果游玩的时间 \ge 要求完成时间则 cout<<-1

注意到每条路的长度大得丧心病狂，如果直接枚举速度显然会 TLE ，经过我们仔细观察发现如果速度越快则需要的天数就越少，速度越慢需要的天数就越多，拥有单调性可以考虑二分

对于二分我们只需要二分其的速度并每次判断此速度是否合法，如果合法试试更小的，不合法试更大的。

注：不开 long\text{ }long见祖宗，只有 50 分

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int maxn(1e5+10);
ll n,m;
ll a[maxn],x[maxn];
bool ch(ll mid){
    ll sum(0);
    for(ll i(1);i<=n;i++){
        sum+=a[i]/mid;
        if(a[i]%mid>0){
            sum++; 
        }
    }
    if(sum<=m){
        return true;
    }
    return false;
}
int main(){
    cin>>n>>m;
    ll sum(0),maxx(0);
    for(ll i(1);i<=n;i++){
        cin>>a[i]>>x[i];
        sum+=x[i];
        maxx=max(maxx,a[i]);
    }
    if(sum>=m){
        cout<<-1<<'\n';
        return 0;
    }
    m-=sum;
    ll l(0),r(maxx);
    while(l<r){
        ll mid((l+r)/2);
        if(ch(mid)){
            r=mid;
        }else{
            l=mid+1;
        }
    }
    cout<<l<<'\n';
    return 0;
}

T4 D

注意到题目求曼哈顿距离的最大值的最小值 ，容易看错题

我们设 D(A,B) 为 A 到 B 的曼哈顿距离，A(x_1,y_1) ，B(x_2,y_2)

\begin{aligned} D (A,B) &=∣x_1 −x_2 ∣+∣y_1 −y_2 ∣ \\ &=max(x_1−x_2 +y_1 −y_2 ,x_1 −x_2 +y_2 −y_1 ,x_2 −x_1+y_1 −y_2,x_2−x_1+y_2 −y_1 )\\ &=max(∣(x_1+y_1 )−(x_2+y_2 )∣,∣(x_1 −y_1 )−(x_2 −y_2 )∣)\\ &=d((x_1 +y_1 ,x_1−y_1 ),(x_2+y_2 ,x_2 −y_2 )) \end{aligned}

实际上表示为下面这个形式就可以了，我们发现

\begin{aligned} D (A,B)&=∣x_1 −x_2∣+∣y_1 −y_2 ∣\\ &=max(x_1 −x_2 +y_1−y_2,x_1 −x_2 +y_2 −y_1,x_2 −x_1+y_1 −y_2 ,x_2−x_1 +y_2−y_1)\\ &=max((x_1+y_1)−(x_2 +y_2),(x_1 −y_1 )−(x_2 −y_2),y_1 −x_1 −(y_2 −x_2 ),−(y_1 +x_1 )−(−(y_2+x_2 ))) \end{aligned}

规律点是

D(A,B)=max((x_1\times dir+y_1\times dir)−(x_2\times dir+y_2\times dir))

其中 dir 表示一个方向，此时的 (x_1,y_1) 和 (x_2,y_2) 是独立的关系，可以只用一个循环求解出来 (x_1,y_1) 四个方向之中的最大值

然后求解出来另外一个点四个方向之中的最大值，最后合并即可

#include<bits/stdc++.h>
using namespace std;
const int maxn(1e6+7);
int a[maxn],b[maxn];
int x[maxn],y[maxn];
int T,n,m;
int d[4][2]={{1,1},{-1,1},{1, -1},{-1, -1}};
int maxx[4];
int main(){
    cin>>T;
    while(T--){
        cin>>n>>m;
        for(int i(1);i<=n;i++){
            cin>>x[i]>>y[i];
        }
        for(int i(1);i<=m;i++){
            cin>>a[i]>>b[i];
        }
        for(int i(0);i<4;i++){
            maxx[i]=-2e9;
        }
        for(int i(1);i<=n;i++){
            for(int j(0);j<4;j++){
                int ans=x[i]*d[j][0]+y[i]*d[j][1];
                maxx[j]=max(maxx[j],ans);
            }
        }
        int res(2e9);
        for(int i(1);i<=m;i++){
            int ans(0);
            for(int j(0);j<4;j++){
                int temp(maxx[j]-a[i]*d[j][0]-b[i]*d[j][1]);
                ans=max(ans,temp);
            }
            res=min(res,ans);
        }
        cout<<res<<'\n';
    }
    return 0;
}