A. 相反数

Solution

签到题, 完全可以加大力度变成大数加法, 这里我直接贴了自己的大数加法模板

Code

#pragma GCC optimize(3)
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long long LL;
const ll mod = 998244353;
const int DEG = 20;
const double PI = acos(-1.0);
const double eps = 1e-10;
const ll inf = 1e18;
const int N = 1e6 + 5;
static auto faster_iostream = []() {
    std::ios::sync_with_stdio(false);  // turn off sync
    std::cin.tie(nullptr);             // untie in/out streams
    return 0;
}();
string add(string a, string b){
    string c;
    if(a.size() > b.size()) swap(a, b);
    int len = min(a.size(), b.size());
    int f = 0;
    for(int i = len - 1, j = b.size() - 1; i >= 0; i--, j--){
        c += ((a[i] - '0' + b[j] - '0' + f) % 10) + '0';
        f = (a[i] - '0' + b[j] - '0' + f) / 10;
    }
    for(int j = b.size() - a.size() - 1; j >= 0; j--){
        c += ((b[j] - '0' + f) % 10) + '0';
        f = (b[j] - '0' + f) / 10;
    }
    if(f){
        c += '1';
    }
    reverse(c.begin(), c.end());
    return c;
}
int main(){
  string s;
  cin >> s;
  string t = s;
  reverse(t.begin(), t.end());
  cout << add(t, s) << "\n";
  return 0;
}

B. Music Problem

Solution

提供一个假的做法, 数据强一点可能只能bitset
题意简化一下就是让我们在数组中找出一组子序列的和为3600的倍数
然后这是一道原题的缩减版原题地址https://ac.nowcoder.com/acm/contest/91/L?&headNav=www
考虑动态规划: $dp[i]$ 表示和在模3600意义下的子序列的个数
我们用一个数组 $temp[i]$ 记录目前为止和在模3600意义下为i的子序列的个数
有 $\begin{cases} dp[j] = dp[j] + 1, j == 0 &\\ dp[(j + a[i]) \% 3600] = dp[(j + a[i]) \% 3600] + 1, temp[j] > 0 \end{cases}$
时间复杂度 $O(7200 * \sum n)$ , 直接搞会超时, 当dp[0] > 0 的时候直接跳出剪枝就行了

Code

#pragma GCC optimize(3)
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long long LL;
const ll mod = 998244353;
const int DEG = 20;
const double PI = acos(-1.0);
const double eps = 1e-10;
const ll inf = 1e18;
const int N = 1e6 + 5;
static auto faster_iostream = []() {
    std::ios::sync_with_stdio(false);  // turn off sync
    std::cin.tie(nullptr);             // untie in/out streams
    return 0;
}();
int a[N];
int dp[4000], temp[4000];
int main(){
  int t;
  cin >> t;
  while(t--){
    int n;
    cin >> n;
    ll sum = 0;
    int flag = 0;
    memset(dp, 0, sizeof(dp));
    memset(temp, 0, sizeof(temp));
    for(int i = 1; i <= n; i++) cin >> a[i];
    for(int i = 1; i <= n; i++){
      if(dp[0] > 0) break;
      for(int j = 0; j < 3600; j++){
        if(j == 0 || temp[j] != 0){
          dp[(j + a[i]) % 3600] = temp[j] + 1;
        }
        if(dp[0] > 0) break;
      }
      for(int j = 0; j < 3600; j++){
        temp[j] = max(temp[j], dp[j]);
      }
    }
    if(dp[0] > 0){
      cout << "YES\n";
    }
    else cout << "NO\n";
  }
  return 0;
}

C. 完全平方数

Solution

签到题, 先打个表, 然后lower_bound() 查找一下下标
注意0也是完全平方数!

Code

#pragma GCC optimize(3)
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long long LL;
const ll mod = 998244353;
const int DEG = 20;
const double PI = acos(-1.0);
const double eps = 1e-10;
const ll inf = 1e18;
const int N = 1e6 + 5;
static auto faster_iostream = []() {
    std::ios::sync_with_stdio(false);  // turn off sync
    std::cin.tie(nullptr);             // untie in/out streams
    return 0;
}();
ll dp[N];
ll solve(ll x){
  int pos = lower_bound(dp + 1, dp + 1 + 100000, x) - dp;
  if(dp[pos] == x) return pos;
  else return pos - 1;
}
int main(){
  int q;
  cin >> q;
  for(ll i = 0; i <= 1e5; i++){
    dp[i + 1] = i * i;
  }
  while(q--){
    ll l, r;
    cin >> l >> r;
    if(l >= 1)
      cout << solve(r) - solve(l - 1) << "\n";
    else cout << solve(r) << "\n";
  }
  return 0;
}

D. 小H和游戏

Solution

因为只需要查询城市距离为2的节点,
对于城市u, 我们考虑用一个fa数组找到城市的祖先fa[u], 它的祖先的祖先就是fa[fa[u]]
因为只需要考虑距离为2以内的节点, 那么只需考虑上述三个节点
开一个cnt[N][3]的数组,
cnt[i][0] 表示 i 点本身的影响
cnt[i][1] 表示 i 点儿子的影响
cnt[i][2] 表示 i 点儿子的儿子的影响
每次查询我们都直接更新cnt数组即可

Code

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long long LL;
const ll mod = 998244353;
const int DEG = 20;
const double PI = acos(-1.0);
const double eps = 1e-10;
const ll inf = 1e18;
const int N = 1e6 + 5;
static auto faster_iostream = []() {
    std::ios::sync_with_stdio(false);  // turn off sync
    std::cin.tie(nullptr);             // untie in/out streams
    return 0;
}();
int tot, head[N];
struct Edge{
  int v, nextz;
}edge[N << 1];
void addedge(int u, int v){
  edge[tot].v = v;
  edge[tot].nextz = head[u];
  head[u] = tot++;
}
void init(){
  tot = 0;
  memset(head, -1, sizeof(head));
}
int fa[N];
void dfs(int u, int par){
  fa[u] = par;
  for(int i = head[u]; ~i; i = edge[i].nextz){
    int v = edge[i].v;
    if(v == par) continue;
    dfs(v, u);
  }
}
int cnt[N][3];
int main(){
  init();
  int n, m;
  cin >> n >> m;
  for(int i = 1; i <= n - 1; i++){
    int u, v;
    cin >> u >> v;
    addedge(u, v);
    addedge(v, u);
  }
  dfs(1, 0);
  while(m--){
    int u;
    cin >> u;
    cnt[u][1]++, cnt[u][2]++;
    cnt[fa[u]][0]++, cnt[fa[u]][1]++;
    cnt[fa[fa[u]]][0]++;
    cout << cnt[u][0] + cnt[fa[u]][1] + cnt[fa[fa[u]]][2] << "\n";
  }
  return 0;
}

E. 水题(water)

Solution

真·套娃题, 打个表我们发现f(i)其实就是个斐波那契数列, 然后我们只需要先判断x是不是斐波那契数

如果是的话, 对 m 做质因数分解统计贡献即可
对于求阶乘的尾0这类题
举个例子求 13! 中 10进制下尾部0的个数
那么因为 13! = 1 * 2 * ...... * 13;
考虑 10 的质因子 2 和 5
其中拥有质因子2的数字包括 2, 4, 6, 8, 10, 12
我们怎么求贡献呢?
我们发现 13 / 2 = 6 就是上面 6个数字的第一层贡献
6 / 2 = 3 就是第二层贡献(有的因子有两个2
3 / 2 = 1 就是第三层贡献
然后就没了, 总的贡献是 3 + 6 + 1 = 10
再考虑质因子5的数字包括 5, 10
总的贡献是 13 / 5 = 2
两者取min, 得到13! 在10进制下有2个尾0
把这个结论推广到m进制就是求m的质因子再统计最小的贡献即可
不是的话就是个n皇后问题，模板贴一贴就好啦

Code

#pragma GCC optimize(3)
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long long LL;
const ll mod = 1e9 + 7;
const int DEG = 20;
const double PI = acos(-1.0);
const double eps = 1e-10;
const ll inf = 1e18;
const int N = 2e5 + 5;
static auto faster_iostream = []() {
    std::ios::sync_with_stdio(false);  // turn off sync
    std::cin.tie(nullptr);             // untie in/out streams
    return 0;
}();
// 1 ^ 2 + 1 ^ 2 = 1 * 2
// 1 ^ 2 + 1 ^ 2 + 2 ^ 2 = 2 * 3
// 1 ^ 2 + 1 ^ 2 + 2 ^ 2 + 3 ^ 2 =  3 * 5
int a[20], q;
int ans = 0;
void dfs(int k){
  if(k == q + 1) {
    ans++; return ;
  }
  int flag = 0;
  for(int i = 1; i <= q; i++){
    a[k] = i; // 第k个皇后在i行
    flag = 1;
    for(int j = 1; j < k; j++){
      if(a[j] == i || i - k == a[j] - j || i + k == a[j] + j){
        flag = 0;
        break;
      }
    }
    if(flag){
      dfs(k + 1);
    }
  }
}
ll F[100];
int main(){
  ll x, m;
  cin >> x >> m;
  F[1] = F[2] = 1;
  for(int i = 3; i <= 90; i++){
    F[i] = F[i - 1] + F[i - 2];
    //cout << F[i] << "\n";
  }
  int pos = -1;
  for(int i = 3; i <= 90; i++){
    if(F[i] == x){
      pos = i;
      break;
    }
  }
  if(pos == -1){
    q = x % min(13LL, m) + 1;
    dfs(1);  // n 皇后
    cout << ans << "\n";
  }
  else {
    vector<pair<int, int> > fac;
    for(int i = 2; i * i <= m; i++){
      if(m % i == 0){
        int cnt = 0;
        while(m % i == 0) m /= i, ++cnt;
        fac.push_back({i, cnt});
      }
    }
    ll ans = 4e18;
    if(m > 1) fac.push_back({m, 1});
    for(int i = 0; i < fac.size(); i++){
      ll cur = x;
      ll res = 0;
      while(cur) res += cur / fac[i].first, cur /= fac[i].first;
      ans = min(ans, res / fac[i].second);
    }
    cout << ans << "\n";
  }
  return 0;
}

牛客算法周周练2 题解

A. 相反数

Solution

Code

B. Music Problem

Solution

Code

C. 完全平方数

Solution

Code

D. 小H和游戏

Solution

Code

E. 水题(water)

Solution

Code