同济大学20年网络赛题解（部分）

发表于 | 分类于 | 本文总阅读量 次
字数统计: 7.5k 字 | 阅读时长 ≈ 32 分钟

20年网络赛题解，有些题太菜了都还没有看，所以就不补了（哭），主要是补前六道题

A.张老师和菜哭武的游戏

题目描述

天才程序员菜哭武和张老师有一天到一个城市旅游，旅途中菜哭武觉得无聊就想和张老师玩一个游戏。菜哭武有n个石子，每个石子都标有1到n之间的数，且各不相同，一开始他们会随机从这堆石子选一个石子放置到一个集合中，张老师选的数是a，菜哭武选的是b（a和b不相同）。接下来菜哭武和张老师轮流按照如下规则拿走一个石子：当石子x能被拿走时，当且仅当集合存在y和z，满足x等于y+z或者y-z，当x被拿走时，把它放到集合中。谁完成最后一轮操作时，谁获胜。张老师总是先手，于是张老师就好奇当决定好a和b时，他是否总是能获胜，你能帮助一下张老师吗？

输入

第一行一个整数T（1≤T≤500），表示共有T组测试数据
对于每组测试数据，第一行三个整数n（2≤n≤20000）、a和b（1≤a,b≤n,a≠b）

输出

若张老师能获胜输出Yes，反之No

样例输入

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
16
2 1 2
3 1 3
67 1 2
100 1 2
8 6 8
9 6 8
10 6 8
11 6 8
12 6 8
13 6 8
14 6 8
15 6 8
16 6 8
1314 6 8
1994 1 13
1994 7 12

样例输出

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
No
Yes
Yes
No
No
No
Yes
Yes
No
No
Yes
Yes
No
Yes
No
No

思路

一开始做这道题的时候其实是没有什么思路的，所以就先跳过了，后面第三道才开始看这道题，其实这是一道还蛮典型的裴蜀定理的题目。

首先，我们可以按照这个题目模拟一下，一开始谁选a，选b无所谓，反正集合里是有a，b两个数，之后我们考虑一下他们能组成的其他可以入选的数字有谁，可以发现有：a-b，a+b，b-a。

现在集合里有这5个数啦，然后我们接着考虑这5个数能组成的其他数，可以发现在这个衍生过程中，a+b可以加b，再加b，也可以加a，再加a，同理，减法也是一样的，也就是说，在给定a，b后，剩下可以拿到的数是所有任意个a与任意个b的线性组合，即可以取到的数p，需要满足p=xa+yb，由裴蜀定理可知，该方程有解一定有p为gcd(a,b)的整数倍。即可取到的数为gcd(a,b)，2*gcd(a,b)，一直到给定的最大数n为止。

由于张老师始终是先手，故张老师一定是取的奇数位的数字，即取第1个数字，第3个数字等等（要不要减去一开始放进去的两个数都一样，因为只需要判断奇偶性），因此只需要判断能取到的数的个数的奇偶，即n/gcd(a,b)的奇偶就可以。

另：我们也考虑最小的数，该数显然需要大于等于1，然后可以发现是取a-b，b-a，a-2b…中的最小值，发现这和辗转相除法很像，最小的数应该是gcd(a,b)，之后其他的数每次最小加减一个gcd(a,b)，所以可以发现其他的数都是gcd(a,b)的倍数，这样半猜的方式也能得到答案。

代码

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
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int main()
{
    ios::sync_with_stdio(0);
    int t;
    cin >> t;
    int a, b, n;
    for (int i = 0; i < t; i++)
    {
        cin >> n >> a >> b;
        int gcd=__gcd(a,b);
        int ans=n/gcd;
        if(ans%2)
        {
            cout<<"Yes"<<'\n';
        }
        else
        {
            cout<<"No"<<'\n';
        }
        
    }
    return 0;
}

B.伤害计算

题目描述

勇士菜哭武获得了一把新的武器，武器有特殊的伤害计算方式。武器的伤害计算方式由若干个部分的和组成，用+号连接。每一部分可以是一个整数a，或者是一个公式ndx。其中a表示固定伤害a点；ndx表示掷n个x面骰子，伤害是所有骰子点数的和。总伤害是每一部分伤害的和。
比如2d6+1d70+3，表示掷两个6面骰子和一个70面骰子（不一定实际存在70面骰子，可以理解成1到70当中随机选择一个整数），再加上固定伤害3点。
他正准备挑选一把好武器，需要计算新武器的伤害期望值，想让你帮他计算一下。

输入

输入一个字符串，表示伤害计算公式。字符串长度不超过5000，对于每一个部分，1≤a, n, x ≤1000。a,n,x都是整数。

输出

输出一个数，表示伤害的期望值。如果不是整数，小数点后位数保留最少，即最终结果只有可能是整数或者小数点后是.5的形式，如果不是整数，那么保留一位小数。

样例输入

1
1d6+1d70+1d10+6

样例输出

1
50.5

思路

字符串解析，也是我的第一道题，对于一个n点的骰子，一共有n种等概率的取法，每种的值依次是1，2…n。因此期望为

∑i=1nnn=1n∗n∗(n+1)2=n+12\frac{\sum_{i=1}^nn}{n}=\frac{1}{n}*\frac{n*(n+1)}{2}=\frac{n+1}{2}

故对xdy来说，其值应该表示为x∗y+12x*\frac{y+1}{2}，对于单独数字直接加上即可。

需要注意的是，首先，在多次浮点计数时可能产生误差，导致输出值不是.5，需要自己处理一下，另外，浮点大数在输出时，很容易输出成科学计数法的形式，导致结果的格式不对，自己就是一开始因为这个WA了三次，貌似之前也被这个东西坑过，今后也一定要注意，要转换成整数输出。题解的话是直接乘二倍判断奇偶输出.5，从而避免了浮点输出的问题，也是很聪明的做法。

代码

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
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int main()
{
    ios::sync_with_stdio(0);
    string st;
    cin >> st;
    double ans = 0;
    int n1 = 0, n2 = 0;
    int flag = 1;
    for (int i = 0; i < (int)st.size(); i++)
    {
        if (st[i] == '+')
        {
            if (flag == 1)
            {
                ans += n1;
            }
            else if (flag == 2)
            {
                ans += n1 * (n2 + 1) / 2.0;
            }
            n1 = n2 = 0;
            flag = 1;
        }
        else if (isdigit(st[i]))
        {
            if (flag == 1)
            {
                n1 *= 10;
                n1 += st[i] - '0';
            }
            else if (flag == 2)
            {
                n2 *= 10;
                n2 += st[i] - '0';
            }
        }
        else if (st[i] == 'd')
        {
            flag = 2;
        }
    }
    if (flag == 1)
    {
        ans += n1;
    }
    else if (flag == 2)
    {
        ans += n1 * (n2 + 1) / 2.0;
    }
    if (fabs(ans - (long long)(ans) - 0.5) < 1e-1)
        cout << (long long)(ans) << '.' << 5;
    else
        cout << (long long)ans;
    return 0;
}

C.张老师的旅行

题目描述

张老师到了一个王国去旅游，王国有n个景点，张老师到达这个城市所在的车站恰好位于第x个景点，这个王国非常特别，恰好所有著名的景点都在分布在直线上，每个景点在坐标pi上(单位：公里)，张老师身体非常好，每走一公里花费一分钟。每个景点都有一个打卡点，并且必须在不迟于相应的时间（时间从张老师到达王国开始计算）前到达才能打卡成功并且给以一个打卡标记，集齐所这些标记就能获得一个大礼包。由于张老师非常想要大礼包，并且因为张老师还着急去下一个王国旅游，所以张老师希望用的时间尽量少，你能帮帮张老师吗？

输入

输入的第一行，包含一个整数n（1≤n≤1000）
第二行包含n个整数pi(1≤pi≤100000)，第i个整数pi为第i个景点的坐标（坐标从小到大排列）
最后一行包含n个整数ti(0≤ti≤10,000,000)，ti表示第i个景点最迟到达的时间，时间为0则表示张老师所在车站的位置且只有一个为0

输出

输出所需的最少时间，若无解输出-1

样例输入

1
2
3
4
1 2 3 4
0 1 2 3

样例输出

1
3

思路

首先，我们遇到这种题肯定先考虑贪心，考虑优先去ddl近的？貌似保证不了时间最短，考虑去最近的？貌似不能保证ddl。其实不难发现这是个多要素的最优化问题，而且观察一下数据范围，10310^3，看起来是个O(n2)\Omicron(n^2)的算法，其实就不难想到应该去用动态规划求解。（比赛时也没有想到，还是做的题太少了）。

接下来我们考虑一下怎么dp，（参照了题解的做法，不过题解说的好简短）我们可以定义状态dp[l][r][x]dp[l][r][x]，表示走完第l个景点到第r个景点这个区间内的所有节点的最短时间，x=0表示停在第l个景点，x=1表示停在第r个景点，因为要走过一个区间内的所有景点，最短的走法一定是会停在边界，这个就不说明了，可以想一想。

对于这个状态我们来进行分析对于一段区间l-r，我们想要继续拓展周围的节点，很显然的只能去拓展l-1或者r+1号景点，如果去拓展l-1号景点，那么最优的情况一定是停在l-1号景点。从l-r推到(l-1)-r，我们需要考虑他是从第l号景点走过来，还是从第r号景点走过来，因为第l号景点走过来虽然近，但是可能dp[l][r][0]dp[l][r][0]的值要比dp[l][r][1]dp[l][r][1]的值大，所以我们需要取它们的最小值。从l号景点走过来的距离是p[l]−p[l−1]p[l]-p[l-1]，从r号景点走过来的距离是p[r]−p[l−1]p[r]-p[l-1]，注意题目告诉的是坐标轴坐标，距离需要去减一下，所以向左递推的方程为

dp[l−1][r][0]=min(dp[l−1][r][0],dp[l][r][0]+p[l]−p[l−1],dp[l][r][1]+p[r]−p[l−1])dp[l-1][r][0]=min(dp[l-1][r][0],dp[l][r][0]+p[l]-p[l-1],dp[l][r][1]+p[r]-p[l-1])

向右递推同理，注意这次最优一定是恰好走到r+1号景点，所以此时x=1，注意一些细节的调整，方程为

dp[l][r+1][1]=min(dp[l][r+1][1],dp[l][r][0]+p[r+1]−p[l],dp[l][r][1]+p[r+1]−p[r])dp[l][r+1][1]=min(dp[l][r+1][1],dp[l][r][0]+p[r+1]-p[l],dp[l][r][1]+p[r+1]-p[r])

所以，最后的结果就是min(dp[1][n][0],dp[1][n][1])min(dp[1][n][0],dp[1][n][1])。

得到了递推方程，接下来我们考虑一下代码怎么写，这也是我看了题解以后纠结了半天的地方，我们发现，这个递推方程，是从中间，向左推，又向右推，所以不能直接暴力上个二重循环，写代码时需要保证递推时的式子是前面已经得到的。

首先，我们可以找到时间为0的位置init_poi（简称ip），表示这是起点，之后，我们可以从这个起点，向右递推，向左递推，即计算dp[ip][ip+1][1]，dp[ip][ip+2][1]...dp[ip][n][1]dp[ip][ip+1][1]，dp[ip][ip+2][1]...dp[ip][n][1]以及dp[ip−1][ip][0]...dp[1][ip][0]dp[ip-1][ip][0]...dp[1][ip][0]。

得到从起始点开始向左向右的数据后，我们考虑剩下数据的递推。依旧是从起始点出发，向左，我们需要计算出dp[ip−1][ip+1][0],dp[ip−1][ip+2][0]dp[ip-1][ip+1][0],dp[ip-1][ip+2][0]等等，一直计算到dp[1][n−1][0],dp[1][n][0]dp[1][n-1][0],dp[1][n][0]，可以知道我们可以用二重循环实现，第一重枚举左端点，第二重枚举右端点。同时，也需要向右计算，推出dp[ip−1][ip+1][1],dp[ip−2][ip+1][1]...dp[2][n][1],dp[1][n][1]dp[ip-1][ip+1][1],dp[ip-2][ip+1][1]...dp[2][n][1],dp[1][n][1]。最后取结果就可以。

不过要注意，目前我们只计算了最小的时间，而没有考虑ddl的问题，即其中的某些方案是否可行，因此，我们在每次递推到第i个景点时，都要考虑一下这个方案的时间是不是比ddl小，如果小，我们才采纳。

还有就是一些细节问题，一开始要初始化为一个极大值，之后dp[ip][ip][0]dp[ip][ip][0]和dp[ip][ip][1]dp[ip][ip][1]要置为0，最后如果发现dp[1][n][0]dp[1][n][0]和dp[1][n][1]dp[1][n][1]的值都是极大值，说明没有可行方案，输出-1。

代码

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
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int n;
const int maxn = 1010;
int poi[maxn];
int t[maxn];
int dp[maxn][maxn][2];
int main()
{
    ios::sync_with_stdio(0);
    memset(dp, 0x3f, sizeof(dp));
    cin >> n;
    int poi_0 = 0;
    for (int i = 1; i <= n; i++)
    {
        cin >> poi[i];
    }
    for (int i = 1; i <= n; i++)
    {
        cin >> t[i];
        if (t[i] == 0)
        {
            poi_0 = i;
        }
    }
    dp[poi_0][poi_0][0] = 0;
    dp[poi_0][poi_0][1] = 0;
    for (int l = poi_0; l - 1 >= 1; l--)
    {
        if (dp[l][poi_0][0] + poi[l] - poi[l - 1] <= t[l - 1])
            dp[l - 1][poi_0][0] = min(dp[l - 1][poi_0][0], dp[l][poi_0][0] + poi[l] - poi[l - 1]);
        if (dp[l][poi_0][1] + poi[poi_0] - poi[l - 1] <= t[l - 1])
            dp[l - 1][poi_0][0] = min(dp[l - 1][poi_0][0], dp[l][poi_0][1] + poi[poi_0] - poi[l - 1]);
    }
    for (int r = poi_0; r + 1 <= n; r++)
    {
        if (dp[poi_0][r][1] + poi[r + 1] - poi[r] <= t[r + 1])
            dp[poi_0][r + 1][1] = min(dp[poi_0][r + 1][1], dp[poi_0][r][1] + poi[r + 1] - poi[r]);
        if (dp[poi_0][r][0] + poi[r + 1] - poi[poi_0] <= t[r + 1])
            dp[poi_0][r + 1][1] = min(dp[poi_0][r + 1][1], dp[poi_0][r][0] + poi[r + 1] - poi[poi_0]);
    }
    for (int l = poi_0; l - 1 >= 1; l--)
    {
        for (int r = poi_0; r <= n; r++)
        {
            if (dp[l][r][0] + poi[l] - poi[l - 1] <= t[l - 1])
                dp[l - 1][r][0] = min(dp[l - 1][r][0], dp[l][r][0] + poi[l] - poi[l - 1]);
            if (dp[l][r][1] + poi[r] - poi[l - 1] <= t[l - 1])
                dp[l - 1][r][0] = min(dp[l - 1][r][0], dp[l][r][1] + poi[r] - poi[l - 1]);
        }
    }
    for (int r = poi_0; r + 1 <= n; r++)
    {
        for (int l = poi_0; l >= 1; l--)
        {
            if (dp[l][r][1] + poi[r + 1] - poi[r] <= t[r + 1])
                dp[l][r + 1][1] = min(dp[l][r + 1][1], dp[l][r][1] + poi[r + 1] - poi[r]);
            if (dp[l][r][0] + poi[r + 1] - poi[l] <= t[r + 1])
                dp[l][r + 1][1] = min(dp[l][r + 1][1], dp[l][r][0] + poi[r + 1] - poi[l]);
        }
    }
    if (min(dp[1][n][0], dp[1][n][1]) == 0x3f3f3f3f)
    {
        cout << -1;
    }
    else
        cout << min(dp[1][n][0], dp[1][n][1]);
    return 0;
}

D.车辆调度

题目描述

张老师设计了一个智能调度系统来控制他的遥控车队，今天，他带着他的车队来到黄渡理工大学的一块空地上测试这个系统。
这块空地可以描述为一个 w * h 大小的长方形，广场上有一些障碍物，几个目标点，当然，还有张老师的车队。
每分钟，调度系统会智能地向其中的一辆遥控车发送以下指令的其中一条：

  1. 向北走，直到撞到空地的边界、障碍物或其他遥控车；
  2. 向南走，直到撞到空地的边界、障碍物或其他遥控车；
  3. 向西走，直到撞到空地的边界、障碍物或其他遥控车；
  4. 向东走，直到撞到空地的边界、障碍物或其他遥控车；

每条指令都会在一分钟之内完成，也就是说，空地上最多只有一辆遥控车在运动。此外，当遥控车无法向相应的方向移动时，它会停在原地。

你想知道，在第 k 分钟时，有没有可能有任意一辆遥控车处在任意一个目标点上。

输入

第一行输入三个数字 w, h, k (1 ≤ w, h ≤ 10, 1 ≤ k ≤ 5) , 含义在题目描述中已给出。
接下来 h 行，每行输入一个长度为 w 的字符串 si，其中第i行的第j个字符表示(i, j)位置的状态。
其中，‘R’ 代表该位置初始有一辆遥控车，‘X’ 代表该位置有障碍物，‘D’ 代表该位置是一个目标点，’.’ 代表该位置可以正常通过。
数据保证广场上的遥控车不超过4辆。

输出

如果k分钟后有可能有任意一个遥控车处在任意一个目标点上，输出 “YES”, 否则输出 “NO”

样例输入

1
2
3
4
5
6
6 5 4
.....R
...X..
..D...
....D.
R.R...

样例输出

1
YES

提示

样例1中，遥控车可以按下述路线移动：

1
2
3
4
5
.....R
...X..
..D...
....D.
R.R...
1
2
3
4
5
R.....
...X..
..D...
....D.
R.R...
1
2
3
4
5
R.....
R..X..
..D...
....D.
..R...
1
2
3
4
5
R.....
..RX..
..D...
....D.
..R...
1
2
3
4
5
R.....
..RX..
..R...
....D.
......

4分钟时，有一辆遥控车达到了目标点。于是输出"YES"

思路

首先，观察数据，发现这个数据量很小，另外，如果在原题上看，可以发现该题的时限有5s，说明大概是指数级别的复杂度，可以知道该题就是去暴搜。

每一步枚举每一辆小车，每一辆小车再枚举每一个方向，即可。

需要注意的是，如果一辆车在时间t(t<k)时已经到达了目的地，那么就可以直接输出yes，而不必一定要在时间k再输出。因为该车能在t时刻到达一个目的地，那么它一定是朝着x方向一直走，碰到障碍物了，才能到达这个目的地，那么我们后面在t+1，t+2时刻仍然可以朝着x方向走，这样小车就会停在原地不动，一直到k时刻，因此前面只要搜到了，直接输出yes，退出就可以。

另外，注意计算到底是搜索到第几层，边界条件的计算，自己就是因为多搜索了一层，而导致浪费了一个半小时，最后还没调出来。

代码

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
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int w, h, k;
struct node
{
    char mm[11][11];
    int c_x[5];
    int c_y[5];

    node()
    {
        memset(c_x, 0, sizeof(c_x));
        memset(c_y, 0, sizeof(c_y));
    }
    node(const node &a)
    {
        for (int i = 1; i <= h; i++)
        {
            for (int j = 1; j <= w; j++)
            {
                mm[i][j] = a.mm[i][j];
            }
        }
        for (int i = 0; i < 5; i++)
        {
            c_x[i] = a.c_x[i];
            c_y[i] = a.c_y[i];
        }
    }
};
const int y_move[] = {-1, 1, 0, 0};
const int x_move[] = {0, 0, 1, -1};
void dfs(int t, node sta)
{
    for (int i = 1; i < 5 && sta.c_x[i] != 0; i++)
    {
        for (int j = 0; j < 4; j++)
        {
            int yy = sta.c_y[i];
            int xx = sta.c_x[i];
            while (1)
            {
                yy += y_move[j];
                xx += x_move[j];
                if (!(xx >= 1 && xx <= w && yy >= 1 && yy <= h && sta.mm[yy][xx] != 'X' && sta.mm[yy][xx] != 'R'))
                {
                    yy -= y_move[j];
                    xx -= x_move[j];
                    if (sta.mm[yy][xx] == 'D')
                    {
                        cout << "YES";
                        exit(0);
                    }
                    node tem = sta;
                    tem.mm[sta.c_y[i]][sta.c_x[i]] = '.';
                    tem.mm[yy][xx] = 'R';
                    tem.c_y[i] = yy;
                    tem.c_x[i] = xx;
                    if (t < k)
                    {
                        dfs(t + 1, tem);
                    }
                    break;
                }
            }
        }
    }
}

int main()
{
    ios::sync_with_stdio(0);
    cin >> w >> h >> k;
    node sta;
    int p_r = 1;
    for (int i = 1; i <= h; i++)
    {
        for (int j = 1; j <= w; j++)
        {
            cin >> sta.mm[i][j];
            if (sta.mm[i][j] == 'R')
            {
                sta.c_y[p_r] = i;
                sta.c_x[p_r] = j;
                p_r++;
            }
        }
    }
    dfs(1, sta);
    cout << "NO";
    return 0;
}

E.弦

题目描述

给定一个圆，圆上有2N个互不重叠的点。每次操作随机选择两个先前未选择过的点连一条弦，共连成N条弦，求所有弦不交的概率。

输入

一行，只有一个整数N（1≤N≤10710^7）

输出

一行，即答案。答案应以模10910^9+7的形式输出。正式地说，令M=10910^9+7， 答案可以表示为最简分数p/q的形式，其中p和q为整数且q与M互质。输出整数x满足 0≤x<M且 x⋅q ≡ p（mod M）。

样例输入

1
2

样例输出

1
666666672

思路

其实这是一道很典型的卡特兰数的题，甚至在百度百科上都能搜到（不是）。我们可以通过计算总的方案数与可行方案数，然后做比来得出结果。接下来考虑两种方案数如何计算。

总的方案数：首先，我们可以考虑取两个点px，py，可以选择的方案数是C2n2C_{2n}^2，接着考虑再取两个点，pm，pn，可以选择的方案数是C2n−222\frac{C_{2n-2}^2}{2}。注意这里有一个除2，可以考虑一下，当任取两个点时，都有px，py与pm，pn交换的取法，即x=1，y=2，m=3，n=4以及x=3，y=4，m=1，n=2这两种取法，12与34被取到的顺序不一样，会被我们算作两种取法，但是实际上这是两种完全相同的取法，因此需要除2。同理，接着考虑，再去两个点时，应该要乘C2n−423\frac{C_{2n-4}^2}{3}。注意这里是除3，对于第三次取到的点p，q，除了第三次取到p，q以外，包含了第三次取到x，y和第三次取到m，n这两种情况，所以应该除3去重。比如，对于12，34，56这三对点来说，第三次取12，34，56这三种取法在我们C_{2n-4}^2}中都会取到，但起始它们对应的都是12，34，56这种结对方式，所以要除3去重（好像讲的很迷糊）。基于此规律，我们可以知道再往后，每次取都要除4，除5等等去重，第一次取相当于除1，一直会取n次，所以，总的方案数：

sum(n)=C2n21∗C2n−222∗C2n−423∗...∗C22nsum(n)=\frac{C_{2n}^2}{1}*\frac{C_{2n-2}^2}{2}*\frac{C_{2n-4}^2}{3}*...*\frac{C_{2}^2}{n}

=1n!∗2n∗(2n−1)2∗(2n−2)(2n−3)2...=(2n)!n!∗2n=\frac{1}{n!}*\frac{2n*(2n-1)}{2}*\frac{(2n-2)(2n-3)}{2}...=\frac{(2n)!}{n!*2^n}

接下来考虑可行的方案数，这个其实算一个典型的卡特兰数。对于一个2n个点的情况，我们可以先考虑将所有点依次标号，从1标到2n，之后从点1出发，我们向点k连线，该线会将其他点分成两部分，可以知道，只有两部分的点数量都为偶数时，才可能出现可行的方案，因此k只能取偶数，1-2之间有0个点，另一边有2n-2个点。1-4有2，3两个点，另一边有2n-4个点等等，因此共有n种划线方法，之后对于每一边，我们又能递归的去求解有2i个点和2n-2i-2点的方案数，因此可行的方案数：

sub(2n)=sub(0)∗sub(2n−2)+sub(2)∗sub(2n−4)+...+sub(2n−2)∗sub(0)sub(2n)=sub(0)*sub(2n-2)+sub(2)*sub(2n-4)+...+sub(2n-2)*sub(0)

对于初始情况，sub(0)和sub(2)都是1，因此，可以发现如果把2n换成n，正好就是一个卡特兰数的递推公式，即sub(2n)=f(n)，f(n)表示n层的卡特兰数。故

sub(2n)=f(n)=C2nnn+1sub(2n)=f(n)=\frac{C_{2n}^{n}}{n+1}

故总的概率：

p(2n)=sub(2n)sum(2n)=C2nnn+1∗n!∗2n(2n)!=(2n)!(n+1)!∗n!∗n!∗2n(2n)!=2n(n+1)!p(2n)=\frac{sub(2n)}{sum(2n)}=\frac{C_{2n}^{n}}{n+1}*\frac{n!*2^n}{(2n)!}=\frac{(2n)!}{(n+1)!*n!}*\frac{n!*2^n}{(2n)!}=\frac{2^n}{(n+1)!}

对于计算，记得运算过程中不断取模，另外可以开long long，防止中间运算爆int，2n2^n可以通过快速幂计算，之后分子要计算它在模意义下的逆元，可以利用费马小定理加快速幂计算，也可以使用拓展欧几里得计算，我这里用的是费马小定理。

代码

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
#include <bits/stdc++.h>
using namespace std;
typedef unsigned long long ll;
ll n;
ll ksm(ll b, ll p, ll k)
{
    ll ans = 1;
    while (p > 0)
    {
        if (p & 1)
        {
            ans = ans * b % k;
        }
        b *= b;
        b %= k;
        p >>= 1;
    }
    return ans % k;
}
const ll mod = int(1e9) + 7;
int main()
{
    ios::sync_with_stdio(0);
    cin >> n;
    ll up = ksm(2, n, mod);
    ll down = 1;
    for (int i = 2; i <= n + 1; i++)
    {
        down *= i;
        down %= mod;
    }
    up*=ksm(down,mod-2,mod);
    up%=mod;
    cout<<up;
    return 0;
}

F.排列计算

题目描述

天才程序员菜哭武和石头组队参加一个叫做国际排列计算竞赛 (International Competition of Permutation Calculation, ICPC) 的比赛，这个比赛的规则是这样的：
一个选手给出一个长度为 n 的排列，另一个选手给出 m 个询问，每次询问是一个形如 (l, r) 的数对，查询队友给出的排列中第 l 个数到第 r 个数的和，并将查询到的这个区间和加入总分，最后总分最高的队伍就能获胜。
石头手速很快，在比赛一开始就给出了 m 个询问；菜哭武也很强，他总是能找到最合适的排列，使得他们队的总分尽可能高。
在看比赛直播的你看到了石头给出的 m 个询问，聪明的你能不能预测出他们队伍最终的得分呢？

一个排列是一个长度为 n 的数列，其中 1 ~ n 中的每个数都在数列中恰好出现一次。比如 [1, 3, 2] 是一个排列，而 [2, 1, 4] 和 [1, 2, 3, 3] 不是排列。

输入

第一行输入两个数 n (1≤n≤200000) 和 m (1≤m≤200000) 。
接下来 m 行，每行输入两个数 l 和 r ，代表这次查询排列中第 l 个到第 r 个的和。

输出

输出一个整数，代表他们队伍总分的最大值。

样例输入

1
2
3
4
7 3
1 3
3 7
5 6

样例输出

1
46

提示

一个符合条件的排列是 [1, 3, 6, 4, 7, 5, 2]，于是最终的得分为 (1 + 3 + 6) + (6 + 4 + 7 + 5 + 2) + (7 + 5) = 46

思路

是简单题，也是我第二道去做的题。

题意很简单，对于1到n的序列，有m次询问，每次询问一个区间，使得该区间内的各位置的询问次数+1，之后给序列的每一个位置都放一个1到n之间的数（每个数都只能用一次），之后得分为每个位置的数乘该位置的询问次数的的总和，求该值的最大值。

很容易能够想到，我们每次贪心的去放数，在询问次数最大的位置放值最大的数，可以使结果最大化。接下来就是考虑如何得到各个位置的查询次数。

如果每次都暴力模拟，那么每次都可能以O(n)\Omicron(n)的代价来使一个区间内的所有位置访问次数+1，然后需要操作m次，复杂度为O(nm)\Omicron(nm)，101010^{10}的数据规模我们显然无法接受。

对于区间操作，我们很容易的想到差分，树状数组，线段树等来优化，我们可以发现，本题需要m次区间修改以及最后的1次区间查询，因此直接差分就完全可以解决，维护初始值为0的差分数组，每次修改l到r的区间，相当于arr[l]++，arr[r+1]–，每次操作的代价是O(1)\Omicron(1)，最后对差分数组求前缀和，即可得到每个位置的查询次数，对数组排序，将次数最高的排在最前面，把数字依次从n到1的与次数匹配，统计答案即可，时间复杂度为O(max(m,nlog⁡n))\Omicron(max(m,n\log n))。

代码

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
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int n,m;
const int maxn=200010;
int nn[maxn]={0};
bool cmp(int a,int b)
{
    return a>b;
}
int main()
{
    ios::sync_with_stdio(0);
    cin>>n>>m;
    int l,r;
    
    for(int i=0;i<m;i++)
    {
        cin>>l>>r;
        nn[l]++;
        nn[r+1]--;
    }
    for(int i=1;i<=n;i++)
    {
        nn[i]=nn[i-1]+nn[i];
    }
    sort(nn,nn+n+2,cmp);
    ll ans=0;
    ll now=n;
    for(int i=0;i<n+2;i++)
    {
        if(nn[i]==0)
        {
            break;
        }
        ans+=nn[i]*now;
        now--;
    }
    cout<<ans;
    return 0;
}