A~F 个人题解

A

#include <iostream>
using namespace std;

int main() {
  int n;
  cin>>n;
  cout<<(n == 1 ? "NO" : "YES")<<'\n';
  
  return 0;
}

B

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

int a[200005];

int main() {
  int t;
  cin>>t;
  while (t--) {
    int n;
    cin>>n;
    long long s = 0;
    for (int i=1; i<=n; i++)
      cin>>a[i], s += a[i];
    sort(a+1, a+1+n);
    cout<<s*2-a[1]-a[2]<<'\n';
  }
  
  return 0;
}

C

必存在一个长度为2的区间其结果最大
因为数字越多 max不会变但mex要么不变要么变小
所以只要枚举所有相邻两个数求max和mex即可

#include <iostream>
using namespace std;

int a[300005];

int mex(int a, int b) {
  int ans = 0;
  if (a == 0 || b == 0) {
    ans++;
    if (a == 1 || b == 1)
      ans++;
  }
  return ans;
}

int main() {
  int t;
  cin>>t;
  while (t--) {
    int n, x, pre, mx = -1e9;
    cin>>n>>pre;
    for (int i=1; i<=n-1; i++)
      cin>>x, mx = max(mx, max(x, pre) - mex(x, pre)), pre = x;
    cout<<mx<<'\n';
  }
  
  return 0;
}

D

赛后才知道可以贪心
要么删第一个要么删最后一个
否则如果删的是中间的把这个数换为第一个或最后一个结果一定更小所以删其他的数一定不会更优
所求可看成“离差和” 类比方差数据越集中离差和越小

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

int a[200005];

int main() {
  int t;
  cin>>t;
  while (t--) {
    int n;
    cin>>n;
    for (int i=1; i<=n; i++)
      cin>>a[i];
    sort(a+1, a+1+n);
    long long ans1 = 0, ans2 = 0;
    for (int i=1; i<=n-1; i++)
      ans1 += abs(a[i]-a[n/2]);
    for (int i=2; i<=n; i++)
      ans2 += abs(a[i]-a[n/2+1]);
    cout<<min(ans1, ans2)<<'\n';
  }
  
  return 0;
}

E

dp
记录后缀数字和为0~9中的某个数的子数组个数
可以先预处理出任意两个个位数的和的数位和
可以用滚动数组优化

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

int main() {
  int g[10][10] = {0};
  for (int i=0; i<10; i++)
    for (int j=0; j<10; j++)
      for (auto &ch: to_string(i+j))
        g[i][j] += ch-'0';
  int t;
  cin>>t;
  while (t--) {
    string s;
    cin>>s;
    int n = s.size(), dp[2][10] = {0};
    long long ans = 0;
    for (int i=1; i<=n; i++) {
      memset(dp[i&1], 0, sizeof dp[i&1]);
      dp[i&1][s[i-1]-'0']++;
      ans += s[i-1]-'0';
      for (int j=0; j<10; j++)
        dp[i&1][g[j][s[i-1]-'0']] += dp[(i-1)&1][j], ans += dp[(i-1)&1][j]*g[j][s[i-1]-'0'];
    }
    cout<<ans<<'\n';
  }
  
  return 0;
}

F

一定存在一种划分划分的块数小于等于2 其结果最大

因为，如果划分的块数大于等于3，每3个连续的块可继续合并为1块。可以断言原先3个块的与运算结果一定小于或等于异或运算合并后的结果。因为：

当与运算结果的二进制的某一位为1时，要求原先的3个块的该位都为1，此时异或运算和它是等价的
当只有1个块的某位为1时，异或运算结果的该位仍然为1，而与运算结果的该位为0，此时异或运算结果大于与运算结果

故对于3个及以上的块，使用异或运算合并它们，一定不会更亏。

#include <iostream>
using namespace std;

int a[300005];

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

题解 | 牛客周赛 Round 110 - A~F 个人题解

A

B

C

D

E

F