2020牛客NOIP赛前集训营-普及组（第五场）

A T1 购物

分析

由于是买 送一，所以我们考虑买 只需要 次花钱的购买。那么可以把 个物品分成很多段，每段的长度为 ，然后处理一下边角就好了。

代码

#include<bits/stdc++.h>
using namespace std;
int read() {int x;scanf("%d",&x);return x;}
int solve(int a,int b,int c) {
    return (a / (b + 1) * b + (a % (b + 1))) * c;
}
int main() {
    int T = read();
    while(T--) {
        int n,k,x;
        n = read();k = read();x = read();
        cout << solve(n,k,x) << endl; 
    }
}

B T2 交换

分析

对于环的分析，我们习惯于破环成链。这样在一个序列上也可以表示所有环了。那么我们就在这个长度为 的序列上找到最长的全为 的子串就好了。需要处理一下子串的长度大于 的情况。

代码

#include<bits/stdc++.h>
using namespace std;
int read() {int x;scanf("%d",&x);return x;}
const int N = 210000;
char ch[N];
int main() {
    scanf("%s",ch + 1);
    int n = strlen(ch + 1),ans = 0;
    for(int i = 1;i < n;i++) ch[i + n] = ch[i];
    for(int i = 1,last = 0;i < n * 2;i++) {
        if(ch[i] == '1' && ch[i - 1] != '1') last = i;
        if(ch[i] == '1' && i - last + 1 <= n) ans = max(ans,i - last + 1);
    } 
    cout << ans << endl;
}

C T3 最少移动

分析

我们发现任意操作都不会改变 的，也就是总和不变。那么最后每个点的权值一定是 的，那么 的就可以输出 。因为要改变 就必须操作 所以我们可以从一个端点 扫一遍就好了。

代码

#include<bits/stdc++.h>
using namespace std;
int read() {int x;scanf("%d",&x);return x;}
#define ll long long
const int N = 1e5 + 100;
int a[N];ll s;
int main() {
    int T = read();
    while(T--) {
        s = 0;int n = read();
        for(int i = 1;i <= n;i++) {
            a[i] = read();
            s += a[i];
        }
        ll ans = 0;
        if(s % n) {printf("-1\n");continue;}
        for(int i = 1;i <= n;i++) {
            int sum = s / n - a[i];
            a[i + 1] -= sum;
            ans += abs(sum);
        }
        cout << ans << endl; 
    }
}

D T4 飞行棋

分析

我们定义 为到节点 的期望回合数，那么 。由于 时每个节点只有 的概率转移到 剩下的 也会转移到另一个 的 节点。所以 时，每个 是相同的。 。那么当 时，直接转移就好了，用前缀和维护一下，时间复杂度为 。注意一下掷出来 时，并不改变回合数。

代码

#include<bits/stdc++.h>
using namespace std;
int read() {int x;scanf("%d",&x);return x;}
#define ll long long
const int N = 1e5 + 100;
double f[N],s[N];
int main() {
    int T = read();
    while(T--) {
        int n = read(),d = read();s[0] = f[0] = 1;
        for(int i = 1;i < d;i++) s[i] = d - 1,f[i] = f[i - 1] + s[i];
        for(int i = d;i <= n;i++) {
            s[i] = (f[i - 1] - f[i - d] + d - 1) / (1.0 * d) + s[i - d] / (1.0 * d);
            f[i] = f[i - 1] + s[i];
        }
        printf("%.2f\n",s[n]);
    }
}