A.小苯接雨水

显然把最长的两块板放在两侧最优。

答案即为次大 $\times (n-1)$ 。

void solve(){
    ll n = read();
    vector<ll> a(n+1);
    for(ll i=1;i<=n;i++) a[i] = read();
    sort(all(a));
    print(a[n-1]*(n-1));
}

B.小芳与残骸

注意到由于限制了 $a_i \in {0, 1}$ ，操作等价于求数组的异或和。

则原数组中必有奇数个 $1$ 。

则种类为 $\sum \limits_{i=1\texttt{ and }i \mod 2 = 1}^{n} C(n, i) = 2^{n-1}$ 。（二项式定理可得）

void solve(){
    print(ksm(2, read()-1));
}

C.小苯的棋盘游戏

手玩一下可以得到，当 $n,m$ 中有一奇数时，可以绕到。否则不能。

void solve(){
    ll n = read(), m = read();
    puts((n%2==1||m%2==1)?"YES":"NO");
}

D.暴暴龙的防奶龙要塞

不难想到，由于题目要求有一个割点且没有割边，我们可以造出两个环公用一个点的图。

例如

solve

使用 $n+1$ 条边。

当 $n < 5$ 时，可以发现没有解。

void solve(){
    ll n = read();
    if(n < 5){
        print(-1);
        return;
    }
    print(n+1);
    print(PLL{1, 2});
    print(PLL{2, 3});
    print(PLL{1, 3});
    for(ll i=4,pre=1;i<=n;i++){
        print(PLL{pre, i});
        pre = i;
    }
    print(PLL{n, 1});
}

E.奶龙与奥利奥自动机

~~个人解法：打表 + OEIS~~

结论：方案数为 $F_{2n+3}-1$ 。（ $F$ 为斐波那契数列。）

令 $奥 = A, 利 = B$ 。

令 $num_{k}$ 为 $k$ 次非空操作形成的字符串数量。

令 $a_k$ 为结尾为操作 $1$ （即添加了 $A$ ）的字符串数量。

令 $b_k$ 为结尾为操作 $2$ （即添加了 $B$ ）的字符串数量。

令 $c_k$ 为结尾为操作 $3$ （即添加了 $AB$ ）的字符串数量。

注意到对于 $b_k$ ，上一步不能结尾为操作 $1$ ，否则会重复，我们约定将这种情况归入 $c_k$ 中。

$a_k, c_k$ 上一步可以任意取。

则有 $a_k = num_{k-1}, c_k= num_{k-1}, b_k = b_{k-1} + c_{k-1}$ 。

所以 $num_k = a_k + b _k + c_k = 2 num_{k-1} + (b_{k-1} + c_{k-1})$

$= 2 num_{k-1} + (num_{k-1} - a_{k-1}) = 3 num_{k-1} - a_{k-1} = 3 num_{k-1} - num_{k-2}$ 。

归纳法或者特征根方程可以得到 $num_k = F_{2k+2}$ 。

则答案为 $\sum \limits_{k=0}^{n} num_k =\sum \limits_{k=0}^{n}F_{2k+2} = F_{2n+3}-1$ 。

void solve(){
    ll n = read();
    ll a = 1, b = 1;
    for(ll i=3;i<=2*n+3;i++){
        ll c = b%MOD;
        b = (a + b)%MOD;
        a = c%MOD;
    }
    print((b-1+MOD)%MOD);
}

F.奶龙智斗暴暴龙

~~个人解法：打表~~

结论：最优解是一个桶 $1$ 个鲱鱼罐头，剩下的全部放另一个,概率为 $P = \frac{3n-2}{4n-2}$ 。

设桶 $1$ 中有 $a$ 个物品， $b$ 个鲱鱼罐头。

不妨令桶 $1$ 中物品数量小于等于桶 $2$ 中物品数量，即 $1\le a\le n$ 。

则概率为 $P = \frac{1}{2} \cdot \frac{b}{a} + \frac{1}{2} \cdot \frac{n-b}{2*n-a} = \frac{2b(n-a)+an}{2a(2n-a)}$ 。

此时可以发现 $P$ 关于 $b$ 单增，则最优取 $b=a$ 。此时概率为 $P = \frac{3an - 2a^2}{2a(2n-a)} = \frac{3n-2a}{4n-2a} = \frac{1}{2} - \frac{n}{4n-2a}$ 。

此时显然 $a=1$ 时最优，概率为 $P = \frac{3n-2}{4n-2}$ 。

void solve(){
    ll n;cin>>n;
    cout<<fixed<<setprecision(6)<<1.0*(3*n-2)/(4*n-2)<<'\n';
}

G.小红的抛物线

直接解方程判断 $a$ 正负就行了。

可得 $a = \frac{(y_3-y_2)(x_2-x_1) - (y_2-y_1)(x_3-x_2)}{(x_3-x_2)(x_2-x_1)(x_3-x_1)}$

ll sign(ll x){
    if(x>0) return 1;
    return -1;
}
void solve(){
    ll x0 = read(), y0 = read(), x1 = read(), y1 = read(), x2 = read(), y2 = read();
    ll fz = sign((y2-y1)*(x1-x0)-(y1-y0)*(x2-x1));
    ll fm = sign((x2-x1)*(x1-x0)*(x2-x0));
    if(fz*fm>0){
        puts("UP");
    }
    else{
        puts("DOWN");
    }
}

H.小苯的序列染色

可以发现最多只有 $2*n$ 个有效序列。（每个点往左一个，往右一个）

只需找出所有的合法区间，贪心找出最小选择数量就行了。

void solve(){
    ll n = read();
    vector<ll> a(n+1);
    for(ll i=1;i<=n;i++){
        a[i] = read();
    }
    vector<ll> dp(n+1, INF);
    dp[0] = 0;
    vector<PLL> segs;
    for(ll i=1;i<=n;i++){
        ll l = i-a[i]+1;
        if(l>=1&&a[i]>=a[l]){
            segs.pb({l, i});
        }
        ll r = i+a[i]-1;
        if(r<=n&&a[i]>=a[r]){
            segs.pb({i, r});
        }
    }
    sort(all(segs), [&](PLL &a, PLL &b){
        if(a.fi!=b.fi) return a.fi<b.fi;
        else return a.se > b.se;
    });
    ll p = 1, idx = 0, cnt = segs.size(), ans = 0, f = 1;
    while(p<=n){
        ll mx = -1;
        while(idx<cnt&&segs[idx].fi<=p){
            mx = max(mx, segs[idx].se);
            idx++;
        }
        if(mx < p){
            f = 0;
            break;
        }
        ans++;
        p = mx + 1;
    }
    print(f?ans:-1);

}

I. 小苯的字符串构造

可以发现 $n$ 为奇数时， $n$ 个 $a$ 满足要求；否则 $n-1$ 个 $a$ 和 $1$ 个 $b$ 拼满足要求。

void solve(){
    ll n;cin>>n;
    string ans(n, 'a');
    if(n%2==0) ans[n-1]='b';
    cout<<ans<<'\n';
}

J. 小苯的运算式

令 $dp_{i, 0}$ 为选择 $a_i$ 且在序列的奇数下标出现的最大值。

$dp_{i, 1}$ 为选择 $a_i$ 且在序列的奇数下标出现的最大值。

则有 $dp_{i, 0} = \max(a_i, \max \limits_{j=1}^{i-1} (dp_{j, 1} + a_i))$

$dp_{i, 1} = \max \limits_{j=1}^{i-1} (dp_{j, 0} + a_i)$

取最大即可。

void solve(){
    ll n = read();
    vector<ll> a(n+1);
    for(ll i=1;i<=n;i++){
        a[i] = read();
    }
    PLL dp = {a[1], -INF};
    for(ll i=2;i<=n;i++){
        PLL ndp = {max({dp.se+a[i],a[i],dp.fi}),max({dp.se, dp.fi-a[i]})};
        dp = ndp;
    }
    print(max(dp.fi,dp.se));
}

K. 小苯的闯关游戏

二分搜索初始战力的最小值即可。

void solve(){
    ll n = read();
    vector<ll> a(n+1);
    for(ll i=1;i<=n;i++){
        a[i] = read();
    }
    function<ll(ll)> check = [&](ll mid){
        ll x = mid;
        for(ll i=1;i<=n;i++){
            if(x > a[i]) x++;
            else if(x < a[i]) x--;
        }
        return x > mid;
    };
    ll l = 0, r = 1e9+7, ans=-1;
    while(l<=r){
        ll mid = (l + r)>>1;
        if(check(mid)){
            ans=  mid;
            r = mid - 1;
        }
        else{
            l = mid + 1;
        }
    }
    print(ans);
}

L. 小苯的序列还原

可以发现，长度为 $n$ 数组操作过后原来的下标会移动成 $[n,n-2,n-4 \dots n-3,n-1]$ 的形式。

双指针模拟还原即可。

void solve(){
    ll n = read();
    vector<ll> a(n+1), ans(n), t(n);// t_i 代表原来下标为 i+1 的数现在的下标
    for(ll i=1;i<=n;i++){
        a[i] = read();
    }
    ll l = 0, r = n-1, num = n;
    for(ll i=1;i<=n;i++){
        if(i&1){
            t[l] = num;
            l++;
        }
        else{
            t[r] = num;
            r--;
        }
        num--;
    }
    for(ll i=1;i<=n;i++){
        ans[t[i-1]-1] = a[i];
    }
    print(ans);
}

M.GPA Calculator

按题意模拟即可。

怕被卡小数的话本题可以全程整数操作。

void solve(){
    string s;cin>>s;
    int num = 0;
    for(auto v:s){
        if(v == '.') continue;
        num = num * 10 + v-'0';
    }
    if(num < 600){
        cout<<"0.00\n";
    }
    else{
        num -= 500;
         
        cout<<num/100<<"."<<setfill('0')<<setw(2)<<num%100<<'\n';
    }
}

题解 | #第十七届北京信息科技大学程序设计竞赛（校外同步赛）#