[题解]oi普及周赛13

[普及组]牛客普及周赛13题解

T1 zn的手环

大讨论一下就好了
先转化成24h制， 然后算一下时间跨度也可以。
具体如下：
1.如果同为早上或者下午， 入睡时间早于起床时间那么答案可以直接算。 否则需要把起床时间+24h来算
2.如果不同的话， 此时我们对起床时间直接+12h即可。

T2 zn的游戏

直接找最接近的两个数之间的距离就行了, 在这里两个数指max{ai}和min{ai}, 然后对距离取min即可

为什么呢...因为如果[l, r]中有子区间[l', r']满足[l', r']包含了最小值和最大值， 
那么肯定不选[l, r]。 

同理我们发现每一对最大值和最小值都能组成一个区间， 然后我们只需要取最接近的一组就行了。

由于读入量过大所以需要快读， 不然会tle最后一个点。

T3 zn的绳子

很容易可以发现， 上一个位置有没有交叉对下一个位置并没有什么影响。
然后我们可以发现最多有n - 1个交叉， 最少有0个交叉
那么我们需要<=k个交叉的话， 只需要在n - 1个交叉中选k个来放， 也就是C(n - 1, k)
然后对于n 最多为1e7 那么我们需要线性求逆元的姿势。
可以先logN算出inv(n!) 然后通过inv(i!) = inv((i + 1)!) * (i + 1) 来倒推

T4 zn的幸运数字

首先，对于质数P有这么一个性质
对于任意整数x满足 $2 \leq x\leq P$ 都有 $F(x) \leq F(P)$
很容易可以证明

首先对于p, 由于a为整数， 所以有Ap >= Ax
然后对于质数p, d(p) = 2， 由于2 ~ p内的整数都满足d(x) >= 2
所以有Bd(p) <= Bd(x)
所以Ap - Bd(p) >= Ax - Bd(x)

所以我们只需要从n往下扫到第一个质数就可以停下来了。

由于质数密度很大，在随机数据下（好像不随机数据也可以），每logN就会出现一个质数

所以期望效率是 $O(\sqrt NlogN)$ 的

但是对于x = 1的时候，考虑到 $d(1) = 1$ ，此时并不满足对于任意A, B有 $F(1) \leq F(P)$

所以我们需要特判一下x = 1时候的情况。

吐槽

QAQ怎么好像没啥人打(((
好像没啥人答疑（对比上一场是不是我语文变好了， 果然文化课快乐（迫真））
好像T2因为数据过大的原因把scanf卡了， 要快读才能过最后一个点

Code

//T1
#include<bits/stdc++.h>
using namespace std;

#define ll long long

inline ll read() {
    ll x = 0, f = 1; char ch = getchar();
    for(; ch < '0' || ch>'9'; ch = getchar())
        if(ch == '-') f = -f;
    for(; ch >= '0' && ch <= '9'; ch = getchar())
        x = x * 10 + ch - '0';
    return x * f;
}

inline void chkmin( int &a, int b ) { if(a > b) a = b; }

inline void chkmax( int &a, int b ) { if(a < b) a = b; }

#define _ read()

#define ln endl

int main()
{
    string s1, s2;
    int h1 = _, m1 = _; cin >> s1;  
    int h2 = _, m2 = _; cin >> s2; 
    if(s1 != s2)
        h2 += 12;
    else
    if(h2 < h1 || h1 == h2 && m1 > m2 )
        h2 += 24;
    int h3 = _, m3 = _;
    if(m1 > m2)
        m2 = m2 + 60, --h2;
    int h4 = h2 - h1, m4 = m2 - m1;
    if(h4 == h3 && m3 == m4)
        return puts("YES"), 0;
    puts("NO");
    cout << h4 << "h" << m4 << "min" << ln;
    // cout << h2 - h1 << "h" <<  m2 - m1 << "min" << ln;
}

//T2
#include<bits/stdc++.h>
using namespace std;

#define ll long long

inline ll read() {
    ll x = 0, f = 1; char ch = getchar();
    for(; ch < '0' || ch>'9'; ch = getchar())
        if(ch == '-') f = -f;
    for(; ch >= '0' && ch <= '9'; ch = getchar())
        x = x * 10 + ch - '0';
    return x * f;
}

inline void chkmin( int &a, int b ) { if(a > b) a = b; }

inline void chkmax( int &a, int b ) { if(a < b) a = b; }

#define _ read()

#define ln endl

int a[10000007];
int pos1, pos2, ans;
int main()
{
    int n = _; int mx = 0, mn = 2e9;
    ans = 2e9;
    for( int i = 1; i <= n; i++ )
        a[i] = _, mx = max(mx, a[i]), mn = min(mn, a[i]);
    for( int i = 1; i <= n; i++ ) 
    {
        if(mx == a[i])
            pos2 = i;
        if(mn == a[i])
            pos1 = i;
        if(pos1 && pos2)
            ans = min(abs(pos2 - pos1) + 1, ans);
    }
    cout << ans << ln;
}

//T3
#include<bits/stdc++.h>
using namespace std;

#define ll long long

inline ll read() {
    ll x = 0, f = 1; char ch = getchar();
    for(; ch < '0' || ch>'9'; ch = getchar())
        if(ch == '-') f = -f;
    for(; ch >= '0' && ch <= '9'; ch = getchar())
        x = x * 10 + ch - '0';
    return x * f;
}

inline void chkmin( int &a, int b ) { if(a > b) a = b; }

inline void chkmax( int &a, int b ) { if(a < b) a = b; }

#define _ read()

#define ln endl

const int mod = 1e9 + 7;
const int N = 1e7 + 7;
int n, k, fac[N], inv[N], ans;

inline int power( int a, int b )
{
    int tmp = 1;
    while(b)
    {
        if(b & 1)
            tmp = 1ll * tmp * a % mod;
        b >>= 1; 
        a = 1ll * a * a % mod;
    }
    return tmp;
}

inline int C( int a, int b )
{
    return 1ll * fac[a] * inv[b] % mod * inv[a - b] % mod;
}

int main()
{
    n = _; k = _; --n;
    fac[0] = 1;
    for( int i = 1; i <= n; i++ ) 
        fac[i] = 1ll * fac[i - 1] * i % mod;
    inv[n] = power(fac[n], mod - 2);
    for( int i = n - 1; i >= 0; i-- ) 
        inv[i] = 1ll * inv[i + 1] * (i + 1) % mod;
    for( int i = 0; i <= min(k, n); i++ ) 
        ans = ( ans + C(n, i) ) % mod;
    cout << ans << ln;
}

//T3
#include<bits/stdc++.h>
using namespace std;

#define ll long long

inline ll read() {
    ll x = 0, f = 1; char ch = getchar();
    for(; ch < '0' || ch>'9'; ch = getchar())
        if(ch == '-') f = -f;
    for(; ch >= '0' && ch <= '9'; ch = getchar())
        x = x * 10 + ch - '0';
    return x * f;
}

inline void chkmin( int &a, int b ) { if(a > b) a = b; }

inline void chkmax( int &a, int b ) { if(a < b) a = b; }

#define _ read()

#define ln endl

ll a, b, r, ans, tmp;

inline bool prime( ll x )
{
    for(ll i = 2; i * i <= x; i++ ) 
        if(x % i == 0 )
            return 0;
    return 1;
} 

inline ll solve( ll x )
{
    ll tmp = 0;
    for( ll i = 1; i * i <= x; i++ )
        if(x % i == 0) 
        {
            ++tmp;
            if(i * i == x);
            else ++tmp;
        }
    return tmp;
}

int main()
{
    a = _, b = _, r = _;
    ans = -2e18;
    while(r)
    {
        ll d = solve(r);
        if(a * r - b * d > ans)
            tmp = r, ans = a * r - b * d;
        // cout << r << " " << a * r + b * d << ln;
        if(prime(r))
            break;
        --r;
    }
    if(a - b > ans)
        tmp = 1;
    // cout << ans << ln;
    // cout << r << ln;
    cout << tmp << ln;
}