比赛链接

难度递增：FDABEC

A

枚举中间隔板的位置，然后分别枚举左右隔板，找到最大值。时间复杂度 。

//赛时代码 by zys
#include<bits/stdc++.h>
using namespace std;
#define int long long 
const int maxn=5010;
int n;
int a[maxn];
int ans;
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        cin>>a[i];
    }
    for(int i=2;i<n;i++)
    {
        int ansl=0;
        int ansr=0;
        for(int l=1;l<i;l++)
        {
            ansl=max(ansl,(i-l)*min(a[l],a[i]));
        }
        for(int r=i+1;r<=n;r++)
        {
            ansr=max(ansr,(r-i)*min(a[i],a[r]));
        }
        ans=max(ans,ansl+ansr);
    }
    cout<<ans;
    return 0;
}

B

容易发现任意五局形成 00111 的概率为 。

长度为 的字符串有 个长度为 的子串，每个字串形成 00111 的概率都是上述值，于是答案就是 。要特判 的情况。

//赛时代码 by fqr
#include<bits/stdc++.h>
using namespace std;
#define endl '\n' 
#define int long long
namespace Main
{
    const int p = 1e9 + 7;
    int qpow(int a,int k)
    {
        int res=1;
        while(k)
        {
            if(k&1)
                res = res * a % p;
            k >>= 1;
            a = a * a % p;
        }
        return res;
    }
    int a, b, n;
    int pwin, plose, p1;
    void solve()
    {
        cin >> a >> b >> n;
        if(n<=4)
            return cout << 0 << endl, void();
        pwin = a * qpow(b, p - 2) % p, plose = (1 - pwin + p) % p;
        p1 = qpow(plose, 2) * qpow(pwin, 3) % p;
        cout << p1 * (n - 4) % p << endl;
    }
     
    void main()
    {
        ios::sync_with_stdio(0);
        cin.tie(0);cout.tie(0);
        int _;cin>>_;while(_--) solve();
    }
};
 
signed main()
{
    Main::main();
    return 0;
}

C

zys 通过打表发现，，比较类似于斐波那契数列的性质。

于是考虑枚举 ，求 的 个数。

zyz 赛时用欧拉函数求的，下面是一个更简单的做法：

设 的 个数为 。则 可以表示为：

( 是 的公约数的 个数 ) ( 的 的个数 )。

则上述式子可以表示为 。倒着递推即可。时间复杂度 。

最终答案即为 

//赛时代码 by zyz
# include <bits/stdc++.h>
 
using namespace std;
 
const int N = 3e6 + 5 , mod = 1e9 + 7;
int n , f[N] , primes[N] , phi[N] , vis[N] , pcnt , ans;
 
void init()
{
    vis[1] = 1;
    phi[1] = 1;
    for(int i = 2; i <= n; i++)
    {
        if(!vis[i]) phi[i] = i - 1 , primes[++pcnt] = i;
        for(int j = 1; j <= pcnt && i * primes[j] <= n; j++)
        {
            vis[i * primes[j]] = 1;
            if(i % primes[j] == 0) 
            {
                phi[i * primes[j]] = 1ll * phi[i] * primes[j] % mod;
                break ;
            }
            phi[i * primes[j]] = 1ll * phi[i] * phi[primes[j]] % mod;
        }
    }
    for(int i = 2; i <= n; i++) phi[i] = (1ll * phi[i - 1] + phi[i]) % mod;
}
 
 
int main()
{
    cin >> n;
    init();
    f[0] = 0 , f[1] = 1;
    for(int i = 2; i <= n; i++) f[i] = (3ll * f[i - 1] % mod + 2ll * f[i - 2] % mod) % mod;
    for(int i = 1; i <= n; i++)
    {
        ans = (ans + 1ll * f[i] * (2ll * phi[n / i] % mod - 1 + mod) % mod) % mod;
    }
    cout << ans;
    return 0;
}

//赛后代码 by fqr
#include<bits/stdc++.h>
using namespace std;
#define int long long

namespace Main
{
    const int N = 3000010, p = 1e9 + 7;
    int n;
    int f[N], F[N];
    void main()
    {
        ios::sync_with_stdio(0);
        cin.tie(0);cout.tie(0);
        cin >> n;
        F[0] = 0, F[1] = 1;
        for (int i = 2; i <= n; i++)
            F[i] = (3 * F[i - 1] % p + 2 * F[i - 2] % p) % p;
        int ans = 0;
        for (int i = n; i >= 1; i--)
        {
            f[i] = (n / i) * (n / i) % p;
            for (int j = i + i; j <= n; j += i)
                f[i] = ((f[i] - f[j]) % p + p) % p;
            ans += f[i] * F[i] % p, ans %= p;
        }
        cout << ans;
    }
};

signed main()
{
    Main::main();
    return 0;
}

D

容易发现某个数除以 可以得到所有胜率，于是场数 ，两层循环暴力枚举即可。

//赛时代码 by zys
#include<bits/stdc++.h>
using namespace std;
int main()
{
    double a;
    cin>>a;
    for(double i=1;i<=10000;i++)
    for(double j=1;j<=i;j++)
    {
        if(abs(100.0*j/i-a)<=0.005) 
        {
            cout<<i;
            return 0;
        }
    }
    return 0;
}

E

引理 1：双方每次取的石子数量都是奇数。

证明： = ，易证 是偶数，所以原式是奇数。

引理 2：谁取到最后一个石子，谁就获胜。

证明：当 或 取 时，两方都可以取 个石子，所以只有当没有石子时会失败，于是谁取到最后一个石子，谁就获胜。

由引理 1 可知，每次取完石子，剩余数量的奇偶性都会改变。由引理 2 可知，游戏结束时，石子数量为 ，是偶数。

因此若 为奇数先手胜，否则后手胜。

//赛时代码 by fqr
#include<bits/stdc++.h>
using namespace std;
#define endl '\n' 
 
namespace Main
{
    void solve()
    {
        int a, b, n;
        cin >> a >> b >> n;
        cout << (n % 2 == 1 ? "Alice" : "Bob") << endl;
    }
     
    void main()
    {
        ios::sync_with_stdio(0);
        cin.tie(0);cout.tie(0);
        int _;cin>>_;while(_--) solve();
    }
};
 
int main()
{
    Main::main();
    return 0;
}

F

经过两位数减法可知，答案为 。

//赛时整活代码 by zys
#include<bits/stdc++.h>
using namespace std;
int main()
{
    int ans=0;
    for(int i=1;i<=27;i++)
    {
        ans++;
    }
    cout<<ans<<endl;
    return 0;
}