A.之前写过题解,不说了。
B.N 钱买 N 鸡,要求 O(n)。
思路还是和之前一样,但是提供一种新写法:
#include<bits/stdc++.h>
#define ll long long
using namespace std;
ll n;
int ans[29] = {1, 0, 0, 0, 1, 0, 0, 1, 1, 0, 0, 1, 1, 0, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1};
int main()
{
scanf("%lld", &n);
printf("%lld\n", n / 28 + ans[n % 28]);
}
把式子列出来,把分数化掉,会得到一个关于 4 和 7 的奇怪式子。通过打表找规律会发现到 4 * 7 的倍数时就是统计答案的新一层。至于代码里 ans[29] 那些也是通过打表体现 4 和 7 之和等可能性。
C.简述一下题目:给你一个序列,对于每个元素,其答案是序列中能被它整除掉的元素个数,对于每个元素求答案。
算是暴力吧:出现的每个数字用桶装一遍,然后对于每个数字找一遍因数加上答案即可。
#include<bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
int n;
int ys[N];
int ans[N], tong[N * 10], a[N];
int main()
{
scanf("%d", &n);
for(int i = 1; i <= n; i ++ )
{
scanf("%d", &a[i]);
tong[a[i]] ++;
}
for(int i = 1; i <= n; i ++ )
{
int tot = 0;
for(int j = 1; j * j <= a[i]; j ++ )
{
if(a[i] % j == 0)
{
ys[++ tot] = j;
if(j != a[i] / j) ys[++ tot] = a[i] / j;
}
}
for(int j = 1; j <= tot; j ++ )
{
ans[i] += tong[ys[j]];
ys[j] = 0;
}
}
for(int i = 1; i <= n; i ++ ) printf("%d\n", ans[i] - 1);
}
找因数那一部分是板子就不说了,书上有解释。
还可以根号分治,优美的暴力!但是本题不太适用,跑的会比较慢。主要原因是我不会写()
题解鸽了很久没有一篇写完的了,所以为这伟大的一篇新鲜出炉的题解撒花表示热烈庆祝!()