这是hcz写的周赛2小结

周赛2小结

A - 卡牌游戏

这道题是纯模拟，

没什么要点，按照题目模拟即可

B - 卡牌

这道题是$DP$

初始化: $f[0][5000]=1$

分析：

$f[i][j]$表示在$b$数组中选择一些方案数使总和为$j$

状态转移方程：

当$j >=x_{i}$ : $f[i][j]=f[i-1][j]$

当$j<x_{i}$ : $f[i][j]=f[i-1][j]+f[i-1][j-x_{i}]$

样例3分析，如下图

1 2	8 5 3 6 2 8 7 6 5 9

伪代码

for(1--n){
    for(-sum+5000--sum+5000){
        if(j >= x[i]){// 两种情况
            f[i][j] = f[i-1][j] + f[i-1][j-x[i]];
        } else {
            f[i][j] = f[i-1][j];
        }
    }
}

printf("%lld", f[n][5000] - 1 > 0 ? f[n][5000] - 1:0);
// 最后输出f[n][5000]-1 ，因为在最开始多了一种方案不选，所以输出要-1

C - 表达式

$|s|<=10$

此题数据较小，$DFS$就能过

可以用substr和stoi函数简化过程

D - 网格涂色

这道题是一道思维题，当你每涂黑一块，以它为中心的$3 ×3$的数所在的九宫格都会$+1$，如图

而在计算时要注意中心点可以在的范围，$x > 1$ && $x < h$ && $y > 1$ && $y < w$

注意最后计算$ans[0]=(h-2)(w-2)-ans[1 \to 9]$

伪代码如下：

for(1--n){
        //输入a, b
        for(j:-1--1){
            for(k:-1--1){
                int x = a+j,y = b+k;
                if(x > 1 && x < h && y > 1 && y < w){

                    now = ++mp[{x, y}];
                    ans[now]++;
                    ans[now-1]--;
                }
            }
        }
    }
// 处理部分

E - 数字

先简化题意，函数$f(b, n)$代表求n的b进制的各位数字之和，要确定最小的数字b使$f(b, n)=s$

2个特判

1：当$n<s$，输出$-1$

因为在任何进制下，数字的各位之和是不会大于 n 的，所以不可能存在

2：当$n=s$,输出$n+1$，这个比较好理解，在$n+1$进制，$n$不变

重点部分

1
2
3

for(int i=2;i<=sqrt(n);i++){
    if(ff(i, n) == s ) ans = min(ans, i);
}

我们需要找到一个进制 b 使得 $f(b,n)=s$，也就是说，找到一个进制 b，使得在该进制下，数字$n$的各位之和等于给定的 s。

当$m> \sqrt{n}$，转换后只有2位

$n=mx+y $
$ s=x+y $
$ n-s=(m-1)x $
$ m=(n-s) x+1$

所以，$x$的范围$1$ ~ $\sqrt{n-s}$

for(int i = sqrt(n - s); i >= 1; i--) {
    if(ff((n - s) / i + 1, n) == s) {
        ans = min(ans, (n - s) / i + 1);
    }
}

输出注意long long

1	printf("%lld", ans == LONG_LONG_MAX ? -1ll : ans);