SRM482 DIV2 AB 两题解题报告

发表于 分类于

今晚最后一题冲动了，没看范围就模拟，为某孩子送去了 50 分。。。

好吧，我在这里说说前两题。。。

275 求平均数

这题对我这个数学不怎么样的人来说，第一反应就搜索了，反正 n≤8n \leq 8 嘛，O(28)O(2^8) 暴过。。

我的代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
int a[10];
int n, cnt;
long long sum;

void dfs(int k, int num, int cur) {
  if (k == n) {
    if (num == 0) return;
    sum += cur;
    cnt += num;
    return;
  }
  dfs(k + 1, num, cur);
  dfs(k + 1, num + 1, cur + a[k]);
}

double average(vector<int> numList) {
  sum = 0;
  cnt = 0;
  n = numList.size();
  for (int i = 0; i < n; i++) a[i] = numList[i];
  dfs(0, 0, 0);
  return (double)sum / cnt;
}

队友的解法，直接求 nn 个数的平均数即可。。。

500 约瑟夫问题

nn 比较小，直接模拟，我用的是 list。

我的代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
int lastOpened(int N) {
  list<int> lst;
  list<int>::iterator it;
  int ret = 1;
  for (int i = 1; i <= N; i++) lst.push_back(i);
  int cnt = 0;
  for (int i = 2; cnt < N; i++) {
    it = lst.begin();
    while (1) {
      ret = *it;
      lst.erase(it++);
      cnt++;
      for (int j = 1; j < i; j++) {
        it++;
        if (it == lst.end()) it++;
        if (it == lst.begin()) break;
      }
      if (it == lst.begin()) break;
    }
  }
  return ret;
}

总结：还是看题！！！看题很重要。。。