寒假训练——第三周（递推公式）

A - 约瑟夫环

A - 约瑟夫环

思路：

• 推公式

推公式步骤：

1. 设 $f[n][m]$ 为 问题为 “ 总人数为 $n$ ，第 $m$ 个人出列 ” 的胜利者在 $n$ 中的编号
2. 当一个人出列过后，将之前的人移动到数组的末尾，问题转化为 $f[n-1][m]$
3. 求子问题 $f[n-1][m]$ 与 $f[n][m]$ 的关系

举例：f[11][3] = 7

按照如上步骤模拟如图所示：

其中：
绿色数字为 $0$ 开头的数组下标，因为 过程要取模 ( % ) 如此比较清楚
红色为每次出列的数字，每出列一个数字，我们就进行下一次出列的排序
最后一行的 7 为胜利的人， 即、$f[11][3]$ = 6（数组下标为 0 开始）

可知递推公式为：f[n][m] = (f[n-1][m] + m) % n

引入及解释：

问题一： 我们已经知道 f[11][3] = 6那么 f[10][3]= ?

答： 我们知道第一次删去下标为 3 的数后，之后的所有数都向前移动了 3 位，胜利者的位置也向前移动了 3 个位置，所以 f[10][3] = 3

问题二： 假设我们已经知道 f[10][3] = 3如何求出 f[11][3]= ?

答： 此问题显然为 问题一 的逆，所以 f[11][3] = f[10][3] + 3，为保证数组不越界 f[11][3] = (f[10][3] + 3) % 11，转化为字符表示：f[n][m] = (f[n-1][m] + m]) % n

总体代码如下：

#include 

#define fast ios::sync_with_stdio(false), cin.tie(nullptr); cout.tie(nullptr)

#define x first
#define y second
#define int long long

using namespace std;

typedef long long LL;
typedef pair<int, int> PII;

const int N = 2010, M = 1010;
const int mod = 1e9 + 7;
const int INF = 0x3f3f3f3f;
const double eps = 1e-9;

int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};

int n, m;

void solve()
{
    cin >> n >> m;
    
    int p = 0;
    for (int i = 1; i <= n; i ++ )
        p = (p + m) % i;
    
    cout << p + 1 << endl;
    
    return;
}

signed main()
{
    //fast;
    int T = 1;
    //cin >> T;
    while(T -- )
        solve();
    
    return 0;
}
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

---

B - 不容易系列之一

B - 不容易系列之一

思路：

• 推公式（有点像 $DP$)

公式为：f[n] = (n-1) * (f[n-1] + f[n-2])

解释：

• 第 $i$ 位 为其他数，有 $i-1$ 种可能, 此位置上的数为 $t$
• 若 $t$ 位置上的数为 $i$，则 剩余 $i-2$ 个位置的 错排 $(f[i-2])$
• 若 $t$ 位置上的数为 不为 $i$, 则剩余 $i-1$ 个位置的 错排( $f[i-1]$)

代码如下：

//#include 
#include 
#include 
#include 

#define fast ios::sync_with_stdio(false), cin.tie(nullptr); cout.tie(nullptr)

#define x first
#define y second
#define int long long

using namespace std;

typedef long long LL;
typedef pair<int, int> PII;

const int mod = 1e9 + 7;
const int INF = 0x3f3f3f3f;
const double eps = 1e-9;

const int N = 50, M = 1010;

const int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};

int n, m;

void solve()
{
    int f[N];
    
    f[0] = f[1] = 0, f[2] = 1;
    for (int i = 3; i <= n; i ++ )
        f[i] = (i - 1) * (f[i - 1] + f[i - 2]);
    
    // 第 i 位 为其他数，有 i-1 种可能, 此位置上的数为 t
    // 若 t 位置上的数为 i，则 剩余 i-2 个位置的 错排 (f[i-2])
    // 若 t 位置上的数为 不为 i, 则剩余 i-1 个位置的 错排(f[i-1])
    
    cout << f[n] << endl;
    
    return;
}

signed main()
{
    //fast;
    int T = 1;
    //cin >> T;
    while(cin >> n)
        solve();
    
    return 0;
}
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

---

C - 骨牌铺方格

C - 骨牌铺方格

思路：

• 推公式

公式：f[i] = f[i-1] + f[i-2]

公式解释：

• 分情况，$DP$
• f[i-1]为删去最后一排
• f[i-2]为删去最后两排

代码如下：

//#include 
#include 
#include 
#include 

#define fast ios::sync_with_stdio(false), cin.tie(nullptr); cout.tie(nullptr)

#define x first
#define y second
#define int long long

using namespace std;

typedef long long LL;
typedef pair<int, int> PII;

const int mod = 1e9 + 7;
const int INF = 0x3f3f3f3f;
const double eps = 1e-9;

const int N = 60, M = 1010;

const int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};

int n, m;
int f[N];

void init()
{
    f[0] = 0, f[1] = 1, f[2] = 2;
    for (int i = 3; i <= 55; i ++ )
        f[i] = f[i - 2] + f[i - 1];
}

signed main()
{
    //fast;
    int T = 1;
    //cin >> T;
    
    init();
    
    while(cin >> n)
        cout << f[n] << endl;
    
    return 0;
}
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

---

D - Logical Expression

D - Logical Expression

思路：

• 设每一步操作为 op[i]
  可知：
  y[0] = x[0]
y[1] = y[0] op1 x[1] = x[0] op[1] x[1]
y[2] = y[1] op2 x[2] = x[0] op1 x[1] op2 x[2]
  …
  综上
  y[n] = x[0] op1 x[1] op2 x[2] … x[n-1] opn x[n]
  要使y[n]=1，只需让n+1个x相运算为1

• 假设已经有了n个x组成的序列，这时候输入了opn

• 如果opn是AND，也就是说整个运算的最后一步是与运算，所以最后一位就必须是1，总方案数没有增加；

• 如果opn是OR，也就是说运算的最后一步是或运算，那么，如果x[n]为0，总方案数没有增加，如果x[n]为1，那么前面n个x可以任取，总方案数就增加2n个。

代码如下：

//#include 
#include 
#include 
#include 

#define fast ios::sync_with_stdio(false), cin.tie(nullptr); cout.tie(nullptr)

#define x first
#define y second
#define int long long

using namespace std;

typedef long long LL;
typedef pair<int, int> PII;

const int mod = 1e9 + 7;
const int INF = 0x3f3f3f3f;
const double eps = 1e-9;

const int N = 60, M = 1010;

const int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};

int n, m;

void solve()
{
    cin >> n;
    int res = 1;
    string s;
    for (int i = 1; i <= n; i ++ )
    {
        cin >> s;
        if(s == "OR") res += (LL)1 << i;
    }
    
    cout << res << endl;
    
    return;
}

signed main()
{
    //fast;
    int T = 1;
    //cin >> T;
    
    while(T -- )
        solve();
    
    return 0;
}
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