# 程序员进阶之算法练习（五）

### 前言

• 几乎所有的程序员都能做A题；
• 思维缜密的程序员可以做B题；
• 数学还没还给老师的能做C题；
• 接受过算法训练的能过D,E题；

### B

```    long long sum = 0, ans = 0, n, m;
cin >> n >> m;
for (int i = 1; i <= n; ++i) {
cin >> c[i];
sum += c[i];
}
for (int i = 1; i <= m; ++i) {
long long k;
cin >> k;
flag[k] = 1;
sum -= c[k];
ans += c[k] * sum;
}
for (int i = 1; i <= n; ++i) {
int next;
if (i == n) {
next = 1;
}
else {
next = i + 1;
}
if (!flag[next] && !flag[i]) {
ans += c[i] * c[next];
}
}

cout << ans;```

### C

```    long long sum = 0, ans = 0, n, w, v, u;
cin >> n >> w >> v >> u;
double k = u * 1.0 / v, ret = 0, l = w * 1.0 / u, minT = 10E9, maxT = -10E9;
while (n--) {
long long x, y;
cin >> x >> y;
double t = y - k * x;

minT = min(minT, -t / k);
maxT = max(maxT, -t / k);
}
if (minT >= 0) {
ret = l;
}
else if (maxT <= 0) {
ret = l;
}
else {
ret = l + maxT / v;
}
printf("%.6lf", ret);```

### D

```int low_bit(int x) {
return x & (-x);
}

void tree_add(int x, int v) {
while (x <= n) {
tree[x] ^= v;
x += low_bit(x);
}
}

int tree_sum(int x) {
int sum = 0;
while (x) {
sum ^= tree[x];
x -= low_bit(x);
}
return sum;
}```

### E

```int n;
long long k;
cin >> n >> k;
long long t = sqrt(k);

for (long long i = 1; i <= t; ++i) {
if (k % i == 0) {
vec.push_back(k / i);
vec.push_back(i);
}
}
int vecSize = vec.size();
sort(vec.begin(), vec.end());
for (int i = 0; i < vecSize; ++i) {
Hash[vec[i]] = i;
}

for (int i = 1; i <= n; ++i) {
scanf("%lld", &a[i]);
b[i] = gcd(a[i], k);
}
if (k == 1)
{
cout << 1 << endl;
cout << min_element(a + 1, a + 1 + n) - a << endl;
return 0;
}

for (int j = 1; j < vecSize; ++j) {
dp[0][j] = make_pair(n + 1, 0);
}

for (int i = 1; i <= n; ++i) {
for (int j = 0; j < vecSize; ++j) {
long long gcdnum = gcd(b[i], vec[j]);
int pre = Hash[vec[j] / gcdnum];

dp[i][j] = min(dp[i - 1][j], make_pair(dp[i - 1][pre].first + 1, dp[i - 1][pre].second + a[i]));
}
}

if (dp[n][vecSize - 1].first > n) {
cout << -1 << endl;
return 0;
}
else {
cout << dp[n][vecSize - 1].first << endl;
int pre = vecSize - 1;
for (int i = n; i > 0; --i) {
if (dp[i][pre] == dp[i - 1][pre]) {
continue;
}
printf("%d ", i);
pre = Hash[vec[pre] / gcd(vec[pre], b[i])];
}
}```

d[i][j][k] 表示前i个数字，第j个因子有k个的最小总数和最小数字和。 最后在所有 d[n][j][k] 中第j个因子中，k大于题目要求中，寻找最小值即可。

d[i][j][k] 根据第i个数的因子，有： d[i][j][k] = min(d[i - 1][j][k], d[i-1][j-s][k-t]) s、t取决于k的第j个因子的个数。

172 篇文章86 人订阅

0 条评论

## 相关文章

50740

21670

74430

### 动态规划|相邻约束下的最优解(House Robber II )

01 House Robber II This time, all houses at this place are arranged in a circl...

38240

28970

23290

### 每周学点大数据 | No.4算法的分析之时间复杂度

No.4期 算法的分析之时间复杂度 小可：嗯，我觉得评价一个算法的最基本方式就是看它运行得快不快。 Mr. 王：嗯，这是重要的考量标准之一。研究算法运行得快不...

29990

20010

### 2017"百度之星"程序设计大赛 - 复赛1003&&HDU 6146 Pokémon GO【数学，递推，dp】

Pokémon GO Time Limit: 3000/1500 MS (Java/Others)    Memory Limit: 32768/32768 K...

35270

32770