2015年8月

好像是去年毛子发明的对付回文串的数据结构。
下午再次研究了一遍,发现总算看懂了。
贴一份模板。

template<int maxn = int(1e5), int sigma = 26>
class PalindromeTree
{
private:
    int n, p, tail;
    int S[maxn];
    int next[maxn][sigma], fail[maxn], len[maxn], cnt[maxn];
    inline int idx(char c){return c - 'a';}

public:
    int newnode(int l)
    {
        cnt[p] = 0;
        len[p] = l;
        return p++;
    }
    void init()
    {
        newnode(0), newnode(-1);
        S[n = 0] = -1;
        fail[0] = 1;
    }

    int get_fail(int x)
    {
        while(S[n - len[x] - 1] != S[n])
            x = fail[x];
        return x;
    }

    void add(char c)
    {
        int id = idx(c);
        S[++n] = id;
        int cur = get_fail(tail);
        if(!next[cur][id])
        {
            int node = newnode(len[cur] + 2);
            fail[node] = next[get_fail(fail[cur])][id];
            next[cur][id] = node;
        }
        tail = next[cur][id];
        cnt[tail]++;
    }

    void count()
    {
        for(int i = p - 1; i >= 0; i--)
            cnt[fail[i]] += cnt[i];
    }
};

最近比赛真是不良心。出的题完全无法下手。
可能也是状态的原因吧,一边打一边想睡觉。
交了ab两发pp后就去睡了,幸好没有fst。
rating终于升回蓝名了。什么时候才能红啊。
……


解/码

A

按照题意,单次下载的总长度即为$$ s + s cdot frac{q-1}{q} + s cdot left( frac{q-1}{q} right) ^2 + cdots + s cdot left( frac{q-1}{q} right) ^n \\
=s cdot left( 1 + frac{q-1}{q} + left( frac{q-1}{q} right) ^2 + cdots + left( frac{q-1}{q} right) ^n right), n to infty$$
易知这个和收敛于一个常数,即极限存在,简单来说若发散那就一次下载完了。
将上述无穷和式记为$ s \cdot A $,通过等比数列求和公式可以推出$$ A=q-q \cdot \left( \frac{q-1}{q} \right) ^ {n+1}, n \to \infty $$
即解极限$$ \displaystyle\lim_{n \to \infty} \left( \frac{q-1}{q} \right) ^ {n+1} $$
$$ q \in \mathbb Z_+ \\\\ \Rightarrow 0 < \frac{q-1}{q} < 1 \\\\ \Rightarrow \left( \frac{q-1}{q} \right) ^ {n+1} \to 0 \\\\ \Rightarrow A = q $$
即单次下载与已缓冲之总秒数为$ s \cdot q $。
那么重开始一次就是$ s \cdot q $,重开始两次就是$ s \cdot q ^ 2 $,重开始n次就是$ s \cdot q ^ n $。
所以题目即为求最小之$ n $满足$$ s \cdot q^n \ge t $$。

#include <iostream>
using namespace std;
int main()
{
    int t, s, q;
    cin>>t>>s>>q;
    s *= q; long long ts = 1;
    while(s < t)
        s *= q, ts ++;
    cout<<ts<<endl;
    return 0;
}

B

求新编号序列。要求1)不重;2)1~n之间;3)改动最少。
直接贪心大暴力咯。

#include <iostream>
using namespace std;
const int maxn = 1e5 + 100;
int a[maxn] = {0};
bool b[maxn] = {false};
int main()
{
    int n;
    cin>>n;
    for(int i = 0; i < n; i++)
    {
        cin>>a[i];
        if(!b[a[i]] && a[i] <= n)
            b[a[i]] = true;
        else
            a[i] = -1;
    }
    int cnt = 0;
    for(int i = 0; i < n; i++)
    {
        if(a[i] != -1)
            cout<<a[i]<<" ";
        else
        {
            while(b[++cnt]);
            cout<<cnt<<" ";
        }
    }
    return 0;
}

前言

又来开一个大坑了。
主要是最近做并查集的题目发现,并查集其实并不是那么简单的,它还有很多妙用。
然后这里就来整理一下并查集相关的东西。

待续。



- 阅读剩余部分 -