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

标签: none

添加新评论