牛客小白月赛31 部分题解

比赛的时候只看了几道题(ABDEGHI)，写一下自己有思考过的题吧。
2021_1_13 补了F题
2021_1_14 补了C题

A. A｜B

Solution

一眼经典数位dp, (但是两年没写过了,忘记怎么写了
复习了一下做出如下总结：
首先数位dp需要我们找到一个通用的状态，使得我们在搜索的时候能够记忆化，有效减少复杂度
其次需要特别处理 $limit$ 状态，因为 $limit$ 限制下后面的搜索不一定都符合条件
这道题我们不妨令 $dp[i]$ 为遍历到第 $i$ 位时, 符合条件的数字方案
根据题目的限定，需要

$1 <= b <= a$
$a | b = a + b$

得到 $a \&b = 0$
所以二进制位上一定满足

$a = 1, b = 0$
$a = 0, b = 1$
$a = 0, b = 0$

注意到根据这种搜索最终得到的答案里包含了0，是不符合条件的，所以最终答案-1。

Code

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 5e5 + 5;
ll dp[50];
int a[50], b[50];
ll dfs(int pos, bool limit) {
    if(pos == -1) return 1;
    if(!limit && dp[pos] != -1) {
        return dp[pos];
    }
    int up = limit ? a[pos] : 1;
    ll ans = 0;
    for(int i = 0; i <= up; i++) {
        if(b[pos] && i) continue;
        ans += dfs(pos - 1, limit && i == up);
    }
    if(!limit) dp[pos] = ans;
    return ans;
}
ll solve(ll x, ll y) {
    int pos = 0;
    while(y) {
        a[pos++] = y % 2;
        y /= 2;
    }
    for(int i = 0; i < 32; i++) {
        if((x >> i) & 1) {
            b[i] = 1;
        } else {
            b[i] = 0;
        }
    }
    return dfs(pos - 1, true);
}
int main() {
    ios::sync_with_stdio(false), cin.tie(nullptr);
    int T; cin >> T;
    while(T--) {
        memset(dp, -1, sizeof(dp));
        int x, y; cin >> x >> y;
        cout << solve(x, y) - 1 << '\n';
    }
    return 0;
}

B. A + B

Solution

模拟题，一开始不太想做这种码农题，最后半小时下定决心开始做，然后赛后3分钟过了
按照题意模拟即可，只需要掌握 $map$
我这里加了个栈记录操作数

#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
const int N = 1e6 + 5;
const int mod = 1e9 + 7;
map<int, string> mp;
map<string, int> rev;
void init() {
  mp[0] = 
    "###\n#.#\n#.#\n#.#\n###\n";
  mp[1] = 
    "..#\n..#\n..#\n..#\n..#\n";
  mp[2] = 
    "###\n..#\n###\n#..\n###\n";
  mp[3] = 
    "###\n..#\n###\n..#\n###\n";
  mp[4] = 
    "#.#\n#.#\n###\n..#\n..#\n";
  mp[5] =
    "###\n#..\n###\n..#\n###\n";
  mp[6] = 
    "###\n#..\n###\n#.#\n###\n";
  mp[7] = 
    "###\n#.#\n#.#\n..#\n..#\n";
  mp[8] = 
    "###\n#.#\n###\n#.#\n###\n";
  mp[9] = 
    "###\n#.#\n###\n..#\n###\n";
  mp[10] =
    "...\n.#.\n###\n.#.\n...\n"; 
  for(int i = 0; i <= 10; i++) {
    rev[mp[i]] = i;
  }
  for(int i = 0; i <= 10; i++) {

  }
}
void output(vector<ll> &v) {
  string tmp[10];
  int p = 0;
  for(int i = 0; i < v.size(); i++) {
    string now = mp[v[i]];
    //cout << now << ' ' << now.size() << '\n';
    p = 0;
    for(int j = 0; j < now.size(); j += 4, ++p) {
      tmp[p] += now[j];
      tmp[p] += now[j + 1];
      tmp[p] += now[j + 2];
      if(i != v.size() - 1) {
        tmp[p] += '.';
      }
    }
  }
  for(int i = 0; i < 5; i++) {
    cout << tmp[i] << '\n';
  }
}
int main() {
  ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
  init();
  int T; cin >> T;
  while(T--) {
    string tmp[10];
    for(int i = 0; i < 5; i++) {
      cin >> tmp[i];
    }
    int len = tmp[0].size();
    ll ans = 0;
    stack<ll> st;
    ll op = 0;
    for(int i = 0; i < len; i += 4) {
      string now;
      for(int j = 0; j < 5; j++) {
        for(int k = i; k < i + 3; k++) {
          now += tmp[j][k];
        }
        now += '\n';
      }
      if(rev[now] <= 9) {
        op = op * 10 + rev[now];
        //cout << "num:" << op << ' ' << rev[now] << '\n';
        now.clear();
      } else if(rev[now] == 10) {
        st.push(op);
        //cout << "push:" << op << '\n';
        op = 0;
        now.clear();
      }
    }
    st.push(op);
    while(st.size() >= 2) {
      auto L = st.top(); st.pop();
      auto R = st.top(); st.pop();
      //cout << L << ' ' << R << '\n';
      st.push(L + R);
    }
    ll cur = st.top();
    vector<ll> v;
    if(cur == 0) {
      v.emplace_back(0);
    } else {
      while(cur) {
        v.emplace_back(cur % 10);
        cur /= 10;
      }
      reverse(v.begin(), v.end());
    }
    output(v);
    if(T)
      cout << '\n';
  }
  return 0;
}

C. 图像存储

Solution

联通分量+判重，关于平移可以每一个都减去坐上角的点，用 $map$ 判断是否出现过

Code

#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
const int N = 1e5 + 5;
const int mod = 1e9 + 7;
int maze[1005][1005];
bool vis[1005][1005];
int dist[4][2] = {0, 1, 0, -1, 1, 0, -1, 0};
vector<pair<int, int> > v;
void dfs(int &n, int &m, int &x, int &y) {
    vis[x][y] = true;
    v.emplace_back(x, y);
    for(int i = 0; i < 4; i++) {
        int xx = x + dist[i][0];
        int yy = y + dist[i][1];
        if(xx >= 1 && xx <= n && yy >= 1 && yy <= m && maze[xx][yy] == 1 && !vis[xx][yy]) {
            dfs(n, m, xx, yy);
        }
    }
}
void init(int n, int m) {
    for(int i = 1; i <= n; i++) {
        for(int j = 1; j <= m; j++) {
            vis[i][j] = 0;
        }
    }
}
int main() {
  ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
  int n, m; 
    while(cin >> n >> m, n && m) {
        init(n, m);
        for(int i = 1; i <= n; i++) {
            for(int j = 1; j <= m; j++) {
                char c; cin >> c;
                maze[i][j] = c - '0';
            }
        }
        int res = 0, ans = 0;
        map<vector<pair<int, int> >, int> mp;
        for(int i = 1; i <= n; i++) {
            for(int j = 1; j <= m; j++) {
                //cout << maze[i][j] << " \n"[j == m];
                if(!vis[i][j] && maze[i][j]) {
                    v.clear();
                    res++;
                    dfs(n, m, i, j);
                    for(auto &x : v) {
                        x.first -= i, x.second -= j;
                    }
                    if(!mp.count(v)) {
                        ans++;
                        mp[v] = 1;
                    }
                }
            }
        }
        cout << res << ' ' << ans << '\n';
    }
  return 0;
}

D. 坐标计数

Solution

这题我第一反应就是先看看

    for i in range(10):
        for j in range(10):
            输出满足题意的二元组

发现答案就是矩形上的所有点，所以只需要输出矩形的面积

Code

#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
const int N = 1e6 + 5;
const int mod = 1e9 + 7;


int main() {
  ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
  int T; cin >> T;

  while(T--) {
    ll px1, px2, py1, py2;
    cin >> px1 >> py1 >> px2 >> py2;
    cout << abs(py2 - py1 + 1) * abs(px2 - px1 + 1) << '\n';
  }
  return 0;
}

E. 解方程

Solution

解方程 $ax + by = xy$
这个长得很像十字相乘法的形式, 添加一个 $ab$
则有 $ax + by + ab = xy + ab$
那么 $ab = xy - ax - by + ab$
于是 $ab = (x - b)(y - a)$
那么合法的方案数就是 $ab$ 的因子数
注意到 $ab \leq 10^{12}, T \leq 1000$
需要先筛出 $[1, 10^6]$ 的素数, 用因数个数定理 $num = (p_1 + 1)*(p_2 + 1)...(p_n + 1)$ 进行求解
时间复杂度 $O(T\frac{10^6}{log10^6})$

Code

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e6 + 5;
int prime[N], vis[N], tot;
void init() {
    for(int i = 2; i <= 1e6; i++) {
        if(!vis[i]) {
            prime[++tot] = i;
        }
        for(int j = 2 * i; j < 1e6; j += i) {
            vis[j] = 1;
        }
    }
}
int main() {
    ios::sync_with_stdio(false), cin.tie(nullptr);
    int T; cin >> T;
    init();
    while(T--) {
        ll a, b; cin >> a >> b;
        ll prod = a * b;
        ll ans = 1;
        for(int i = 1; i <= tot; i++) {
            ll cnt = 1;
            if(prod % prime[i] == 0) {
                while(prod % prime[i] == 0) prod /= prime[i], ++cnt;
            }
            ans *= cnt;
        }
        cout << ans << '\n';
    }    
    return 0;
}

F 消减整数

Solution

设每次减后剩余的部分为 $m$ , 此时减到了 $k$ , 那么显然 $k +1 > m$ , 否则可以继续减
可以设想每次都会多出 $m$ , 于是剩余的部分会变成 $m, 2m,\dots am$
当 $am == b(k + 1)$ 时，可以完成相减, 其中 $b$ 是有效的减去 $(k + 1)$ 的次数
这里的 $am$ 和 $b(k + 1)$ 其实就是 $lcm(m, k + 1)$
那么答案就是 $lcm / m$

#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
const int N = 1e6 + 5;
const int mod = 1e9 + 7;
ll cal(ll x) {
    return x * (x + 1) / 2;
}
int main() {
  ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
  int T; cin >> T;
    while(T--) {
        int n; cin >> n;
        int now = n, res = 0;
        int left = 1, right = n, ans = -1;
        while(left <= right) {
            int mid = left + right >> 1;
            if(cal(mid) <= now) {
                ans = mid;
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        if(cal(ans) == n) {
            cout << 1 << '\n'; continue;
        }
        int last = ans + 1;
        int m = n - cal(ans);
        cout << 1LL * last * m / __gcd(last, m) / m << '\n';
    }
  return 0;
}

G 简单题的逆袭

Solution

对于式子 $x^k \leq y$ , 两边取 $ln$
得到 $k \leq \frac{lny}{lnx}$
分析这个式子, 当 $x = 0, y = 0, x = 1$ 的时候无解
其他时候是有解的，直接进行对数运算会有精度误差
可以试想有解的前提 $k < 64$
因为 $10^{18} < 2^{64}$
直接试除, 看能除多少次即可。

Code

import math
T = int(input())
for it in range(T):
  x, y = map(int, input().split())
  if x == 0 or y == 0 or x == 1:
    print(-1)
  elif y == 1 and x != 1:
    print(0)
  else:
    ans = 0
    while(y // x > 0):
      y //= x
      ans += 1

      #print(x, y)
    print(ans)

H. 对称之美

Solution

容易想到要行程字符串只需要对应位的字符串中含有一个相同的字母
即 $s_1$ 和 $s_n$ , $s_2$ 和 $s_{n - 1} \dots$ 含有一个相同字母, 检验一下即可。

Code

#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
typedef long long LL;
const int N = 1e6 + 5;
const int mod = 1e9 + 7;

string a[N];
int main() {
  ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
  int T; cin >> T;
  while(T--) {
    int n; cin >> n;
    for(int i = 1; i <= n; i++) {
      cin >> a[i];
    }
    bool flag = true;
    for(int l = 1, r = n; l < r; l++, r--) {
      int f = 0;
      for(int j = 0; j < 26; j++) {
        int cnt = 0;
        for(int i = 0; i < a[l].size(); i++) {
          if(a[l][i] == char('a' + j)) {
            cnt++; break;
          }
        }
        for(int i = 0; i < a[r].size(); i++) {
          if(a[r][i] == char('a' + j)) {
            cnt++; break;
          }
        }
        if(cnt == 2) {
          f = 1; break;
        }
      }
      if(!f) {
        flag = false; break;
      }
    }
    if(!flag) {
      cout << "No\n";
    } else {
      cout << "Yes\n";
    }
  }
  return 0;
}

I. 非对称之美

Solution

检查原串是不是只含有一种字母，如果是，输出0
否则检查原串是否为非回文串，如果是，输出 $n$
剩下的情况，可以猜到答案只能是 $n - 1$
这里我写了一个暴力，找长度为 $[n - 10, n]$ 的子串是否满足题意

Code

#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
typedef long long LL;
const int N = 1e6 + 5;
const int mod = 1e9 + 7;

int a[N];
bool cal(string s) {
  string t = s;
  reverse(t.begin(), t.end());
  return s == t;
}
int main() {
  ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
  string s; cin >> s;
  auto t = s;
  reverse(t.begin(), t.end());
  if(t != s) {
    cout << s.size() << '\n';
  } else {
    set<char> st;
    for(auto &x : s) {
      st.insert(x);
    }
    if(st.size() == 1) {
      cout << 0 << '\n';
      return 0;
    }
    for(int i = 0; i <= min(10, int(s.size())); i++) {
      int len = s.size() - i;
      for(int j = 0; j < s.size() - len + 1; j++) {
        auto now = s.substr(j, len);
        if(!cal(now)) {
          cout << len << '\n';
          return 0;
        }
      }
    }
    cout << 0 << '\n';
  }
  return 0;
}