CSP-J 2024 t3 小木棍
xinlong666
·
·
题解
题面
已知题目，可知要尽量位数最小，又要尽量高位最小，可知道一个贪心策略，从高到低每一位都取最小。
```cpp
int w = (n+6)/7;
int s = n;
```
是不是就求出来了。
接着整个循环，对于每一位找到可以取的**最大根数**和**最小根数**。
```cpp
for (int i = 1 ; i <= w ; i ++){
int l,r;
l=max((int)2,s-(w-i)*7);//小的位数都用8要 (w-i)*7 根木棍
r=min((int)7,s);
//省略
}
```
知道这些后，我们整个打表代码造两个数组。
```cpp
#include<bits/stdc++.h>
#define int long long
using namespace std;
int su[10] = {0,0,1,7,4,2,6,8,0,0};//这里还要6改成0再整一次。
int kk[10][10];
signed main (){
ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
for (int i = 2 ; i <= 7 ; i ++){
for (int j = i ; j <= 7 ; j ++){
kk[i][j] = 1e9;//赋值大数
for (int k = i ; k <= j ; k ++){
kk[i][j] = min(kk[i][j],su[k]);//寻找最小值
}
}
}
for (int i = 2 ; i <= 7 ; i ++){
cout << '{';
for (int j = 2 ; j <= 7 ; j ++){
cout << kk[i][j] << ',';//输出答案
}
cout << '}' << ',' << endl;
}
return 0;
}
```
然后我们得到了两个数组。
$kk_{i,j}$ 表示第 $i+2$ 到第 $j+2$ 个木棍可以拼成的最小数。
$kc$ 数组为第一位的表。
```cpp
int kk[6][6] = {
{1,1,1,1,0,0,},
{0,7,4,2,0,0,},
{0,0,4,2,0,0,},
{0,0,0,2,0,0,},
{0,0,0,0,0,0,},
{0,0,0,0,0,8,}
};
int kc[6][6] = {
{1,1,1,1,1,1,},
{0,7,4,2,2,2,},
{0,0,4,2,2,2,},
{0,0,0,2,2,2,},
{0,0,0,0,6,6,},
{0,0,0,0,0,8,}
};
```
有什么用呢，当然是让我们的查找变为 $O(1)$ 的复杂度。
再定义一个数组为数 $i$ 要用的木棍数位 $su_i$ 。
然后使用就好了。
```cpp
for (int i = 1 ; i <= w ; i ++){
int l,r;
l=max((int)2,s-(w-i)*7);
r=min((int)7,s);
//cout << l << ' ' << r << endl;
l-=2;
r-=2;
if(i==1){
cout << kc[l][r];
s-=su[kc[l][r]];
continue;
}
cout << kk[l][r];
s-=su[kk[l][r]];
}
cout << endl;
```
完整代码如下
```cpp
#include<bits/stdc++.h>
#define int long long
using namespace std;
int su[10] = {6,2,5,5,4,5,6,3,7,6};
int kk[6][6] = {
{1,1,1,1,0,0,},
{0,7,4,2,0,0,},
{0,0,4,2,0,0,},
{0,0,0,2,0,0,},
{0,0,0,0,0,0,},
{0,0,0,0,0,8,}
};
int kc[6][6] = {
{1,1,1,1,1,1,},
{0,7,4,2,2,2,},
{0,0,4,2,2,2,},
{0,0,0,2,2,2,},
{0,0,0,0,6,6,},
{0,0,0,0,0,8,}
};
void zxk(){
int n;
cin >> n;
if(n==1){
cout << -1 << endl;
return;
}
int w = (n+6)/7;
int s = n;
for (int i = 1 ; i <= w ; i ++){
int l,r;
l=max((int)2,s-(w-i)*7);
r=min((int)7,s);
//cout << l << ' ' << r << endl;
l-=2;
r-=2;
if(i==1){
cout << kc[l][r];
s-=su[kc[l][r]];
continue;
}
cout << kk[l][r];
s-=su[kk[l][r]];
}
cout << endl;
return;
}
signed main (){
ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
int t;
cin >> t;
while(t--)zxk();
return 0;
}
```