[CF1025] Codeforces Round #504 (Div.1+Div.2)

发表于 | 评论数： | 阅读次数：

链接：http://codeforces.com/contest/1025

这一场大家fst得都好惨啊。

A：水题不多解释，注意$n=1$的时候输出Yes。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
#include <bits/stdc++.h>
using namespace std;
#pragma optimize("O3")

const int maxn = 222;
int n;
int vis[maxn];
char s[100100];

signed main() {
  // freopen("in","r",stdin);
  while(~scanf("%d%s",&n,s)) {
    if(n == 1) {
      printf("Yes\n");
      continue;
    }
    memset(vis, 0, sizeof(vis));
    for(int i = 0; i < n; i++) vis[s[i]-'a']++;
    bool ok = 0;
    for(int i = 0; i < 26; i++) {
      if(vis[i] > 1) {
        ok = 1;
      }
    }
    if(ok) printf("Yes\n");
    else printf("No\n");
  }
  return 0;
}

B：有$n$个数对，让你找到一个大于1的数字，使得这个数字为这个$n$对数中任意一个数的因数。

这个数一定是每一对数中某个数的因数，不妨建一个队列，把第一对中两个数的所有质因数去重后压到队里，看看队首的数是不是接下来的数对中任意一个数的因数。如果不是就出队，到最后看看有没有剩下数。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
#include <bits/stdc++.h>
using namespace std;
#pragma optimize("O3")

using LL = long long;
const int maxn = 160600;
int n;

signed main() {
  // freopen("in","r",stdin);
  LL a, b;
  queue<int> q;
  set<int> vis;
  while(~scanf("%d",&n)) {
    while(!q.empty()) q.pop();
    vis.clear();
    for(int i = 1; i <= n; i++) {
      scanf("%I64d%I64d",&a,&b);
      if(i == 1) {
        for(int j = 2; j * j <= a; j++) {
          if(a % j == 0) {
            q.push(j);
            vis.insert(j);
            while(a % j == 0) a /= j;
          }
        }
        if(a > 1) {
        	q.push(a);
          vis.insert(a);
        }
        for(int j = 2; j * j <= b; j++) {
          if(b % j == 0) {
	          if(vis.find(j) == vis.end()) {
	          	vis.insert(j);
	            q.push(j);
	          }
            while(b % j == 0) b /= j;
          }
        }
        if(b > 1) {
          if(vis.find(b) == vis.end()) {
          	vis.insert(b);
	        	q.push(b);
	        }
        }
      }
      else {
        while(!q.empty()) {
          if(a % q.front() == 0 || b % q.front() == 0) {
          	break;
          }
          q.pop();
        }
      }
    }
    if(!q.empty()) {
      printf("%d\n", q.front());
    }
    else printf("-1\n");
  }
  return 0;
}

C：给你一个只有b和w两种字符的串s，希望让你通过一个操作获得尽可能长的bw交替的子串。这个操作是选中某一个位置切分，让两边都翻转。

考虑这个操作的本质，两头翻转以后，原本在串两端的字符接到了一起，中间的到了两端。再选一个位置也是这样，那么实际上两头是可以通过这个操作接到一起的。于是我们把整个串看成一个环，找最长的不超过字符串本身长度的bw串就行了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
#include <bits/stdc++.h>
using namespace std;
#pragma optimize("O3")

using LL = long long;
const int maxn = 150500;
int n;
char s[maxn<<2];

signed main() {
  // freopen("in","r",stdin);
  while(~scanf("%s",s)) {
    n = strlen(s);
    for(int i = 0; i < n; i++) {
      s[i+n] = s[i];
    }
    int ret = 1;
    int t, i = 0;
    while(i < 2 * n) {
      if(s[i] == 'b') {
        t = 0;
        while(i + 1 < 2 * n && s[i+1] != s[i]) {
          t++; i++;
        }
        ret = max(ret, t+1);
      }
      i++;
    }
    i = 0;
    while(i < 2 * n) {
      if(s[i] == 'w') {
        t = 0;
        while(i + 1 < 2 * n && s[i+1] != s[i]) {
          t++; i++;
        }
        ret = max(ret, t+1);
      }
      i++;
    }
    printf("%d\n", min(n, ret));
  }
  return 0;
}

D：给你n个数，问你能不能构成一棵二叉排序树，并且每2个相邻节点之间的gcd不是1。

首先想到了暴力枚举每一层的根节点，但是这样复杂度是$O(n^{logn})$的，显然不科学。

注意到一个点作为根的时候与它和它的儿子具体是谁有关系，我们考虑区间dp，维护$dp(i,j,k)$，表示$[i,j]$区间内的第$k$个数字能否做根，这个关系可以用bitset维护。

于是我们枚举长度和起止端点，特判端点作为根的时候能否成立，区间里面的数则直接枚举位置，看看这个k是否能分别做左右两棵树的根，如果能的话，直接给大区间做标记。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
#include <bits/stdc++.h>
using namespace std;
#pragma optimize("O3")

const int maxn = 707;
int n, a[maxn];

signed main() {
  // freopen("in","r",stdin);
  while(~scanf("%d",&n)) {
    for(int i = 1; i <= n; i++) {
      scanf("%d",&a[i]);
    }
    bitset<maxn> ok[n+1];
    bitset<maxn> dp[n+1][n+1];
    for(int i = 1; i <= n; i++) {
      for(int j = i + 1; j <= n; j++) {
        if(__gcd(a[i], a[j]) != 1) {
          ok[i][j] = ok[j][i] = 1;
        }
      }
    }
    for(int i = 1; i <= n; i++) dp[i][i][i] = 1;
    for(int len = 2; len <= n; len++) {
      for(int i = 1; i + len - 1 <= n; i++) {
        int j = i + len - 1;
        if((ok[i] & dp[i+1][j]).any()) {
          dp[i][j][i] = 1;
        }
        if((ok[j] & dp[i][j-1]).any()) {
          dp[i][j][j] = 1;
        }
        for(int k = i + 1; k < j; k++) {
          if(dp[i][k][k] && dp[k][j][k]) {
            dp[i][j][k] = 1;
          }
        }
      }
    }
    if(dp[1][n]!=0) puts("Yes");
    else puts("No");
  }
  return 0;
}