徐老师的仓鼠小队

题解

贪心，先排序，然后每三个一组，用这三个的最大值减最小值。

三只一组其实和两只一组是一个意思，就是如何分组可以让每组的距离之和最小

那自然是相邻的分一组最好

标程

#include <bits/stdc++.h>
using namespace std;
int a[100005];
int main(){
    int n;
    cin >> n;
    long long ans = 0;
    for(int i = 1; i <= n; i++){
        cin >> a[i];
    }
    sort(a + 1, a + 1 + n);
    for(int i = 1; i <= n; i += 3){
        ans += a[i + 2] - a[i];
    }
    cout << ans << endl;
}

徐老师的羊腿出售

题解

首先很容易想到可以用前缀和来优化，对于 $[l,r]$ 的询问

设询问的两个字母分别是 $T_1, T_2$

如果枚举一个左端点 $a[i] == T_1$ 的话，$a[i]$ 能组成的方案数就是 $sum[T_2][r] - sum[T_2][i-1]$

但是这样的操作复杂度依旧是 $O(n^2)$，只有 $40$ 分

那么观察数据范围可以发现，必须是 $O(n)$ 或者 $O(nlogn)$

并且仔细思考为什么这道题是字母而不是数字

字母只有 $26$ 个，所以我们可以考虑能否提前处理出任意两个字母两两对应的二次前缀和

也就是说处理出 $f[T][i]$ 表示到 $i$ 为止字母 $T$ 的前缀和

然后即可处理出 $sum[T_1][T_2][i]$ 表示到 $i$ 为止的 $T_1$ 对应 $T_2$ 的方案数前缀和

那么对于每次询问，即可二分出最左侧的 $T_2$ 位置 $ql$ 和最右侧的 $T_2$ 位置 $qr$

那么就可以用 $ans = sum[T_2][T_1][qr] - sum[T_2][T_1][ql - 1]$ 来计算出区间 $[l,r]$ 内的所有 $T_2$ 对于 $T_1$ 组合的方案数

再减去 $[l,r]$ 区间内的 $T_2$ 对于 $1 \sim l - 1$ 中 $T_1$ 组合的方案数即可

最后答案为 $ans = sum[T_2][T_1][qr] - sum[T_2][T_1][ql - 1] - cnt * f[l-1][T_1]$

标程

#include<bits/stdc++.h>
using namespace std;
int n,q;
string S,T;
const int MN=2e5+5;
vector<int>pos[26],sum[26][26];
int f[MN][26];
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin>>n>>q;
    cin>>S;
    for(int i=1; i<=n; i++) {
        int t=(int)(S[i-1]-'a');
        for(int x=0; x<26; x++){
            f[i][x]=f[i-1][x];
            sum[t][x].push_back(f[i][x]);
        } 
        pos[t].push_back(i);
        f[i][t]++;
    }
    for(int t=0; t<26; t++) {
        for(int x=0; x<26; x++) {
            for(int j=1; j<sum[t][x].size(); j++){
                sum[t][x][j]+=sum[t][x][j-1];
            }
        }
    }
    while(q--) {
        int l,r;
        cin>>l>>r>>T;
        int a=T[0]-'a',b=T[1]-'a';
        int ql=lower_bound(pos[b].begin(),pos[b].end(),l)-pos[b].begin();
        int qr=upper_bound(pos[b].begin(),pos[b].end(),r)-pos[b].begin()-1;
        if(ql>qr) {
            printf("0\n");
            continue;
        }
        int cnt=qr-ql+1;
        printf("%d\n",sum[b][a][qr]-(ql==0?0:sum[b][a][ql-1])
            -f[l-1][a]*cnt);
    }
    return 0;
}

徐老师的数字拼接

题解

观察数据范围可以发现，最大只会到 $99999999$，并且 $n$ 很小，直接暴力 $dfs$ ，最后去重计数即可

标程

#include<iostream>
#include<cstdio>
#include<cassert>
#include<vector>
#include<algorithm>
using namespace std;
const int N = 15,K = 5;
int n,k;
int a[N];
bool vis[N];
int b[K];
int uppw10(int x) {
    int cnt = 1;
    while(x > 0){
        x/=10;
        cnt*=10;
    }
    return cnt;
}
vector<int>v;
void dfs(int step) {
    if(step > k) {
        int val = 0;
        for(int i= 1 ; i <= k; i++)
            val = val * uppw10(b[i]) + b[i];
        v.push_back(val);
        return;
    }
    for(int i = 1; i <= n; i++){
        if(!vis[i]) {
            vis[i] = true;
            b[step] = a[i];
            dfs(step + 1);
            vis[i] = false;
        }
    }
    return;
}
int main() {
    scanf("%d%d", &n, &k);
    for(int i = 1; i <= n; i++){
        scanf("%d", &a[i]);
    }
    dfs(1);
    sort(v.begin(),v.end());
    int ans=0;
    for(int i = 0; i < (int)v.size(); i++){
        if(i==0||v[i]!=v[i-1]){
            ans++;
        }
    }
    printf("%d",ans);
    return 0;
}

徐老师的倒水计划plus

题解

可以发现，最后保留 $m$ 个玻璃杯，这些玻璃杯的水能被保留，其他玻璃杯的水就被保留一半，然后和这 $k$ 个玻璃杯的容量总和求个 $min$ 就可以了

很容易想到的就是贪心，但是显然贪心是错误的，因为你并不知道应该选容量越大的还是原本水越多的

所以明显是个类似于背包的 dp 问题

设被选中的 $m$ 个杯子的容量总和为 $a$, 水量总和为 $b$，剩下 $n - m$ 个杯子的水量之和为 $c$

答案即为 $min(a, b + c/2)$，这里我们可以发现当 $a,b$ 确认时 $c$ 是可以直接计算的

那么我们可以设 $dp[i][j][a]$ 为前 $i$ 个杯子，选了 $j$ 个，被选玻璃杯容量和为 $a$ 时的最大水量

那么我们在转移的时候只要考虑第 $i + 1$ 个杯子选或者不选即可完成转移

标程

#include <bits/stdc++.h>
using namespace std;
int a[55], b[55], dp[55][5010];

int main() {
    int n, s = 0;
    cin >> n;
    for (int i = 1; i <= n; ++i) cin >> a[i] >> b[i], s += b[i];
    memset(dp, -0x3f, sizeof(dp));
    dp[0][0] = 0;
    for (int i = 1; i <= n; ++i)
        for (int j = i; j; --j)
            for (int k = a[i]; k <= 5000; ++k)
                dp[j][k] = max(dp[j][k], dp[j - 1][k - a[i]] + b[i]);
    for (int i = 1; i <= n; ++i) {
        double ans = 0;
        for (int j = 1; j <= 5000; ++j)
            ans = max(ans, min(1.0 * j, 0.5 * (s + dp[i][j])));
        printf("%.1f ", ans);
    }
    return 0;
}