徐老师的吉祥数

题解

送分题，暴力枚举即可

标程

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

bool check(int x) {
    while (x > 1){
        if (x % 3 != 0){
            return false;
        }
        x /= 3;
    }
    return true;
}
int a[1000100], len = 0;
int main() {
    int l, r, ans = 0;
    scanf("%d%d", &l, &r);
    for (int i = l; i <= r; ++i){
        if (check(i)){
            ans++;
            a[len++] = i;
        }
    }
    printf("%d\n", ans);
    for (int i = 0; i < len; ++i){
        printf("%d ", a[i]);
    }
    return 0; 
}

徐老师的二进制加法

题解

想太多容易做不出来，其实这道题直接模拟计算即可

因为每次只加一个 $2^k$ 也就是二进制上只有 $1$ 个 $1$

单次进位次数最多可以达到 $n$ 次，比如 $11111111 + 1$

但是这次以后进位次数就没了，所以平均下来进位次数最多也就是 $n + m$

所以直接模拟即可，不会超时

为了方便计算可以像高精度一样把数字倒过来存

但是注意数组得多开一些，因为最高位可能会进位

至少需要开到 $n + logm$

当然了，平时习惯好的话数组稍微大一点就可以，比如开到 $1000100$ 肯定够用了

标程

#include <bits/stdc++.h>
using namespace std;
const int N=1e6+30;
int n,q,k,ans;
bool a[N];
char c[N];

int main(){
    scanf("%d", &n);
    scanf("%s", c);
    for(int i = 0; i < n; ++i){
        a[n - i - 1] = c[i] - '0';
    }
    scanf("%d", &q);
    while(q--){
        scanf("%d", &k);
        ans = 1;
        while(a[k]){
            a[k++] = 0;
            ans++;
        }
        a[k] = 1;
        printf("%d\n", ans);
    }
    n += log2(n) + 1;
    while(!a[n]){
        n--;
    }
    for(int i = n; i >= 0; --i){
        printf("%d", a[i]);
    }
    return 0;
}

徐老师的同桌分配

题解

很容易想到贪心就是最小的配最大的，如果只求一次结果，直接排序即可，现在的问题是每新增一组就要进行一次计算

这里我们可以考虑，因为每次只在两个数组中各新增一个数字，之前的数组如果已经有序，其实可以用插入排序的方式维护一次即可，那么可以用二分找到应该插入的位置，然后插入并计算结果，但是这样的话一次插入的复杂度依旧是 $O(n)$ 的，总体复杂度 $O(n^2)$

观察题目可以发现，这道题有一个特殊的约束，就是成绩最大只有 $100$ 分，所以为了方便维护，我们完全可以直接用桶排序来做到每次插入一个数字

这样的话配对的过程就只需要枚举 $100$ 次分数即可，那么复杂度就可以降低到 $O(100 * n)$ 即可通过

标程

#include <bits/stdc++.h>
using namespace std;
const int N=1e5+5,V=105;
int n,a[N],b[N],ta[V],tb[V],tmpa[V],tmpb[V];

int qry(){
    for(int i=1;i<=100;++i)tmpa[i]=ta[i],tmpb[i]=tb[i];
    int l=1,r=100,maxn=0,tmp;
    while(!tmpa[l])l++;
    while(!tmpb[r])r--;
    while(l<=100&&r>=1){
        tmp=min(tmpa[l],tmpb[r]);
        tmpa[l]-=tmp,tmpb[r]-=tmp;
        maxn=max(maxn,l+r);
        while(!tmpa[l] && l <= 100)l++;
        while(!tmpb[r] && r >= 1)r--;
    }
    return maxn;
}

int main(){
    scanf("%d", &n);
    for(int i=1;i<=n;++i){
        scanf("%d%d", &a[i], &b[i]);
        ta[a[i]]++,tb[b[i]]++;
        printf("%d\n", qry());
    }
    return 0;
}

徐老师的炉石传说

题解

首先对于过牌的技能来说，就是让这个牌组变成了一个环，那我们可以破坏成链，把卡组复制一遍即可解决这个问题，这个也是部分分中会考虑用到的

接着考虑正解

首先我们会发现，不管是递推也好搜索也好，打牌顺序决定了能打出的牌，如果陷入这个角度可能会很难想到正解

我们从结果倒推回来观察会发现，其实能打出去的牌一定就是在 $n$ 张牌中选了一部分

比如现在选中了 $S$ 张牌，那这 $S$ 张牌要符合一个什么要求呢？

要保证这 $S$ 张牌打出的时候不会导致其他被选中的牌被弃

我们会发现，被选中的这 $S$ 张牌的 $x_i$ 之和必然是 $\leq n$ 的，这个毋庸置疑，弃牌数量总和不可能超过 $n$

接着我们把选出的这 $S$ 张牌之间的距离记为 $dis_i$，也可以发现 $\sum{dis_i} = n$

结合以上两点，我们可以确认，在这 $S$ 张牌中至少存在一张 $x_i \leq dis_i$ 的牌

即打出这张牌时不会导致下一张牌被弃，那么打出这张牌，接着剩下 $S-1$ 张牌，又回到了上述问题

所以可以证明，只要选好了 $S$ 张牌，必然存在一定的出牌顺序使得这 $S$ 张牌被打出并且互不影响

那么现在的问题就变成了，在 $n$ 张牌中选 $S$ 张牌，保证 $\sum{x_i} \leq n$ 的情况下，求最大的 $\sum{y_i}$ 这就是一个基础 $01$ 背包问题了

标程

#include<bits/stdc++.h>
using namespace std;
int n, x[1010], y[1010], dp[1010], ans;

int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; i++){
        scanf("%d", &x[i]);
    }
    for (int i = 1; i <= n; i++){ 
        scanf("%d", &y[i]);
    }
    for (int i = 1; i <= n; i++){
        for (int j = n; j >= 0; j--){
            if (j >= x[i]){ 
                dp[j] = max(dp[j], dp[j - x[i]] + y[i]);
            }
        }
    }
    for (int i = 1; i <= n; i++){ 
        ans = max(ans, dp[i]);
    }
    printf("%d\n", ans);
    return 0;
}