分类 Codeforces 下的文章

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

这次犯了好多脑残错误。
B题FST直接导致rating降了。
带两个新手打比赛。
D、E分别WA/T了。
其中都是很简单的。


解&码

A
看有没有1就行。

#include <iostream>
using namespace std;
int main()
{
    int n;
    cin>>n;
    bool ok = false;
    for(int i = 0; i < n; i++)
    {
        int tmp;
        cin>>tmp;
        if(tmp == 1)
        {
            ok = true;
            break;
        }
    }
    if(ok)
        cout<<-1<<endl;
    else
        cout<<1<<endl;
    return 0;
}

B
分别放两个角,四个if就行。

#include <iostream>
using namespace std;
int a1, b1, a2, b2, a3, b3;
inline bool check(int x1, int y1, int x2, int y2)
{
    return !(x1 > x2 && y1 > y2) && x1 >= 0 && x2 >= 0 && y1 >= 0 && y2 >= 0 && x1 <= a1 && x2 <= a1 && y1 <= b1 && y2 <= b1;
}
int main()
{
    cin>>a1>>b1>>a2>>b2>>a3>>b3;
    if(check(a2, b2, a1 - a3, b1 - b3) || check(b2, a2, a1-a3,b1-b3) || check(a2,b2,a1-b3,b1-a3) || check(b2,a2,a1-b3,b1-a3))
        cout<<"YES"<<endl;
    else
        cout<<"NO"<<endl;
    return 0;
}

C
数三角。直接面积算更好。
这份是数单位三角形。

#include <iostream>
using namespace std;
int main()
{
    int a, b, c, d, e, f;
    cin>>a>>b>>c>>d>>e>>f;
    int bian = a + b + c;
    int sum = 0;
    for(int i = 0, j = 1; i < bian; i++, j += 2)
        sum += j;

    for(int i = 0, j = 1; i < a; i++, j += 2)
        sum -= j;

    for(int i = 0, j = 1; i < c; i++, j += 2)
        sum -= j;

    for(int i = 0, j = 1; i < e; i++, j += 2)
        sum -= j;
    cout<<sum<<endl;
    return 0;
}

面积大法。

#include <iostream>
using namespace std;
int main()
{
    int a, b, c, d, e, f;
    cin>>a>>b>>c>>d>>e>>f;
    cout<<(a+b+c)*(a+b+c)-a*a-c*c-e*e<<endl;
    return 0;
}

D
Orz暴力模拟O(n lg n)得出字符串最小之匹配即可。

#include <iostream>
#include <string>
using namespace std;

string que(string s)
{
    if(s.length() % 2 == 1)
        return s;
    string s1, s2;
    for(int i = 0; i < s.length() / 2; i++)
        s1 += s[i];
    for(int i = s.length() / 2; i < s.length(); i++)
        s2 += s[i];
    s1 = que(s1), s2 = que(s2);
    return min(s1, s2) + max(s1, s2);
}

int main()
{
    string s, t;
    cin>>s>>t;
    s = que(s);
    t = que(t); 
    if(s == t)
        cout<<"YES"<<endl;
    else
        cout<<"NO"<<endl;
    return 0;
}

E
小学奥数。组合数去模。结论在想怎么证。
结论其实很简单,一共走r+c-2步,其中r-1步向下,c-1步向右,组合选一下即是$ {r+c-2 \choose r-1} $

#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;
const int mod = 1e9 + 7;
const int maxn = 1e6 + 10, maxm = 2000 + 10;
long long factor[maxn] = {0}, d[maxm] = {0};
vector<pair<int, int> > v;
template<class T> 
void read(T& x)
{
    char c = getchar(); T p = 1, n = 0;
    while(c < '0' || c > '9'){if(c == '-') p = -1; c = getchar();}
    while(c >= '0' && c <= '9'){n = n * 10 + c - '0'; c = getchar();}
    x = p * n;
}

struct node
{
    int r, c;
    bool operator<(const node& a) const
    {
        return r < a.r || (r == a.r && c < a.c);
    }
} black[maxm];

long long power(long long a, int n)
{
    long long ans = 1;
    a %= mod;
    while(n > 0)
    {
        if(n & 1)
        {
            ans *= a;
            ans %= mod;
        }
        a *= a;
        a %= mod;
        n >>= 1;
    }
    return ans;
}

int C(int m, int n)
{
    return factor[m] * power(1LL * factor[n] * factor[m - n], mod - 2) % mod;
}
int main()
{
    int h, w, n;
    read(h), read(w), read(n);
    for(int i = 0; i < n; i++)
        read(black[i].r), read(black[i].c);
    sort(black, black + n);
    
    int max = h + w;
    factor[0] = 1;
    for(int i = 1; i <= max; i++)
        factor[i] = 1LL * factor[i - 1] * i % mod;
        
    black[n++] = (node){h, w};
    for(int i = 0; i < n; i++)
    {
        int r = black[i].r, c = black[i].c;
        d[i] = C(r + c - 2, r - 1);
        for(int j = 0; j < i; j++)
        {
            int r1 = black[j].r, c1 = black[j].c;
            if(c < c1)
                continue;
            d[i] -= d[j] * C(r + c - r1 - c1, r - r1) % mod;
            if(d[i] < 0)
                d[i] += mod;
        }
    }
    printf("%d", d[n - 1]);
    return 0;
}