总结
成绩：SOLVE：3，Penalty：7
1002
签到题
非常裸的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
| void SINGLE_TEST() {
int n, k;
cin >> n >> k;
vector<int> a(n + 1), b(n + 1), c(n + 1), d(n + 1);
for (int i = 1; i <= n; i++) {
cin >> a[i] >> b[i] >> c[i] >> d[i];
}
vector<int> dp(k + 1, INF);
dp[0] = 0;
for (int id = 1; id <= n; id++) {
for (int i = k; i >= 0; i--) {
if (i - 1 >= 0) {
dp[i] = min(dp[i], dp[i - 1] + a[id]);
}
if (i - 2 >= 0) {
dp[i] = min(dp[i], dp[i - 2] + b[id]);
}
if (i - 3 >= 0) {
dp[i] = min(dp[i], dp[i - 3] + c[id]);
}
if (i - 4 >= 0) {
dp[i] = min(dp[i], dp[i - 4] + d[id]);
}
}
}
cout << dp[k] << "\n";
}
|
1008
根据n的每一位去分类，‘1’有12种，‘0’有4种
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
| void SINGLE_TEST() {
int n, k;
cin >> n >> k;
ll anss = 1;
for (int b = k; b >= 0; b--) {
int t = (n >> b & 1);
ll ans = 0;
if (t == 1) {
ans += 8 + 4;
} else {
ans += 4;
}
anss *= ans;
}
cout << anss / 4 << "\n";
}
|
1001
处理字符串相等时（字符串匹配），不难想到哈希解决
这里我们初步考虑存A的每一个循环串，但是空间太大，利用哈希简化即可
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
| const int P = 1E9 + 7;
void SINGLE_TEST() {
string s, t;
cin >> s >> t;
int n = s.size(), m = t.size();
s = s + s;
vector<ll> h1(2 * n + 1), h2(m + 1);
vector<ll> p1(2 * n + 1), p2(m + 1);
p1[0] = 1;
p2[0] = 1;
for (int i = 1; i <= 2 * n; i++) {
p1[i] = p1[i - 1] * P;
h1[i] = h1[i - 1] * P + s[i - 1];
}
for (int i = 1; i <= m; i++) {
p2[i] = p2[i - 1] * P;
h2[i] = h2[i - 1] * P + t[i - 1];
}
auto get1 = [&](int l, int r) { return h1[r] - h1[l - 1] * p1[r - l + 1]; };
auto get2 = [&](int l, int r) { return h2[r] - h2[l - 1] * p2[r - l + 1]; };
map<int, int> mp;
for (int i = 1; i <= n; i++) {
mp[get1(i, i + n - 1)]++;
}
ll ans = 0;
for (int i = 1; i + n - 1 <= m; i++) {
if (mp.count(get2(i, i + n - 1))) ans++;
}
cout << ans << '\n';
}
|
赛时队友写了KMP的做法，相较于哈希繁杂很多，但也可以通过
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
| void Solve() {
ll ans = 0;
cin >> pat >> txt;
//make next
nxt[0] = -1;
for(ll i = 1, j = -1; i < pat.size(); i ++ ) {
while(j != -1 && pat[i] != pat[j + 1]) j = nxt[j];
if(pat[i] == pat[j + 1]) j ++ ;
nxt[i] = j;
}
vector<ll> pos(txt.size() * 2, 0); // pos为pat最后一位
//kmp
for(ll i = 0, j = -1; i < txt.size(); i ++ ) {
while(j != -1 && txt[i] != pat[j + 1]) j = nxt[j];
if(txt[i] == pat[j + 1]) j ++ ;
if(j == pat.size() - 1) {
// pos[i] = 1;
if(pos[i] != 1) {
ans ++ ;
pos[i] = 1;
}
for(ll k = i + 1; k < txt.size() && k < i + pat.size(); k ++ ) { // 向后匹配
if(txt[k] == pat[k - i - 1]) {
ans ++ ;
pos[k] = 1;
}
else break;
}
for(ll k = i - j - 1, poss = pat.size() - 1; k >= 0 && pos[k + pat.size() - 1] != 1; k --, poss -= 1) { // 向前匹配
if(poss == -1) poss = pat.size() - 1;
if(txt[k] == pat[poss]) ans ++ ;
else break;
}
} else {
if(i < txt.size() - 1 && txt[i + 1] != pat[j + 1] && j != -1 || i == txt.size() - 1) {
bool ff = 0;
ll cnt = 0;
for(ll k = i - j - 1, poss = pat.size() - 1; k >= 0 && pos[k + pat.size() - 1] != 1; k -- , poss -= 1) {
if(poss == -1) poss = pat.size() - 1;
if(txt[k] != pat[poss]) break;
cnt ++ ;
if(cnt + j == pat.size() - 1) {
ans ++ ; ff = 1;
pos[k + pat.size() - 1] = 1;
}
else if(ff) {
ans ++ ;
pos[k + pat.size() - 1] = 1;
}
}
}
}
}
cout << ans << "\n";
}
|