【非官方题解】牛客算法周周练2

A、相反数

Solution

签到题，没什么很值得注意的，我写的是python，其实这题完全可以改成大数，那样的话python会更方便

Code

n=input()
m=int(n[::-1])
n=int(n)
print(n+m)

B、Music Problem

传送戳我

题目大意

给定T组数据，每组数据一个n，表示n个元素，每个元素有一个值，问能不能从n个元素里面选出若干元素，达成和为3600的倍数

Solution

因为这题不需要知道每一个时间点如何求到，只需要知道能不能求到，所以我们借助bitset容器可以方便解题，开一个大小为3600的bitset容器，如果bitset[i] = true，说明这一个值可以给求解出来，那么我们每一步也很明显，吧bitset[a[i] % 3600] = true，那么对于整个过程，原来求解出来的值加上 a[i] or 加上a[i]后的溢出部分，都是可被求解状态。
100 + 100 =200 可解
3500 + 3500 = 3400 可解

#include <bits/stdc++.h>
using namespace std;
#define js ios::sync_with_stdio(false);cin.tie(0); cout.tie(0)
typedef long long ll;

inline int read() {
    int s = 0, w = 1; char ch = getchar();
    while (ch < 48 || ch > 57) { if (ch == '-') w = -1; ch = getchar(); }
    while (ch >= 48 && ch <= 57) s = (s << 1) + (s << 3) + (ch ^ 48), ch = getchar();
    return s * w;
}

const int N = 3600;
const int M = 1e5 + 7;
int a[M];
bitset<N> bit;

int main() {
    int T = read();
    while (T--) {
        int n = read();
        for (int i = 1; i <= n; ++i) a[i] = read();
        bit >>= N;
        for (int i = 1; i <= n; ++i) {
                   //  直接加上a[i]            原先可求值加a[i]的溢出部分
            bit |= ((bit << (a[i] % N)) | (bit >> (3600 - (a[i] % N))));
            //自己本身谁也不加也可解
            bit[a[i] % N] = true;
        }
        if (bit[0]) puts("YES");
        else        puts("NO");
    }
    return 0;
}

C、完全平方数

传送戳我

Solution

题目给定 $图片说明$ ,求解在这个区间的完全平方数，我们直接把左区间开根号并且向上取整，右区间开根号向下取整，得到的新区间就是任意x属于这个区间，平方和都在 $图片说明$ 内。还要值得注意一点区间减法+1回去，带端点减法，别求错元素个数了。

#include <bits/stdc++.h>
using namespace std;
#define js ios::sync_with_stdio(false);cin.tie(0); cout.tie(0)
typedef long long ll;

inline int read() {
    int s = 0, w = 1; char ch = getchar();
    while (ch < 48 || ch > 57) { if (ch == '-') w = -1; ch = getchar(); }
    while (ch >= 48 && ch <= 57) s = (s << 1) + (s << 3) + (ch ^ 48), ch = getchar();
    return s * w;
}

int main() {
    int T = read();
    while (T--) {
        int l = read(), r = read();
        int ans = 1 - ceil(sqrt(l)) + floor(sqrt(r));
        printf("%d\n", ans);
    }
    return 0;
}

D、小H和游戏

传送戳我

Solution

题目给定每次影响范围都为2，我们通过一次dfs找到每个节点的父节点。
并且开一个计数数组 sum[N][3]；
sum[i][0] 表示i为根对自己的波及次数
sum[i][1] 表示i为根对儿子的波及次数
sum[i][2] 表示i为根对孙子的波及次数
这样我们不难考虑到，每次输入轰炸城市city，向下对儿子和孙子波及次数+1
向上对父亲和爷爷节点波及次数也+1
哪还有自己同父亲的兄弟节点未被考虑到，所以我们可以吧父亲节点对儿子节点波及次数+1
自己的那个波及次数算在父亲节点对全部儿子节点影响里面了
最后得到 $图片说明$ $图片说明$

Code

#include <bits/stdc++.h>
using namespace std;
#define js ios::sync_with_stdio(false);cin.tie(0); cout.tie(0)
typedef long long ll;

inline int read() {
    int s = 0, w = 1; char ch = getchar();
    while (ch < 48 || ch > 57) { if (ch == '-') w = -1; ch = getchar(); }
    while (ch >= 48 && ch <= 57) s = (s << 1) + (s << 3) + (ch ^ 48), ch = getchar();
    return s * w;
}

const int N = 7.5e5 + 7;
vector<int> e[N];
int father[N];
int sum[N][3]; //  0自己 1父亲 2爷爷

void dfs(int u, int fa) {
    father[u] = fa;
    for (auto it : e[u])
        if (it != fa)   dfs(it, u);
}

int main() {
    int n = read(), m = read();
    for (int i = 1; i < n; ++i) {
        int u = read(), v = read();
        e[u].push_back(v);
        e[v].push_back(u);
    }
    dfs(1, 0);
    while (m--) {
        int city = read();
        ++sum[city][1];
        ++sum[city][2];
        ++sum[father[city]][0];
        ++sum[father[city]][1];
        ++sum[father[father[city]]][0];
        printf("%d\n", sum[city][0] + sum[father[city]][1] + sum[father[father[city]]][2]);
    }
    return 0;
}

E、水题(water)

传送戳我

Solution

看到这个递推式其实我本来是知道斐波那契数列前n项平方和，等于f(n) * f(n+1)但是一眼并没有看出来。
以致于我只有手算了前几项，1 1 2 3 5 8 …… 这样明眼人都看得出是斐波那契数列了吧。这时候我就想起了斐波那契数列前n项和等于f(n) * f(n+1)和定义相同。。只是换了个位置，我就没看出来有点不应该。
那么题目就转变为是否有一项斐波那契数等于n。通过递推一项项推到大于等于n的那一项停止，如果这一项大于n，那么就是求 n=z的n皇后问题，这个比较简单，直接网上搜方法数打表或者我用了一下江大佬的究极优化版求n皇后问题，没有用递归去求。）就是抄了手板子。
如果这一项斐波那契数不等于n，那么就要求 n!在m进制下的末尾0的个数。
我们先考虑10进制下， $图片说明$ 末尾0的个数，只有2 * 5 = 10，那么就是转换成求解 1-x中约数2的个数和约数5的个数，用100打比方，有因子5的是 5 10 15 20 25 …… 一共20个，
其中25 50 75 100，比较特殊，25 = 5 * 5，50 = 2 * 5 * 5……所以需要多加一个5，所以因子5的个数为24个。
因子2的个数通过公式求得为 $图片说明$
24个5，97个2，一共最多可以凑到24对（2，5），所以末尾有24个0。
那么到3进制下，就是找 $图片说明$ 里面有几个因子3。
9进制下就是找 $图片说明$ 里面有几个9，又因为 $图片说明$ 所以，我们计算得到 $图片说明$ 里面3的因子个数，再除以9里面3的因子个数，就是答案。
通过上面又可以发现，和数的因子数目，可以通过素数个数除法得到，又因为存在多个数乘积等于m，所以我们枚举小于等于m的全部素数，依次求解，得到最小值，就是最优解。

Code

#include <bits/stdc++.h>
using namespace std;
#define js ios::sync_with_stdio(false);cin.tie(0); cout.tie(0)
typedef long long ll;
typedef unsigned long long ull;

inline int read() {
    int s = 0, w = 1; char ch = getchar();
    while (ch < 48 || ch > 57) { if (ch == '-') w = -1; ch = getchar(); }
    while (ch >= 48 && ch <= 57) s = (s << 1) + (s << 3) + (ch ^ 48), ch = getchar();
    return s * w;
}

const int maxn = 1e2 + 7;
int QUEEN[maxn];
int N, Num = 0;
void SetQueen(ll Row, ll Column, ll LeftSlash, ll RightSlash) {
    ll available = ((1 << N) - 1) & ~(Column | LeftSlash | RightSlash);
    while (available) {
        ll p = available & -available;
        available ^= p;
        QUEEN[Row] = (int)(log2(p)) + 1;
        if (Row == N - 1) {
            ++Num;
            //for (int i = 0; i < N; ++i) cout << QUEEN[i] << " ";
            //cout << endl;
        }
        else
            SetQueen(Row + 1, Column | p, (LeftSlash | p) >> 1,
                (RightSlash | p) << 1);
    }
}
int main() {
    ull n;
    int m;
    scanf("%llu %d", &n, &m);
    ull f1 = 1, f2 = 1, f3;
    do {
        f3 = f1 + f2;
        f1 = f2;
        f2 = f3;
    } while (f3 < n);
    if (f3 != n) {
        N = n % min(13, m) + 1;
        SetQueen(0, 0, 0, 0);
        /*cout << "There are " << Num << " solutions to the problem of the " << N
            << " Queens" << endl;*/
        printf("%d\n", Num);
    }
    else {
        ull tmp = f3;
        ll ans = 1e18, sum1 = 0, sum2 = 0;
        for (int i = 2; i <= 100; ++i) {
            if (m % i)    continue;
            sum1 = sum2 = 0;
            while (m % i == 0)    ++sum1, m /= i; //sum1记录m中包含质因数i的个数
            f3 = n;
            while (f3) {
                sum2 += f3 / i; //sum2记录x！中包含质因数i的个数
                f3 /= i;
            }
            ans = min(ans, sum2 / sum1);
        }
        printf("%lld\n", ans);
    }
    return 0;
}