多校训练营1
LyFive
标签
后缀自动机(SAM)
题意
给一个长度为n个数字串（有前导零）。计算这个数字串中有多少对子串（A，B均为可能存在前导零的数字）满足。
思路
不难发现，我们可以考虑对于一个串不存在9，在后加入一个就能凑出对。由于是对子串的匹配联想到的的性质大小意味着某个子串出现的次数，每一个状态对应一个，设此刻为状态分别接收转移到，此时状态表示的子串恰好凑成对，并且对答案的贡献为的大小乘积，即。同时状态表示子串的个数为，故状态转移至的答案贡献为
为此，遍历所有的状态判断转移方向累计答案即可。 对于特殊情况含有字符9的状态，考虑9进位后者进1并将9归0，故可以表示为分别转移到，故对于特殊情况9可以在每次转移到后枚举9的情况。
参考代码
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 | #include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 8e5 + 10;
int tot = 1, last = 1;
struct Node
{
int len, fa;
int ch[10];
} node[N];
char str[N];
LL f[N], ans;
int h[N], e[N], ne[N], idx;
void extend(int c)
{
int p = last, np = last = ++tot;
f[tot] = 1;
node[np].len = node[p].len + 1;
for (; p && !node[p].ch[c]; p = node[p].fa)
node[p].ch[c] = np;
if (!p)
node[np].fa = 1;
else
{
int q = node[p].ch[c];
if (node[q].len == node[p].len + 1)
node[np].fa = q;
else
{
int nq = ++tot;
node[nq] = node[q], node[nq].len = node[p].len + 1;
node[q].fa = node[np].fa = nq;
for (; p && node[p].ch[c] == q; p = node[p].fa)
node[p].ch[c] = nq;
}
}
}
void add(int a, int b)
{
e[idx] = b, ne[idx] = h[a], h[a] = idx++;
}
void dfs(int u)
{
for (int i = h[u]; ~i; i = ne[i])
{
dfs(e[i]);
f[u] += f[e[i]];
}
}
void getAns()
{
for (int x = 1; x <= tot; x++)
{
for (int i = 0; i < 9; i++)
{
int q = node[x].ch[i];
int p = node[x].ch[i + 1];
while (q && p)
{
ans += (node[x].len - node[node[x].fa].len) * f[q] * f[p];
q = node[q].ch[9];
p = node[p].ch[0];
}
}
}
}
int main()
{
int n;
cin >> n;
node[0].len = -1;
scanf("%s", str);
for (int i = 0; str[i]; i++)
extend(str[i] - '0');
memset(h, -1, sizeof h);
for (int i = 2; i <= tot; i++)
add(node[i].fa, i);
dfs(1);
getAns();
cout << ans << endl;
return 0;
}
|
z3475
标签
单调队列,计算几何
题意
在二维坐标系中到的矩阵包含的整数点为座位，到为电视，一个座位为好座位当且仅当它和电视形成的三角形内没有人。给定其他同学坐的位置，每个回合都有一个人移动位置坐，求每个回合后好位子数量。
思路
考虑人对位置的影响，发现一个人会ban掉所有到为方向，以为开始的射线和到的射线围着的座位。考虑一边，另一边可以以同样的方法算出。取min即可。
发现对于所有人形成从开始的所有以为斜率的射线中，和值构成了一个单调队列like的形式，即如果且其，则前者完全可以替代掉后者，按斜率排序后添加至单调队列就可以维护每一个y对应的最小x值。
参考代码
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 | #include <bits/stdc++.h>
using namespace std;
struct FAST_IO {
FAST_IO() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
}
} __fast_io;
template <class T>
using vec = vector<T>;
using ll = long long;
struct P {
int x, y;
};
int n, m, k, q;
bool operator==(const P& a, const P& b) { return a.x == b.x && a.y == b.y; }
struct CMP0 {
bool operator()(const P& a, const P& b) const {
return (ll)(a.x) * (b.y - 1) - (ll)(a.y - 1) * (b.x) < 0;
}
};
struct CMP1 {
bool operator()(const P& a, const P& b) const {
return (ll)(a.x) * (b.y - m) - (ll)(a.y - m) * (b.x) > 0;
}
};
P d[200000 + 10];
int dl = 0, dr = 0;
P v[200000 + 10];
int ans[200000 + 10];
vec<P> v0, v1;
int main() {
cin >> n >> m >> k >> q;
for (int i = 1; i <= k; i++) {
int x, y;
cin >> x >> y;
v[i] = {x, y};
v0.push_back({x, y});
v1.push_back({x, y});
}
sort(v0.begin(), v0.end(), CMP0());
sort(v1.begin(), v1.end(), CMP1());
for (int qi = 0; qi < q; qi++) {
for (int i = 1; i <= m; i++) ans[i] = n;
int pi, xi, yi;
cin >> pi >> xi >> yi;
v0.erase(find(v0.begin(), v0.end(), v[pi]));
v1.erase(find(v1.begin(), v1.end(), v[pi]));
v[pi] = {xi, yi};
v0.insert(lower_bound(v0.begin(), v0.end(), v[pi], CMP0()), v[pi]);
v1.insert(lower_bound(v1.begin(), v1.end(), v[pi], CMP1()), v[pi]);
dl = dr = 0;
for (auto p : v0) {
if (dl == dr || d[dr - 1].y > p.y) {
d[dr++] = p;
}
}
for (int i = m; i >= 1; i--) {
while (dl != dr && d[dl].y > i) {
++dl;
}
if (dl == dr) continue;
auto y = d[dl].y;
if (y == 1) {
continue;
}
double x = d[dl].x;
if (y != i) {
x += (double)(i - y) / (y - 1) * (x);
}
double xx = abs(floor(x) - x) < 1e-6 ? floor(x) - 1 : floor(x);
if (xx < ans[i]) ans[i] = xx;
}
dl = dr = 0;
for (auto p : v1) {
if (dl == dr || d[dr - 1].y < p.y) {
d[dr++] = p;
}
}
// for (auto i:d) cerr<<i.x<<" "<<i.y<<endl;
for (int i = 1; i <= m; i++) {
while (dl != dr && d[dl].y < i) {
++dl;
}
if (dl == dr) continue;
auto y = d[dl].y;
if (y == m) {
continue;
}
double x = d[dl].x;
if (y != i) {
x += (double)(y - i) / (m - y) * (x);
}
double xx = abs(floor(x) - x) < 1e-6 ? floor(x) - 1 : floor(x);
if (xx < ans[i]) ans[i] = xx;
}
ll ans0 = 0;
for (int i = 1; i <= m; i++) ans0 += ans[i];
cout << ans0 << "\n";
}
}
|
LyFive
标签
DP,期望DP
题意
牌库总共34×4张牌，起手摸13张。玩家每次摸一张牌丢一张牌，直到摸到恰好凑成7对牌后胜利。现求最优策略到达胜利所需摸牌数的期望。
思路
不难发现最优策略就是保留手上的单牌，若摸一张不是手上的单牌就丢掉，否则就保留。现设为还缺个对子，牌库还剩下张牌获胜的期望。基于此，不难发现若缺个对子，则手中已有个对子，剩下张单牌。考虑当前状态下摸一张牌，那么这张牌是需要的单牌的概率应该为，不是则为，每次摸牌牌库都会减少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
71
72
73
74 | #include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const LL mod = 1e9 + 7;
const LL N = 2e5 + 100;
LL t, n, m, x, y, k;
LL dp[8][136]; // 还缺i个对子，牌堆还有j张牌获胜的期望
LL inv[136];
LL ksm(LL x, LL y)
{
if (y == 0)
return 1;
if (y == 1)
return x % mod;
LL as = ksm(x, y / 2);
if (y % 2)
return as * as % mod * x % mod;
return as * as % mod;
}
LL mint(LL x)
{
return x % mod;
}
void init()
{
for (int i = 1; i < 136; i++)
{
inv[i] = ksm(i, mod - 2);
}
for (int i = 1; i <= 7; i++)
{
for (int j = i; j <= 123; j++)
{
dp[i][j] = mint(dp[i - 1][j - 1] + 1) * mint((6 * i - 3) * inv[j]) % mod +
mint(dp[i][j - 1] + 1) * mint((j - 6 * i + 3) * inv[j]) % mod;
dp[i][j] %= mod;
}
// cout << dp[i][123] << endl;
}
}
string s[13];
void solve()
{
char x[3];
for (int i = 0; i < 13; i++)
{
scanf("%2s", x);
swap(x[0], x[1]);
s[i] = x;
}
sort(s, s + 13);
int cnt = 0;
for (int i = 1; i < 13; i++)
if (s[i] == s[i - 1])
cnt++;
cout << dp[7 - cnt][123] << "\n";
}
int main()
{
init();
cin >> t;
for (int i = 1; i <= t; i++)
{
cout << "Case #" << i << ": ";
solve();
}
}
|
z3475
标签
并查集
题意
有一张 n 个点 m 条边的无重边无自环的有向图。初始时可以选择一个点染黑，其余点均为白点。若某个点所有入边的起点均为黑点，则该点可以被染黑。最大化图中黑点数量。（无入边表示不能被染黑）
思路
以 表示初始将节点 标黑所形成的黑点集合，选取两个集合发现 和 只能存在下面三种情况的一种
证明留作习题，正因为有这个性质，集合的集合和集合的包含关系形成了一个森林。因为包含关系还能传递，所以可以套用并查集。考虑森林中每棵树的根节点所对应的点。如果一颗树能被其他树合并，则点的所有入边都长在一棵树上。因为很大考虑反着维护入边。考虑树合并到树之后的状态维护，如果能创造出一颗树其代表点为能合并到，此时的来自不同树的入边有2，分别代表，可以合并到，添加到队列即可。注意的是和可能之后并是各自所属的树的根，拿并查集整个fa即可。
参考代码
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 | #include <bits/stdc++.h>
using namespace std;
struct FAST_IO {
FAST_IO() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
}
};
template <class T>
using vec = vector<T>;
int main() {
int T;
cin >> T;
for (int Ti = 1; Ti <= T; Ti++)
cout << "Case #" << Ti << ": " << []() -> int {
int n;
cin >> n;
vec<set<int>> G(n);
vec<int> ins(n, 0);
queue<pair<int, int>> tomerge;
vec<int> mfset(n);
vec<int> sz(n, 1);
iota(mfset.begin(), mfset.end(), 0);
function<int(int)> fa = [&](int i) {
return mfset[i] == i ? i : (mfset[i] = fa(mfset[i]));
};
auto merge = [&](int i, int j) { // i->j
if (i == j)
return;
mfset[i] = j;
sz[j] += sz[i];
auto &Gii = G[i], &Gjj = G[j];
if (Gii.size() > Gjj.size())
swap(Gii, Gjj);
for (auto Gi : Gii) {
auto Gji = Gjj.find(Gi);
if (Gji == Gjj.end()) {
Gjj.insert(Gi);
} else {
if (--ins[Gi] == 1)
tomerge.push({Gi, j});
}
}
};
for (int i = 0; i < n; i++) {
int k;
cin >> ins[i];
for (int j = 0; j < ins[i]; j++) {
cin >> k;
k--;
G[k].insert(i);
}
if (ins[i] == 1)
tomerge.push({i, k});
}
while (tomerge.size()) {
int u = fa(tomerge.front().first), v = fa(tomerge.front().second);
tomerge.pop();
merge(u, v);
}
int ans = 0;
for (int i = 0; i < n; i++) {
ans = max(ans, sz[i]);
}
return ans;
}() << endl;
}
|
build本页面最近更新：2022/7/28 17:14:31，更新历史
edit发现错误？想一起完善？ 在 GitHub 上编辑此页！
people本页面贡献者：
copyright本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用