徐老师的吉祥数
题解
送分题，暴力枚举即可
标程
#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;
}