[题解] 五一节刷题集合

oi

五一节刷题集合

luogu1005

代码

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
#include <bits/stdc++.h>

using namespace std;

namespace IO
{
inline char read()
{
static const int IN_LEN = 1000000;
static char buf[IN_LEN], *s, *t;
s == t ? t = (s = buf) + fread(buf, 1, IN_LEN, stdin) : 0;
return s == t ? -1 : *s++;
}

template <typename T>
inline void read(T &x)
{
static char c;
static bool iosig;

for (c = read(), iosig = false; !isdigit(c); c = read())
{
if (c == -1) return;
c == '-' ? iosig = true : 0;
}

for (x = 0; isdigit(c); c = read())
x = (x + (x << 2) << 1) + (c ^ '0');

iosig ? x = -x : 0;
}
}

namespace luogu1005
{
const int maxn = 80 + 5;
__int128 f[maxn][maxn], a[maxn][maxn], ans;
int n, m;

inline void put(__int128 val)
{
if(val <= 0) return;
put(val / 10);
putchar(val % 10 + '0');
}

inline void solve()
{
using namespace IO;
// f[i][j] 从行头取i个,从行尾取j个的最大值
read(n); read(m);
for (int i = 1; i <= n; ++i)
for (int j = 1; j <= m; ++j)
read(a[i][j]);

for (int l = 1; l <= n; ++l)
{
memset(f, 0, sizeof(f));
for (int k = 0; k <= m; ++k)
for (int i = 1; i <= m - k; ++i)
f[i][i + k] = max((__int128)(f[i + 1][i + k] + a[l][i]) << 1, (__int128)(f[i][i + k - 1] + a[l][i + k]) << 1);
ans += f[1][m];
}

if(ans == 0) putchar('0');
else put(ans);
}
}

int main()
{
cin.tie(0);
ios::sync_with_stdio(false);

luogu1005::solve();
return 0;
}

luogu1373

代码

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
88
89
90
91
92
93
94
95
96
97
98
99
100
// by kririae
// dp
#include <bits/stdc++.h>

using namespace std;

namespace IO
{
inline char read()
{
static const int IN_LEN = 1000000;
static char buf[IN_LEN], *s, *t;
s == t ? t = (s = buf) + fread(buf, 1, IN_LEN, stdin) : 0;
return s == t ? -1 : *s++;
}

template <typename T>
inline void read(T &x)
{
static char c;
static bool iosig;

for (c = read(), iosig = false; !isdigit(c); c = read())
{
if (c == -1) return;
c == '-' ? iosig = true : 0;
}

for (x = 0; isdigit(c); c = read())
x = (x + (x << 2) << 1) + (c ^ '0');

iosig ? x = -x : 0;
}
}

namespace luogu1373
{
const int maxn = 800 + 3;
const int maxk = 15 + 3;

int n, m, mod, f[maxn][maxn][maxk][2], a[maxn][maxn];

template<typename T>
inline void add(T &a, T &b)
{
a = (a + b) % 1000000007;
}

inline void solve()
{
using namespace IO;
read(n); read(m); read(mod);
++mod;

for (int i = 1; i <= n; ++i)
for (int j = 1; j <= m; ++j)
read(a[i][j]);

for (int i = 1; i <= n; ++i)
for (int j = 1; j <= m; ++j)
for (int k = 0; k <= mod; ++k)
f[i][j][a[i][j] % mod][1] = 1;

// f[i][j][k][1] -> 到达第(i, j)个点,两人魔瓶的差值是k,小a先走的方法
// 同理 f[i][j][k][0]是uim先走的
register int i, j, k;
for (i = 1; i <= n; ++i)
for (j = 1; j <= m; ++j)
for (k = 0; k <= mod; ++k)
{
if(i + 1 <= m)
{
add(f[i + 1][j][(k - a[i + 1][j] + mod) % mod][0], f[i][j][k][1]);
add(f[i + 1][j][(k + a[i + 1][j]) % mod][1], f[i][j][k][0]);
}

if(j + 1 <= n)
{
add(f[i][j + 1][(k - a[i][j + 1] + mod) % mod][0], f[i][j][k][1]);
add(f[i][j + 1][(k + a[i][j + 1]) % mod][1], f[i][j][k][0]);
}
}

int ans = 0;
for (int i = 1; i <= n; ++i)
for (int j = 1; j <= m; ++j)
add(ans, f[i][j][0][0]);

cout << ans % 1000000007<< endl;
}
}

int main()
{
cin.tie(0);
ios::sync_with_stdio(false);

luogu1373::solve();
return 0;
}

luogu1220

代码

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
// by kririae
#include <bits/stdc++.h>

using namespace std;

namespace luogu1220
{
const int maxn = 80 + 5;

int n, from, f[maxn][maxn][2], p[maxn], c[maxn], s[maxn];

inline void solve()
{
memset(f, 0x3f, sizeof(f));

cin >> n >> from;
for (int i = 1; i <= n; ++i)
cin >> p[i] >> c[i], s[i] = s[i - 1] + c[i];

f[from][from][0] = f[from][from][1] = 0;

for (int k = 2; k <= n; ++k)
{
for (int i = 1; i <= n - k + 1; ++i)
{
int j = i + k - 1;
f[i][j][0] = min(f[i + 1][j][1] + (p[j] - p[i]) * (s[i] + s[n] - s[j]), f[i + 1][j][0] + (p[i + 1] - p[i]) * (s[i] + s[n] - s[j]));
f[i][j][1] = min(f[i][j - 1][1] + (p[j] - p[j - 1]) * (s[i - 1] + s[n] - s[j - 1]), f[i][j - 1][0] + (p[j] - p[i]) * (s[i - 1] + s[n] - s[j - 1]));
}
}

cout << min(f[1][n][0], f[1][n][1]) << endl;
}
}

int main()
{
cin.tie(0);
ios::sync_with_stdio(false);

luogu1220::solve();
return 0;
}

[学习笔记] 一点SPFA的随笔

oi

一点SPFA的随笔

大佬勿喷orz…都是些很基础的东西,因为我太菜了

  1. SPFA有一个$O(m\log{n})$的堆优化策略(见魔法猪学院),而且代码很短,应该卡的没那么严重。
  2. SPFA(bfs)可以解决很大一部分状压DP的问题(见软件补丁问题、愤怒的小鸟(需要Ofast优化过)),虽然速度会慢很多,作为下策吧..应该可以骗一半以上的分。
  3. SPFA支持动态加点(详见Poq的魔法森林解法),如果能够可持久化d数组会很爽。
  4. SPFA的queue支持定制,queue中装的是转移,可以当成dp来思考(详见FULL TANK?)(可以解决k短路,k步最短路等等问题(虽然效率不行))(详见魔法猪学院配合A*,还有一个k步最短路的用矩阵快速幂解的?)