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];
    }
};

Codeforces #315

最近比赛真是不良心。出的题完全无法下手。
可能也是状态的原因吧,一边打一边想睡觉。
交了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;
}

神奇至极的并查集

前言

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

待续。

- 阅读剩余部分 -

bst g22 jinniu lilai opebet orange88 vinbet xbet yuebo zunlong shijiebei bet007 hg0088 ju111 letiantang m88 mayaba qg777 qianyiguoji sbf777 tengbohui tlc ule weilianxier waiweitouzhu xingfayule xinhaotiandi yinheyule youfayule zhongying 2018shijiebei w88 18luck 188bet beplay manbet 12bet 95zz shenbo weide1946 ca88 88bifa aomenxinpujing betway bodog bt365 bwin tongbao vwin weinisiren 88jt fenghuangyule hongyunguoji 918botiantang huanyayule jianada28 jixiangfang libo long8 hongzuyishi zuqiutouzhu