刷了一套题散散心，Div 3，全部是 1 A，感觉比以前慢了好多好多啊。

这几天也整理了一下自己要做的事情，工作上要努力... ... 晚上还是要认认真真背英语的。

找了几个同学问了一下，有点想自己做点 project 了，再学学机器学习，深度学习之类的，弄点小 AI project 玩玩吧... ...没事看点各种科技新闻开开眼界。

 

【】

 

A - 

挺简单的，只要知道哪几个位置要输出就可以了。

时间复杂度：$O(N)$

#include 
     
      using namespace std;const int maxn = 1e5 + 10;char s[maxn], len;int main() {  scanf("%d", &len);  scanf("%s", s);  int p = 0;  for(int i = 0; i < len; i = i + p) {    printf("%c", s[i]);    p++;  }  printf("\n");  return 0;}
     

　　

B - 

不是删原数组中的最小值就是删最大值。

时间复杂度：应该是可以 $O(N)$ 实现的吧，但是排个序 $O(N*logN)$ 写起来多简单。

#include 
     
      using namespace std;const int maxn = 1e5 + 10;int a[maxn], n;int main() {  scanf("%d", &n);  for(int i = 1; i <= n; i ++) {    scanf("%d", &a[i]);  }  sort(a + 1, a + 1 + n);  printf("%d\n", min(a[n - 1] - a[1], a[n] - a[2]));  return 0;}
     

　　

C - 

先将 $N$ 转换成二进制，如果不到 $k$ 个，那么可以找一个数字出来，除以 $2$，拆成两个，这样就多了一个，按这样慢慢操作就好了。

时间复杂度：在实现的时候我把所有数字扔进了优先队列，每次拆最大的那个，事实上每次拆一个可拆的就可以了。$O(K*logK)$。

#include 
     
      using namespace std;int n, k;priority_queue
      
        Q;int cnt_Q;int main() {  scanf("%d%d", &n, &k);  for(int i = 29; i >= 0; i --) {    if(n >= (1 << i)) {      Q.push(i);      cnt_Q ++;      n -= (1 << i);    }  }  if(cnt_Q > k) {    printf("NO\n");    return 0;  }  while(cnt_Q < k) {    int tp = Q.top();    if(tp == 0) {      printf("NO\n");      return 0;    }    Q.pop();    Q.push(tp - 1);    Q.push(tp - 1);    cnt_Q ++;  }  printf("YES\n");  while(!Q.empty()) {    int tp = Q.top();    printf("%d ", 1 << tp);    Q.pop();  }  return 0;}
      
     

　　

D - 

这题比较逗，数据保证一定有解。emmmm... 那是不是很大概率填完就是可行解呢？我也不太会证明，反正这样写了一下就 AC 了，写之前就挺有把握。

复杂度可能是线性的？

#include 
     
      using namespace std;const int maxn = 2e5 + 10;int n;int a[maxn];int b[maxn][5];int flag;void dfs(int x) {  int num1 = b[a[x]][1];  int num2 = b[a[x]][2];  if(b[num1][1] == num2 || b[num1][2] == num2) {    a[x + 1] = num1;    a[x + 2] = num2;    if(x == n - 2) {      flag = 1;      return;    }    dfs(x + 1);    if(flag) return;  }  if(b[num2][1] == num1 || b[num2][2] == num1) {    a[x + 1] = num2;    a[x + 2] = num1;    if(x == n - 2) {      flag = 1;      return;    }    dfs(x + 1);    if(flag) return;  }}int main() {  scanf("%d", &n);  for(int i = 1; i <= n; i ++) {    scanf("%d%d", &b[i][1], &b[i][2]);  }  flag = 0;  a[1] = 1;  dfs(1);  for(int i = 1; i <= n; i ++) {    printf("%d ", a[i]);  }  printf("\n");  return 0;}
     

 

E - 

这个题意是，问你有几个位置，只改变这个位置，能让它变成合法括号匹配串。

括号匹配常见套路。左括号变成 1，右括号变成 -1，算前缀和 $S_i$。

一个合法的括号匹配串的充要条件是：[1] 对于任何 $i$， $S_i$ 都非负。[2] $S_n = 0$。

balabalabala.....

然后你大概就会做了。

#include 
     
      using namespace std;const int maxn = 1e6 + 10;int n;int a[maxn], b[maxn], c[maxn];char s[maxn];int main() {  scanf("%d", &n);  scanf("%s", s);  for(int i = 1; i <= n; i ++) {    a[i] = (s[i - 1] == '(') ? 1 : -1;  }  for(int i = 1; i <= n; i ++) {    a[i] += a[i - 1];  }  c[1] = a[1];  for(int i = 2; i <= n; i ++) {    c[i] = min(a[i], c[i - 1]);  }  b[n] = a[n];  for(int i = n - 1; i >= 1; i --) {    b[i] = min(a[i], b[i + 1]);  }  for(int i = 1; i <= n; i ++) {   // printf("[i: %d]  a: %d, b: %d, c: %d\n", i, a[i], b[i], c[i]);  }  int ans = 0;  for(int i = 1; i <= n; i ++) {    if(s[i - 1] == '(') {      if(c[i - 1] >= 0 && b[i] - 2 >= 0 && a[n] - 2 == 0) ans ++;    } else {      if(c[i - 1] >= 0 && b[i] + 2 >= 0 && a[n] + 2 == 0) ans ++;    }  }  printf("%d\n", ans);  return 0;}
     

　　

F - 

这个最小生成树还挺好玩。摸索了半天才知道啊。。果然洞察力减弱了。

就是两种边，一种读入的边，另一种原来就有的边，每次怎么取呢？

突破口是样例 2，先看看 $m$ 是 0 的时候要怎么弄？也就是全是原来的边的时候答案是怎么来的。

画画图就能知道是哪些边了... ... 我就不写了。

$m$ 不是 0 的时候，那岂不是就是把这些边和读入的边合起来做个 MST 吗...

The world is so funny, but I am so naive. 

#include 
     
      using namespace std;const int maxn = 4e5 + 10;struct Edge {  int x, y;  long long w;}e[maxn];int cnt_e;int n, m;long long a[maxn];int f[maxn];bool cmp(const Edge& a, const Edge& b) {  return a.w < b.w;}int Find(int x) {  if(x != f[x]) f[x] = Find(f[x]);  return f[x];}int main() {  scanf("%d%d", &n, &m);  for(int i = 1; i <= n; i ++) {    scanf("%lld", &a[i]);    f[i] = i;  }  int index = 1;  for(int i = 2; i <= n; i ++) {    if(a[i] < a[index]) {      index = i;    }  }  for(int i = 1; i <= n; i ++) {    if(i == index) continue;    e[cnt_e].x = i;    e[cnt_e].y = index;    e[cnt_e].w = a[i] + a[index];    cnt_e ++;  }  while(m--) {    scanf("%d%d%lld", &e[cnt_e].x, &e[cnt_e].y, &e[cnt_e].w);    cnt_e ++;  }  sort(e, e + cnt_e, cmp);  long long ans = 0;  for(int i = 0; i < cnt_e; i ++) {    int fx = Find(e[i].x);    int fy = Find(e[i].y);    if(fx == fy) continue;    ans = ans + e[i].w;    f[fx] = fy;  }  printf("%lld\n", ans);  return 0;}