[题解] [文化课] 五一作业T22

神题

已知各项均为正数的数列$\lbrace an \rbrace$满足$a{n +1}^2 = 2a_{n}^2 + an a{n +1}$,且$a_2 + a_4 = 2a_3 + 4$,其中$n \in N^*$。

$(1)$ 求数列$\lbrace a_n \rbrace$的通项公式;

$(2)$ 设数列$\lbrace b_n \rbrace$满足$b_n = \frac{na_n}{(2n +1)a^n}$,是否存在正整数$n, m (1 < m < n)$ 使得$b_1, b_m, b_n$成等比数列,若存在,求出所有$m, n$的值,若不存在,请说明理由。

$(3)$ 令$cn = \frac{(n +1)^2 + 1}{n(n +1)(a{n +2})}$,记数列$\lbrace c_n \rbrace$的前n项和为$S_n$,其中$n \in N^*$,证明$\frac{5}{16} \leq S_n < \frac{1}{2}$。

明天发题解

1
2
3
4
5
6
7
8
9
# 神题

已知各项均为正数的数列$\lbrace a_n \rbrace$满足$a_{n +1}^2 = 2a_{n}^2 + a_n a_{n +1}$,且$a_2 + a_4 = 2a_3 + 4$,其中$n \in N^*$。

$(1)$ 求数列$\lbrace a_n \rbrace$的通项公式;

$(2)$ 设数列$\lbrace b_n \rbrace$满足$b_n = \frac{na_n}{(2n +1)a^n}$,是否存在正整数$n, m (1 < m < n)$ 使得$b_1, b_m, b_n$成等比数列,若存在,求出所有$m, n$的值,若不存在,请说明理由。

$(3)$ 令$c_n = \frac{(n +1)^2 + 1}{n(n +1)(a_{n +2})}$,记数列$\lbrace c_n \rbrace$的前n项和为$S_n$,其中$n \in N^*$,证明$\frac{5}{16} \leq S_n < \frac{1}{2}$。

[题解] 五一节刷题集合

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;
}

[题解] 2018-4-5学习

https://www.luogu.org/problemnew/show/P1879

运算符优先级害死人…

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

using namespace std;

namespace CORNFIELDS
{
const int maxn = 12;
int m, n, a[maxn + 1][maxn], l[maxn + 1], f[maxn + 1][1 << maxn];
vector<int> p;

inline void solve()
{
cin >> m >> n;
for (int i = 0; i < m; ++i)
for (int j = 0; j < n; ++j)
cin >> a[i][j];

for (int i = 0; i < m; ++i)
for (int j = 0; j < n; ++j)
if(a[i][j]) l[i] |= (1 << j);

for (int i = 0; i < (1 << n); ++i)
{
bool flag = true;
for (int j = 0; j < n - 1; ++j)
if(i & (1 << j) && i & (1 << j + 1)) flag = false, j = n;
if(flag) p.push_back(i);
}

for (int j = 0; j < (1 << n); ++j) f[0][j] = 1;

for (int i = 0; i < m; ++i)
for (int j = 0; j < p.size(); ++j)
if((l[i] & p[j]) == p[j])
for (int k = 0; k < p.size(); ++k)
if(((l[i + 1] & p[k]) == p[k]) && ((p[k] & p[j]) == 0))
f[i + 1][p[k]] = (f[i + 1][p[k]] + f[i][p[j]]) % 100000000;
int ans = 0;
for (int i = 0; i < (1 << n); ++i) {
ans = (ans + f[m][i]) % 100000000;
}
cout << ans << endl;
}
}

int main()
{
cin.tie(0);
ios::sync_with_stdio(false);
CORNFIELDS::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步最短路的用矩阵快速幂解的?)