Reincarnation

正因为梦易碎，才格外美好。

ZROI - 20连测day1

发表于 更新于 分类于 ，
本文字数： 10k 阅读时长 ≈ 9 分钟

大概是没法改的一套题。

比赛链接：http://zhengruioi.com/contest/1463

题目简介

两个人博弈，游戏内容如下：

存在一个正整数集合 ，其中所有数满足 。每次可以选择一个 ，并将 与其所有因子全部删去。不能操作的玩家输。

给定 ，求先手是否必胜。

数据范围：

考虑如果 为空则后手胜，如果 则先手胜。然后归纳扩展。

首先，如果先手选择了 能够直接删空 ，则先手必胜，否则删掉 ，此时 少 。然后将类似的情况扔给后手，但后手不存在一步删完的方案，所以后手操作后又会将集合丢回先手，然后先手再次判断是否存在删完的操作，否则继续执行。

所以，除非 为空，否则先手必胜。时间复杂度 ，代码 行结束。

不太清楚为什么只开到 ，是怕开太大被找规律吗？

观前提醒

后面三道题并不在我的知识范围内，而且都是比较神秘的期望 ，所以我可能改不了，直接放官方题解和出题人代码。

B. 涂鸦 / C. 迷路 / D. 潘多拉的魔盒

题面

题目简介

给定一个大小为 的棋盘，每个格子有黑白两种颜色，给定初始状态和目标状态。每次会随机一个位置 ，并随机一个颜色 ，然后执行操作，将以 的二维前缀（即所有点 满足 ）的点全部染成 。这次操作的代价为 。

求变成目标状态的期望代价。

数据范围：

题目简介

给定一个 的网格作为地图。地图内有 个树，地图外可以到达，但是没有树。现在你在地图内，你的出发点是 个不同的随机点中的一个，现在对于所有情况，你需要知道你找到自己到底是这 个出发点中的哪一个的最小期望步数。

期望步数的计算是，视空地为 ，树为 ，你从这 个点出发，将经过的路径连成字符串，最小步数则是当这 个字符串前缀两两不同的长度。

请注意，你的行走路径应是下右左上的螺旋形，即按照：

的路径行走。

数据范围：

时空限制：

题目简介

给定 个盒子，每个盒子打开的代价为 ，打开这个盒子后，盒子中会出现一个物品，这个物品会从 个物品中等概率随机，其中第 个物品价值 ，出现概率 ，满足 。请注意，你最终只能带走一个物品。

现在你以最优策略操作这 个盒子，即是否打开以及打开顺序。注意策略动态，也就是你可以通过得到的物品获得接下来的策略。求期望最大收益（带走物品的价值减所有打开的盒子的代价）。

数据范围：

题解

未加载请刷新页面重试。

代码

AC Code
 
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
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
#include <bits/stdc++.h>
using namespace std;
const int mod = 998244353;
int binpow(int a, int t)
{
    int res = 1, p = a;
    for (int i = t; i; i >>= 1)
    {
        if (i & 1) res = 1ll * res * p % mod;
        p = 1ll * p * p % mod;
    }
    return res;
}
int n, m, cnt;
char s[555];
int a[55][55], b[55][55], arr[55], cur, mat[555][555], iv, c[55][55], res[555];
int p[55], ap[555][55];
map<int, int> mp;
void dfs(int i, int j, int msk)
{
    if (i == n + 1) 
    {
        mp[msk] = ++cnt;
        for (int k = 1; k <= n; k++) ap[cnt][k] = p[k];
        return;
    }
    for (int k = 0; k <= j; k++)
    {
        p[i] = k;
        dfs(i + 1, k, msk * (m + 1) + k);
    }
}
int get(int a[55][55])
{
    for (int i = n; i >= 1; i--)
    {
        arr[i] = 0;
        for (int j = m; j >= 1; j--)
        {
            if (a[i][j] != b[i][j])
            {
                arr[i] = j;
                break;
            }
        }
        if (i != n) arr[i] = max(arr[i], arr[i + 1]);
    }
    int msk = 0;
    for (int i = 1; i <= n; i++)
    {
        msk = msk * (m + 1) + arr[i];
    }
    return mp[msk];
}
void gauss()
{
    for (int i = 1; i <= cnt; i++)
    {
        int pos = -1;
        for (int j = i; j <= cnt; j++)
        {
            if (mat[j][i]) 
            {
                pos = j;
                break;
            }
        }
        assert(~pos);
        for (int j = 1; j <= cnt + 1; j++) swap(mat[i][j], mat[pos][j]);
        for (int j = i + 1; j <= cnt; j++)
        {
            int iv = -1ll * mat[j][i] * binpow(mat[i][i], mod - 2) % mod;
            for (int k = i; k <= cnt + 1; k++)
            {
                mat[j][k] = (1ll * iv * mat[i][k] + mat[j][k]) % mod;
            }
        }
    }
    for (int i = cnt; i >= 1; i--)
    {
        for (int j = i + 1; j <= cnt; j++)
        {
            mat[i][cnt + 1] = (-1ll * mat[i][j] * res[j] + mat[i][cnt + 1]) % mod;
        }
        res[i] = 1ll * mat[i][cnt + 1] * binpow(mat[i][i], mod - 2) % mod;
    }
}
int main()
{
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i++)
    {
        scanf("%s", s);
        for (int j = 1; j <= m; j++)
        {
            a[i][j] = (s[j - 1] == 'B');
        }
    }
    for (int i = 1; i <= n; i++)
    {
        scanf("%s", s);
        for (int j = 1; j <= m; j++)
        {
            b[i][j] = (s[j - 1] == 'B');
        }
    }
    dfs(1, m, 0);
    assert(mp[0] == 1);
    mat[1][1] = 1; mat[1][cnt + 1] = 0;
    iv = binpow(n * m * 2, mod - 2);
    for (int i = 2; i <= cnt; i++)
    {
        mat[i][i] = 1;
        for (int j = 1; j <= n; j++)
        {
            for (int k = 1; k <= m; k++)
            {
                for (int r = 0; r < 2; r++)
                {
                    for (int s = 1; s <= n; s++)
                    {
                        for (int t = 1; t <= ap[i][s]; t++) c[s][t] = 2;
                        for (int t = ap[i][s] + 1; t <= m; t++) c[s][t] = b[s][t];
                    }
                    for (int s = 1; s <= j; s++)
                    {
                        for (int t = 1; t <= k; t++)
                        {
                            c[s][t] = r;
                        }
                    }
                    int id = get(c);
                    mat[i][id] = (mat[i][id] - iv) % mod;
                    mat[i][cnt + 1] = (1ll * iv * (j * k) + mat[i][cnt + 1]) % mod;
                }
            }
        }
    }
    gauss();
    printf("%d\n", (res[get(a)] + mod) % mod);
    return 0;
}
AC Code
 
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
101
102
103
104
105
106
107
108
109
#include <bits/stdc++.h>
using namespace std;
const int maxn = 330, mod = 998244353;
int dx[] = {0, -1, 0, 1}, dy[] = {1, 0, -1, 0};
int n, m, k, r, xx, yy, cnt, dir, stp, mx, f[666], cntf[222222], re[222222], cntg, ans, cnr;
int x[333], y[333], id[666][666], cur[222222], to[222222];
vector<int> v[555555], buc;
int binpow(int a, int t)
{
    int res = 1, p = a;
    for (int i = t; i; i >>= 1)
    {
        if (i & 1) res = 1ll * res * p % mod;
        p = 1ll * p * p % mod;
    }
    return res;
}
int Get(int x, int y)
{
    return (x - 1) * m + y;
}
void split(int a, int b, int c) // /(1 + ax) * (1 + bx) * (1 + cx)
{
    assert(b + c == a);
    for (int i = 1; i <= r; i++)
    {
        f[i] = (-1ll * f[i - 1] * a + f[i]) % mod;
    }
    for (int i = r; i >= 1; i--)
    {
        f[i] = (1ll * f[i - 1] * b + f[i]) % mod;
    }
    for (int i = r; i >= 1; i--)
    {
        f[i] = (1ll * f[i - 1] * c + f[i]) % mod;
    }
}
int main()
{
    scanf("%d%d%d%d", &n, &m, &k, &r);
    for (int i = 1; i <= k; i++) scanf("%d%d", &x[i], &y[i]);
    id[maxn][maxn] = 1; id[maxn + 1][maxn] = 2;
    cnt = 2; xx = 1; yy = 0; dir = 0;
    while(1)
    {
        xx += dx[dir]; yy += dy[dir];
        if (xx > maxn || xx < -maxn || yy > maxn || yy < -maxn) break;
        cnt++;
        id[xx + maxn][yy + maxn] = cnt;
        if (!id[xx + dx[(dir + 1) % 4] + maxn][yy + dy[(dir + 1) % 4] + maxn]) dir = (dir + 1) % 4;
    }
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= m; j++)
        {
            for (int h = 1; h <= k; h++)
            {
                mx = max(mx, id[x[h] - i + maxn][y[h] - j + maxn]);
                v[id[x[h] - i + maxn][y[h] - j + maxn]].push_back(Get(i, j));
            }
        }
    }
    cnr = 1;
    for (int i = 1; i <= r; i++)
    {
        cnr = 1ll * cnr * (n * m - i + 1) % mod;
        cnr = 1ll * cnr * binpow(i, mod - 2) % mod;
    }
    f[0] = 1; f[1] = n * m; ans = (cnr - f[r]) % mod;
    for (int i = 1; i <= n * m; i++) 
    {
        re[i] = 1;
    }
    cntf[1] = n * m; cntg = 1;
    for (int i = 1; i <= mx; i++)
    {
        for (int j = 0; j < v[i].size(); j++)
        {
            int idx = v[i][j];
            if (!cur[re[idx]]) buc.push_back(re[idx]);
            cur[re[idx]]++;
        }
        for (int j = 0; j < buc.size(); j++)
        {
            if (cur[buc[j]] == cntf[buc[j]]) continue;
            ++cntg;
            to[buc[j]] = cntg;
            split(cntf[buc[j]], cur[buc[j]], cntf[buc[j]] - cur[buc[j]]);
            cntf[buc[j]] -= cur[buc[j]];
            cntf[cntg] = cur[buc[j]];
        }
        for (int j = 0; j < v[i].size(); j++)
        {
            int idx = v[i][j];
            if (to[re[idx]]) re[idx] = to[re[idx]];
        }
        for (int j = 0; j < buc.size(); j++)
        {
            cur[buc[j]] = to[buc[j]] = 0;
        }
        buc.clear();
        ans = (1ll * ans + cnr - f[r]) % mod;
        if (cntg == n * m) break;
    }
    for (int i = 1; i <= n * m; i++) assert(cntf[re[i]] == 1);
    ans = 1ll * ans * binpow(cnr, mod - 2) % mod;
    printf("%d\n", (ans + mod) % mod);
    return 0;
}
AC Code
 
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
#include <bits/stdc++.h>
using namespace std;
const long double eps = 1e-9;
int n, num[111111], al;
long double c[111111], x, y, psi[111111], cur, pro, prod, p[111111], ans, rr, sm;
vector<pair<long double, long double> > a[111111];
vector<pair<pair<long double, long double>, int> > all;
int main()
{
    scanf("%d", &n);
    for (int i = 1; i <= n; i++)
    {
        scanf("%Lf", &c[i]);
        scanf("%d", &num[i]);
        for (int j = 1; j <= num[i]; j++)
        {
            scanf("%Lf%Lf", &x, &y);
            y /= 1000.00; 
            a[i].push_back(make_pair(x, y));
        }
        sort(a[i].begin(), a[i].end());
        reverse(a[i].begin(), a[i].end());
        cur = c[i]; pro = 0.00;
        bool flg = 0;
        for (int j = 0; j < (int)a[i].size() - 1; j++)
        {
            pro += a[i][j].second;
            if (cur < pro * (a[i][j].first - a[i][j + 1].first)) 
            {
                psi[i] = a[i][j].first - cur / pro;
                flg = 1;
                break;
            }
            else cur -= pro * (a[i][j].first - a[i][j + 1].first);
        }
        if (!flg) psi[i] = a[i].back().first - cur; 
        pro = 0.00;
        for (int j = 0; j < a[i].size(); j++)
        {
            if (a[i][j].first < psi[i]) all.push_back(make_pair(a[i][j], i));
            else pro += a[i][j].second;
        }
        if (pro > eps) all.push_back(make_pair(make_pair(psi[i], pro), i));
    }
    sort(all.begin(), all.end()); prod = 1.00;
    reverse(all.begin(), all.end());
    for (int i = 1; i <= n; i++) p[i] = 1.00;
    for (int i = 0; i < all.size(); i++)
    {
        rr = prod;
        prod /= p[all[i].second];
        p[all[i].second] -= all[i].first.second;
        prod *= p[all[i].second];
        rr -= prod;
        ans += (all[i].first.first * rr);
    }
    ans = fmax(0.00, ans);
    printf("%.12Lf\n", ans);
    return 0;
}
相关文章