[Codeforces1011] Round #499 (Div. 2)

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

用hexo搭了博客，以后就在这里写题解和随笔了。

$$
mathjax测试：C_i=\sum_{j×k=i}A_j*B_k
$$
复健开了一场CF div2，感觉非常不好啊。。

比赛链接是http://codeforces.com/contest/1011

A：n个字符取k个，不能取字典序相邻的，也不能取相同的。就这样取，问最小的ascii-‘a’+1的和是多少。

贪心，给字符排个序，取第一个，然后后面的取最小的。

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;

const int maxn = 111;
char s[maxn];
int n, k;

signed main() {
  // freopen("in", "r", stdin);
  while(~scanf("%d%d",&n,&k)) {
    scanf("%s", s);
    sort(s, s+n);
    int pre = 0, ret = s[0] - 'a' + 1, tot = 1;
    for(int i = 1; i < n; i++) {
      if(tot >= k) break;
      if(s[i] - s[pre] > 1) {
        ret += s[i] - 'a' + 1;
        pre = i;
        tot++;
      }
    }
    if(tot < k) {
      printf("-1\n");
    }
    else printf("%d\n", ret);
  }
  return 0;
}

B：n个人吃东西，一共m个东西，每个东西都有一类。每个人每天只能吃一个同一类东西，问怎么分配这m个东西，让这n个人吃得时间最久。

m很小，直接遍历天数day，然后贪心地check就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
29
30
31
32
33
34
35
36
#include <bits/stdc++.h>
using namespace std;

const int maxn = 111;
int n, m;
int a[maxn], vis[maxn];

int ok(int day) {
  int tot = 0;
  for(int i = 0; i < 101; i++) {
    if(vis[i] >= day) tot += (int)(vis[i] / (double)day);
  }
  return tot >= n;
}

signed main() {
  // freopen("in", "r", stdin);
  while(~scanf("%d%d",&n,&m)) {
    int lo = 0, hi = 100000;
    memset(vis, 0, sizeof(vis));
    for(int i = 1; i <= m; i++) {
      scanf("%d", &a[i]);
      vis[a[i]]++;
    }
    if(n > m) {
      printf("0\n");
      continue;
    }
    int ret = 0;
    for(int mid = 0; mid < 101; mid++) {
      if(ok(mid)) ret = mid;
    }
    printf("%d\n", ret);
  }
  return 0;
}

C：n个星球，一个人坐重量为m的飞船从1出发到n，需要走1->2->..->n->1这样的路径，从每个点起飞要消耗ai的燃油，在每个点降落要消耗bi的燃油，燃油只能从1上带，问这人要带多少燃油才能完成这个路径。

二分燃油的量，判断是否满足，或从1->n->n-1->…1逆推，上一次的燃油量是x*m/(x-1)，x为起飞or降落的消耗。

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

const int maxn = 1010;
const double eps = 1e-9;
int n, m;
double a[maxn], b[maxn];

int ok(double fuel) {
  double tot = fuel + m;
  for(int i = 1; i <= n - 1; i++) {
    tot -= (double)tot / (double)a[i];
    tot -= (double)tot / (double)b[i+1];
  }
  for(int i = n; i >= 2; i--) {
    tot -= (double)tot / (double)a[i];
    tot -= (double)tot / (double)b[i-1];
  }
  return tot - m >= eps;
}

signed main() {
  // freopen("in", "r", stdin);
  while(~scanf("%d%d",&n,&m)) {
    for(int i = 1; i <= n; i++) {
      cin >> a[i];
    }
    for(int i = 1; i <= n; i++) {
      cin >> b[i];
    }
    double ret = m;
    for(int i = 1; i < n; i++) {
    	ret = b[i] * ret / (b[i] - 1.0);
    	ret = a[i+1] * ret / (a[i+1] - 1.0);
    }
  	ret = b[n] * ret / (b[n] - 1.0);
  	ret = a[1] * ret / (a[1] - 1.0);
  	ret -= m;
  	if(ret > 1e9) {
  		printf("-1\n");
  	}
  	else printf("%.10f\n", ret);
  }
  return 0;
}

D：猜一个1到m的数字x，可以询问最多60次。每次回答有可能是假的，假的情况那么会输出真答案判别的相反数（大于的时候返回1，如果假的情况就返回-1，小于同理），回答的真假情况序列p的长为n，回答按照这个序列循环返回结果。求这个数字x。

可以用数字1去试探n次（当然答案是1的时候可以直接结束程序了），把n次询问的真假情况预处理出来记下，之后就可以愉快地二分x，根据上面预处理出来的真假情况修改返回结果了。

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;

const int maxn = 100100;
int p[maxn];
int n, m;

int query(int y) {
  printf("%d\n", y);
  fflush(stdout);
  int t;
  scanf("%d", &t);
  if(t == 0 || t == 2) exit(0);
  return t;
}

signed main() {
  // freopen("in", "r", stdin);
  while(~scanf("%d%d",&m,&n)) {
    memset(p, 0, sizeof(p));
    for(int i = 0; i < n; i++) {
      int t = query(1);
      p[i] = (t == 1);
    }
    int lo = 2, hi = m;
    for(int q = 0; ; q++) {
      int mid = (lo + hi) >> 1;
      int t = query(mid);
      if(!p[q%n]) t = -t;
      if(t == 1) lo = mid + 1;
      else hi = mid - 1;
    }
  }
  return 0;
}

E：n个数，每个数可以取任意次，相加后对k取模。求模的结果的个数。

统计k和每个数的gcd，答案就是k/gcd，依次取0,k/gcd,2k/gcd…就行了。过阵子尝试证明一下，相关概念有：有限域，生成元，生成多项式，循环群，裴蜀定理。

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

using LL = long long;
const int maxn = 100100;
int n;
LL k;
LL a[maxn];
bool vis[maxn];

signed main() {
  // freopen("in", "r", stdin);
  while(~scanf("%d%lld",&n,&k)) {
    memset(vis, 0, sizeof(vis));
    LL x = k;
    for(int i = 1; i <= n; i++) {
      scanf("%lld", &a[i]);
      x = __gcd(x, a[i]);
    }
    printf("%lld\n", k / x);
    for(LL i = 0; i < k; i+=x) {
      printf("%lld ", i);
    }
    printf("\n");
  }
  return 0;
}