专栏文章

8.30 下午训练

KKoei
算法·理论参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@mio23plp
此快照首次捕获于
2025/12/02 12:06
3 个月前
此快照最后确认于
2025/12/02 12:06
3 个月前
查看原文
T1 AT2 BT3 CT4 D
100010040

T1 A

两分钟就可以 ACAC 的入门题，依题意直接写就行
注：一开始题目看错，所以 a 和 ba\text{ 和 }b 是反的
CPP
#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

通过推出第四种情况我们可以发现 dp4=dp1+dp2+dp3+方案数dp_4=dp_1+dp_2+dp_3+方案数 由此可得 dpi=dpi−1+dpi−2+dpi−3+fidp_i=dp_{i-1}+dp_{i-2}+dp_{i-3}+f_i ，dpidp_i 为长度为 ii 时所需要的个数 ，fif_i 为长度为 ii 时有多少种方案数。
1ada
注意到不取模见祖宗
CPP
#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-1 于是直接 cout<<−1cout<<-1 拿到 1010 分，然后我们想如何可以在正常情况下拿到这 1010 分（正常情况指写的是暴力或正解的情况），注意到鱼大大每个城市都要游玩至少一天的时间 1≤x1\le x ，且在路上耗费的天数要向上取整: ⌈dv⌉\lceil \frac{d}{v}\rceil（两个城市之间的距离为 d，而速度为 v），也就是说在每两个城市之间在路上至少要花费一天赶路，所以如果游玩的时间 ≥\ge 要求完成时间则 cout<<−1cout<<-1
注意到每条路的长度大得丧心病狂，如果直接枚举速度显然会 TLETLE ，经过我们仔细观察发现如果速度越快则需要的天数就越少，速度越慢需要的天数就越多，拥有单调性可以考虑二分
对于二分我们只需要二分其的速度并每次判断此速度是否合法，如果合法试试更小的，不合法试更大的。

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

CPP
#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)D(A,B) 为 AA 到 BB 的曼哈顿距离，A(x1,y1)A(x_1,y_1) ，B(x2,y2)B(x_2,y_2)
D(A,B)=∣x1−x2∣+∣y1−y2∣=max(x1−x2+y1−y2,x1−x2+y2−y1,x2−x1+y1−y2,x2−x1+y2−y1)=max(∣(x1+y1)−(x2+y2)∣,∣(x1−y1)−(x2−y2)∣)=d((x1+y1,x1−y1),(x2+y2,x2−y2))\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}
实际上表示为下面这个形式就可以了，我们发现
D(A,B)=∣x1−x2∣+∣y1−y2∣=max(x1−x2+y1−y2,x1−x2+y2−y1,x2−x1+y1−y2,x2−x1+y2−y1)=max((x1+y1)−(x2+y2),(x1−y1)−(x2−y2),y1−x1−(y2−x2),−(y1+x1)−(−(y2+x2)))\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((x1×dir+y1×dir)−(x2×dir+y2×dir))D(A,B)=max((x_1\times dir+y_1\times dir)−(x_2\times dir+y_2\times dir))
其中 dirdir 表示一个方向，此时的 (x1,y1)(x_1,y_1) 和 (x2,y2)(x_2,y_2) 是独立的关系，可以只用一个循环求解出来 (x1,y1)(x_1,y_1) 四个方向之中的最大值
然后求解出来另外一个点四个方向之中的最大值，最后合并即可
CPP
#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;
}

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...