前言
这道题题面明确,思路浅显,数据也不大,本来是一道dp新手或数论萌新的练习好题,但我在本站上过了之后,在$Libre$ $OJ$和$Luogu$上都过不了,然而在下载数据后本机没问题,在$Linux$系统下的$IDE$上输出一直都与本机不一样,可能$AcWing$的系统是类似$Windows$的,一直调上调下调不出问题,可能是参数传递过程中没有初始化,或者越界了。$Linux$系统和$Windows$系统可能有一些细节的不同。然后我写了一个思路相同的$Pascal$代码(故事告诉我们多学一门语言的重要性),在这两个$OJ$上都过了,果然还是$Pascal$逻辑更加严谨
鸣谢
学委 SXL 帮我找$C++$代码中的问题,在此感谢
题目&样例
题面很清晰,没什么好说的,样例还自带解释,为用心的出题人点赞
算法1
(搜索) $O({(2^k)}^{⌈\frac{w}{k}⌉})$
把二进制下的w位分成k为一节,可以分成\frac{w}{k}节,暴力枚举每一节的数值,思路很好想,代码也不贴了(其实是没写),最后一节要特别处理,然后判断一下计下个数就好了
时间复杂度
$O({(2^k)}^{⌈\frac{w}{k}⌉})$
这个算法面对题目的数据范围肯定是会超限的,我们要对此进行优化
算法2
(dp) $O$(200 * w * $2^k$)
我们先忽略高精度
以上文所说的每一节所要填的数为阶段,转移上一节的状态,就像数位dp一样,将上一节所有比这个数大的方案全部转移过来,累加就可以了,这个思路其实并没有比暴力难想多少。
用公式表达就是
$$f[i][j]= \sum_{t=j+1}^{2^k-1}{f[i-1][t]}$$
我们可以发现,这一节的状态只与上一节有关,所以可以用滚动数组优化降低内存消耗,将空间复杂度从$O$$(200 * w * 2^k)$降低到$O$(200 * $2^k$)
同时,在累加的时候从$2^k-1$倒着遍历到$j+1$可以省去一重循环统计答案,降低$O(2^k)$的时间复杂度
答案的公式就是
$$ans= \sum_{i=2}^{⌈\frac{w}{k}⌉}\sum_{j=1}^{2^k-1}{f[i][j]}$$
$i=2$是由于题目的要求
(1)r至少是个2位的$2^k$进制数。
$j=1$是因为最高位不能为0
注意
最后一行要单独处理,只要在统计答案的时候特判就可以了
时间&空间复杂度
时间:$O$(200 * w * $2^k$)
空间:$O$(200 * $2^k$)
C++ 代码
//loj格式化大法好
#include <bits/stdc++.h>
using namespace std;
int k, w, i, ans, anss[520], t[520], j, kk, last, nown, a[50], f[5][520][520], ff[520];
int jia(int *a, int *b) {//把b加到a里面
int lenc = 0, x = 0;
while (lenc < a[0] || lenc < b[0]) {
a[++lenc] = a[lenc] + b[lenc] + x;
x = a[lenc] / 10;
a[lenc] %= 10;
}
if (x > 0)
a[++lenc] = x;
a[0] = lenc;
}//luogu第一篇题解上扣来的高精度加法(虽然那篇题解是错的),在AcWing是过的
int main() {
cin >> k >> w;
a[0] = 1;
for (i = 1; i <= 10; i++) a[i] = a[i - 1] * 2;//预处理2^k
ans = w / k;
if (w % k != 0)
ans++;//预处理节数,最后一节的处理
anss[0] = 1;
for (i = 2; i <= a[k] - 1; i++) f[1][i][0] = 1, f[1][i][1] = 1;//预处理第一节的答案
last = 1;
nown = 0;//滚动数组初始化
for (i = 2; i <= ans; i++) {
for (j = 0; j <= a[k] - 1; j++) {
for (kk = f[nown][j][0]; kk >= 1; kk--) f[nown][j][kk] = 0;
f[nown][j][0] = 1;
}//清空滚动数组
if (i == ans && w % k != 0) {//如果是最后一节且与其他节的长度不同(方便处理,避免处理余数为0的情况)
for (j = a[k] - 1; j >= 1; j--) {//枚举填的数字
jia(f[nown][j], f[nown][j + 1]);
jia(f[nown][j], f[last][j + 1]);//累加比它大的数的答案
if (j < a[w % k])//最后一节的特判,因为只有w%k位可以用,多算的对答案没有影响
jia(anss, f[nown][j]);//累加答案
}
} else {
for (j = a[k] - 1; j >= 1; j--) {
jia(f[nown][j], f[nown][j + 1]);
jia(f[nown][j], f[last][j + 1]);
jia(anss, f[nown][j]);//连特判都不用写了,注释同上
}
}
nown = 1 - nown;
last = 1 - last;//滚动
}
for (i = anss[0]; i >= 1; i--) printf("%d", anss[i]);//倒序输出
printf("\n");
}
Pascal 代码
//与c++代码同理,就不注释了
type
arr1 = array[0..221] of longint;
var
k, w, i, ans, j, kk, last, nown: longint;
anss, a, c: arr1;
f: array[0..2, 0..600] of arr1;
function jia(x, y: arr1): arr1;//把a,b加起来返回结果
var
lenc, xx: longint;
begin
fillchar(c, sizeof(c), 0);//同memset0
lenc := 0;
xx := 0;
while (lenc < x[0]) or (lenc < y[0]) do
begin
Inc(lenc);
c[lenc] := x[lenc] + y[lenc] + xx;
xx := c[lenc] div 10;
c[lenc] := c[lenc] mod 10;
end;
if xx > 0 then
begin
Inc(lenc);
c[lenc] := xx;
end;
c[0] := lenc;
exit(c);//exit带出值,类似于return
end;
begin
readln(k, w);
a[0] := 1;
for i := 1 to 20 do
a[i] := a[i - 1] * 2;
ans := w div k;
if w mod k <> 0 then
Inc(ans);
anss[0] := 1;
for i := 2 to a[k] - 1 do
begin
f[1][i][0] := 1;
f[1][i][1] := 1;
end;
last := 1;
nown := 0;
for i := 2 to ans do
begin
for j := 0 to a[k] - 1 do
begin
for kk := 1 to f[nown][j][0] do
f[nown][j][kk] := 0;
f[nown][j][0] := 1;
end;
if (i = ans) and (w mod k <> 0) then
begin
for j := a[k] - 1 downto 1 do
begin
f[nown][j] := jia(f[nown][j + 1], f[last][j + 1]);
if (j < a[w mod k]) then
anss := jia(anss, f[nown][j]);
end;
end else
begin
for j := a[k] - 1 downto 1 do
begin
f[nown][j] := jia(f[nown][j + 1], f[last][j + 1]);
anss := jia(anss, f[nown][j]);
end;
end;
nown := 1 - nown;
last := 1 - last;
end;
for i := anss[0] downto 1 do
Write(anss[i]);
writeln;
end.
后记
本题也可以用排列组合的方式解决,希望可以自行尝试