dexterity
- 没有传送门
- 题目大意
- 样例输入
- 样例输出
- 样例解释（原题没有）
- 考场上的思路
- 参考代码
没有传送门
题目大意
A 和 B 猜拳，要猜
样例输入
5
rrsrr
3 1
3 1
3 1
3 1
3 1样例输出
12样例解释（原题没有）
A 一直出布，肯定能拿
考场上的思路
考虑 Special instance，当
注意到，当比赛进行到足够长，使得当前 B 已经出的拳仅为一个循环同构串的前缀时，我们就相当于知道了接下来 B 怎么出拳，也就能一直获胜了。当然也可能永远不满足这个条件，却依然能够一直获胜（比如
不妨将所有循环同构串建成一棵 Trie。发现，每个串的后缀对应在 Trie 上的一条链就是我们上面说的能够一直获胜的情况。那不能获胜的情况呢？这就很自然地想到了树形 DP。对于一个点，我们枚举它出石头剪刀还是布，然后计算对方出某个时的答案。由于是在最坏情况，因此取最小值；由于要取最优决策，因此在三个决策中取最大值。时间复杂度
然而我忘记把串倍增（准确地说是我在最后十分钟想到了这个做法，但是忘了我把之前倍增串的代码删了），爆零垫底了。
接下来显然只需要把 Trie 改成后缀树就可以了。
参考代码
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>
#include <cassert>
#include <cctype>
#include <climits>
#include <ctime>
#include <iOStream>
#include <algorithm>
#include <vector>
#include <string>
#include <stack>
#include <queue>
#include <deque>
#include <map>
#include <set>
#include <bitset>
#include <list>
#include <functional>
typedef long long LL;
typedef unsigned long long ULL;
using std::cin;
using std::cout;
using std::endl;
typedef LL INT_PUT;
INT_PUT readIn()
{
INT_PUT a = 0; bool positive = true;
char ch = getchar();
while (!(ch == '-' || std::isdigit(ch))) ch = getchar();
if (ch == '-') { positive = false; ch = getchar(); }
while (std::isdigit(ch)) { a = a * 10 - (ch - '0'); ch = getchar(); }
return positive ? -a : a;
}
void printOut(INT_PUT x)
{
char buffer[20]; int length = 0;
if (x < 0) putchar('-'); else x = -x;
do buffer[length++] = -(x % 10) + '0'; while (x /= 10);
do putchar(buffer[--length]); while (length);
putchar('\n');
}
const int maxn = int(1e5) + 5;
int n;
int str[maxn * 2];
int w[maxn], d[maxn];
LL sum[maxn];
int table[3][3] = { { 0, 1, -1 }, { -1, 0, 1 }, { 1, -1, 0 } };
#define RunInstance(x) delete new x
struct brute
{
struct Trie
{
struct Node
{
int son[3];
Node() : son() {}
};
std::vector<Node> nodes;
Trie() : nodes(1) {}
void insert(int st)
{
int cnt = 0;
for (int i = 0; i < n; i++)
{
if (!nodes[cnt].son[str[st + i]])
{
nodes[cnt].son[str[st + i]] = nodes.size();
nodes.push_back(Node());
}
cnt = nodes[cnt].son[str[st + i]];
}
}
LL DP(int node = 0, int depth = 1)
{
if (depth == n + 1) return 0;
LL ret = 0;
LL temp[3] = {};
for (int i = 0; i < 3; i++)
if (nodes[node].son[i])
temp[i] = DP(nodes[node].son[i], depth + 1);
for (int i = 0; i < 3; i++)
{
LL min = LLONG_MAX;
for (int j = 0; j < 3; j++)
{
if (nodes[node].son[j])
{
int accum = 0;
switch (table[i][j])
{
case 1: accum = w[depth]; break;
case 0: accum = d[depth]; break;
case -1: accum = 0; break;
}
min = std::min(min, temp[j] + accum);
}
}
ret = std::max(ret, min);
}
return ret;
}
} trie;
brute()
{
for (int i = 1; i <= n; i++)
trie.insert(i);
printOut(trie.DP());
}
};
struct work
{
struct SAM
{
struct Node
{
int len;
int link;
int pos;
int ch[3];
Node() : len(), link(), ch() {}
} nodes[maxn * 4];
int size;
int last;
SAM() : size(), G() { nodes[last = size++].link = -1; }
void extend(int x, int pos)
{
int cur = size++;
nodes[cur].len = nodes[last].len + 1;
nodes[cur].pos = pos;
int p = last;
last = cur;
for (; ~p && !nodes[p].ch[x]; p = nodes[p].link)
nodes[p].ch[x] = cur;
if (!~p)
{
nodes[cur].link = 0;
return;
}
int q = nodes[p].ch[x];
if (nodes[p].len + 1 == nodes[q].len)
{
nodes[cur].link = q;
return;
}
int clone = size++;
nodes[clone] = nodes[q];
nodes[clone].pos = pos;
nodes[clone].len = nodes[p].len + 1;
nodes[cur].link = nodes[q].link = clone;
for (; ~p && nodes[p].ch[x] == q; p = nodes[p].link)
nodes[p].ch[x] = clone;
}
int G[maxn * 4][3];
void build()
{
for (int i = 1; i < size; i++)
G[nodes[i].link][str[nodes[i].pos + nodes[nodes[i].link].len]] = i;
}
LL DP(int node = 0, int depth = 0)
{
LL base = 0;
if (node)
{
int length = nodes[node].len - nodes[nodes[node].link].len;
if (depth >= n)
return sum[n] - sum[depth - length + 1];
else
base = sum[depth] - sum[depth - length + 1];
}
LL temp[3] = {};
for (int i = 0; i < 3; i++)
if (G[node][i])
temp[i] = DP(G[node][i], depth + nodes[G[node][i]].len - nodes[node].len);
LL ret = 0;
for (int i = 0; i < 3; i++)
{
LL min = LLONG_MAX;
for (int j = 0; j < 3; j++)
{
if (G[node][j])
{
int accum = 0;
switch (table[i][j])
{
case 1: accum = w[depth + 1]; break;
case 0: accum = d[depth + 1]; break;
case -1: accum = 0; break;
}
min = std::min(min, temp[j] + accum);
}
}
ret = std::max(ret, min);
}
return ret + base;
}
} sam;
work()
{
for (int i = n << 1; i; i--)
sam.extend(str[i], i);
sam.build();
printOut(sam.DP());
}
};
bool checkSame()
{
std::vector<int> temp(str + 1, str + 1 + n);
return std::unique(temp.begin(), temp.end()) - temp.begin() == 1;
}
void run()
{
n = readIn();
for (int i = 1; i <= n; i++)
{
char ch = getchar();
while (!std::isalpha(ch)) ch = getchar();
if (ch == 'r') str[i] = 0;
else if (ch == 's') str[i] = 1;
else if (ch == 'p') str[i] = 2;
}
std::memcpy(str + n + 1, str + 1, sizeof(str[0]) * n);
for (int i = 1; i <= n; i++)
{
w[i] = readIn();
d[i] = readIn();
}
for (int i = 1; i <= n; i++)
sum[i] = w[i];
for (int i = 2; i <= n; i++)
sum[i] += sum[i - 1];
if (checkSame())
{
LL ans = 0;
for (int i = 1; i <= n; i++)
ans += w[i];
printOut(ans);
return;
}
if (n <= 1000)
RunInstance(brute);
else
RunInstance(work);
}
int main()
{
#ifndef local
freopen("dexterity.in", "r", stdin);
freopen("dexterity.out", "w", stdout);
#endif
run();
return 0;
}有关后缀自动机转后缀树的内容见专题。
相关阅读
题目描述 Description一个平面直角坐标系上，有N个点，标号为1到N，其中第i个点的坐标为(x[i], y[i])。 求满足以下两个条件的点列{
Description 众所周知，小 naive 有一张 n 个点，m 条边的带权无向图。第 i 个点的颜色为 ci。d(s, t)表示从点 s 到点 t 的权值最小
description 因为小Y 是知名的白富美，所以自然也有很多的追求者，这一天这些追求者打算进行一次游戏来踢出一些人，小R 自然也参加了。
description 邮局需要你来帮助他们为某个邮递员设计出一条能够穿过那遥远乡村的所有村子和小路至少一次的邮路（输入数据将会保证这
题意 从nnn个人中选kkk个人，问被选到的概率。思路 根据数学知识可知答案为k/nk/nk/n。代码 无。