EOJ Monthly 2018.12

比赛地址：https://acm.ecnu.edu.cn/contest/125/

收获

• 新的运行时间认识，1E8？
• 随机数题
• 蒙特卡洛模拟算法
• 多次询问记得避免重复计算

A. 仰望星空

单测试点时限: 2.0 秒

内存限制: 512 MB

你就这样静坐在草地上，离我稍远的地方。
我用眼角瞅着你，你什么话也别说。
语言是误会的根源。
但是，每天，你可以坐得离我近一些……

你和她一起仰头仰望着布满星辰的天空。你的星星对她而言只不过是众星中的一颗。

她会喜欢仰望天际所有的繁星，他们都会是她的朋友。但你深信你不会是万众中一颗毫不起眼的星星。

于是你默默地记录着每天你们仰望星空时的距离，你发现每天你们的距离或许减少、或许不变，但一定不会增加。

可是你们在一起仰望星空的日子太长了，长到你只记得你们第一天在星空下的距离。

今天，你们的距离是 A；你们又在一起仰望星空了。你却突然想知道一起仰望星空 N 天来，你们之间的距离之和。

由于你已经不记得每天的距离，只能依稀记起第一天的距离是 B，所以你只想知道你们这么多天来的距离之和有多少种不同的可能性。

输入
输入数据包含一行，包含三个整数 N,A,B (2≤N≤109,1≤A≤B≤109)，分别表示你们一起仰望星空的天数、今天你们之间的距离以及第一天你们之间的距离。

输出
输出数据包含一行一个整数，表示不同可能和的个数。

样例
input
3 1 2
output
2
提示
对于样例有以下几种不同的距离情况：{2,1,1},{2,2,1}；他们的和分别是 4 和 5，所以有两种不同的和。

思路

已知最大的和最小的，那么和最大的情况一定是除了一个最小的，其余全部是最大的；相反地，和最小的情况一定是除了一个最大的，其余全部都是最小的。
显然，我们可以通过一些调整，取到从和的最小到最大这整个区间里所有的数。

AC

#include <iostream>
#include <cmath>
#include <algorithm>
#include <iomanip>
#include <cstring>
#include <vector>
#include <set>
#include <map>
#define LL long long
#define maxn 10005
using namespace std;

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

    LL N, A, B;
    cin >> N >> A >> B;
    LL maxSum = B * (N - 1) + A;
    LL minSum = A * (N - 1) + B;
    cout << maxSum - minSum + 1 << endl;
	return 0;
}

B. 清点星辰

单测试点时限: 2.0 秒

内存限制: 512 MB

“夜里，
你要抬头仰望满天的星星。
我那颗实在太小了，
我都没法指给你看它在哪儿。”

这样倒也好，我的星星，对你来说就是满天星星中的一颗。

所以，你会爱这满天的星星…所有的星星都会是你的朋友。

即使只能通过狭小的洞口，在楼宇的夹缝中仰望布满星辰的天空，你还是无法割舍对它的期待。

星星数不胜数，但你还是不厌其烦地清点他们。日复一日，终于在今天，你把他们都数清楚了。

于是你又开始找别的事情做了。你开始计算他们两两之间的最近距离。

你仰望星空的洞口是一个 1×1 的正方形，每天，星辰的位置都会发生变化，具体地说，每天都会有 n 个星辰随机地散落在这个正方形内的某个坐标上（每个点横纵坐标满足独立同分布 U(0,1)）。

每天的距离都在变化，所以现在你只想知道他们两两之间最近距离的期望是多少。

输入
输入一个整数 n (2≤n≤109) ，表示星辰的数量。

输出
一行一个小数，输出答案。绝对误差在 10−3 内会被视为正确。

样例
input
2
output
0.521405
input
3
output
0.3055302430

思路

蒙特卡洛模拟算法。
精度要求只有 10−3，显然大的时候可以直接输出 0。
对不是 0 的部分，显然 n 越大答案的方差越小，所以 n 越大需要的生成次数就越小，所以可以直接控制复杂度 1E8 或者运行时间。
那么 n 要多大才可以输出 0 了呢？可以试一试：好像 700 多一点点就可以输出 0 了……

第一次WA了1发，在测试样例的时候误差也超出了1E3的范围，尽量把单次的运行时间卡在边缘，即n越小的时候要模拟次数越多。

AC

#include <bits/stdc++.h>
using namespace std;

int main()
{
    int seed = time(0);
    srand(seed);
    int n;
    const double eps = 1e-3;
    cin >> n;
    if (n > 900) {
        cout << 0 << endl;
        return 0;
    }

    double sumDis = 0;
    int cnt = 1e8 / (n * n);
    for (int i = 0; i < cnt; i++) {
        double x[1005], y[1005];
        for (int j = 0; j < n; j++) {
            x[j] = rand() / (RAND_MAX + 1.0);;
            y[j] = rand() / (RAND_MAX + 1.0);;
            //cout << x[j] << endl;
        }
        double minDis = 100;
        for (int j = 0; j < n; j++) {
            for (int k = j + 1; k < n; k++) {
                double dis = sqrt((x[j] - x[k]) * (x[j] - x[k]) + (y[j] - y[k]) * (y[j] - y[k]));
                if (dis < minDis) minDis = dis;
            }
        }
        sumDis += minDis;
    }
    sumDis /= cnt;
    cout << sumDis << endl;
    return 0;
}

C. 她的名字

单测试点时限: 4.0 秒

内存限制: 512 MB

“他走过一个又一个星球，
却始终放不下对她的思念。“
”深情终究是一趟孤独的旅程，
她是他永远的牵绊。”

我们每个人心中都有一只小狐狸。我们渴望被自己喜欢的人驯服。

爱情是彼此之间至为甜蜜的臣服。我们都是傻痴痴的小狐狸，徒具一副精明的外表。

就像你走到哪都挂念着她，想把她写进自己的歌里，成为你们共同的记忆。

你想从她全部由数字构成的名字里取出其中的 N 个数字，维持原来的顺序，组成结尾为数字 XY 的新词。

你自然希望自己的歌能够很长很长，歌词的每一句都能饱含甜蜜。

所以你想知道，她的名字能够组成多少个长度为 N 且结尾为数字 XY 的新词（如果从她名字中取出的任意一个数字位置不同，两个词就被认为是不同的）。

输入
第一行包含一个由数字构成的字符串 S (1≤|S|≤2 000)。

第二行包含一个整数 Q (1≤Q≤5⋅105)，表示需要选择的不同结尾数量。

接下来的 Q 行，每行包含了一个整数 N (1≤N≤5⋅105) 和两个数字 XY，用空格隔开，表示需要选择的歌词的长度和结尾。

输出
对于每一个询问，输出一个整数，表示答案。

答案可能会很大，你只需要输出对于 109+7 取模后的结果。

样例
input
312121
4
2 21
3 31
4 22
3 22
output
3
0
1
2
提示
样例中第一个询问：312121, 312121, 312121.

第二个询问：无。

第三个询问：312121.

思路

可以发现，询问很多，但是主串 S 的长度并不长。考虑预处理所有的结尾情况。
我们可以枚举第一个位置 X ，预处理出 X 后面分别接 10 个数字的时候，可以组成字符串的数量。
假设当前枚举到的一个位置 i 满足 Si=X 。题目需要组成新字符串的长度为 N ，假设位置 i 后面有 Ay 个 Y ，则他对答案的贡献就是 (i−1n−2)Ay 。
显然，Ay 是可以先处理掉的，然后再继续暴力预处理所有结尾情况下新字符串的数量。
预处理完成以后，对于所有的询问都可以 O(1) 出结果。
但是我们发现询问给出的 N 很大，但可以显然地发现，当 N>|S| 很大的时候是没有解的。

暴力时间复杂度：2000×2000×100
但还是卡了TLE，首先一直错找不出原因，花了一天多才发现是组合数算错了。然后TLE，优化避免重复的询问，存储答案。

AC

#include <bits/stdc++.h>
#define LL long long
using namespace std;

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    const int mod = 1e9 + 7;

    string str;
    cin >> str;
    LL cnt[10][10][2005];   // 两个位置形成末尾共有多少的前缀
    memset(cnt, 0, sizeof(cnt));

    int len = str.size();
    for (int i = 0; i < len; i++) {
        for (int j = i + 1; j < len; j++) {
            int head = str[i] - '0';
            int tail = str[j] - '0';
            cnt[head][tail][i]++;
        }
    }

    static LL C[2005][2005];  // 组合数
    for(int i = 0; i < len; i++) {
        C[i][i] = C[i][0] = 1;
        for(int j = 1; j < i; j++) {
            C[i][j] = C[i - 1][j - 1] + C[i - 1][j];
            C[i][j] %= mod;
        }
    }

    int Q, N, X, Y;
    char A, B;
    cin >> Q;

    // 优化
    static LL ret[10][10][2005]; // 存储结果，如果是相同的询问避免重复计算
    bool vis[10][10][2005];
    while (Q--) {
        cin >> N >> A >> B;  // 不能写成一个数的输入，可能有前缀0
        //cout << A << B << endl;
        X = A - '0';
        Y = B - '0';
        LL ans = 0;
        if (N > 1 && N <= len) {
            if (vis[X][Y][N]) ans = ret[X][Y][N];
            else {
                int M = N - 2;
                for (int i = 0; i < len; i++) {  // 时间复杂度O(5*10^5*10^3=10^8)
                    if (cnt[X][Y][i] && i >= M) { // 一定要满足组合数条件
                        ans += C[i][M] * cnt[X][Y][i];
                        ans %= mod;
                    }
                }
                ret[X][Y][N] = ans;
                vis[X][Y][N] = true;
            }
        }
        cout << ans << endl;
    }
    return 0;
}

/*
输入：
312121
4
2 21
3 31
4 22
3 22

输出：
3
0
1
2

提交WA了9次，提交AC了才能看别人的代码。

居然是组合数求错了。。。。。
不可能啊。。。。。。
*/


/*
输入：
312121
4
2 21
3 31
4 22
3 22

输出：
3
0
1
2

提交WA了9次，提交AC了才能看别人的代码。
居然是组合数求错了。。。。。
不可能啊。。。。。。

原来是没有计算C(0,0)=1。而是写成了默认值C(0,0)=0。
*/