补完题 发一下个人题解

A

模拟

#include <iostream>
using namespace std;

int main() {
  string s, t = "while";
  cin>>s;
  int cnt = 0;
  for (int i=0; i<5; i++)
    if (s[i] != t[i])
      cnt++;
  cout<<cnt<<'\n';
  
  return 0;
}

B

前缀和

#include <iostream>
using namespace std;

long long a[100005], s[100005];

int main() {
  int n;
  cin>>n;
  for (int i=1; i<=n; i++)
    cin>>a[i], s[i] = s[i-1] + a[i];
  long long mx = 0;
  for (int i=1; i<=n; i++)
    mx = max(mx, s[i]-s[max(i-10, 0)]);
  cout<<mx<<'\n';
  
  return 0;
}

C

前缀最大值

#include <iostream>
using namespace std;

int a[200005], mx[200005];

int main() {
  int t;
  cin>>t;
  while (t--) {
    int n;
    cin>>n;
    for (int i=1; i<=n; i++)
      cin>>a[i], mx[i] = max(mx[i-1], a[i]);
    int ans = 0;
    for (int i=n; i>=1; i--)
      if (mx[i-1] > a[i])
        ans = max(ans, mx[i-1]+a[i]);
    cout<<ans<<'\n';
  }
  
  return 0;
}

D

求连续自然数的段数吧 注意长度为1每个都看作单独的段

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
  int t;
  cin>>t;
  while (t--) {
    int n,x;
    cin>>n;
    vector<int> vec;
    for (int i=1; i<=n; i++)
      cin>>x, vec.push_back(x);
    sort(vec.begin(), vec.end());
    int cnt = 0, l = 0, r = -1, t = 0;
    for (auto &x: vec) {
      if (x > r+1) {
        cnt += l == r ? t : 1;
        l = x;
        t = 0;
      }
      r = x;
      t++;
    }
    cnt += l == r ? t : 1;
    cout<<cnt-2<<'\n';
  }
  
  return 0;
}

E

题意是仅选择两行 或两列 或一行一列
其中两行可以重复 这时候就相当于什么也不做
我们只要关注所有行的1的个数的种类 和所有列的1的个数的种类
然后讨论这四种情况最后形成的图案

• 什么也不做: 个数为0的行数为n
• 选择两行: 个数为0的行数为n-2, 个数为m的行数为2
• 选择两列: 个数为0的列数为m-2, 个数为n的行数为2
• 选择一行一列: 个数为1的行数为n-1, 个数为m-1的行数为1, 个数为1的列数为m-1, 个数为n-1的列数为1

#include <iostream>
#include <cstring>
#include <unordered_map>
using namespace std;

int ax[1005], ay[1005];

int main() {
  int t;
  cin>>t;
  while (t--) {
    int n,m;
    cin>>n>>m;
    char ch;
    memset(ax, 0, sizeof(int)*(n+1));
    memset(ay, 0, sizeof(int)*(m+1));
    for (int i=1; i<=n; i++)
      for (int j=1; j<=m; j++)
        cin>>ch, ax[i] += ch == '1', ay[j] += ch == '1';
    unordered_map<int, int> mpx, mpy;
    for (int i=1; i<=n; i++)
      mpx[ax[i]]++;
    for (int i=1; i<=m; i++)
      mpy[ay[i]]++;
    if (mpx[0] == n
        || mpx[0] == n-2 && mpx[m] == 2
        || mpy[0] == m-2 && mpy[n] == 2
        || mpx[1] == n-1 && mpx[m-1] == 1 && mpy[1] == m-1 && mpy[n-1] == 1)
      cout<<"YES"<<'\n';
    else
      cout<<"NO"<<'\n';
  }
  
  return 0;
}

F

根据唯一分解定理

其因子个数为

依据是乘法原理 从每种质因子pi中选出0~ki个该因子

由于只有2既是偶数又是质数 而只有奇数*奇数=奇数
假设p1是质因数2 则其奇因子个数实际上就是

那么思路就是预处理出1~1e6的每个数的阶乘的因子个数和奇因子个数
求法是利用递推 对当前的数n质因数分解 对于它的每个因数pi 在n-1的结果上除掉之前的贡献 再乘上新的贡献

时间稍微有点紧

#include <iostream>
#include <vector>
#include <unordered_map>
using namespace std;
const int M = 998244353;

long long a[1000005], b[1000005];

long long pow(long long a, int k) {
  return k?pow(a*a%M,k/2)*(k%2?a:1)%M:1;
}

void get_factor(int n, vector<pair<int, int>> &vec) {
  for (int i=2; i*i<=n; i++) {
    if (n%i == 0) {
      int cnt = 0;
      while (n%i == 0)
        n /= i, cnt++;
      vec.push_back({i, cnt});
    }
  }
  if (n != 1)
    vec.push_back({n, 1});
}

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  unordered_map<int, int> mp;
  a[1] = 1; b[1] = 1;
  for (int n=2; n<=1000000; n++) {
    vector<pair<int, int>> vec;
    get_factor(n, vec);
    a[n] = a[n-1]; b[n] = b[n-1];
    for (auto &[p, k]: vec) {
      if (mp.find(p) == mp.end())
        mp[p] = 1;
      int t = pow(mp[p], M-2)*(mp[p]+k)%M;
      if (p != 2)
        a[n] *= t, a[n] %= M;
      b[n] *= t, b[n] %= M;
      mp[p] += k;
    }
  }
  int t,n;
  cin>>t;
  while (t--)
    cin>>n, cout<<a[n]*pow(b[n], M-2)%M<<' ';
  
  return 0;
}