2020牛客国庆集训派对day1 签到题题解

前情摘要：退役选手，一个人不想读英文题，只做签到题0.0

A. ABB

Solution

题意:可以在后面添加字符，使得原串变成回文串，问需要添加的最少字符数。
思路：Manacher里的p[i]数组指以某个点为中心的回文半径，利用这个数组就可以做这道题，模板是网上随手复制的。
时间复杂度 $O(n)$

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <iostream>
using namespace std;
typedef long long ll;
const int N = 1e6 + 5;
char s[11000002];
char s_new[21000002];//存添加字符后的字符串
int p[21000002];
int n;
int Init() {//形成新的字符串
    int len=strlen(s);//len是输入字符串的长度
    s_new[0]='$';//处理边界，防止越界
    s_new[1]='#';
    int j=2;
    for(int i=0;i<len;i++) {
        s_new[j++]=s[i];
        s_new[j++]='#';
    }
    s_new[j]='\0';//处理边界，防止越界（容易忘记）
    return j;// 返回s_new的长度
}

int Manacher() {//返回最长回文串
    int len=Init();//取得新字符串的长度， 完成向s_new的转换
    int max_len=-1;//最长回文长度
    int id;
    int mx=0;
    for(int i=1;i<=len;i++) {
        if(i<mx)
            p[i]=min(p[2*id-i],mx-i);//上面图片就是这里的讲解
        else p[i]=1;
        while(s_new[i-p[i]]==s_new[i+p[i]])//不需边界判断，因为左有'$'，右有'\0'标记；
            p[i]++;//mx对此回文中点的贡献已经结束，现在是正常寻找扩大半径
        if(mx<i+p[i]) {//每走移动一个回文中点，都要和mx比较，使mx是最大，提高p[i]=min(p[2*id-i],mx-i)效率
            id=i;//更新id
            mx=i+p[i];//更新mx
        }
        max_len=max(max_len,p[i]-1);
    }
    int ans = 1e9;
//    for(int i = 1; i <= len; i++) {
//      cout << i << ' ' << p[i] << "\n";
//    }
    for(int i = len; i >= 1; i--) {
      if(p[i] + i >= len) {
        ans = min(ans, n - p[i] + 1);
      }
    }
    return ans;
}
int main() {
  cin >> n;
  cin >> s;
  cout << Manacher() << "\n";
  return 0;
}

C. Bob in Wonderland

Solution

题意:给一个图，对于每条边可以断开重连，想要得到一条链
思路：最终一条链那么最后他们的度为1（起始点） 2 2 .... 2 1（结束点），直接对度大于2的点进行处理，设每个点的度为 $k$ , 花费为 $k - 2(k > 2)$ ,可以理解为将他们断开连接到度为1的点。
时间复杂度 $O(n)$

Code

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <iostream>
using namespace std;
typedef long long ll;
const int N = 1e6 + 5;
vector<int> G[N];
int main() {
  int n; cin >> n;
  for(int i = 1; i <= n - 1; i++) {
    int u, v; cin >> u >> v;
    G[u].push_back(v);
    G[v].push_back(u);
  }
  ll ans = 0;
  for(int i = 1; i <= n; i++) {
    if(G[i].size() > 2)
      ans += (G[i].size() - 2);
  }
  cout << ans << "\n";
  return 0;
}

E. Zeldain Garden

题意：找[l, r]区间内每个数字的因子数
思路：前缀和的思想求 $ans_r - ans_{l - 1}$
要求区间的因子数可以想到 [1, r]里
1出现 $\frac{r}{1}$ 次
2出现 $\frac{r}{2}$ 次
......
最终答案就是经典问题整除分块 $\sum\limits_{i = 1}^n \lfloor{\frac{n}{i} \rfloor}$
时间复杂度 $O(\sqrt{n})$

Code

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <iostream>
using namespace std;
typedef long long ll;
const int N = 1e6 + 5;
ll solve(ll n) {
  ll res = 0;
  for(ll l = 1, r; l <= n; l = r + 1) {
    r = n / (n / l);
    res += (r - l + 1) * (n / l);
  }
  return res;
}
int main() {
  ll l, r; cin >> l >> r;
  cout << solve(r) - solve(l - 1) << "\n";
  return 0;
}

H. PPonk Warshall

Solution

题意：字符串A最少能经过多少次两两交换变成字符串B
思路：分三种情况：

A B 这种情况，能够一次交换使得两两对应
B A
A B C 这种情况，能够两次交换使得两两对应
B C A
A B C D 这种情况，能够三次交换使得两两对应
B C D A

于是只需要一个二维数组存储字符间的关系，随后三种情况从第一种开始枚举即可。

Code

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <iostream>
#include<map>
using namespace std;
typedef long long ll;
const int N = 1e6 + 5;
map<char, int> mp;
int maze[10][10];
void init() {
  mp['A'] = 1, mp['C'] = 2, mp['G'] = 3, mp['T'] = 4;
}
int solve(int x, int y, int z) {
  int ans = 0;
  int l = min(maze[x][y], min(maze[y][z], maze[z][x]));
  int r = min(maze[x][z], min(maze[z][y], maze[y][x]));
  ans += 2 * (l + r);
  maze[x][y] -= l, maze[y][z] -= l, maze[z][x] -= l;
  maze[x][z] -= r, maze[z][y] -= r, maze[y][x] -= r;
  return ans;
}
int main() {
  init();
  string s, t; cin >> s >> t;
  for(int i = 0; i < s.size(); i++) {
    if(s[i] == t[i]) continue;
    maze[mp[s[i]]][mp[t[i]]]++;
  }
  int ans = 0;
  for(int i = 1; i <= 4; i++) {
    for(int j = i + 1; j <= 4; j++) {
      if(maze[i][j] >= maze[j][i]) {
        maze[i][j] -= maze[j][i];
        ans += maze[j][i];
        maze[j][i] = 0;
      } else {
        maze[j][i] -= maze[i][j];
        ans += maze[i][j];
        maze[i][j] = 0;
      }
    }
  }
  for(int i = 1; i <= 4; i++) {
    for(int j = i + 1; j <= 4; j++) {
      for(int k = j + 1; k <= 4; k++) {
        ans += solve(i, j, k);
      }
    }
  }
  for(int i = 1; i <= 4; i++) {
    ans += 3 * maze[1][i];
  }
  cout << ans << "\n";
  return 0;
}

F. Light Emitting Hindenburg

Solution

题意：n个数字里取k个，使得按位与最大
思路：二进制位上从大到小考虑，用一个数组标记作为备选的数字，对于高位上不为1的数字都可以排除。于是从高位往低位贪心取即可。
时间复杂度 $O(64n)$

Code

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <iostream>
#include<map>
using namespace std;
typedef long long ll;
const int N = 1e6 + 5;
ll a[N];
int vis[70];
int need[N];
int main() {
  int n, k; cin >> n >> k;
  for(int i = 1; i <= n; i++) cin >> a[i], need[i] = 1;
  ll ans = 0;
  for(int i = 63; i >= 0; i--) {
    for(int j = 1; j <= n; j++) {
      if(need[j] && ((a[j] >> i) & 1)) {
        vis[i]++;
      }
    }
    //cout << i << ' ' << vis[i] << "\n";
    if(vis[i] >= k) {
      ans += (1LL << i);
      for(int j = 1; j <= n; j++) {
        if(!need[j]) continue;
        if((!((a[j] >> i) & 1)) && need[j]) {
          need[j] = 0;
        }
      }
    }
  }
  cout << ans << "\n";
  return 0;
}