好久沒擼 TC 了，手都生了。前兩天剛折騰好 LinuxMint + Cinnamon，順便手賤把 TC 環境配好了。
隨便進去扯了一套最新的 SRM 來搞，全跑完之後才發現原來這場比賽還處於 System Running 階段。於是知道了比賽一結束還在 Running 的時候你就已經可以自己拉出來做了。小綠名大家不要笑。
Summary
這次 DIV 2 的難度一般，一道簽到題加兩道普通的 DP。
Code on GitHub.
250pt - Goose Tattarrattat
題意很簡單，就是給你一個字符串，問你最少改變多少字符讓字符串所有字符都一樣。
簽到題，找最多的字符跟總長度一減就OK了。
cpp1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
| #define SIZE(x) ((int)(x.size()))
#define LENGTH(x) ((int)(x.length()))
class GooseTattarrattatDiv2
{
public:
int getmin(string S);
};
int GooseTattarrattatDiv2::getmin(string S)
{
int maxsame = 0;
map<char, int> mp;
for(int i = 0; i < LENGTH(S); i++)
{
mp[S[i]]++;
maxsame = max(maxsame, mp[S[i]]);
}
return LENGTH(S) - maxsame;
}
|
500pt - Gears
有 N 個齒輪圍成一圈，相鄰兩個齒輪要反方向轉才能正常運轉不卡到其它輪子。你要從中間拿掉幾個齒輪（留空了就不影響其左邊的左邊的齒輪），問最少拿掉幾個使得所有齒輪能正常轉。
我們建兩個二維 dp 數組，或者一個三維 dp 數組：
cpp
第一維 i 代表當前是第 i 個齒輪。第二維若是 0 則表示這個齒輪拿走，若是 1 代表留下。第三維若是 0 則代表第一個齒輪拿走，1 代表第一個齒輪留下。整個數組的每個元素就代表該齒輪留下或者拿走且第一個齒輪是留下或者拿走的情況下的最少拿走齒輪數。
所以我們能得到幾個狀態轉移方程：
第一個齒輪
cpp1
2
3
4
| dp[i][0][0] = 1;
dp[i][0][1] = INF;
dp[i][1][1] = 0;
dp[i][1][0] = INF;
|
第二個齒輪
如果與第一個同向那麼就有了一留一走或者兩個都走的情況。否則就是四種情況都可以。
cpp1
2
3
4
5
6
7
8
9
10
11
12
13
14
| if(與第一個齒輪同向)
{
dp = 1;
dp = 1;
dp = 2;
dp = INF;
}
else
{
dp = 2;
dp = 1;
dp = 1;
dp = 0;
}
|
之後的所有齒輪
若該齒輪與前一個齒輪方向相同 ，那麼該齒輪留下的時候，前一個齒輪必須得走，那麼就是 dp[i - 1][0][?];該齒輪走的時候，前一個齒輪可走可留，就是 dp[i - 1][0|1][?] + 1 的稍微小一點那個。
若方向不相同 ，那麼就是該齒輪留下的時候，前一個齒輪也可以留下。
cpp1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
| if(與前一個齒輪同向)
{
dp = dp;
dp = dp;
dp = min(dp, dp) + 1;
dp = min(dp, dp) + 1;
}
else
{
dp = min(dp, dp);
dp = min(dp, dp);
dp = min(dp, dp) + 1;
dp = min(dp, dp) + 1;
}
|
最後若最後一個齒輪與第一個齒輪同向，那麼在 dp[i - 1][0][0]、dp[i - 1][0][1]、dp[i - 1][1][0] 中挑一個。若不同向，那麼多了個 dp[i - 1][1][1] 這個選擇。
下面就是代碼了：
cpp1
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
| class GearsDiv2
{
public:
int getmin(string Directions);
};
int GearsDiv2::getmin(string Directions)
{
int dp;
for(int i = 0; i < LENGTH(Directions); i++)
{
if(i == 0)
{
dp = 1;
dp = 10000000;
dp = 0;
dp = 10000000;
}
else
if(i == 1)
{
if(Directions == Directions)
{
dp = 1;
dp = 1;
dp = 2;
dp = 10000000;
}
else
{
dp = 2;
dp = 1;
dp = 1;
dp = 0;
}
}
else
if(Directions == Directions)
{
dp = dp;
dp = dp;
dp = min(dp, dp) + 1;
dp = min(dp, dp) + 1;
}
else
{
dp = min(dp, dp);
dp = min(dp, dp);
dp = min(dp, dp) + 1;
dp = min(dp, dp) + 1;
}
}
int ans;
int mi = LENGTH(Directions) - 1;
if(Directions == Directions)
{
ans = min(dp, min(dp, dp));
}
else
{
ans = min(min(dp, dp), min(dp, dp));
}
return ans;
}
|
1000pt - Flipping Bits
給你一個 01串 與一個正整數 M。01串 有如下三種操作:
- 隨便反轉一位（0 -> 1, 1 -> 0）。
- 將開頭
k * M 位反轉。k 可以是任何正整數。
- 將末尾
k * M 位反轉。k 可以是任何正整數。
問最少需要幾步將整個字符串變成都是 1。
這又是一個 DP 的題目。
我們先設有 G 組，一組 M 個 01字符。那麼就能有
cpp
其中 i 代表第 i 組，第二維如果是 0 就代表這一組採用一位位反轉的操作將這組全變成 1，如果是 1 則將整組全部反轉再採用一位位反轉的操作將這組全變成 1 。至於 dp1 和 dp2 則代表從頭到尾和從尾到頭。
由於只有 0 和 1 反轉，那麼一組反轉兩次就能還原原狀——這是一個非常重要的性質。
如果某一組採用整組反轉的操作，若前一組也是整組反轉，那麼就相當於操作次數不變，只是將前一組的反轉範圍延續到這一組；若前一組是非整組反轉，那麼就相當於從頭到這一組反轉之後，前面的所有組再反轉回去——相當於是多了兩次操作。於是就有了（先只拿 dp1 作爲例子）：
cpp1
2
3
4
| dp1[i][1] = min(
dp[i - 1][0] + 這一組1的數量 + 2,
dp[i - 1][1] + 這一組1的數量
);
|
如果某一組採用非整組反轉，那麼操作次數就是前一組的整組反轉或者非整組反轉的操作次數加上這一組 0 的數量：
cpp1
2
3
4
| dp1[i][0] = min(
dp[i - 1][0] + 這一組0的數量,
dp[i - 1][0] + 這一組0的數量
);
|
用上面的轉移方程把正反向都求了一遍之後，我們就可以求總答案了，總答案就是我們枚舉中間只有操作1的段的首尾，加上該中間段前部分的 dp 答案和其後部分的 dp 答案，取出最小值就是了。
cpp1
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
| class FlippingBitsDiv2
{
public:
int getmin(vector <string> S, int M);
string str;
int group;
int tn1[2600], tnsum1[2600];
int tn2[2600], tnsum2[2600];
int dp1[2600][2];
int dp2[2600][2];
int calcsum(int l, int r)
{
if(l > r) return 0;
int tot = tnsum1[r] - tnsum1[l - 1];
return tot;
}
};
int FlippingBitsDiv2::getmin(vector <string> S, int M)
{
str = "";
for(int i = 0; i < SIZE(S); i++) str += S[i];
group = LENGTH(str) / M;
ZERO(tn1);
ZERO(tn2);
// init.
for(int i = 0; i < group; i++)
{
int op = i * M;
int ed = op + M;
for(int j = op; j < ed; j++)
{
if(str[j] == '0') tn1[i]++, tn2[group - i - 1]++;
}
dp1[i][0] = 100000;
dp1[i][1] = 100000;
dp2[i][0] = 100000;
dp2[i][1] = 100000;
}
// tnsum
for(int i = 0; i < group; i++)
{
if(i == 0) tnsum1[0] = tn1[0], tnsum2[0] = tn2[0];
else
{
tnsum1[i] = tnsum1[i - 1] + tn1[i];
tnsum2[i] = tnsum2[i - 1] + tn2[i];
}
}
// dp.
for(int i = 0; i <= group; i++)
{
if(i == 0)
{
dp1[i][0] = dp1[i][1] = dp2[i][0] = dp2[i][1] = 0;
}
else
if(i == 1)
{
// head -> tail
dp1[i][0] = tn1[i - 1];
dp1[i][1] = 1 + (M - tn1[i - 1]);
// tail -> head
dp2[i][0] = tn2[i - 1];
dp2[i][1] = 1 + (M - tn2[i - 1]);
}
else
{
// head -> tail
dp1[i][0] = min(
dp1[i - 1][0] + tn1[i - 1],
dp1[i - 1][1] + tn1[i - 1]
);
dp1[i][1] = min(
dp1[i - 1][0] + 2 + (M - tn1[i - 1]),
dp1[i - 1][1] + (M - tn1[i - 1])
);
// tail -> head
dp2[i][0] = min(
dp2[i - 1][0] + tn2[i - 1],
dp2[i - 1][1] + tn2[i - 1]
);
dp2[i][1] = min(
dp2[i - 1][0] + 2 + (M - tn2[i - 1]),
dp2[i - 1][1] + (M - tn2[i - 1])
);
}
}
int minans = 100000000;
for(int i = 0; i <= group; i++)
{
for(int j = 0; j <= group - i; j++)
{
int zzl = i;
int zzr = group - j - 1;
minans = min(minans,
min(dp1[i][0], dp1[i][1]) +
min(dp2[j][0], dp2[j][1]) +
calcsum(zzl, zzr)
);
}
}
return minans;
}
|