文章目录
- A、Stone Game
- B、Friends and Candies
- C、Number of Pairs
- D、 Another Problem About Dividing Numbers
- F、Interesting Function
A、Stone Game
1.思路
先找到最大值和最小值的下标，然后分3类讨论(只操作左端点，只操作右端点，和两端都操作）取最小值即可。
2.参考代码
#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e5 + 10;
int a[maxn];
int n;
int main()
{
int t;
scanf("%d", &t);
while (t--)
{
int maxx = INT_MIN, maxi = 0, minn = INT_MAX, mini = 0;
scanf("%d", &n);
for (int i = 1; i <= n; i++)
{
scanf("%d", &a[i]);
if (a[i] > maxx)
{
maxx = a[i];
maxi = i;
}
if (a[i] < minn)
{
minn = a[i];
mini = i;
}
}
int sum1 = 0, sum2 = 0, sum3 = 0;
sum1 = max(maxi, mini);
sum2 = n - min(maxi, mini) + 1;
sum3 = min(maxi, mini) + n - max(maxi, mini) + 1;
printf("%d\n", min(sum1, min(sum2, sum3)));
}
}
B、Friends and Candies
1.思路
要将每个a[i]值都变成相同，则需要将大于平均值的数取出来然后进行分配，知道这点就能轻松AC，但是注意要判断输出-1的情况（a[i]的和不能被n整除）。
2.参考代码
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int maxn = 2e5 + 10;
ll a[maxn];
ll sum;
ll n;
int main()
{
int t;
scanf("%d", &t);
while (t--)
{
sum = 0;
scanf("%lld", &n);
for (int i = 1; i <= n; i++)
{
scanf("%lld", &a[i]);
sum += a[i];
}
if (sum % n != 0)printf("-1\n");
else
{
ll avge = sum / n;
int ans = 0;
for (int i = 1; i <= n; i++)
if (a[i] > avge)ans++;
printf("%d\n", ans);
}
}
}
C、Number of Pairs
1.思路
要找到有多少对符合条件的数对，则我们可以通过for循环来枚举起点，至于终点要怎么得到呢？
继续for循环？如果继续for循环将喜提TLE，起点确定了来确定符合条件的一段区间可以通过二分来获取。先sort一下，然后二分下标找符合条件的数对对数。
二分可以巧用upper_bound和lower_bound。用upper_bound来找到第一个大于**r - a[i]的下标，用lower_bound来找到第一个大于等于l - a[i]**的下标。在两个下标之间的个数就是全部符合条件的个数。注意upper_bound和lower_bound返回下标时可能小于了i，这是我们需要去掉这段区间。
2.参考代码
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int maxn = 2e5 + 10;
ll a[maxn];
ll n, l1, r1;
int main()
{
int t;
scanf("%d", &t);
while (t--)
{
scanf("%lld%lld%lld", &n, &l1, &r1);
for (int i = 1; i <= n; i++)
scanf("%lld", &a[i]);
sort(a + 1, a + 1 + n);
ll ans = 0;
for (int i = 1; i <= n; i++)
{
ll x = upper_bound(a + 1, a + n + 1, r1 - a[i]) - a - 1;
if (x <= i)continue;
ans += x - i;
ll y = lower_bound(a + 1, a + n + 1, l1 - a[i]) - a - 1;
if (y <= i)continue;
ans -= y - i;
}
printf("%lld\n", ans);
}
}
D、 Another Problem About Dividing Numbers
1.思路
这题主要是找到符合a、b转换相同的次数的区间较难。
首先我们可以把a、b的最大公约数求出来。转化的时候就是最大公约数gcd可以转换2次，则最多可以转化2*（最大公约数的质因子个数）次。那a/gcd、b/gcd也可转化各自的质因子的个数次。
则转化为相同数的最多次数为2*（最大公约数的质因子个数）+a/gcd的质因子的个数+b/gcd的质因子的个数
最小的地方判断要更加细心，我由于粗心导致WA了两发。首先在ab的地方k一定是不能等于1的。其次ab的时候，最小转化次数为0。a % b ==0|| b % a == 0时，最小转化次数为1，那其余的情况则为2了。
2.参考代码
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int maxn = 1e5 + 10;
ll a, b, k;
ll prime[maxn];
bool vis[maxn];
ll cnt;
ll gcd(ll x, ll y)
{
return y == 0 ? x : gcd(y, x % y);
}
void Prime()
{
for (int i = 2; i < maxn; i++)
{
if (vis[i] == false) prime[cnt++] = i;
for (int j = 0; i * prime[j] < maxn; j++)
{
vis[i * prime[j]] = true;
if (i % prime[j] == 0) break;
}
}
}
ll solve(ll h)
{
ll ans = 0;
for (int i = 0; i < cnt; i++)
{
if (prime[i] * prime[i] > h)break;
if (h % prime[i] == 0)
{
ll sum = 0;
while (h % prime[i]==0)
{
h /= prime[i];
sum++;
}
ans +=sum;
}
}
if (h != 1)ans += 1;
return ans;
}
int main()
{
int t;
scanf("%d", &t);
Prime();
while (t--)
{
scanf("%lld%lld%lld", &a, &b, &k);
if (a == b && k == 1)printf("NO\n");
else if (a == 1 && b == 1 && k != 0)printf("NO\n");
else
{
ll l, r;
ll xx = gcd(a, b);
ll yy = a / xx, zz = b / xx;
if (a == b)l = 0;
else if (a % b == 0 || b % a == 0)l = 1;
else l = 2;
r = 2 * solve(xx) + solve(yy) + solve(zz);
if (k >= l && k <= r)printf("YES\n");
else printf("NO\n");
}
}
}
F、Interesting Function
1.思路
思路极其简单，只需要判断l到r中，每一位数字变化的次数相加即可。（水题放这么后面，cf搞心态呀）
2.参考代码
#include<bits/stdc++.h>
using namespace std;
#define ll long long
int main()
{
int t;
scanf("%d", &t);
while (t--)
{
ll ans = 0;
ll l, r;
scanf("%lld%lld", &l, &r);
while (r)
{
ans += r - l;
r /= 10;
l /= 10;
}
printf("%lld\n", ans);
}
}