引言
今天写的都是一些全新的题目,而且也都挺有挑战性的,希望自己能够继续加油下去,让自己多练题,多熟悉题型,加油!
一、小苹果
标签:模拟
思路:
这个问题如果一个一个枚举肯定是不行的,所以得换一种思路。要求的有两个总天数和最后一个拿走的天数,每天会拿走n/3上取整个数,然后每次循环遍历直至n为0,然后就是求最后一个,最后一个的编号永远为n,所以如果n%3=1,那么把天数记下就行了,另外只能赋值一次
题目描述:
小 Y 的桌子上放着 n 个苹果从左到右排成一列,编号为从 1 到 n。
小苞是小 Y 的好朋友,每天她都会从中拿走一些苹果。
每天在拿的时候,小苞都是从左侧第 1 个苹果开始、每隔 2 个苹果拿走 1 个苹果。
随后小苞会将剩下的苹果按原先的顺序重新排成一列。
小苞想知道,多少天能拿完所有的苹果,而编号为 n 的苹果是在第几天被拿走的?
输入格式
输入的第一行包含一个正整数 n,表示苹果的总数。
输出格式
输出一行包含两个正整数,两个整数之间由一个空格隔开,分别表示小苞拿走所有苹果所需的天数以及拿走编号为 n 的苹果是在第几天。
数据范围
对于所有测试数据有:1≤n≤109。
特殊性质:小苞第一天就取走编号为 n 的苹果。
输入样例:
8
输出样例:
5 5
样例解释
小苞的桌上一共放了 8 个苹果。
小苞第一天拿走了编号为 1、4、7 的苹果。
小苞第二天拿走了编号为 2、6 的苹果。
小苞第三天拿走了编号为 3 的苹果。
小苞第四天拿走了编号为 5 的苹果。
小苞第五天拿走了编号为 8 的苹果。
示例代码:
#include <iostream>
using namespace std;
int main()
{
int n;
cin >> n;
int days = 0, date = 0;
while(n)
{
days++;
if(!date && n % 3 == 1) date = days;
n -= (n + 2) / 3;
}
printf("%d %d\n", days, date);
return 0;
}
二、公路
标签:贪心
思路:
这道题可以反着来看,油可以先欠着,到了站点再补油,看欠了多少油,然后从之前的站点找一个最便宜的油加上。犯的错就是不应该把油量每次都模拟出来,可以把总的油量和总的距离给弄出来就行了,不然整的很复杂的,而且要算出每段用了多少油,还有精度的问题很麻烦的。
题目描述:
小苞准备开着车沿着公路自驾。
公路上一共有 n 个站点,编号为从 1 到 n。
其中站点 i 与站点 i+1 的距离为 vi 公里。
公路上每个站点都可以加油,编号为 i 的站点一升油的价格为 ai 元,且每个站点只出售整数升的油。
小苞想从站点 1 开车到站点 n,一开始小苞在站点 1 且车的油箱是空的。
已知车的油箱足够大,可以装下任意多的油,且每升油可以让车前进 d 公里。
问小苞从站点 1 开到站点 n,至少要花多少钱加油?
输入格式
输入的第一行包含两个正整数 n 和 d ,分别表示公路上站点的数量和车每升油可以前进的距离。
输入的第二行包含 n−1 个正整数 v1,v2…vn−1,分别表示站点间的距离。
输入的第三行包含 n 个正整数 a1,a2…an,分别表示在不同站点加油的价格。
输出格式
输出一行,仅包含一个正整数,表示从站点 1 开到站点 n,小苞至少要花多少钱加油。
数据范围
对于所有测试数据保证:1≤n≤105,1≤d≤105,1≤vi≤105,1≤ai≤105。
特殊性质 A:站点 1 的油价最低。
特殊性质 B:对于所有 1≤i<n,vi 为 d 的倍数。
输入样例:
5 4
10 10 10 10
9 8 9 6 5
输出样例:
79
样例解释
最优方案下:小苞在站点 1
买了 3
升油,在站点 2
购买了 5
升油,在站点 4
购买了 2
升油。
示例代码:
#include <cstdio>
#include <iostream>
using namespace std;
const int N = 1e5+10;
typedef long long LL;
int n, d;
int v[N], a[N];
int main()
{
scanf("%d%d", &n, &d);
for(int i = 1; i <= n - 1; ++i) scanf("%d", &v[i]);
for(int i = 1; i <= n; ++i) scanf("%d", &a[i]);
LL money = 0, dist = 0, oil = 0;
int price = a[1];
for(int i = 2; i <= n; ++i)
{
dist += v[i-1];
LL t = (dist+d-1) / d - oil; //需要的油
money += price * t;
oil += t;
price = min(price, a[i]);
}
cout << money << endl;
return 0;
}
三、互质数的个数
标签:数学
思路:
这求的是互质数的个数可以根据欧拉定理即可,然后求的是 a b a^b ab的欧拉函数,然后可以根据欧拉函数: ϕ ( N ) = N ⋅ ( 1 − 1 1 − p 1 ) ⋅ ( 1 − 1 1 − p 2 ) ⋯ ( 1 − 1 1 − p k ) \phi(N)=N\cdot(1-\frac{1}{1-p_{1}})\cdot(1-\frac{1}{1-p_{2}})\cdots(1-\frac{1}{1-p_{k}}) ϕ(N)=N⋅(1−1−p11)⋅(1−1−p21)⋯(1−1−pk1)也就是可以转换为: ϕ ( a b ) = a b − 1 ⋅ a ⋅ ( 1 − 1 1 − p 1 ) ⋅ ( 1 − 1 1 − p 2 ) ⋯ ( 1 − 1 1 − p k ) \phi(a^b)=a^{b-1} \cdot a \cdot(1-\frac{1}{1-p_{1}})\cdot(1-\frac{1}{1-p_{2}})\cdots(1-\frac{1}{1-p_{k}}) ϕ(ab)=ab−1⋅a⋅(1−1−p11)⋅(1−1−p21)⋯(1−1−pk1)然后用欧拉函数和快速幂求解即可,如有理论不懂可参考我之前的博客欧拉函数、快速幂
题目描述:
给定 a,b,求 1≤x<ab 中有多少个 x 与 ab互质。
由于答案可能很大,你只需要输出答案对 998244353 取模的结果。
输入格式
输入一行包含两个整数分别表示 a,b,用一个空格分隔。
输出格式
输出一行包含一个整数表示答案。
数据范围
对于 30% 的评测用例,ab≤106;对于 70% 的评测用例,a≤106,b≤109;对于所有评测用例,1≤a≤109,1≤b≤1018。
输入样例1:
2 5
输出样例1:
16
输入样例2:
12 7
输出样例2:
11943936
示例代码:
#include <cstdio>
#include <iostream>
using namespace std;
typedef long long LL;
const int MOD = 998244353;
LL qmi(LL a, LL b)
{
LL res = 1;
while(b)
{
if(b & 1) res = res * a % MOD;
a = a * a % MOD;
b >>= 1;
}
return res;
}
LL a, b;
int main()
{
cin >> a >> b;
if(a == 1)
{
cout << 0 << endl;
return 0;
}
LL res = a, x = a;
for(int i = 2; i <= x / i; ++i)
{
if(x % i == 0)
{
res = res - res / i;
while(x % i == 0) x /= i;
}
}
if(x > 1) res = res - res / x;
cout << res * qmi(a, b-1) % MOD << endl;
return 0;
}