个人题解 A~E

A

#include <iostream>
using namespace std;

int main() {
  int x,y;
  cin>>x>>y;
  cout<<(y+x-1)/x<<'\n';
  
  return 0;
}

B

诈骗？

#include <iostream>
using namespace std;

int main() {
  int t;
  cin>>t;
  while (t--) {
    int n,k,x;
    cin>>n>>k;
    long long ans = 0;
    while (n--)
      cin>>x, ans += (x > 0 ? x : 0);
    cout<<ans<<'\n';
  }
  
  return 0;
}

C

用stack试了试 诶 结果就过了
直接先贪心地消除 所有相邻的 可以消除的字符
最后剩余01相间的串 0101...
这个串需要修改length/2次

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

int main() {
  int t;
  cin>>t;
  while (t--) {
    int n;
    string s;
    cin>>n>>s;
    stack<char> stk;
    for (auto &ch: s)
      if (!stk.empty() && stk.top() == ch)
        stk.pop();
      else
        stk.push(ch);
    cout<<stk.size()/2<<'\n';
  }
  
  return 0;
}

D

盲猜结果不会太大 因为gcd使得数据减小的速度非常快(实际上是因为次数不会超过3)
直接用个队列暴力bfs 就过了

看了讲解 原来是构造题 因为是可重集合 任意用两次同一个操作x op y并加到集合中 再把这两个数异或就得到了0 所以答案不会超过3 剩下直接枚举即可
不如直接枚举((

#include <iostream>
#include <numeric>
#include <queue>
#include <vector>
using namespace std;

int main() {
  int t;
  cin>>t;
  while (t--) {
    int x,y;
    cin>>x>>y;
    queue<vector<int>> que;
    que.push({x,y});
    while (!que.empty()) {
      auto vec = que.front();
      que.pop();
      for (int i=0; i<vec.size(); i++)
        for (int j=i+1; j<vec.size(); j++) {
          if ((vec[i]&vec[j]) == 0 || (vec[i]^vec[j]) == 0) {
            cout<<vec.size()-1<<'\n';
            goto end;
          }
          int g = gcd(vec[i], vec[j]), a[4] = {vec[i]&vec[j], vec[i]|vec[j], vec[i]^vec[j], g};
          for (int i=0; i<4; i++)
            vec.push_back(a[i]), que.push(vec), vec.pop_back();
        }
    }
    end:;
  }
  
  return 0;
}

E

先对所有边排序
枚举所有的最长边 对所有比它小的边 用类似多项式生成函数的方法(或者说背包dp) 记录组合出的所有可能值 可以用bitset+移位实现
然后贪心地找第一个大于这条边的长度

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

int main() {
  int t;
  cin>>t;
  while (t--) {
    int n,a[102];
    cin>>n;
    for (int i=1; i<=n; i++)
      cin>>a[i];
    sort(a+1, a+1+n);
    bitset<202> b;
    b[0] = b[a[1]] = b[a[2]] = b[a[1]+a[2]] = 1;
    int ans = 2e9, mx = a[1]+a[2];
    for (int p=3; p<=n; p++) {
      for (int i=a[p]+1; i<=mx; i++)
        if (b[i]) {
          ans = min(ans, a[p]+i);
          break;
        }
      mx = max(mx, mx+a[p]);
      b |= b<<a[p];
    }
    cout<<(ans == int(2e9) ? -1 : ans)<<'\n';
  }
  
  return 0;
}