必威体育Betway必威体育官网
当前位置:首页 > IT技术

JZOJ ???? dexterity

时间:2019-06-27 10:42:09来源:IT技术作者:seo实验室小编阅读:52次「手机版」
 

dexterity

          • 没有传送门
          • 题目大意
            • 样例输入
            • 样例输出
            • 样例解释(原题没有)
          • 考场上的思路
          • 参考代码

没有传送门
题目大意

A 和 B 猜拳,要猜 n" role="presentation">n 轮。对于第 i" role="presentation">i 轮,获胜分数加 wi" role="presentation">wi,平局分数加 di" role="presentation">di,失败分数不变。A 知道 B 的出拳顺序是一个给定串 s" role="presentation">s 的循环同构串,求 A 用最优策略在最坏情况下能得多少分。

n≤105" role="presentation">n105w,d∈int" role="presentation">w,dint

样例输入
5
rrsrr
3 1
3 1
3 1
3 1
3 1
样例输出
12
样例解释(原题没有)

A 一直出布,肯定能拿 12" role="presentation">12 分。可以证明不存在更优的出拳方法。

考场上的思路

考虑 Special instance,当 s" role="presentation">s 只存在一个字符时该怎么做。显然只要一直出能够获胜的就可以了。

注意到,当比赛进行到足够长,使得当前 B 已经出的拳仅为一个循环同构串的前缀时,我们就相当于知道了接下来 B 怎么出拳,也就能一直获胜了。当然也可能永远不满足这个条件,却依然能够一直获胜(比如 s" role="presentation">s 只存在一个字符时)。

不妨将所有循环同构串建成一棵 Trie。发现,每个串的后缀对应在 Trie 上的一条链就是我们上面说的能够一直获胜的情况。那不能获胜的情况呢?这就很自然地想到了树形 DP。对于一个点,我们枚举它出石头剪刀还是布,然后计算对方出某个时的答案。由于是在最坏情况,因此取最小值;由于要取最优决策,因此在三个决策中取最大值。时间复杂度 O(n2)" role="presentation">O(n2)

然而我忘记把串倍增(准确地说是我在最后十分钟想到了这个做法,但是忘了我把之前倍增串的代码删了),爆零垫底了。

接下来显然只需要把 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;
}

有关后缀自动机转后缀树的内容见专题。

相关阅读

jzoj1901. 光棱坦克

题目描述 Description一个平面直角坐标系上,有N个点,标号为1到N,其中第i个点的坐标为(x[i], y[i])。   求满足以下两个条件的点列{

【JZOJ A组】naive 的图

Description 众所周知,小 naive 有一张 n 个点,m 条边的带权无向图。第 i 个点的颜色为 ci。d(s, t)表示从点 s 到点 t 的权值最小

【JZOJ4212】我想大声告诉你

description 因为小Y 是知名的白富美,所以自然也有很多的追求者,这一天这些追求者打算进行一次游戏来踢出一些人,小R 自然也参加了。

【JZOJ1319】邮递员

description 邮局需要你来帮助他们为某个邮递员设计出一条能够穿过那遥远乡村的所有村子和小路至少一次的邮路(输入数据将会保证这

【数学】JZOJ_4745 看电影

题意 从nnn个人中选kkk个人,问被选到的概率。思路 根据数学知识可知答案为k/nk/nk/n。代码 无。

分享到:

栏目导航

推荐阅读

热门阅读