rt。我的 T3 代码:(赛后凭记忆又写了一遍)
#include<bits/stdc++.h>
using namespace std;
int t,n,m;
int dp[100050],father[100050];
int v[] = {0,6,2,5,4,3,7};
bool flag = 0;
vector<int> ans;
int main(){
scanf("%d",&t);
while(t--){
scanf("%d",&n);
flag = 0;
memset(dp,0x3f,n*4+20);
memset(father,0,n*4+20);
dp[0] = 0;
ans.clear();
ans.push_back(-1);
for(int i = 1; i <= 6; i++){
for(int j = v[i]; j <= n; j++){
if(dp[j] > dp[j-v[i]]+1){
dp[j] = dp[j-v[i]]+1;
father[j] = i;
}
}
}
if(dp[n] >= 0x3f3f3f3f){
printf("-1\n");
continue;
}
int now;
now = n;
while(now){
switch(father[now]){
case 1:
ans.push_back(0);
break;
case 2:
flag = 1;
ans.push_back(1);
break;
case 3:
flag = 1;
ans.push_back(2);
break;
case 4:
flag = 1;
ans.push_back(4);
break;
case 5:
flag = 1;
ans.push_back(7);
break;
case 6:
flag = 1;
ans.push_back(8);
break;
}
now -= v[father[now]];
}
m = ans.size()-1;
sort(ans.begin()+1,ans.end());
if(m == 1 && flag == 0){
printf("6\n");
continue;
}
if(flag == 0){
ans[1] = 2;
ans[m] = 8;
}
for(int i = 1; i <= m; i++){
if(ans[i] != 0){
swap(ans[i],ans[1]);
break;
}
}
for(int i = 1; i <= m; i++){
printf("%d",ans[i]);
}
printf("\n");
}
return 0;
}
发现假了。大概的得分范围是多少?对于哪些情况会 WA?
最希望 CCF 数据弱的一次。