Old-NOIP 泛做一

首先简介一下这篇文章的来历……

此时的我正在瞎翻之前做过的、看起来还可以的NOIP水题,觉得哪个地方值得注意就整了下来。然而实际上我是只想整理“泛做二”里的题目。不过一想似乎自己基础不扎实,于是才有了这篇水文。

$1~2013B$ 火柴排队

Link

这真是个水题。但是之前做的时候没意识到一些问题,前几天翻来看看又把这个题秒了一遍。

观察整个式子,我们拆开之后就发现是在最小化$-\sum a_ib_i$,也就是最大化$\sum a_ib_i$。然后根据选修4-5里面的排序不等式,逆序和<乱序和<顺序和,直接找逆序对就好。

偷偷学数学真有用啊/kk

$2 ~2014C$ 飞扬的小鸟

Link

……一道gou题。

当时全天下都知道状态$f_{i,j}$就我不会转移…背包其实挺显然的,上升的时候做完全背包,注意由于即使🐦在天花板里面($h= m$)时也可以跳,所以多转移几次, 且注意既可以从i-1转移过来,也可以从现在的i转移过来;下降的时候做反向值域的01背包。

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
int main(){
cin >> N >> M >> K ; ans = Inf ;
for (i = 1 ; i <= N ; ++ i)
scanf("%d%d", &up[i], &dw[i]) ;
for (i = 1 ; i <= N ; ++ i)
Wd[i][0] = -1, Wd[i][1] = M + 1 ; memset(dp, 63, sizeof(dp)) ;
for (i = 1 ; i <= K ; ++ i)
scanf("%d", &k), S[k] = 1, scanf("%d%d", &Wd[k][0], &Wd[k][1]) ;
for (i = 0 ; i <= M ; ++ i) dp[0][i] = 0 ;
/*for (i = 2 ; i <= N ; ++ i)
for (j = Wd[i][0] + 1 ; j < Wd[i][1] ; ++ j){
dp[i][j] = dp[i - 1][j + dw[i]] ;
for (k = 0 ; k <= (j - Wd[i - 1][0] - 1) / up[i] ; ++ k)
dp[i][j] = min(dp[i - 1][j - k * up[i]] + k, dp[i][j]) ;
}*/
for (i = 1 ; i <= N ; ++ i){
for (j = up[i] + 1 ; j <= M + up[i] ; ++ j)
dp[i][j] = min(dp[i - 1][j - up[i]], dp[i][j - up[i]]) + 1 ;
for (j = M + 1 ; j <= M + up[i] ; ++ j)
dp[i][M] = min(dp[i][M], dp[i][j]) ;
for (j = 0 ; j <= M - dw[i] ; j ++)
dp[i][j] = min(dp[i][j], dp[i - 1][j + dw[i]]) ;
for (j = 0 ; j <= Wd[i][0] ; ++ j) dp[i][j] = Inf ;
for (j = Wd[i][1] ; j <= M ; j ++) dp[i][j] = Inf ;
}
for (i = 1 ; i <= M ; ++ i) ans = min(ans, dp[N][i]) ;
if (ans < 19260817) return printf("%d\n%d\n", 1, ans),0 ;
for (i = 1 ; i <= N ; ++ i) S[i] = S[i - 1] + S[i] ; l = 1, r = N, p ;
while (l <= r){
mid = (l + r) >> 1, ans = Inf ;
for (i = 1 ; i <= M ; ++ i) ans = min(ans, dp[mid][i]) ;
if (ans < 19260817) l = mid + 1, p = mid ; else r = mid - 1 ;
}
cout << 0 << endl << S[p] << endl ; return 0 ;
}

$3~2001C$ 统计单词数

$Link$ 一道很水的DP,难点(如果可以称之为难的话)在于判断。然后此处用的是哈希,判断的时候就瞎判就好了(雾

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
using namespace std ;
pair <int, int> p ;
char D[MAXLEN][10] ;
const UN LL base = 131 ;
LL Hash[MAXLEN][MAXLEN], H[10] ;
stack< pair <int, int> > s, s2 ;
const UN LL Mod = 192183781721LL ;
int dp[MAXLEN][50], Len, Length[10], o ;
int P, M, K, i, j, k, di, dj ; char S[MAXLEN] ;

inline LL Hashh(int Mark){
UN LL res = 0 ;
if (!Mark) {
for (k = j ; k <= i ; ++ k)
res = (res * base + S[k]) % Mod ;
return res ;
}
for (k = 0 ; k <= Length[Mark] ; ++k)
res = (res * base + D[Mark][k]) % Mod ;
return res ;
}
inline int Sum(int x, int y){
LL res[7] ;
memset(res, 0, sizeof(res)) ;
for (di = 1; di <= M ; ++ di)
for (dj = x ; dj <= y - Length[di] ; ++ dj)
if (Hash[dj][dj + Length[di]] == H[di]) ++ res[di] ;
while (!s.empty()) {
p = s.top() ;
res[p.first] > res[p.second] ? res[p.second] : res[p.first] = 0 ;
s.pop(), s2.push(p) ;
}
while (!s2.empty()) s.push(s2.top()), s2.pop() ;
return res[1] + res[2] + res[3] + res[4] + res[5] + res[6] ;
}
signed main(){
cin >> P >> K ;
for (i = 0 ; i < P ; ++ i)
scanf("%20s", S + i * 20) ; cin >> M ; Len = strlen(S) ;
for (i = 1 ; i <= M ; ++ i)
scanf("%s", D[i]), Length[i] = strlen(D[i]) - 1, H[i] = Hashh(i) ;
for (i = 1 ; i <= M ; ++ i)
for (j = 1 ; j < i ; ++ j){
bool flag = 1 ;
for (di = 0 ; di <= min(Length[j], Length[i]) ; ++ di)
if (D[j][di] != D[i][di]){ flag = 0 ; break ; }
if (flag) s.push({i, j}), ++ o ;
}
for (i = 0 ; i < Len ; ++ i)
for (j = 0 ; j <= i ; ++ j)
Hash[j][i] = Hashh(0) ;
/*for (i = 0 ; i < Len ; ++ i)
for (j = 0 ; j < i ; ++ j)
printf("%d%c", Sum(j, i)," \n"[j == i - 1]) ;*/
for (k = 1 ; k <= K ; ++ k)
for (i = 0 ; i < Len ; ++ i)
for (j = k - 1 ; j <= i ; ++ j)
dp[i][k] = max(dp[i][k], dp[max(0, j - 1)][k - 1] + Sum(j, i)) ;
cout << dp[Len - 1][K] << endl ; return 0 ;
}

$4~2005B$ 过河

$Link$

也是一道很水的DP。整理这个题的原因是因为好久之前的当时做这题时用了一种诡异的做法,即通过对$\sqrt{1e9}$取模进行压缩,但是这显然不对因为1:我的写法没有处理mod之后位置相同的情况;再者转移过程也十分地不服责任:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
int mod=32501;
int f[200000];
bool pos[200000];
int main(){
int n,l,r,m,cnt=0;
cin>>n>>l>>r>>m;
for(int i=1;i<=m;i++){
int x; cin>>x;
pos[x%mod]=1; if(l==r&&x%l==0)cnt++;
}
if(l==r){ cout<<cnt; return 0;}
for(int i=1;i<=mod;i++) f[i]=MAXN;
f[0]=0;
for(int i=1;i<=mod;i++)
for(int j=l;j<=r;j++){
int k=i%mod;
if(i>=j)f[i]=min(f[i],f[i-j]+pos[k]);
}
cout<<f[mod];
}

但问题是,它过了,这就很迷。仔细想想,似乎可能是因为石头数量太小了,只有100,所以随机丢到空间里去期望意义上每$1e7$会有一块石头,且mod之后位于同一个位置的概率的相反数是$32501$,所以很难有这种数据出现……换句话说,数据水死了。

然而真正的做法应该是“2520缩”,意思就是因为题目中的 s~t 的取值范围是 1~10,所以取$lcm(1,2,..,10)=2520$是可行的。

$5~2009B$ Hankson的趣味题

$Link$

整这个题只是因为情怀……

遥不可及的过去啊……Solution

$6~2004D$ 虫食算

$Link$

整这个题更是因为情怀了……

当时是何时?不记得是末冬还是暑假,只记得我十分开心地去高中部培训,吃早饭之前跟rqy瞎聊,聊什么“是不是只要我发明出可以处理负权边的Dijkstra就可以上清华了”,不自觉地聊到了这道题。嗯…场景什么的都历历在目,尤其是餐厅东边洒落的白色的阳光,一直在我的记忆中闪亮…

可惜我不是当年那个我了,rqy也不是当年那个rqy了,大家都在迈着自己的步子踏实地前进,终于还是会分道扬镳吧……

诶诶我在干什么,qaq,学习,学习……

暴力就是枚举全排列,但显然只有30pts。 于是考虑一个可行性剪枝,其实就是每次dfs刚开始先check一遍合不合法。但是整理这个题的目的也不在于此,而在于其中的pos数组,其实就是用来记录从低位到高位每个未知数的出现顺序的。那么实际上这也是一个优秀的剪枝,因为在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
45
46
47
char _Char ; int pos[MAX] ;
int Ans[MAX] ; bool mark[MAX] ;
int N, A[MAX], B[MAX], C[MAX], tot ;

inline void Print(){
for(int i = 0; i < N ; ++ i) cout << Ans[i] << " " ; exit(0) ;
}
inline bool Judge(){
int X = 0 ;
for(int i = N - 1; i >= 0 ; -- i){
int NA = Ans[A[i]], NB = Ans[B[i]], NC = Ans[C[i]] ;
if((NA + NB + X) % N != NC) return 0 ;
X = (NA + NB + X) / N ;
}
return 1 ;
}
inline bool Speed(){
if(Ans[A[0]] + Ans[B[0]] >= N) return 0 ;
for(int i = N - 1; i >= 0 ; i --){
int NA = Ans[A[i]], NB = Ans[B[i]], NC = Ans[C[i]] ;
if (NA == -1 || NB == -1 || NC == -1) continue ;
if ((NA + NB) % N != NC && (NA + NB + 1) % N != NC) return 0 ;
}
return 1 ;
}
inline void dfs(int sum){
if (!Speed()) return ;
if (sum == N + 1){if (Judge()) Print() ; return ;}
for(int i = N - 1; i >= 0 ; -- i)
if(!mark[i]){
Ans[pos[sum]] = i, mark[i] = 1 ;
dfs(sum + 1) ;
Ans[pos[sum]] = -1, mark[i] = 0 ;
}
return ;
}
inline void work_pos(int x){if(!mark[x]) mark[x] = 1, pos[++ tot] = x ;}
int main(){
cin >> N ;
fill(Ans, Ans + MAX + 2, -1) ;
for (int i = 0; i < N ; ++ i){ cin >> _Char ; A[i] = _Char - 'A' ;}
for (int i = 0; i < N ; ++ i){ cin >> _Char ; B[i] = _Char - 'A' ;}
for (int i = 0; i < N ; ++ i){ cin >> _Char ; C[i] = _Char - 'A' ;}
for (int i = N - 1; i >= 0 ; -- i)
work_pos(A[i]), work_pos(B[i]), work_pos(C[i]) ;
fill(mark, mark + MAX + 2, 0) ; dfs(1) ; return 0 ;
}

$\rm{Afterword}$

遥望扬州满地雪,不知已是惊蛰节。