A~E 个人题解

A

看个位是不是0

#include <iostream>
using namespace std;

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

B

当且仅当突变次数为0或2时 可以

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

int a[100005];

int main() {
  int t;
  cin>>t;
  while (t--) {
    int n, cnt = 0;
    cin>>n;
    cin>>a[1];
    for (int i=2; i<=n; i++)
      cin>>a[i], cnt += a[i] != a[i-1];
    cnt += a[n] != a[1];
    cout<<(cnt <= 2 ? "YES" : "NO")<<'\n';
  }
  
  return 0;
}

C

dp[i] = dp[i-1]*2 答案就是
因为新的数要么加在最左边 要么加在最右边

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

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 n;
  cin>>n;
  cout<<pow(2, n-1)<<'\n';
  
  return 0;
}

D

答案要么是0 要么是1 要么是2
当且仅当突变次数大于等于3时 答案为0
否则 只要不是全0或全1 或0011 0110 1001 1100这四个串 答案为1
其余情况 答案为2

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

int main() {
  int t;
  cin>>t;
  while (t--) {
    int n;
    string s;
    cin>>n>>s;
    int cnt = 0;
    bool iszero = s[0] == '0', isone = s[0] == '1';
    for (int i=1; i<n; i++)
      cnt += s[i] != s[i-1], iszero = iszero && s[i] == '0', isone = isone && s[i] == '1';
    if (cnt >= 3)
      cout<<0<<'\n';
    else if (!iszero && !isone && s != "0011" && s != "0110" && s != "1001" && s != "1100")
      cout<<1<<'\n';
    else
      cout<<2<<'\n';
  }
  
  return 0;
}

E

dfs
因为数字的二进制位数最多为21 可以直接预处理出树上所有的长度小于21的链所代表的数字
dfs时用一个栈维护每个节点的数字

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

vector<int> g[100005];
bool ans[1<<21];
string s, t;

void dfs(int u, int f) {
  t.push_back(s[u-1]);
  int lb = max(0, int(t.size()) - 21);
  for (int i=t.size()-1; i>=lb; i--) {
    string p = t.substr(i);
    ans[stoi(p, 0, 2)] = true;
    reverse(p.begin(), p.end());
    ans[stoi(p, 0, 2)] = true;
  }
  for (auto &v: g[u]) {
    if (v == f)
      continue;
    dfs(v, u);
  }
  t.pop_back();
}

int main() {
  int n,q,u,v,x;
  cin>>n>>q>>s;
  for (int i=1; i<=n-1; i++)
    cin>>u>>v, g[u].push_back(v), g[v].push_back(u);
  dfs(1, 0);
  while (q--)
    cin>>x, cout<<(ans[x] ? "YES" : "NO")<<'\n';
  
  return 0;
}