夏令营7.10总结

今天是夏令营的第一天

上午

学习了枚举，就是一种优雅的暴力

开始做题~

T1

题意

题意为给定一个 N，求满足 $A\le B \le C$ 且 $A\times B\times C\le N$ 的整数 $a,b,c$ 的数量。

数据范围是

• $1\le N\le 10^{11}$，要用 long long。
• 答案 $\le 2^{63}$，也要用 long long。

思路

枚举 AB，计算 C 的可能个数。

使用双重循环，第一层枚举 $A^3$，第二层枚举 $A\times B^2$。

代码

#include<bits/stdc++.h>
using namespace std;
#define int long long
int n;
int ans=0;
signed main(){
	cin>>n;
	for(int a=1;a*a*a<=n;a++){
		for(int b=a;a*b*b<=n;b++){
			int c=n/(a*b);
			if(c<b) continue;
			ans+=c-b+1;
		}
	}
	cout<<ans;
	return 0;
}

T2

题意

求大于 X 的一个十进制数 N，使得 N 的全部位数按位数排序后为等差数列。

思路

是长度为 L 的，各项为 0 到 9 的，首项不是 9 的等差数列。

数列由首项与公差决定。

• 首项: 1,2,…,9
• 公差: -9,-8,…,9

直接枚举，枚举量小于 200。

代码

#include<bits/stdc++.h>
using namespace std;
#define int long long
signed main(){
	int x;
	cin>>x;
	int ans=x*10;
	int len=to_string(x).size();
	for(int a=1;a<=9;a++){
		for(int d=-9;d<=9;d++){
			int sum=0;
			for(int i=0;i<len;i++){
				int t=a+d*i;
				if(t<0||t>9) break;
				sum=sum*10+t;
			}
			if(sum>=x){
				ans=min(ans,sum);
			}
		}
	}
	cout<<ans;
	return 0;
}

T3

题意

给定正整数 N 和 M，找到最小正整数 X，使得 X 可以表示为 a，b 两个整数的乘积且 $1\le a,b\le N$（a，b 可以相同）且 $M\le X$。

数据范围：

• $1\le N\le 10^{12}$
• $1\le N\le 10^{18}$

简化

找到 a,b 满足：

• $1\le a,b\le N$
• $m\le a\times b$

思路

枚举 a，从 1 到 $min(N,\sqrt{M})$

代码

#include<bits/stdc++.h>
using namespace std;
#define int long long
signed main(){
	int n,m;
	cin>>n>>m;
	int ans=-1;
	for(int a=1;a<=n;a++){
		int b=(m+(a-1))/a;
		if(b<=n){
			if(ans==-1||ans>a*b){
				ans=a*b;
			}
		}
		if(a*a>=m){
			break;
		}
	}
	cout<<ans;
	return 0;
}

中午

睡觉………………

下午

题目逐渐变得难了起来…

T4（随堂练习）

题意

有三种物品，是易拉罐，普通罐头和开罐器。易拉罐可以获得 x 点体力，普通罐头要消耗开罐器的一点耐久，获得 x 点体力，开罐器可以开罐 x 次。从 N 个中拿走 N 个，求最大可以获取的体力值。

数据范围：

• $1\le M\le N\le2\times10^5$
• $1\le x_i\le10^9$

思路

• 无论是什么东西，都优先拿 x 更大的。
• 如果要拿普通罐头，则一定要打开。打不开的干脆不拿。
• 由拿的普通罐头数量决定开罐器的数量。尽量不要多拿。
• 其实也可以那小于 m 个物品，效果一样。

代码逻辑

1. 把物品分类后按 x 的大小排序
2. 计算每种物品的前缀和数组
3. 枚举拿几个普通罐头，几个开罐器，几个易拉罐头。

代码

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;

signed main(){
	int n,m;
	cin>>n>>m;
	vector<int> X[3];
	for(int i=0;i<n;i++){
		int t,x;
		cin>>t>>x;
		X[t].push_back(x);
	}
	for(int i=0;i<3;i++){
		sort(X[i].rbegin(),X[i].rend());
	}
	vector<ll> sum[3];
	for(int i=0;i<3;i++){
		sum[i].resize(X[i].size()+1);
		for(int j=0;j<X[i].size();j++){
			sum[i][j+1]=sum[i][j]+X[i][j];
		}
	}
	ll ans=0;
	int j=0;
	for(int i=0;i<=(int)X[1].size();i++){
		if(i>m) break;
		if(sum[2][j]<i) j++;
		if(j>(int)X[2].size()||i+j>m) break;
		int k=min(m-i-j,(int)X[0].size());
		ans=max(ans,sum[0][k]+sum[1][i]);
	}
	cout<<ans;
	return 0;
}