A~F 个人题解

A

#include <iostream>
using namespace std;

int main() {
  int n,k;
  cin>>n>>k;
  if (k <= (n+9)/10)
    cout<<"Gold Medal"<<'\n';
  else if (k <= (n+9)/10*3)
    cout<<"Silver Medal"<<'\n';
  else if (k <= (n+9)/10*6)
    cout<<"Bronze Medal"<<'\n';
  else
    cout<<"Da Tie"<<'\n';
  
  return 0;
}

B

要么直接取最大的牌 要么弃掉所有牌获得点数为n的牌

#include <iostream>
using namespace std;

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

C

要么1次 要么2次 因为总可以一次涂所有的0 一次涂所有的1
则当且仅当字符串本身就是回文串时涂1次 否则2次

#include <iostream>
using namespace std;

int main() {
  int t;
  cin>>t;
  while (t--) {
    string s;
    cin>>s;
    string t(s.rbegin(), s.rend());
    cout<<(t == s ? 1 : 2)<<'\n';
  }
  
  return 0;
}

D

即 从2n个数中取n个数 使得这n个数的按位与最大
对于从高到低的每个位 统计有多少个数在该位上为1 且在之前的计入ans的高位上也都为1
如果这样的数的个数不少于n个 则该位取1 否则取0

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

long long a[400005];

int main() {
  int t;
  cin>>t;
  while (t--) {
    int n;
    cin>>n;
    for (int i=1; i<=n*2; i++)
      cin>>a[i];
    bitset<34> bs;
    for (int j=33; j>=0; j--) {
      int cnt = 0;
      for (int i=1; i<=n*2; i++)
        if (a[i]>>j&1 && (a[i]&bs.to_ullong()) == bs.to_ullong())
          cnt++;
      if (cnt >= n)
        bs[j] = 1;
    }
    cout<<bs.to_ullong()<<'\n';
  }
  
  return 0;
}

E

考虑容斥原理 用总数减去非美丽的子序列个数
对于一个序列，如果它是非美丽的，则这个序列中必存在一个最小的数x，序列中所有数都是x的倍数
枚举每个数的倍数，统计的倍数的个数
则以为最小值的子序列个数为

枚举倍数是一个调和级数 复杂度是的

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

int a[200005];

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

int main() {
  int t;
  cin>>t;
  while (t--) {
    int n,x;
    cin>>n;
    memset(a, 0, sizeof a);
    for (int i=1; i<=n; i++)
      cin>>x, a[x]++;
    long long ans = 0;
    for (int i=1; i<=n; i++) {
      long long s = 0;
      for (int j=i*2; j<=n; j+=i)
        s += a[j];
      ans += pow(2, s)*(pow(2, a[i])-1)%M;
    }
    cout<<((pow(2, n)-1-ans)%M+M)%M<<'\n';
  }
  
  return 0;
}

F

赛后补题
状压dp 需要预处理前缀和
第一次见这种前缀和 感觉很巧妙

#include <iostream>
#include <cstring>
using namespace std;
const int M = 1e9+7;

int dp[1<<20], s[1<<20];

int main() {
  int t;
  cin>>t;
  while (t--) {
    int n, a[20], b[20];
    cin>>n;
    string t;
    for (int i=0; i<n; i++) {
      cin>>t;
      int ans = 0, mn = 1e9;
      for (auto &ch: t)
        ans += ch == '(' ? 1 : -1, mn = min(mn, ans);
      a[i] = ans;
      b[i] = mn;
    }
    for (int i=1; i<1<<n; i++)
      s[i] = s[i^(i&-i)] + a[__builtin_ctz(i)];
    if (s[(1<<n)-1] != 0) {
      cout<<0<<'\n';
      continue;
    }
    memset(dp, 0, sizeof dp);
    dp[0] = 1;
    for (int i=0; i<1<<n; i++)
      for (int j=0; j<n; j++) {
        if (i>>j&1 || s[i]+b[j] < 0)
          continue;
        dp[i|1<<j] += dp[i];
        dp[i|1<<j] %= M;
      }
    cout<<dp[(1<<n)-1]<<'\n';
  }
  
  return 0;
}