2021“MINIEYE杯”中国大学生算法设计超级联赛(5) 杭电多校5 题解
sdxjzsq
2021-08-15 16:40:14
## 目录
| 题号 | 题目 | 知识点 | 完成度 |
| ---- | ------------------------------------------------------------ | ------ | ------ |
| 1009 | HDU7020 [Array](https://acm.hdu.edu.cn/showproblem.php?pid=7020) | 前缀和 | √ |
| 1004 | HDU7015 [Another String](https://acm.hdu.edu.cn/showproblem.php?pid=7015) | - | - |
| 1005 | HDU7016 [Random Walk 2](https://acm.hdu.edu.cn/showproblem.php?pid=7016) | - | - |
| 1013 | HDU7024 [Penguin Love Tour](https://acm.hdu.edu.cn/showproblem.php?pid=7024) | - | - |
| 1008 | HDU7019 [Supermarket](https://acm.hdu.edu.cn/showproblem.php?pid=7019) | - | - |
| 1002 | HDU7013 [String Mod](https://acm.hdu.edu.cn/showproblem.php?pid=7013) | - | - |
| 1001 | HDU7012 [Miserable Faith](https://acm.hdu.edu.cn/showproblem.php?pid=7012) | x | x |
| 1012 | HDU7023 [Yet Another Matrix Problem](https://acm.hdu.edu.cn/showproblem.php?pid=7023) | x | x |
## 1009 HDU7020 [Array](https://acm.hdu.edu.cn/showproblem.php?pid=7020)
### 题意
统计存在严格意义的众数的区间个数。
### 思路
枚举每个数作为众数，并且将数组变成只有 $1$（是这个数） 和 $-1$ （不是这个数）数组，并对此求前缀和，然后根据前缀和的差求解。
### code
```cpp
#include <cmath>
#include <cstdio>
using namespace std;
int t;
long long n;
const int maxp = 10000001;
int pr[maxp], prime[maxp], top = 0;
int check(long long x)
{
if (x > 10000000)
{
for (int i = 1; 1ll * prime[i] * prime[i] <= x; ++i)
if (x % prime[i] == 0) return 0;
return 1;
}
return !pr[x];
}
inline void getPrime(int maxprime)
{
pr[1] = 1;
for (int i = 2; i <= maxprime; i++)
{
if (!pr[i]) prime[++top] = i;
for (int j = 1; j <= top && i * prime[j] <= maxprime; j++)
{
pr[i * prime[j]] = 1;
if (!(i % prime[j])) break;
}
}
}
int main()
{
getPrime(10000000);
for (scanf("%d", &t); t--;)
{
scanf("%lld", &n);
long long ans = 0;
int flag = 1;
if (n <= 0) flag = 0, ans = (-n * 2) + 1, n = -n + 1;
if (check(n))
ans += 1;
else if (check(2 * n + 1))
ans += 2;
else if (flag && check(n * 2 - 1))
ans += 2;
else
{
if (flag)
ans += n * 2 + 1, ++n;
else
ans += 2, ++n;
int orz = 1;
while (orz)
{
if (check(n))
ans += 1, orz = 0;
else if (check(n * 2 + 1))
ans += 2, orz = 0;
else
ans += 2, ++n;
}
}
printf("%lld\n", ans);
}
return 0;
}
```