翻车笔记_ 暴零的考试(Double) [翻车, 搜索, 剪枝, 离散化, Floodfill]

有些题是不需要高级算法的

扯淡的 题解(和题目大意)

T1

1
2
3
近日,CWTV网络电视公司为了提高收视率,举办了一场CWTV拳击擂台赛。一共有n名选手参赛,分别为A1,A2……An。拳击赛的举办者对每名参赛选手的实力作了详尽的分析,发现若Ai能击败Aj,则一定有Ai>Aj。
现在举办者需要制定一个出场次序,第一个出场的作为第一任擂主,然后其他选手依次出场向擂主挑战,凡是挑战者战胜了擂主,那么这个挑战者就顶替原擂主的位置成为新的擂主。由于举办者希望比赛尽量的精彩,他希望在整个擂台赛中一共更换k次擂主。请你帮助他算出满足他的要求的出场次序的个数。
例如:出场顺序14253说明了擂主依次是1,4,5,这符合n=5和k=2。

第二类斯特林数…GG
还得写高精…GG GG

T2

1
给出n(n <= 100)个矩形(坐标范围 < 1000), 问将平面分成了几个部分

显然离散化乱搞
把坐标离散化后在bool矩阵中暴力修改矩形的边, 最后floodfill求部分, 别忘了最外面的也是一部分

T3

1
给一个四位素数, 每次只能修改四位数的一位, 且每次修改后这个数也要是素数, 求把这个素数变成另一个给定素数需要的最小步数

打表
最短路 || 搜索

T4

1
给定一个带点权的无向图, 从中挑出最多的节点, 让这些节点两两不**直接**相连, 如果有多种方案, 输出点权最大的

搜索 && 剪枝

总结

考得都不是很高级的算法…但是我就是不会…
T1 想到另一个题上去了(忽略了如果打不过擂主擂主是不会变的)…推出了方程沾沾自喜然后发现…诶样例不对啊…这时候大概心态就有点崩了…

T2 肛T1花了1.5h+吧(太菜了)…然后T2就没有时间了…

T3 简单的最短路居然没有看出来TUT觉得这几天出的迭代加深就应该是个迭代加深…然后就写了半天…说好的图论是强项呢???!!! GG…

T4 Dev和我的心头一起崩了…迭代加深是没毛病…然后剪枝剪残了…然后搜索的方向也反了…GG

总之…非常失败…感觉状态还是太差…一天三节课感觉并无卯月…醒醒啊!陈严宽! 说好的叉院呢!!! 老师家长你对得起谁啊!!! 最近要练一下DP了…还有搜索…代码能力题也要写一下了…打好基础才是关键是不是…最近是不是又㕛叒叕太急于求成了…还有Blog已经花了太多时间了…Emmmm…颓废什么的还是要废止啊…Emmmmm

沙茶的 代码

T1

要压维要不然会爆空间…
f[i][j]代表在长度为i, 换了j个擂主的方案数

1
2
3
f[i][j] += (i - 1) * f[i - 1][j] //可以倒着推, 假设f[i - 1][j]里的序列是 2 ~ i, 那么f[i][j]就相当于插入一个1, 而1插入到哪里(除了开头)都不会对换擂主次数产生影响(因为谁都打不过, 像我TUT)
if (j > 0)
f[i][j] += f[i - 1][j - 1] //向上面一样倒着推, 这就是1插入到开头的情况, 因为在f[i - 1][j]代表的序列中谁都能打败1, 所以换擂次数会 + 1, 所以是从f[][j - 1]转移

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
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <stack>
#define MAXN (500 + 5)
#define max(a, b) ((a) > (b) ? (a) : (b))
#define min(a, b) ((a) < (b) ? (a) : (b))
#define BI (100000000)
#define INF (0x7ffffff)
#define LL gjd
//#define LL __int128
using namespace std;
struct gjd
{
int len;
long long a[MAXN];
void init(int x)
{
memset(a, 0, sizeof(a));
if (!x)
{
len = 1;
a[len] = x;
}
while (x)
{
a[++len] = x % 10;
x /= 10;
}
}
void zl()
{
while (!a[len] && len > 0)
{
--len;
}
if (len <= 0)
len = 1;
}
void print()
{
zl();
printf("%lld", a[len]);
for (int i = len - 1; i >= 1; i--)
{
printf("%08lld", a[i]);
}
}
};
int n;
int m;
LL f[2][MAXN];
void init();
void print(LL);
gjd jia(gjd&, gjd&);
void che(gjd&, gjd&, int);
int main()
{
freopen("c.in", "r", stdin);
freopen("c.out", "w", stdout);
scanf("%d%d", &n, &m);
init();
f[n % 2][m].print();
return 0;
}
void init()
{
f[0][1].init(1);
f[0][0].init(1);
for (int i = 3; i <= n; i++)
{
for (int j = 0; j <= i; j++)
{
che(f[i % 2][j], f[(i - 1) % 2][j], i - 1);
if (j > 0)
f[i % 2][j] = jia(f[(i - 1) % 2][j - 1], f[i % 2][j]);
// f[i][j] = f[i - 1][j - 1] + (i - 1) * f[i - 1][j];
// f[i][j] = (i - 1) * f[i - 1][j];
// cout << f[i][j] << "\t";
// f[i][j].print();
// cout << "\t";
}
// cout << endl;
}
}
gjd jia(gjd& js, gjd& jsh)
{
gjd re;
re.init(0);
re.len = max(js.len, jsh.len);
js.zl(), jsh.zl();
int jw = 0;
for (int i = 1; i <= max(js.len, jsh.len); i++)
{
re.a[i] = js.a[i] + jsh.a[i] + jw;
jw = re.a[i] / BI;
re.a[i] %= BI;
}
while (jw)
re.a[++re.len] = jw % BI, jw /= BI;
re.zl();
return re;
}
void che(gjd& re, gjd& ch, int x)
{
re.init(0);
ch.zl();
re.len = ch.len;
int jw = 0;
for (int i = 1; i <= ch.len; i++)
{
re.a[i] = ch.a[i] * x + jw;
jw = re.a[i] / BI;
re.a[i] %= BI;
}
while (jw)
re.a[++re.len] = jw % BI, jw /= BI;
re.zl();
}

/*
20922789888000
8683317618811886495518194401280000000
*/

T2

cena爆栈…Emmmmm…

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
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#define OSTACK {int size = 50 << 20; char *p = (char*)malloc(size) + size; __asm__("movl %0, %%esp\n" :: "r"(p));}
#define MAXN (100 + 5)
#define MAXL (400 + 5)
#define bhs(a) (a)
#define bhx(a) ((a) + n)
const int xy[4][2] = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
using namespace std;
struct node
{
int x, y;
bool isx;
int belong;
node() {}
node(int a, int b): x(a), y(b) {}
} b[MAXN << 2];

int n;
int ans;
int cnts = 0;
bool a[MAXL][MAXL];
void init();
void solve();
void dfs(int, int);
bool cmp1(node, node);
bool cmp2(node, node);
void print(int, int, int, int);
void dqprint();
int main()
{
freopen("rectangle.in", "r", stdin);
freopen("rectangle.out", "w", stdout);
scanf("%d", &n);
int srx, sry, srxx, sryy;
for (int i = 1; i <= n; i++)
{
scanf("%d%d%d%d", &srx, &sry, &srxx, &sryy); // x1, y1 && x2, y2
/*
s: (x2, y2)
--------------------
| |
| |
| |
| |
--------------------
x: (x1, y1)
*/
b[bhs(i)].belong = b[bhx(i)].belong = i;
b[bhs(i)].x = srxx, b[bhs(i)].y = sryy;
b[bhx(i)].x = srx, b[bhx(i)].y = sry;
}
init();
OSTACK;
solve();
printf("%d", ans);
return 0;
}
void init()
{
memset(a, false, sizeof(a));
int gz = 0;
int last = -1;
sort(b + 1, b + (n << 1) + 1, cmp1);
for (int i = 1; i <= (n << 1); i++)
{
if (b[i].x != last)
++gz;
last = b[i].x;
b[i].x = gz << 1;
}
sort(b + 1, b + (n << 1) + 1, cmp2);
gz = 0;
last = -1;
for (int i = 1; i <= (n << 1); i++)
{
if (b[i].y != last)
++gz;
last = b[i].y;
b[i].y = gz << 1;
}
for (int i = 1; i <= (n << 1); i++)
{
for (int j = i + 1; j <= (n << 1); j++)
{
if (b[i].belong == b[j].belong)
{
print(min(b[i].x, b[j].x), min(b[i].y, b[j].y), max(b[j].x, b[i].x), max(b[j].y, b[i].y));
// printf("\n%d: -----------------------------------\n", b[i].belong);
// dqprint();
}

}
}
// dqprint();

}
bool cmp1(node x, node y)
{
return x.x < y.x;
}
bool cmp2(node x, node y)
{
return x.y < y.y;
}
/*
(x1, y2) s: (x2, y2)
--------------------
| |
| |
| |
| |
--------------------
x: (x1, y1) (x2, y1)
*/
void print(int x, int y, int xx, int yy)
{
for (int i = x; i <= xx; i++)
{
a[i][yy] = true;
a[i][y] = true;
}
for (int i = y; i <= yy; i++)
{
a[x][i] = true;
a[xx][i] = true;
}
}
void solve()
{
for (int i = 1; i <= (n << 3); i++)
{
for (int j = 1; j <= (n << 3); j++)
{
if (!a[i][j])
{
++ans;
dfs(i, j);
}
}
}
}
void dfs(int dqx, int dqy)
{
// printf("%d %d: %d\n", dqx, dqy, ++cnts);
a[dqx][dqy] = true;
for (int i = 0; i < 4; i++)
{
int nx = dqx + xy[i][0], ny = dqy + xy[i][1];
if (nx < 1 || nx > (n << 3) || ny < 1 || ny > (n << 3) || a[nx][ny])
continue;
dfs(nx, ny);
}
}
void dqprint()
{
for (int i = 1; i <= (n << 2); i++)
{
for (int j = 1; j <= (n << 2); j++)
{
if (a[i][j])
{
printf("■");
}
else
{
printf(" ");
}
}
puts("");
}
}

/*
3
10 20 50 30
40 10 50 25
40 25 80 30
*/

T3 Loli: 哈! 没想到吧! T3才是最水的~

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
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <algorithm>
#define MAXN (10000)
#define min(a, b) ((a) < (b) ? (a) : (b))
#define max(a, b) ((a) > (b) ? (a) : (b))
using namespace std;
int s, t;
int ans;
bool ok = false;
bool vis[MAXN];
bool v[MAXN];
void shai();
void solve();
void dfs(int, int);
int cmp(int, int);
int change(int, int, int);
int mpow(int, int);
int main()
{
// std::cout << "Hello, World!" << std::endl;
freopen("prime.in", "r", stdin);
freopen("prime.out", "w", stdout);
scanf("%d%d", &s, &t);
shai();
solve();
printf("%d", ans);
return 0;
}
void shai()
{
memset(vis, true, sizeof(vis));
for (int i = 2; i < MAXN; i++)
{
for (int j = 2; i * j < MAXN; j++)
{
vis[i * j] = false;
}
}
}
void solve()
{
for (ans = 0; (!ok); ans++)
{
memset(v, false, sizeof(v));
v[s] = true;
dfs(s, 0);
}
ans--;
}
void dfs(int dq, int de)
{
if (dq == t)
{
ok = true;
return ;
}
if (de >= ans)
return ;
if (de + cmp(dq, t) > ans)
return ;
for (int i = 1; i <= 4; i++)
{
for (int j = 0; j <= 9; j++)
{
if (i == 1 && (!j))
continue;
int to = change(dq, i, j);
if (!v[to] && vis[to])
{
v[to] = true;
dfs(to, de + 1);
v[to] = false;
}
if (ok)
{
// printf("%d\n", dq);
return ;
}
}
}
}
int cmp(int x, int y)
{
int re = 0;
while (x)
{
if (x % 10 != y % 10)
re++;
x /= 10, y /= 10;
}
return re;
}
int change(int x, int wz, int y)
{
int tw = mpow(10, 4 - wz), re = x % tw + y * tw + x / (10 * tw) * (10 * tw);
return re;
}
int mpow(int x, int y)
{
int re = 1;
for (int i = 1; i <= y; i++)
{
re *= x;
}
return re;
}

/*
1033 8179
*/

T4

搜索是从0开始搜索往上面加点比较方便剪枝
选下一步要选的节点时按照编号顺序枚举
这样就可以记录当前选的节点中编号最大的, 而在之后的枚举中比这个编号小的节点都不会被选上(之前节点少都选不上现在又添了一些节点更选不上了), 就可以达到剪枝的目的…详情见注释…%%%马浩然
癌…搜索还是菜啊…

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
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#define MAXN (30 + 5)
#define INF (1073741825)
#define max(a, b) ((a) > (b) ? (a) : (b))
#define min(a, b) ((a) < (b) ? (a) : (b))
#define MAXM (1000 + 5)
#define pii pair<int, int>
const int s = 0;
using namespace std;
struct edg
{
int from;
int to;
int next;
} b[MAXN * MAXN << 1];
int gb[MAXN];
int cntb;

int cnt = 0;
bool ok = true;
int n;
int mon;
int minc = INF, maxc = 0;
int cost[MAXN];
bool vis[MAXN];
pii att[MAXN * MAXN];
bool g[MAXN][MAXN];
int ans, ansd, del, totc;
int attn;
void solve();
void dfs(int, int, int);
void dfs1(int, int, int);
void adn(int, int);
int ws(int);
int main()
{
freopen("fish.in", "r", stdin);
freopen("fish.out", "w", stdout);
scanf("%d%d", &mon, &n);
int srx, sry;
for (int i = 1; i <= n; i++)
{
scanf("%d%d", &srx, &sry);
minc = min(minc, sry);
maxc = max(maxc, sry);
cost[srx] = sry;
cost[0] += sry;
}
memset(g, false, sizeof(g));
while (1)
{
scanf("%d%d", &srx, &sry);
if ((!srx) && (!sry))
break;
if (!g[srx][sry])
{
att[++attn] = make_pair((1 << srx), (1 << sry));
adn(srx, sry);
adn(sry, srx);
g[srx][sry] = g[sry][srx] = true;
}
}
solve();
/*int pn = 0, pc = 0;
for (int i = 1; i <= n; i++)
{
if (ans & (1 << i))
{
pn++;
pc += cost[i];
}
}
printf("%d %d\n", pn, pc);*/
printf("%d %d\n", del, totc);
for (int i = 1; i <= n; i++)
{
if (ans & (1 << i))
{
printf("%d\n", i);
}
}
return 0;
}
void adn(int from, int to)
{
b[++cntb].from = from;
b[cntb].to = to;
b[cntb].next = gb[from];
gb[from] = cntb;
}
void solve()
{
for (del = 0; (ok) && del <= n; )
{
ok = false;
dfs1(s, 0, 0);
del++;
}
del -= 2;
if (del < 0)
del = 0;
}
void dfs1(int dq, int de, int dqc)
{
// printf("%d\n", ++cnt);
if (dqc > mon)
return ;
if (de == del)
{
if (de != ansd)
{
totc = dqc;
ans = dq;
ansd = de;
}
else if (dqc > totc)
{
ans = dq;
totc = dqc;
}
ok = true;
return ;
}
if (dqc + (del - de) * minc > mon) // 剪枝
return ;
int last = ws(dq); // 计算当前已经选的节点集合中最大的编号
if (n - last < del - de)
return ;
for (int i = last + 1; i <= n; i++) // 从最大的编号开始枚举下一步要选的节点, 而不是从1到n枚举
{
if (!(dq & (1 << i)))
{
bool dqok = false;
for (int j = gb[i]; j; j = b[j].next)
{
if (dq & (1 << b[j].to))
{
dqok = true;
break;
}
}
if (!dqok)
{
dfs1(dq | (1 << i), de + 1, dqc + cost[i]);
/* if (ok)
return ;*/
}
}
}
}
int ws(int x)
{
for (int i = n; i >= 1; i--)
{
if (x & (1 << i))
{
return i;
}
}
return 0;
}

/*
170 7
1 70
2 50
3 30
4 40
5 40
6 30
7 20
1 4
1 7
3 4
3 5
5 7
6 7
0 0
*/