牛客算法周周练2

A - 相反数

Solution

签到题，直接std::stoi即可。

Code

#include <bits/stdc++.h>
using namespace std;

using ll = long long;

int main() {
  cin.sync_with_stdio(false), cin.tie(nullptr);

  string s;
  cin >> s;
  string t(s.rbegin(), s.rend());
  cout << stoi(s) + stoi(t) << "\n";
}

B - Music Problem

Solution

bitset优化背包。

这题实际要求的是能否选出一些数，使得它们的和模为；

显然，这是个很普通的背包问题，但是因为数据范围比较大，并且我们只需要知道是否大于，所以要用bitset优化dp过程。

复杂度为，注意在时就可以结束dp了，不需要继续做下去。

Code

#include <bits/stdc++.h>
using namespace std;

using ll = long long;

int main() {
  cin.sync_with_stdio(false), cin.tie(nullptr);

  int t;
  cin >> t;
  while (t--) {
    int n;
    cin >> n;
    vector<int> a(n);
    for (int i = 0; i < n; i++) {
      cin >> a[i];
    }
    bitset<3600> res, cur;
    for (int i = 0; i < n; i++) {
      int x = a[i] % 3600;
      cur.reset(), cur.set(x);
      cur |= (res << x) | (res >> (3600 - x));
      res |= cur;
      if (res.test(0)) {
        break;
      }
    }
    cout << (res.test(0) ? "YES\n" : "NO\n");
  }
}

C - 完全平方数

Solution

直接预处理出所有小于的完全平方数(约个)，在查询时直接二分查询即可，复杂度

Code

#include <bits/stdc++.h>
using namespace std;

using ll = long long;

int main() {
  cin.sync_with_stdio(false), cin.tie(nullptr);

  vector<int> v;
  for (int i = 0; i <= 1000000000 / i; i++) {
    v.push_back(i * i);
  }
  int t;
  cin >> t;
  while (t--) {
    int l, r;
    cin >> l >> r;
    cout << upper_bound(v.begin(), v.end(), r) - lower_bound(v.begin(), v.end(), l) << "\n";
  }
}

D - 小H和游戏

Solution

设为“结点被轰炸的次数”、“结点的子结点被轰炸的次数”、“结点的子结点的子结点被轰炸的次数”；
设为结点的父结点。

考虑结点在什么时候会被炸到：

1. 结点本身被轰炸，次数。
2. 结点的子结点被轰炸，次数。
3. 结点的子结点的子结点被轰炸，次数。
4. 结点的父结点被轰炸，次数。
5. 结点的父结点除外的子结点被轰炸，次数。
6. 结点的父结点的父结点被轰炸，次数。

基于此，我们只要维护好，即可回答询问。

因为只需要在结点被轰炸时，令、、分别，所以更新过程也是的。

总复杂度。

Code

#include <bits/stdc++.h>
using namespace std;

using ll = long long;

struct edge {
  int v, next;
} G[750005 << 1];
int n, q, tot, h[750005], sum[750005][3];
int anc[750005];

void init() {
  memset(h, -1, sizeof h);
}

void addedge(int u, int v) {
  G[tot] = { v, h[u] }, h[u] = tot++;
  G[tot] = { u, h[v] }, h[v] = tot++;
}

void dfs(int u, int f) {
  anc[u] = f;
  for (int i = h[u]; ~i; i = G[i].next) {
    if (G[i].v != f) {
      dfs(G[i].v, u);
    }
  }
}

int main() {
  cin.sync_with_stdio(false), cin.tie(nullptr);

  init();
  cin >> n >> q;
  for (int i = 1; i < n; i++) {
    int x, y;
    cin >> x >> y;
    addedge(x, y);
  }
  dfs(1, 0);
  while (q--) {
    int x;
    cin >> x;
    sum[x][0]++, sum[anc[x]][1]++, sum[anc[anc[x]]][2]++;
    int res = sum[x][0] + sum[x][1] + sum[x][2];
    if (anc[x]) {
      res += sum[anc[x]][0] + sum[anc[x]][1] - sum[x][0];
    }
    if (anc[anc[x]]) {
      res += sum[anc[anc[x]]][0];
    }
    cout << res << "\n";
  }
}

E - 水题(water)

Solution

打表发现，实际上就是斐波那契数列的第项，故而直接判断是否是斐波那契数列的一项即可。

若不是斐波那契数列的一项，打表输出皇后的方案数即可。

否则：
假设(均为质数)；

那么，在进制下末尾的的个数即为，其中为~中作为质因子出现的次数之和。

先对分解质因子，然后按公式求解即可。

Code

#include <bits/stdc++.h>
using namespace std;

using ll = long long;

const ll inf = 1e18;

int main() {
  cin.sync_with_stdio(false), cin.tie(nullptr);

  ll x, m;
  cin >> x >> m;

  ll f[205] = { 0 };
  f[1] = f[2] = 1;
  for (int n = 3; n <= 87; n++) {
    f[n] = f[n - 1] + f[n - 2];
  }
  set<ll> S(f + 1, f + 1 + 87);
  if (S.find(x) == S.end()) {
    int z = x % min(13ll, m) + 1;
    const int ans[] = { 1, 1, 0, 0, 2, 10, 4, 40, 92, 352, 724, 2680, 14200, 73712 };
    cout << ans[z] << "\n";
    return 0;
  }

  vector<pair<int, int>> factor;
  for (int i = 2; i * i <= m; i++) {
    if (m % i == 0) {
      int cnt = 0;
      while (m % i == 0) {
        ++cnt, m /= i;
      }
      factor.push_back({ i, cnt });
    }
  }
  if (m > 1) {
    factor.push_back({ m, 1 });
  }

  ll res = 0;
  for (int i = 0; i < (int) factor.size(); i++) {
    int p = factor[i].first, e = factor[i].second;
    ll cnt = 0;
    for (ll cur = p; cur <= x; cur *= p) {
      cnt += x / cur;
      if (cur > x / p) {
        break;
      }
    }
    if (i == 0) {
      res = cnt / e;
    } else {
      res = min(res, cnt / e);
    }
  }
  cout << res << "\n";
}