1.考试状态
考试开始：第一题有点思路，第二题不就是异或高斯消元嘛，先放一会，再看第三题
先打T1,前40分钟打出来了正确的爆搜，然后用1.5小时的时间吧正确的爆搜改错，最后发现搜的不对又去打DP……
然后就爆零了(考试前刚说过我从来就没爆过零)
这次考试算是一个教训吧，反正长记性了
2.调整措施
不要死磕，要争取拿更多的分，好好读题
3.题解
T1
考场的错误想法：DFS爆搜，认为每个游乐场不能重复玩
正确思路：打DP，转移概率，而不是期望。
DP数组[2][maxn][maxt],第一维的2分别存概率和期望，第二维是点数，第三维是所用时间
纠正错误思想：不用一路搜到底，一层一层的转移就可以了（相当于把每种时间下的每个点的可能情况都算出来了。之所以用+=就是因为期望可以叠加（个人表述））
code（毒瘤）
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
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
|
#include <bits/stdc++.h>
using namespace std;
const int maxn = 510, tmax = 490;
struct EDGE {
int to, next, w;
} edge[maxn];
struct DP {
double first, second;//两个人
} dp[2][maxn][tmax]; // 0 概率 2 期望
int head[maxn], tote, availout[maxn];
void add_edge(int from, int to, int cost) {
edge[++tote].next = head[from];
edge[tote].to = to;
edge[tote].w = cost;
head[from] = tote;
}
struct point {
int c, h1, h2;
} pnt[maxn];
int n, m, k;
double ans1, ans2;
int main() {
scanf("%d%d%d", &n, &m, &k);
for (int i = 1; i <= n; i++) {
scanf("%d%d%d", &pnt[i].c, &pnt[i].h1, &pnt[i].h2);
dp[1][i][pnt[i].c].first = pnt[i].h1 / (n * 1.0);
dp[1][i][pnt[i].c].second = pnt[i].h2 / (n * 1.0);
dp[0][i][pnt[i].c].first = 1.0 / (n * 1.0);
dp[0][i][pnt[i].c].second = 1.0 / (n * 1.0);
}
for (int i = 1; i <= m; i++) {
int f, t, l;
scanf("%d%d%d", &f, &t, &l);
add_edge(f, t, l);
add_edge(t, f, l);
}
for (int time = 1; time < k; time++) {
for (int id = 1; id <= n; id++) {
bool haveOut = 0;
int num = 0;
for (int i = head[id]; i; i = edge[i].next) {
int to = edge[i].to;
if (time + edge[i].w + pnt[to].c <= k) num++;//计算可以到达的点
}
for (int i = head[id]; i; i = edge[i].next) {
int to = edge[i].to;
if (time + edge[i].w + pnt[to].c <= k) {
haveOut = 1;
dp[1][to][time + edge[i].w + pnt[to].c].first +=
dp[1][id][time].first * (1.0 / num) +
pnt[to].h1 * dp[0][id][time].first * (1.0 / num);
dp[1][to][time + edge[i].w + pnt[to].c].second +=
dp[1][id][time].second * (1.0 / num) +
pnt[to].h2 * dp[0][id][time].second * (1.0 / num);
dp[0][to][time + edge[i].w + pnt[to].c].first +=
dp[0][id][time].first * (1.0 / num);
dp[0][to][time + edge[i].w + pnt[to].c].second +=
dp[0][id][time].second * (1.0 / num);
}
}
if (haveOut == 0) {//没有出路，哪里都玩不了（100%）
dp[0][id][k].first += dp[0][id][time].first;
dp[0][id][k].second += dp[0][id][time].second;
dp[1][id][k].first += dp[1][id][time].first;
dp[1][id][k].second += dp[1][id][time].second;
}
}
}
for (int i = 1; i <= n; i++) {
ans1 += dp[1][i][k].first;
ans2 += dp[1][i][k].second;
}
printf("%.5lf %.5lf", ans1, ans2);
return 0;
}
|
T2
原本想用高斯消元，但是不知什么原因去打树形迪屁了……
思路：一路dfs，在回溯的路上更新状态，在dfs到当前节点时就赋4个初值（见程序），然后特判父亲节点进行dfs
这道题有两个特性：
- 若当前节点亮了，则它和它的儿子节点中有奇数个按了，若当前节点没亮，则它和它的儿子节点中有偶数个按了
- 如果当前节点没亮，那么它的儿子节点都亮，vice versa
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
54
55
56
57
|
#include <bits/stdc++.h>
using namespace std;
const int maxn = 101;
struct EDGE {
int next, to;
} edge[maxn * 2];
int tote, head[maxn];
void add_edge(int from, int to) {
edge[++tote].next = head[from];
edge[tote].to = to;
head[from] = tote;
}
int press[maxn][2], doNotpress[maxn][2];
int n;
void dfs(int x, int fa) {
doNotpress[x][1] = press[x][0] = 110;
press[x][1] = 1;
doNotpress[x][0] = 0;
for (int i = head[x]; i; i = edge[i].next) {
if (edge[i].to == fa) continue;
int p1 = press[x][1], p0 = press[x][0], np1 = doNotpress[x][1],
np0 = doNotpress[x][0];
dfs(edge[i].to, x);
press[x][0] =
min(p1 + press[edge[i].to][0], p0 + doNotpress[edge[i].to][0]);
press[x][1] =
min(p0 + press[edge[i].to][0], p1 + doNotpress[edge[i].to][0]);
doNotpress[x][0] =
min(np1 + press[edge[i].to][1], np0 + doNotpress[edge[i].to][1]);
doNotpress[x][1] =
min(np0 + press[edge[i].to][1], np1 + doNotpress[edge[i].to][1]);
}
}
int main() {
while (1) {
scanf("%d", &n);
if (n == 0) {
return 0;
} else {
int a1, a2;
tote = 0;
memset(head, 0, sizeof(head));
for (int i = 1; i < n; i++) {
scanf("%d%d", &a1, &a2);
add_edge(a1, a2);
add_edge(a2, a1);
}
dfs(1, 0);
printf("%d\n", min(press[1][1], doNotpress[1][1]));
}
}
return 0;
}
|
T3
因为k $\leq$ 8，所以考虑用状压
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
|
#include <bits/stdc++.h>
#define MOD 1000000007
using namespace std;
long long n, m, k;
long long dp[50][50][1001][50];
int main() {
cin >> n >> m >> k;
dp[1][0][0][0] = 1;
long long maxs = (1 << (k + 1)) - 1;
for (long long i = 1; i <= n; i++) {
for (long long j = 0; j <= m; j++) {
for (long long state = 0; state <= maxs; state++) {
for (long long t = min(i - 1, k); t; t--) {
long long t0 = dp[i][j][state][t];
dp[i][j][state][t - 1] = (dp[i][j][state][t - 1] + t0) % MOD;
if (j < m)
dp[i][j + 1][state ^ (1 << t) ^ 1][t] =
(dp[i][j + 1][state ^ (1 << t) ^ 1][t] + t0) % MOD;
}
if (!(state & (1 << k))) {
dp[i + 1][j][(state << 1) & maxs][min(k, i)] =
(dp[i + 1][j][(state << 1) & maxs][min(k, i)] +
dp[i][j][state][0]) %
MOD;
}
}
}
}
cout << dp[n][m][0][0] << endl;
return 0;
}
|