Old-NOIP 泛做二

事实上我不久前才发现原来NOIP里面的一些题是很好的……

然后大概接下来整理的都是些我认为挺有难度的吧qwq

但是感觉似乎这么好的题放在一块有点憋屈……于是就缩短了篇幅增多了篇目

$~1~2011F$ 观光公交

$Link$

这题我还是去年的3月19号做的,显然是抄的题解,于是现在又要重做一遍/sad

那么其实贪心的思路很简单,找最多人经过的那条路。由于$n$是$1000$所以直接$O(nk)$的暴力就很稳了。然后注意消除后效性——大体上就是如果你这一站用了什么“氮气加速”,结果下一站还得在那等着,就没有任何作用了,这种情况就gg[i]=i+1,你只能拯救下一站下车的乘客;否则你也可以拯救更多的,就是gg[i]=gg[i+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
struct person{
int w,f,t;
}p[100001];
int max_each[100001],sum_max[100001],get[100001],time[100001],gg[100001];
int main(){
int n,m,k,ans=0;
cin>>n>>m>>k;
for(register int i=1;i<=n-1;i++)cin>>time[i];
for(register int i=1;i<=m;i++){
cin>>p[i].w>>p[i].f>>p[i].t;
max_each[p[i].f]=max(p[i].w,max_each[p[i].f]);
sum_max[p[i].t]++;
}
for(register int i=2;i<=n;i++)sum_max[i]+=sum_max[i-1];
get[1]=max_each[1];
for(register int i=2;i<=n;i++)get[i]=max(get[i-1],max_each[i-1])+time[i-1];
for(register int i=1;i<=m;i++){ans+=(get[p[i].t]-p[i].w);}//cout<<ans<<endl;
while(k--){
gg[n]=gg[n-1]=n;
int maxn=0,f;
for(int i=n-2;i>=1;i--)
gg[i]=get[i+1]<=max_each[i+1]?i+1:gg[i+1];
for(int i=1;i<n;i++)
if(sum_max[gg[i]]-sum_max[i]>maxn&&time[i]){
maxn=sum_max[gg[i]]-sum_max[i];f=i;
}
ans-=maxn;time[f]--;
for(int i=2;i<=n;i++)get[i]=max(get[i-1],max_each[i-1])+time[i-1];
}
cout<<ans;
}

拿什么拯救我当年幼稚的码风啊

$2~2015C$ 斗地主

Link

一道喜闻乐见的搜索题。其实蛮简单的,就是每次把能出的牌出一遍就好了,就是调有点难调,在这个时候输出调试法+肉眼查错法比什么gdb好用多了。

以下是整理的细节:

  • 至于如何出单牌和对子,只需要每次dfs时每次最后把不能出花的都出了就好,就是这样:
1
for (int j = 1 ; j <= 14 ; ++ j) if (buc[j]) step ++ ; Ans = min(Ans, step) ; return ;
反之如果在出单牌/对子的时候再设置回溯——没有必要且严重扩展了状态数。
  • 还是剪枝,大概就是一个最优性剪枝:
    1
    if (step >= Ans) return ;

​ 可能是因为太套路了我一直记不住= =

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
void dfs(int m, int step){
if (step >= Ans) return ;
for (int j = 1 ; j <= 12 ; ++ j){ //单顺子
int cnt = 0, pos ;
for (int k = 1 ; ; ++ k)
if (!buc[j + k - 1] || j + k > 13) {
cnt = k - 1 ; pos = j + k - 2 ; break ;
}
if (cnt >= 5){
for (int k = j ; k <= pos ; ++ k) buc[k] -- ;
dfs(m - cnt, step + 1) ; for (int k = j ; k <= pos ; ++ k) buc[k] ++ ;
}
}
for (int j = 1 ; j <= 12 ; ++ j){ //双顺子
int cnt = 0, pos ;
for (int k = 1 ; ; ++ k)
if (buc[j + k - 1] < 2 || j + k > 13) {
cnt = k - 1 ; pos = j + k - 2 ; break ;
}
if (cnt >= 3){
for (int k = j ; k <= pos ; ++ k) buc[k] -= 2 ;
dfs(m - cnt * 2, step + 1) ; for (int k = j ; k <= pos ; ++ k) buc[k] += 2 ;
}
}
for (int j = 1 ; j <= 12 ; ++ j){ //三顺子
int cnt = 0, pos ;
for (int k = 1 ; ; ++ k)
if (buc[j + k - 1] < 3 || j + k > 13) {
cnt = k - 1 ; pos = j + k - 2 ; break ;
}
if (cnt >= 3){
for (int k = j ; k <= pos ; ++ k) buc[k] -= 3 ;
dfs(m - cnt * 3, step + 1) ; for (int k = j ; k <= pos ; ++ k) buc[k] += 3 ;
}
}
for (int j = 1 ; j <= 13 ; ++ j){ //炸弹 or 四带二
int p[3], tot = 0, q[3], cnt = 0 ;
if (buc[j] >= 4){
for (int k = 1 ; k <= 14 ; ++ k){
if (j != k){
if (buc[k] >= 2 && cnt < 2) q[++ cnt] = k ;
else if (buc[k] && tot < 2) p[++ tot] = k ;
}
}
if (tot < 2 && cnt < 2) { buc[j] -= 4 ; dfs(m - 4, step + 1) ; buc[j] += 4 ; }
else if (cnt < 2) {
buc[p[2]] --, buc[p[1]] --, buc[j] -= 4 ;
dfs(m - 6, step + 1) ; buc[p[2]] ++, buc[p[1]] ++, buc[j] += 4 ;
}
else {
buc[q[2]] -= 2, buc[q[1]] -= 2, buc[j] -= 4 ;
dfs(m - 8, step + 1) ; buc[q[2]] += 2, buc[q[1]] += 2, buc[j] += 4 ; }
}
}
for (int j = 1 ; j <= 13 ; ++ j){ // 三带XXX
if (buc[j] >= 3){
buc[j] -= 3 ;
for(int k = 1 ; k <= 14 ; ++ k){
if( !buc[k] || k == j ) continue ;
buc[k] -- ; dfs(m - 4, step + 1) ; buc[k] ++ ;
}
for(int k = 1 ; k <= 13 ; ++ k){
if( buc[k] <= 1 || j == k) continue ;
buc[k] -= 2 ; dfs(m - 5, step + 1) ; buc[k] += 2 ;
}
buc[j] +=3 ;
}
}
for (int j = 1 ; j <= 14 ; ++ j) if (buc[j]) step ++ ; Ans = min(Ans, step) ; return ;

}

= =其实这题最恶心的还是粗心地写错,毕竟那么多函数都是ctrl c+ctrl v的,鬼知道什么地方就崩掉了……

$3~2015\text{C+/G}$ 斗地主加强版

Link

直接粘一份代码过来你甚至可以获得74pts的好成绩= =

其实主要思想就是拆牌,原因是假设你又两组三张,一组炸,你的思路是出三次,但实际上只需要两次就可以——把一组三张拆成一单+一对,然后带走只需要两次。

但是我并不想写诡异的剪枝,于是索性根据题解区写了一个DP。即设$dp_{i,j,k,l,o}$表示剩下的单张有$i$个,对牌有$j$个,三张有$k$组,四张有$l$组,王有$o$个的最小出牌次数。然后转移就是朴素的转移,同时由于拆牌的存在,我们需要多加两组拆牌的转移,这就需要我们先枚举三张和炸才能转移。

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
void Init_dp(){
memset(dp, 63, sizeof(dp)) ;
dp[0][0][0][0][0] = 0 ;
for (rr int l = 0 ; l <= N ; ++ l)
for (rr int k = 0 ; k <= N ; ++ k)
for (rr int i = 0 ; i <= N ; ++ i)
for (rr int j = 0 ; j <= N ; ++ j)
for (rr int o = 0 ; o <= 2 ; ++ o){
rr int res = 100 ;
// Single
if (i) res = min(res, dp[i - 1][j][k][l][o] + 1) ;
if (j) res = min(res, dp[i][j - 1][k][l][o] + 1) ;
if (k) res = min(res, dp[i][j][k - 1][l][o] + 1) ;
if (l) res = min(res, dp[i][j][k][l - 1][o] + 1) ;
if (o) res = min(res, dp[i][j][k][l][o - 1] + 1) ;
if (o > 1) res = min(res, dp[i][j][k][l][o - 2] + 1) ;
// T -> 1
if (i && k) res = min(res, dp[i - 1][j][k - 1][l][o] + 1) ;
if (k && o) res = min(res, dp[i][j][k - 1][l][o - 1] + 1) ;
// T -> 2
if (j && k) res = min(res, dp[i][j - 1][k - 1][l][o] + 1) ;
// F -> 2
if (l > 1) res = min(res, dp[i][j][k][l - 2][o] + 1) ;
if (j && l) res = min(res, dp[i][j - 1][k][l - 1][o] + 1) ;
if (i > 1 && l) res = min(res, dp[i - 2][j][k][l - 1][o] + 1) ;
if (j > 1 && l) res = min(res, dp[i][j - 2][k][l - 1][o] + 1) ;
if (o > 1 && l) res = min(res, dp[i][j][k][l - 1][o - 2] + 1) ;
if (i && o && l) res = min(res, dp[i - 1][j][k][l - 1][o - 1] + 1) ;
// CHAI
if (l) res = min(res, dp[i + 1][j][k + 1][l - 1][o]) ;
if (k) res = min(res, dp[i + 1][j + 1][k - 1][l][o]) ;
// Trans
dp[i][j][k][l][o] = min(res, dp[i][j][k][l][o]) ;
}
}

拆牌分别是“炸拆成三张和单张”以及“三张拆成对子和单张”。

然后由于顺子这种东西不能根据数量转移,所以就还是dfs暴力算(dp按理说也是暴力吧/kk),最后加回来就完了。

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
void dfs(int m, int step){
if (step >= Ans) return ;
for (rr int j = 1 ; j <= 12 ; ++ j){ //单顺子
rr int cnt = 0 ;
for (rr int k = 1 ; ; ++ k)
if (!buc[j + k - 1] || j + k > 13) { cnt = k - 1 ; break ; }
if (cnt >= 5){
for (rr int p = 5 ; p <= cnt ; ++ p){
for (rr int k = j ; k <= j + p - 1 ; ++ k) buc[k] -- ;
dfs(m - p, step + 1) ;
for (int k = j ; k <= j + p - 1 ; ++ k) buc[k] ++ ;
}
}
}
for (rr int j = 1 ; j <= 12 ; ++ j){ //双顺子
rr int cnt = 0, pos ;
for (rr int k = 1 ; ; ++ k)
if (buc[j + k - 1] < 2 || j + k > 13) { cnt = k - 1 ; break ; }
if (cnt >= 3){
for (rr int p = 3 ; p <= cnt ; ++ p){
pos = j + p - 1 ;
for (rr int k = j ; k <= pos ; ++ k) buc[k] -= 2 ;
dfs(m - cnt * 2, step + 1) ;
for (int k = j ; k <= pos ; ++ k) buc[k] += 2 ;
}
}
}
for (rr int j = 1 ; j <= 12 ; ++ j){ //三顺子
rr int cnt = 0, pos ;
for (rr int k = 1 ; ; ++ k)
if (buc[j + k - 1] < 3 || j + k > 13) { cnt = k - 1 ; break ; }
if (cnt >= 2){
for (rr int p = 2 ; p <= cnt ; ++ p){
pos = j + p - 1 ;
for (rr int k = j ; k <= pos ; ++ k) buc[k] -= 3 ;
dfs(m - cnt * 3, step + 1) ;
for (int k = j ; k <= pos ; ++ k) buc[k] += 3 ;
}
}
}
memset(tong, 0, sizeof(tong)) ;
for (int j = 1 ; j <= 13 ; ++ j) tong[buc[j]] ++ ; tong[5] = buc[14] ;
Ans = min(Ans, step + dp[tong[1]][tong[2]][tong[3]][tong[4]][tong[5]]);return ;
}

$4~2015E$ 子串

$Link$

又是一道情怀题,还记得当时做的时候觉得可难了…(当时的pks:这个转移是人能想出来的吗?)

但其实状态很简单,$f_{i,j,k,0/1}$记录A到了$i$,B到了$j$,A迄今为止分成$k$段,$A[i]$选或者不选的方案数。

然后转移时考虑分类讨论:

  • 首先 $A[i] = B[j]:$

    • 1 : $f_{i,j,k,1} = f_{i-1,j-1,k-1,1} + f_{i-1,j-1,k-1,0} + f_{i-1,j-1,k,1}$ 也就是{i,j}和前面的是一段/不是一段且和前面的段之间有空格/不是一段且和前面的段之间没空格(讨论空格是为了保证转移的完整性)。
    • 2 : $f_{i,j,k,0} = f_{i - 1,j, k, 1} + f_{i -1, j, k, 0}$ 前面一位选/不选
  • 否则 $A[i]\not = B[j]$

    • 1: $f_{i,j,k,1} = 0\\$ 不合法的转移
      2: $f_{i,j,k,0} = f_{i - 1,j, k, 1} + f_{i -1, j, k, 0}$

其实感觉这个方程…怎么说呢,挺有学习意义的。这其实也算是做了一个状态的前缀和,因为理论上是要从$k\text{~}i-1$中转移的,但因为是方案数,所以可以直接做一个前缀和过来;同时因为此时我们的“主元”是$A$,所以如果不选的话只能是从$(i-1,j)$转移过来而不是$(i,j-1)$(即$k$这一维限制的是$i$) 。

然而还有另外一种定义状态的方式;

其余的都差不多,还是$f_{i,j,k,1}$表示必选,但是$f_{i,j,k,0}$则表示“可选可不选”。那我们来思考这样如何转移:

  • 1:$f_{i,j,k,1} = (f_{i-1,j-1,k,1} +f_{i - 1,j-1, k-1, 0})\cdot [A_i=B_j] $ 还是分类讨论“连不连成一整段”
  • 2:$f_{i,j,k,0} = f_{i−1,j,k,0}+f_{i,j,k,1}$,即保证了这一位不选的上一位的选/不选保证了这一位必选的方案数。

思想也大体相同。注意数据范围的限制,滚一下就好了。

嗯,是一道不错的题。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
int main(){
cin >> N >> M >> K ; dp[0][0][0] = 1 ;
for(i = 1; i <= N; i ++) cin >> A[i] ;
for(i = 1; i <= M; i ++) cin >> B[i] ;
for(d = i = 1; i <= N; i ++, d ^= 1){
dp[d][0][0] = 1 ;
for(j = 1; j <= M; j ++)
for(k = 1; k <= K ;k ++){
if(A[i] == B[j])
f[d][j][k] = (dp[d ^ 1][j - 1][k - 1] + f[d ^ 1][j - 1][k]) % mod ;
else f[d][j][k] = 0 ;
dp[d][j][k] = (dp[d ^ 1][j][k] + f[d][j][k]) % mod ;
}
}
cout << dp[N & 1][M][K]% mod ;
}

$5~2011C$ Mayan游戏

Link

想当年这可真是噩梦……

简单来讲就是爆搜吧,只不过记得当时没想到是真的每次搜一遍$7\cdot5$的方阵……

然后这是以前的笔记:

  • 1、每次搜索要保留本次的状态,这是比较好想的,我也成功的想到了。但是问题是我们不能单纯地用一个二维数组来$copy$,需要记录步数,因为如果单纯的reset会导致之前走过的也消失。于是最终我们需要一个三维数组来记录。后半段是$qcr$告诉我的。
  • 2、还有就是一个小小的剪枝。就是由于对于每一个格子,我们考虑它向两边替换,而我们为了避免重复搜索,所以就决定单向搜索,即对于每个块,如果他左边也是一个块,那就不去$exchange$,只考虑右边;而如果左边是空白格,才$exchange$。显然这个剪枝的优化性是很显著的。

  • 3、我一开始写的$remove()$、$down()$和$check()$十分的麻烦——或者说专一?反正之后我懒得调试了,直接听的$qcr$的,每次执行这几个函数的时候,直接全屏扫一遍

  • 4、$qcr$给我讲了一个很神的$down()$函数——其实也不算多神,只是很简单地处理了每一行的悬空态方块,但是说“神”的原因则是因为“简单”。对,简单,而有时往往我会想复杂。

  • 5、对于$exchange$,我们要不断的$while(remove()) ~;$,因为会不断地有新情况出现。

  • 6、最后我挂了……几个点来着……忘记了。反正原因是因为,每次$remove()$之前应该先$down()$,然而我并没有$down()$干净233

  • 7、最后再说一个剪枝儿,不是必要性的,但是确实可以加快速度。就是我们再每次遍历$7 \times 5$的时候,遇到空白的,不是continue而是break,因为我们$down$一定是完备的,即从下向上枚举时,如果下方的已经clear了,上方的不可能悬空。所以可以少好几次空遍历。

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
struct D{ int x, y ;} ; stack <D> s ;
struct Ans{ int x, y, d ;} res[100] ; int Remove[50][50] ;
int N, T[30][30], base[4000][10][10], qwq[4000][30], color[30], i, j, t, tot ;

inline int qr(){
....
}
inline void down(){
int ttt = 0 ;
for(int di = 1 ; di <= 5 ; ++ di){
ttt = 0 ;
for(int dj = 1 ; dj <= 7 ; ++ dj)
if(T[di][dj] == -1) ++ ttt ;
else{
if(! ttt) continue ;
T[di][dj - ttt] = T[di][dj], T[di][dj] = -1 ;
}
}
}
inline bool remove(){ // void -> bool
bool Mark = 0 ;
memset(Remove, 0, sizeof(Remove)) ;
for (int di = 1 ; di <= 5 ; ++ di)
for (int dj = 1 ; dj <= 7 ; ++ dj){
if (T[di][dj] != -1 && di >= 2 && di <= 4
&& T[di][dj] == T[di + 1][dj] && T[di][dj] == T[di - 1][dj]){
Remove[di + 1][dj] = Remove[di - 1][dj] = Remove[di][dj] = 1,
Mark = 1 ;
}
if (T[di][dj] != -1 && dj >= 2 && dj <= 6
&& T[di][dj] == T[di][dj + 1] && T[di][dj] == T[di][dj - 1]){
Remove[di][dj + 1] = Remove[di][dj - 1] = Remove[di][dj] = 1,
Mark = 1 ;
}
}
if (!Mark) return 0 ;
for (int di = 1 ; di <= 5 ; ++ di)
for (int dj = 1 ; dj <= 7 ; ++ dj)
T[di][dj] = (!Remove[di][dj]) ? T[di][dj] : -1 ;
down() ; return 1 ;

}
inline bool judge(){
for (int di = 1 ; di <= 5 ; ++ di)
for (int dj = 1 ; dj <= 7 ; ++ dj)
if (T[di][dj] != -1) return false ;
return true ;
}
inline void Prepare(int x){//copy
for (int di = 1 ; di <= 5 ; ++ di)
for (int dj = 1 ; dj <= 7 ; ++ dj)
base[x][di][dj] = T[di][dj] ;
}
inline void _reset(int x){//copy_back
for (int di = 1 ; di <= 5 ; ++ di)
for (int dj = 1 ; dj <= 7 ; ++ dj)
T[di][dj] = base[x][di][dj] ;
}
inline void dfs_work(int step){
if (judge()){
for (int di = 1 ; di <= N ; ++ di)
printf("%d %d %d\n", res[di].x, res[di].y, res[di].d) ;
exit(0) ;
}
if (step == N + 1) return ; Prepare(step) ;
for (int di = 1 ; di <= 5 ; ++ di)
for (int dj = 1 ; dj <= 7 ; ++ dj){
if (T[di][dj] == -1) break ;
if (di > 1 && T[di - 1][dj] == -1){
swap(T[di][dj], T[di - 1][dj]) ; down() ; while (remove()) ;
res[step] = (Ans){di - 1, dj - 1, -1} ;
dfs_work(step + 1) ; _reset(step) ; res[step] = (Ans){-1, -1, -1} ;
}
if (di < 5 && T[di][dj] != T[di + 1][dj]){
swap(T[di][dj], T[di + 1][dj]) ; down() ; while(remove()) ;
res[step] = (Ans){di - 1, dj - 1 ,1} ;
dfs_work(step + 1) ; _reset(step) ; res[step] = (Ans){-1, -1, -1} ;
}
}
}
int main(){
cin >> N ; memset(T, -1, sizeof(T)) ;
for (i = 1 ; i <= 5 ; ++ i) T[i][0] = 0 ;
for (i = 1 ; i <= 5 ; ++ i)
while((t = qr()) != 0) T[i][++ T[i][0]] = t ;
dfs_work(1) ; cout << -1 << endl ; return 0 ;
}

$\text{Afterwords}$

准确来说,没有人在到达之前知道自己到底要去哪儿。