Luogu NOIP 2018 训练

while(1){if(“NOIP2018win”==prompt(“请输入密码继续:)”)){alert(“正确了ヾ(o′?`o)? “);break;}else{alert(“错误的密码╮(╯﹏╰)╭”);location=”http://flyinthesky.win/";}}

搜索专题

例题 1

给你$ n $张扑克牌,保证这$ n $张来自于同一副。你可以打若干次牌,第一次可以打任意数字,之后每次打的数字,必须是之前打过的数字之和的约数。问是否存在一种打牌方案,使得可以打出所有牌,输出方案。
$1 ≤ n ≤ 52$。

本题可以很简单得写出一个爆搜程序,但是如果正搜的话解答树会很大,因为前面的决策多后面的决策少,所以我们可以调换搜索顺序,这样使得前面的决策少后面的决策多。

本题心得:对于这种题目开始决策比较多的,可以考虑倒搜,使得初始决策变少。(就算没有明显的变化也可以尝试倒搜)

例题 2

Bzoj 5439

给出一个由a, b, c组成的长度为$n$ 的字符串。定义一个子序列 $T$ 的价值为 $\frac {len^2_T}{c_T}$,其中$ lenT$ 表示$ T$ 的长度,$ c_T $表示$ T $的最小循环节长度。找出价值最大的子序列。
$1 ≤ n ≤ 10^4。$

尝试使用上下界剪枝 (可行性剪枝)。对于本题要关注”由a, b, c组成”的特殊条件。我们想一个理论最小价值。我们找到一个出现最多的字符,他的出现次数一定大于等于$\frac n3$。所以选择这个字符的价值为$(\frac n3)^2$,所以价值无论如何都能取到$\frac {n^2}9$
因为$n$比任何子序列长都大,所以循环节长度最大不能超过$9$,即找到一个下界。所以枚举最大不超过$9$的循环节来更新答案即可。

代码:Bzoj 5439

本题心得:对于这种没什么思路的题目可能有结论(比如只有某些情况有解/能剪大量枝(有上下界))来辅助。对于题目的特殊限制要加以思考。

例题 3

给出平面上$ n$ 个点$ (xi, yi)$,要求找到一个点$ (x, y)$,使得这个点到给出的那些点的欧几里得距离之和最短。
$1 ≤ n ≤ 1000。$
$−10^6 ≤ xi, yi ≤ 10^6。$

这题与搜索没什么关系。
考虑定下这个点的$x$,来找$y$的位置,发现答案与$y$的位置有单峰函数的关系,使用三分找到这个唯一的极值点即为答案。同理$x$的位置也与答案有单峰函数的关系。三分套三分即可。

本题心得:数学题几何题最优化问题二分无法解决可能是三分问题,并且可以用感性的思想来判断一个对应关系是不是单峰函数。

例题 4

定义$ ′ $运算如下:
如果 $p = 1, p′ = 0。$
如果 $p$ 是质数,$ p′ = 1$
否则 $p′ = (a \times b)′ = a′ \times b + a \times b′$
给出 $k, r$,求出所有满足 $x′ = kx, 1 ≤ x ≤ r $的$ x。$
$1 ≤ k ≤ 30, 1 ≤ r ≤ 2 × 10^{18}。$

关注”$p$ 是质数,$ p′ = 1$“,“$p′ = (a \times b)′ = a′ \times b + a \times b′$”,提示我们要分解质因数。
分解质因数得$p=\prod^t_{i=1} p_i^{q_i}​$,则可以得到$p′ =\sum_{i=1}^t\frac{q_ip}{p_i}​$
这一步可以找规律,设$p=\prod_{i=1}^k$发现$p′ =\sum_{i=1}^k \frac{\prod_{j=1}^k p_j}{p_i}$,易得上一个式子。乘$q_i$是因为每个相等质因子都要加一次。
然后就可以使$p′ =\sum_{i=1}^t\frac{q_ip}{p_i}=kp$,约掉$p$,变为
$\sum_{i=1}^t\frac{q_i}{p_i}=k$
然后我们考虑因为$p_i$都是质数,所以两个$\frac{q_i}{p_i}, \frac{q_j}{p_j}$最简形式是分数的不能合并成整数,所以$q_i$一定是$p_i$整数倍。
那么直接预处理质数$p_i$,然后用$p_i^{p_i}$来 DFS 拼 $p$ 即可。

本题心得:本题对于题目的特殊限制/特性加以思考。找规律也是很好的发现式子的方式,如果不能肉眼找,就打表找。

例题 5

给出$ n $杯糖水,第$ i $杯糖水的总质量为$ m_i$,其中糖的质量为$ t_i$。现在给出一个分数$ \frac ba$,问选出若干杯糖水,使得这些杯混合之后,糖的质量占总质量之比为$\frac ba$的方案数。
$2 ≤ n ≤ 35。$
$1 ≤ t_i ≤ m_i ≤ 10000。$
$1 ≤ a ≤ b ≤ 10000。$

本题可以枚举子集,但是时间复杂度$O(2^n)$,太大了。
考虑将子集分开两边枚举。设$m=\frac n2$, 然后再前$m$和后$m$的区间范围内枚举子集,考虑怎么才能快速合并两段答案。原题求$\frac {\sum t_i}{\sum m_i}=\frac ab$ 对于这种分数等式我们转化为乘积式,$a\sum m_i=b \sum t_i$
那么我们枚举的两个子集满足题意就是$a(\sum_{i \in S_1} m_i +\sum_{i \in S_2} m_i)=b(\sum_{i \in S_1} t_i +\sum_{i \in S_2} t_i)$
移项,则$a\sum_{i \in S_1} m_i-b\sum_{i \in S_1} t_i = -(a\sum_{i \in S_2} m_i-b\sum_{i \in S_2} t_i))$
所以我们就可以用 map 维护形如$a\sum_{i \in S_1} m_i-b\sum_{i \in S_1} t_i$的东西,前一半的存进 map,后一半在 map 中查询。然后统计即可。
这种方式叫折半搜索。

本题心得:对于这种题目直接搜索慢的,看能不能切成几块然后快速合并。并且这题将分式化为乘积式方便了计算。将关于$i$的式子放一边然后用数据结构维护这一坨的思想很重要。

标程:

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
#include <map>
#include <cstdio>
#include <cstdlib>
#include <climits>
#include <iostream>
const int MAXN = 40;
using namespace std;
int n, a, b, x[MAXN], y[MAXN];
long long work() {
map<int, int> M;
int p = n / 2, q = n - p;
long long ans = 0;
for(int i = 0; i < (1 << p); i++) {
int curA = 0, curB = 0;
for(int j = 1; j <= p; j++) {
if(i >> (j - 1) & 1) {
curA += x[j], curB += y[j];
}
}
M[a * curB - b * curA]++;
}
for(int i = 0; i < (1 << q); i++) {
int curA = 0, curB = 0;
for(int j = p + 1; j <= n; j++) {
if(i >> (j - p - 1) & 1) {
curA += x[j], curB += y[j];
}
}
int need = a * curB - b * curA;
ans += M[-need];
}
return ans - 1;
}
int main() {
scanf("%d %d %d", &n, &a, &b); // a / b
for(int i = 1; i <= n; i++) {
scanf("%d %d", &x[i], &y[i]); // x[i] / y[i]
}
long long ans = LLONG_MAX;
ans = min(ans, work());
printf("%lld\n", ans);
return 0;
}

我的程序

1
2

例题 6

Bzoj 5445

Johnny 有若干个玩具,玩具的种类可能相同也可能不同。现在已知他的这些玩具有$ n $个本质不同的子集(包括空集),问玩具的个数可能是多少。输出所有的可能解。
$1 ≤ n ≤ 10^9$。

看样例解释可以找到规律,几个数乘起来等于$n$的几个数减一的和为一个答案。DFS 分解因数(用$n$除$n$约数方便快捷)。
数学方法证明:$n=\prod_{i=1}^t (a_i+1)$,所以DFS 分解因数(用$n$除$n$约数方便快捷)。

本题心得:要善于从题中找规律,并且 DFS 时也要考虑复杂度如何优化,正向思想和反向思想。

代码:

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
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<vector>
#include<stack>
#include<set>
#include<queue>
#include<climits>
#include<cmath>
#define ms(i, j) memset(i, j, sizeof i)
#define LL long long
#define db double
using namespace std;
namespace flyinthesky {
int n;
vector<int > ans;
void dfs(int tmp, int tot, int lst) {
ans.push_back(tot + tmp - 1);//当前约数加上tmp因子
int gg = (int)sqrt(tmp) + 1;
for (int i = lst; i <= gg; i++) if (tmp % i == 0) dfs(tmp / i, tot + i - 1, i);
}
void clean() {
}
int solve() {
scanf("%d", &n);
clean();
dfs(n, 0, 2);//n/i方向搜索快
int whw;
sort(ans.begin(), ans.end()), whw = unique(ans.begin(), ans.end()) - ans.begin();
printf("%d\n", whw);
for (int i = 0; i < whw; i++) printf("%d ", ans[i]);
return 0;
}
}
int main() {
flyinthesky::solve();
return 0;
}

例题 8

Bzoj 5049

给出一个$ n​$个点$ m ​$条边的随机生成的无权无向图,有$ q ​$次询问,每次给出 $x, y(1 ≤ x, y ≤ n, x ≠ y)​$,询问$ x ​$到$ y​$的最短路。
$n = 10^5, m = 3 × 10^5, q = 10^4。$

由于题目中随机生成,期望最短路小,所以直接从两点开始双向 BFS 即可。

本题心得:要敢于猜想敢于暴力,就算不知道结论也可以双向优化

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
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<vector>
#include<stack>
#include<set>
#include<queue>
#include<climits>
#define ms(i, j) memset(i, j, sizeof i)
#define LL long long
#define db double
using namespace std;
namespace flyinthesky {
const int MAXN = 100000 + 5, MAXM = 300000 + 5;
struct edge {int v, nxt;} ed[MAXM * 2];
struct data {int u, dis, isZ;};
int n, m, Q, hd[MAXN], en, vis[MAXN], dis[MAXN], f[MAXN];
void ins(int x, int y) {ed[++en] = (edge){y, hd[x]}, hd[x] = en;}
int find(int x) {return (x == f[x]) ? x : (f[x] = find(f[x]));}
int bfs(int ith, int s, int t) {
queue<data > q;
dis[s] = dis[t] = 0, vis[s] = ith, vis[t] = -ith;
q.push((data){s, 0, ith}), q.push((data){t, 0, -ith});
while (!q.empty()) {
data p = q.front(); q.pop();
for (int i = hd[p.u]; i > 0; i = ed[i].nxt) {
edge &e = ed[i];
if (vis[p.u] == -vis[e.v]) return dis[p.u] + dis[e.v] + 1;
if (vis[e.v] != p.isZ) vis[e.v] = p.isZ, dis[e.v] = dis[p.u] + 1, q.push((data){e.v, dis[e.v], p.isZ});
}
}
return -1;
}
void clean() {
en = 0, ms(hd, -1), ms(vis, 0);
}
int solve() {
scanf("%d%d%d", &n, &m, &Q);
clean();
for (int i = 1; i <= n; i++) f[i] = i;
for (int u, v, i = 1; i <= m; i++) {
scanf("%d%d", &u, &v), ins(u, v), ins(v, u);
int x = find(u), y = find(v);
if (x != y) f[x] = y;
}
for (int s, t, i = 1; i <= Q; i++) {
scanf("%d%d", &s, &t);
if (find(s) != find(t)) printf("-1\n"); else printf("%d\n", bfs(i, s, t));
}
return 0;
}
}
int main() {
flyinthesky::solve();
return 0;
}

例题 9

给出一个$ n $个点$ m $条边的无向图连通简单图。每条边的长度为$ 1$;第$ i $个点种有$ v_i $个金币。小偷住在$ 1$ 号点,王宫在$ 2 $号点,小偷需要沿着到王宫的最短路去进贡。在去进贡的途中,对于经过的每个点,他都可以选择偷或不偷。如果偷,他将获得这个点的金币,但是回程时将不能访问这个点。小偷想知道在他能回家的前提下,最多可以进贡多少金币。
$2 ≤ n ≤ 36, 1 ≤ m ≤ \frac{n(n^2−1)}{2}$

结论:对于一个简单无向图来说,两点间的最短路的条数约为$O(e^{\frac ne} ) $级别。
我们可以将选择问题转化为删除问题。即本题先搜到一条最短路,然后将所有节点选择,然后再想如何删除使得回程路径能连通。所有我们正向做最短路,然后反向以点权拆成两点一边来做最短路。

本题心得选择问题转化为删除问题思想很重要,是这题解题的一个关键。以及简单无向图两点间的最短路的条数小。如果要用到点权作为最短路之类的算法,可以将点拆成两点一边,这样通过这条边相当于通过这个点,并且花费这个点的代价。

DP 专题

部分分专题

图论专题

第一场模拟赛

T1

水题,将一个数固定以后其他数可选可不选,所以这个数对答案的贡献为$2^{n-1} \cdot a_i$
或者根据样例解释找规律。

T2

求 $\sum_{i=1}^{n} n \mod i$,多组询问,$n \leq 10^7$

用$a\% b = a-\lfloor \frac ab \rfloor\cdot b$,得出原式等于$\sum_{i=1}^{n} n-\lfloor \frac ni \rfloor\cdot i$
即$n^2-\sum_{i=1}^{n} \lfloor \frac ni \rfloor\cdot i$,打表观察或者因为$ \lfloor \frac ni \rfloor$表示的是$n$最多由几个$i$相加而成,$\sum_{i=1}^{n} \lfloor \frac ni \rfloor=\sum_{i=1}^{n}d_0(i)$,$\sum_{i=1}^{n} \lfloor \frac ni \rfloor\cdot i=\sum_{i=1}^{n}d_1(i)$,线性筛$d_1(i)$前缀和即可。

本题心得:数论要会打表。$a\% b = a-\lfloor \frac ab \rfloor\cdot b$。线性筛的新知识

T3

毒瘤题。线段树扫描线+倍增处理

本题心得:倍增处理一些较长的距离但是单一能维护信息的操作。扫描线可以扫描平面内的一些东西来储存信息。

第二场模拟赛

T1

按题意可以将豆子按$x+y$排序(或者$x$为第一关键字,$y$第二关键字),然后对于两两点之间求路径条数然后相乘。关键在于这个条数怎么求。可以用 DP 递推,也可以使用组合数,我们从$dx+dy$步中选$dx$步出来往下走(反着来也行),答案为$C^{dx}_{dx+dy}$,然后组合数求解用预处理阶乘和阶乘逆元即可。

知识点:
1、数组大小想清楚开
2、注意题目中无解输出什么

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
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<vector>
#include<climits>
#include<cmath>
#define ms(i, j) memset(i, j, sizeof i)
#define LL long long
#define db double
#define fir first
#define sec second
#define mp make_pair
using namespace std;
namespace flyinthesky {
const int MAXN = 100000 + 5, MO = 1000000000 + 7;
int n, m, k;
LL jc_inv[MAXN * 2], jc[MAXN * 2];
pair<int, int > pnt[MAXN];
LL ksm(LL a, LL b) {
LL bs = a, ans = 1ll;
while (b) {
if (b & 1) ans = (ans * bs) % MO;
bs = (bs * bs) % MO;
b >>= 1;
}
return ans;
}
LL c(LL m, LL n) {
if (m > n) return 0;
LL tmp = jc[n];
tmp = (tmp * jc_inv[m]) % MO;
tmp = (tmp * jc_inv[n - m]) % MO;
//cout << "m=" << m << ", n=" << n << ", tmp=" << tmp << "\n";
return tmp;
}
void clean() {}
int solve() {
cin >> n >> m >> k;
clean();
jc_inv[0] = jc[0] = 1;
jc_inv[1] = jc[1] = 1;
for (int i = 2; i <= 200000; i++) {
jc[i] = (jc[i - 1] * (LL)i) % MO;
jc_inv[i] = (jc_inv[i - 1] * ksm((LL)i, MO - 2)) % MO;
}
//for (int i = 1; i <= 100; i++) cout << jc_inv[i] << " ";
for (int i = 1; i <= k; i++) scanf("%d%d", &pnt[i].fir, &pnt[i].sec);
pnt[k + 1] = mp(1, 1), pnt[k + 2] = mp(n, m), k += 2;
sort(pnt + 1, pnt + 1 + k);
LL ans = 1ll;
for (int i = 2; i <= k; i++) {
int dlx = pnt[i].fir - pnt[i - 1].fir;
int dly = pnt[i].sec - pnt[i - 1].sec;
if (dlx < 0 || dly < 0) return printf("0\n"), 0;
//printf("dlx=%d, dly=%d\n", dlx, dly);
ans = (ans * c(dlx, dlx + dly)) % MO;
}
cout << ans;
return 0;
}
}
int main() {
flyinthesky::solve();
return 0;
}

------ 本文结束 ------