[Codeforces1017A-D] Codeforces Round 502 (Div.1+Div.2)

发表于 | 分类于 ， | 评论数： | 阅读次数：

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

这把肯定要上分的，结果因为服务器爆炸，unrated了好气。。

A：太水了不多说。

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
#include <bits/stdc++.h>
using namespace std;

using P = struct {
  int a, b, c, d;
  int s, id;
};

const int maxn = 1010;
int n;
P p[maxn];

signed main() {
  // freopen("in", "r", stdin);
  while(cin >> n) {
    for(int i = 1; i <= n; i++) {
      cin >> p[i].a>>p[i].b>>p[i].c>>p[i].d;
      p[i].s = p[i].a+p[i].b+p[i].c+p[i].d;
      p[i].id = i;
    }
    sort(p+1, p+n+1, [](P a, P b) {
      return a.s == b.s ? a.id < b.id : a.s > b.s;
    });
    for(int i = 1; i <= n; i++) {
      if(p[i].id == 1) {
        printf("%d\n", i);
        break;
      }
    }
  }
  return 0;
}

B：给你两个01串，要求你交换第一个串中的任意两个数，使得这两个串“或”操作后的结果和原始的不一样，问多少种换法。

手写一下会发现导致变化的a、b串某一位置的组合是“10”（用0换掉第一个1）和“00”（用1换掉第一个0），我们统计这样的位置，以及0、1的出现次数，把这两种结果加起来，再减掉一次10和00出现的组合乘积就行了（因为10中的1和00中的0会多进行一次）。

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
#include <bits/stdc++.h>
using namespace std;

using LL = long long;
const int maxn = 100100;
int n;
char a[maxn], b[maxn];
LL tot;
int vis[2];

signed main() {
  // freopen("in", "r", stdin);
  while(cin >> n) {
    memset(vis, 0, sizeof(vis));
    cin >> a >> b;
    LL o = 0, z = 0, cnt = 0;
    for(int i = 0; i < n; i++) {
      vis[a[i]-'0']++;
      if(a[i] == '1') o++;
      if(a[i] == '0') z++;
    }
    if(vis[0] == n || vis[1] == n) {
      printf("0\n");
      continue;
    }
    LL x = 0, y = 0;
    tot = 0;
    for(int i = 0; i < n; i++) {
      if(a[i] == '0' && b[i] == '0') x++;
      if(a[i] == '1' && b[i] == '0') y++;
    }
    cout << o*x+z*y-x*y << endl;
  }
  return 0;
}

C：构造一个长度为n排列，使得这个排列的LIS和LDS长度之和最小。

遇事不决打个表：

img

我们发现一个规律：当要构造长度为n的排列时，我们可以找到第一个比n大的平方数$k^2$，然后我们依次放入$k^2-k+1,…k^2-1,k^2,…,1,2,…,k$，当要放的数比n大的时候不输出就ok了。

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
#include <bits/stdc++.h>
using namespace std;

using LL = long long;
const int maxn = 100100;
LL n, nn;
vector<int> tmp, gen;

signed main() {
  // freopen("in", "r", stdin);
  while(cin >> n) {
    gen.clear();
    LL nn = 1;
    while(nn * nn < n) nn++;
    LL circle = nn;
    nn = nn * nn;
    LL del = nn - n;
    while(nn) {
      tmp.clear();
      for(int i = 0; i < circle; i++, nn--) tmp.emplace_back(nn);
      reverse(tmp.begin(), tmp.end());
      for(auto x : tmp) gen.emplace_back(x);
    }
    for(auto x : gen) if(x <= n) cout << x << " ";
    cout << endl;
  }
  return 0;
}

打表代码：

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
#include <bits/stdc++.h>
using namespace std;

const int maxn = 110;
const int maxm = 1100;
int n;
int a[maxn], b[maxn];
int f[maxn];

int lis() {
  memset(f, 0, sizeof(f));
  for(int i = 1; i <= n; i++) {
    f[i] = 1;
    for(int j = 1; j <= n; j++) {
      if(a[i] > a[j]) f[i] = max(f[i], f[j]+1);
    }
  }
  int ret = 0;
  for(int i = 1; i <= n; i++) ret = max(ret, f[i]);
  return ret;
}

int lds() {
  memset(f, 0, sizeof(f));
  for(int i = 1; i <= n; i++) {
    f[i] = 1;
    for(int j = 1; j <= n; j++) {
      if(a[i] < a[j]) f[i] = max(f[i], f[j]+1);
    }
  }
  int ret = 0;
  for(int i = 1; i <= n; i++) ret = max(ret, f[i]);
  return ret;
}

signed main() {
  // freopen("in", "r", stdin);
  while(~scanf("%d",&n)) {
    for(int i = 1; i <= n; i++) a[i] = i, b[i] = i;
    int ret = 1000000;
    do {
      int tmp = lis() + lds();
      if(tmp <= ret) {
        ret = tmp;
        printf("%d: ", ret);
        for(int i = 1; i <= n; i++) {
          b[i] = a[i];
          printf("%d ", b[i]);
        }
        printf("\n");
      }
    }while(next_permutation(a+1, a+n+1));
    printf("%d: ", ret);
    for(int i = 1; i <= n; i++) {
      printf("%d ", b[i]);
    }
    printf("\n");
  }
  return 0;
}

D：两个01串有个匹配的价值，对应位相同的话就要加上那位的价值。给你一些询问串，问有多少串和它的匹配价值不超过k。

这题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
63
64
65
66
#include <bits/stdc++.h>
using namespace std;
#pragma optimize(2)

const int maxn = 15;
int n, m, q;
int w[maxn];
int wu[4096][4096];
int ret[4096][101];
int vis[500500];
char tmp[maxn];

inline int conv(char *x) {
  int ret = 0;

  return ret;
}

signed main() {
  // freopen("in", "r", stdin);
  scanf("%d%d%d",&n,&m,&q);
  memset(vis, 0, sizeof(vis));
  memset(ret, 0, sizeof(ret));
  for(int i = 0; i < n; i++) scanf("%d",&w[i]); 
  int nn = 1 << n;
  for(int i = 0; i < m; i++) {
    scanf("%s", tmp);
    int x = 0;
    for(int i = 0; i < n; i++) {
      x <<= 1;
      x += tmp[i] - '0';
    }
    vis[x]++;
  }
  for(int i = 0; i < nn; i++) {
    for(int j = 0; j < nn; j++) {
      if(!vis[j]) continue;
      int tmp = 0;
      for(int k = 0; k < n; k++) {
        if(((1<<k)&i) == ((1<<k)&j)) {
          tmp += w[n-1-k];
          if(tmp > 100) {
            break;
          }
        }
      }
      if(tmp <= 100) ret[i][tmp] += vis[j];
    }
  }
  for(int i = 0; i < nn; i++) {
    for(int k = 1; k <= 100; k++) {
      ret[i][k] += ret[i][k-1];
    }
  }
  while(q--) {
    int k;
    scanf("%s%d",tmp,&k);
    int x = 0;
    for(int i = 0; i < n; i++) {
      x <<= 1;
      x += tmp[i] - '0';
    }
    printf("%d\n", ret[x][k]);
  }
  return 0;
}