AcWing——第 71 场周赛
AcWing——第 71 场周赛
4621. 三个整数
问题解析
因为数据很小，仅有1≤a≤b≤c≤d≤100，那么我们可以直接用三层for循环，第一层在a~b枚举x，第二层z 在bc枚举y，第三层在cd枚举z，找到一个满足x+y>z的结果后将他们输出即可。
AC代码
void solve()
{
int a, b, c, d;
cin >> a >> b >> c >> d;
for (int i = a; i <= b; i++)
{
for (int j = b; j <= c; j++)
{
for (int k = c; k <= d; k++)
{
if (i + j > k)
{
cout << i << " " << j << " " << k << endl;
return;
}
}
}
}
}
4622. 整数拆分
问题解析
f(x)表示整数 x 的除本身之外的最大因数，那么当x为质数时，f(x)=1，所以这一题其实就是让我们用最少的质数相加得到x，质数的个数就是这一题的答案。
- 那么当x为质数时，f(x)直接就等于1了，不用拆分。
- 当x为偶数时，这里就要讲一个非常著名的猜想：哥德巴赫猜想。哥德巴赫猜想是说，对于任意一个大于2的偶数都可以拆分成两个质数之和（虽然只是猜想，没法验证，但是用起来是完全没问题的）。所以当x为偶数时，结果就是2。
- 当x为奇数时，我们要再分情况考虑，如果x-2是一个质数，那么我们把x拆分成x-2和2就可以得到最小的结果，结果是2；如果x-2不是质数，我们就可以把x拆分成3和一个偶数，这样的结果是3.
AC代码
bool check(int x)
{
for (int i = 2; i <= x / i; i++)
{
if (x % i == 0)return false;
}
return true;
}
void solve()
{
int n;
cin>>n;
if(check(n))
{
cout<<1;
}
else if(n%2==0)cout<<2;
else if(check(n-2))cout<<2;
else cout<<3;
}
4623. 买糖果 - AcWing题库
问题解析
这题看着花里胡哨，实则解法非常暴力，我们只用一轮一轮的模拟即可，用cnt记录可以买到的糖果数。
- 初始先计算如果所有的糖果都买需要多少钱，记为sum。
- 如果我们的钱t大于sum，那我们就可以通过：当前店铺数*t/sum来得到我们可以一直买下去的糖果数，之后我们的金钱变为t%sum。
- 当sum大于t时，我们遍历一遍所有的店铺，如果这个店铺的糖果我们能买，则cnt++，金钱减去这个店铺的售价a[i]。如果这个店铺的糖果我们不能买，我们用st数组记录下这个店铺，并把它从sum中减去。
- 重复第2，3操作，知道我们一个糖果都买不了为止。
int a[N];
bool st[N];
void solve()
{
int n, t, sum = 0, cnt = 0;
cin >> n >> t;
int ans = n;
for (int i = 1; i <= n; i++)
{
cin >> a[i];
sum += a[i];
}
while (1)
{
cnt += ans * (t / sum);
t %= sum;
bool flag = false;
for (int i = 1; i <= n; i++)
{
if (st[i])continue;
if (t >= a[i])
{
cnt++;
t -= a[i];
flag = true;
}
else
{
st[i] = true;
sum -= a[i];
ans--;
}
}
if (!flag)break;
}
cout << cnt;
}