爱悠闲 > Codeforces Round #259 (Div. 1)

Codeforces Round #259 (Div. 1)

分类: ACM_CF&&TC  |  作者: u011433745 相关  |  发布日期 : 2014-08-16  |  热度 : 213°

题意:给你一个m面的筛子,抛掷N次, 求最大值的期望

分析:m面的骰子抛掷n次, 所有的情况有m ^ n, 其中最大值为x的情况为x^n - (x-1) ^ n


#include <cstdio>
#include <cmath>
int n, m;
int main() {
  scanf("%d%d", &m, &n);
  double ans = 0;
  for(int i=1; i<=m; i++)
    ans += (pow(i*1.0/m, n) - pow((i-1.0)/m, n)) * i;
  printf("%.12f\n", ans);
  return 0;
}


B

题意:给你一个长度为n的a数组, 求一个两两互质的, 长度为n的b数组, 使得最小

分析:

1 b[i] >= 1 && b[i] <= 58, 因为如果去到b[i] > 58, 不如取1

2 状态压缩dp, dp[i][j] 表示确定前i个时, 已选约数的集合为j时的最小值

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;

const int maxn = (1 << 16) + 10;
const int inf = 0x3f3f3f3f;
int dp[110][maxn], pre[110][maxn], f[110][maxn];
int state[100], vis[100], a[110], p[50];
int n, pnum;

void get_prime() {
  vis[0] = vis[1] = 1;
  for(int i = 2; i*i <= 58; i++) if(!vis[i]) {
     for(int j = i*i; j <= 58; j += i) vis[j] = 1;
  }
  pnum = 0;
  for(int i=2; i<=58; i++) {
    if(!vis[i]) p[++pnum] = i;
  }
  for(int i = 1; i <= 58; i++)
    for(int j = 1; j <= pnum; j++) {
       if(i % p[j] == 0) state[i] |= 1 << (j-1);
    }
}
void print(int x, int y) {
   if(x == 0)  return ;
   print(x-1, pre[x][y]);
   printf("%d ", f[x][y]);
}
int main() {
   get_prime();
   scanf("%d", &n);
   for(int i = 1; i <= n; i++) scanf("%d", &a[i]);
   memset(dp, inf, sizeof(dp));
   dp[0][0] = 0;
   int full = (1 << pnum) - 1;
   for(int i = 1; i <= n; i++)
     for(int j = 0; j <= full; j++) {
        if(dp[i-1][j] < inf) {
            for(int k = 1; k <= 58; k++) {
                if(state[k] & j) continue;
                int x = state[k] | j;
                if(dp[i][x] > dp[i-1][j] + abs(a[i] - k)) {
                    dp[i][x] = dp[i-1][j] + abs(a[i] - k);
                    pre[i][x] = j;
                    f[i][x] = k;
                }
            }
        }
     }
   int ans = inf, id = -1;
   for(int i = 0; i <= full; i++) {
     if(ans > dp[n][i]) {
        ans = dp[n][i];
        id = i;
     }
   }
   print(n, id);
   puts("");
   return 0;
}


C:

题意:给你一副n个顶点, m条边的无向图, 每个顶点的取值为0 或 1, 表示经过该点需走偶数次 或 奇数次, 构造一条路径满足上诉要求

分析:

1:图的深度优先遍历的扩展, dfs遍历每一个点, 回溯是判断儿子节点是否满足要求, 若不满足, 则往下走一步, 再往回走即可, 父亲由父亲的父亲控制

2:若遍历结束跟节点不满足要求, 删除根节点即可

#include <cstdio>
#include <cstring>
#include <vector>
using namespace std;

vector <int> e[100010];
vector <int> path;
int col[100010], vis[100010];
int n, m;

void dfs(int x) {
  vis[x] = 1;
  path.push_back(x);
  col[x] = !col[x];
  for(int i=0; i<e[x].size(); i++) {
     int y = e[x][i];
     if(vis[y])  continue;
     dfs(y);
     path.push_back(x);
     col[x] = !col[x];
     if(col[y]) {
        path.push_back(y);
        col[y] = !col[y];
        path.push_back(x);
        col[x] = !col[x];
     }
  }
}
int main() {
  scanf("%d%d", &n, &m);
  int x, y;
  while(m--) {
    scanf("%d%d", &x, &y);
    e[x].push_back(y);
    e[y].push_back(x);
  }
  int cnt = 0;
  for(int i=1; i<=n; i++) {
    scanf("%d", &col[i]);
    cnt += col[i];
  }
  if(cnt == 0) {
    puts("0");
    return 0;
  }
  int id;
  for(int i=1; i<=n; i++) if(col[i]) {
    id = i;
    dfs(id);
    break;
  }
  if(col[id]) {
    path.pop_back();
    col[id] = 0;
  }
  for(int i=1; i<=n; i++)
    if(col[i]) {
       puts("-1");
       return 0;
    }
  printf("%d\n", path.size());
  for(int i=0; i<path.size(); i++)
    printf("%d ", path[i]);
  puts("");
  return 0;
}