https://ac.nowcoder.com/acm/contest/6885
D - 牛妹爱数列
题意：给定一个01序列，两种操作：翻转某一位；翻转第一位到某一位所有位。问最少几次操作使得变为全 0.
dp
做法一：翻转某一个区间需要 2 次操作。考虑枚举翻转的块的大小，则需要枚举所有 1 到 i-1，需要再化简dp式子，用一个 mn 记录前面的值。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
| #include<bits/stdc++.h>
using namespace std;
#define ll long long
const int INF = 0x3f3f3f3f;
const ll inf = 0x3f3f3f3f3f3f3f3f;
const int N = 2e6 + 10;
const ll mod = 1e9 + 7;
int n;
int dp[N], a[N], s[N];
int main() {
scanf("%d", &n);
for (int i = 1; i <= n; i++)scanf("%d", &a[i]), s[i] = s[i - 1] + a[i];
dp[1] = a[1];
int mn = dp[1] + s[1] - 1;
for (int i = 2; i <= n; i++) {
dp[i] = mn + i - s[i] + 2;
dp[i] = min(dp[i], s[i]);
dp[i] = min(dp[i], i - s[i] + 1);
dp[i] = min(dp[i], dp[i - 1] + a[i]);
mn = min(mn, dp[i] + s[i] - i);
}
printf("%d\n", dp[n]);
return 0;
}
|
做法二：题解做法。
dp[i][0/1] 表示把前 i 位全变成 0/1 的最少操作次数。
如果当前位置上a[i]=1，则：
dp[i][0]=min(dp[i−1][0]+1,dp[i−1][1]+1)，我们可以将a[i]单独翻转，也可以将这前缀1一起翻转；
dp[i][1]=min(dp[i−1][1],dp[i−1][0]+1)，我们可以将前缀0翻转，然后把a[i]拼上去。
如果当前位置上a[i]=0 类似。
1
2
3
4
5
6
7
8
9
10
| rep(i, 1, n) {
if (a[i] == 1) {
dp[i][0] = min(dp[i - 1][0] + 1, dp[i - 1][1] + 1);
dp[i][1] = min(dp[i - 1][1], dp[i - 1][0] + 1);
} else {
dp[i][0] = min(dp[i - 1][0], dp[i - 1][1] + 1);
dp[i][1] = min(dp[i - 1][0] + 1, dp[i - 1][1] + 1);
}
}
printf("%d\n", dp[n][0]);
|
E - 牛妹游历城市
题意：给定 n 个数，两个数如果二进制并不为 0，则有连边，边权为二进制并的lowbit，问从第 1 个点到第 n 个点的最短路径长度。1≤n≤105,1≤ai<232
二进制+最短路
点很多，直接求肯定超时，但是既然是二进制，那么可以试着把点转化为边，把二进制作为点。
原本的点仍然保留，再对每个二进制位各建一个点，对于每个数，把它原本的点与该数为 1 的二进制位对应的新点连接，新图不带边权，带点权，旧点点权为 0，新点点权为 对应二进制大小。
则两个旧点需要联通必定要经过一些二进制点，为了走最短路，必定走的是两个数的lowbit。
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
| #include<bits/stdc++.h>
using namespace std;
#define ll long long
const int INF = 0x3f3f3f3f;
const ll inf = 0x3f3f3f3f3f3f3f3f;
const int N = 2e6 + 10;
const ll mod = 1e9 + 7;
int T;
int n;
ll w[N], a[N];
vector<int>G[N];
typedef pair<ll, int>pii;
ll d[N];
ll bfs() {
priority_queue<pii, vector<pii>, greater<pii> >q;
memset(d, 0x3f, sizeof(d));
d[1] = 0;
q.push(pii(0, 1));
while (!q.empty()) {
ll di = q.top().first; int u = q.top().second; q.pop();
if (di > d[u])continue;
if (u == n)return di;
for (int v : G[u]) {
if (d[v] > d[u] + w[v]) {
d[v] = d[u] + w[v];
q.push(pii(d[v], v));
}
}
}
return -1;
}
int main() {
scanf("%d", &T);
while (T--) {
scanf("%d", &n);
for (int i = 1; i <= n + 32; i++)G[i].clear();
fill(w, w + n + 33, 0);
for (int i = 1; i <= n; i++) {
scanf("%lld", &a[i]);
for (int j = 1; j <= 32; j++) {
if (a[i] >> (j - 1) & 1) {
G[i].push_back(j + n);
G[j + n].push_back(i);
}
}
}
for (int i = 1; i <= 32; i++)w[i + n] = (1ll << (i - 1));
ll ans = bfs();
if (ans == -1)puts("Impossible");
else printf("%lld\n", ans);
}
return 0;
}
|
