雄安微网站开发,建设银行黑龙江省分行官方网站,推荐个好看的网站,宁波培训网站建设【每日一题】8月28日题目精讲 编号 链接#xff1a;https://ac.nowcoder.com/acm/problem/19925 来源#xff1a;牛客网
题目描述 你需要给一批商品编号#xff0c;其中每个编号都是一个7位16进制数#xff08;由0~9, a-f组成#xff09;。为了防止在人工处理时不小心把编…【每日一题】8月28日题目精讲 编号 链接https://ac.nowcoder.com/acm/problem/19925 来源牛客网
题目描述 你需要给一批商品编号其中每个编号都是一个7位16进制数由0~9, a-f组成。为了防止在人工处理时不小心把编号弄错要求任意两个编号至少有三个位置对应的数字不相同。第一个编号为0000000第二个编号为不违反上述规定的前提下最小的编号…每次分配一个新编号时总是选择不和前面编号冲突的最小编号注意编号都是16进制数可以比较大小。 按此规律前面若干编号分别是0000000, 0000111, 0000222, …, 0000fff, 0001012, 0001103,0001230,0001321,0001456,… 输入k你的任务是求出第k小的编号。 输入描述: 第一行为整数k。 输出描述: 输出第k小的编号字母必须输出小写。输入保证这个编号存在。 示例1 输入 复制
20输出 复制
0001321备注: 对于30%的数据k≤200 对于70%的数据k≤10000 对于100%的数据k≤200000。
题解
暴力出奇迹。。。 题目要求至少有三个位置对应的数字不相同 一个七个数所以存五个数的信息就行因为如果五个数一样那肯定不符合要求 七个选五个一共是21种方案 dp[i][a][b][c][d][e]表示第i个位置5个位置的数是a,b,c,d,e 如果一个数可行也就是21种位置上的数都没被排除
代码
#includeiostream
#includecstdio
#includecstring
#includecmath
using namespace std;
#define MAXN 10
#define for10(x) for (x0;x16;(x))int a[30][16][16][16][16][16];
int main() {/freopen(loop05.in,r,stdin);//freopen(loop05.out,w,stdout);int a1,a2,a3,a4,a5,a6,a7,k,s0;cink;for10(a1)for10(a2)for10(a3)for10(a4)for10(a5)for10(a6)for10(a7) {if(!a[0][a3][a4][a5][a6][a7]!a[1][a2][a4][a5][a6][a7]!a[2][a2][a3][a5][a6][a7]!a[3][a2][a3][a4][a6][a7]!a[4][a2][a3][a4][a5][a7]!a[5][a2][a3][a4][a5][a6]!a[6][a1][a4][a5][a6][a7]!a[7][a1][a3][a5][a6][a7]!a[8][a1][a3][a4][a6][a7]!a[9][a1][a3][a4][a5][a7]!a[10][a1][a3][a4][a5][a6]!a[11][a1][a2][a5][a6][a7]!a[12][a1][a2][a4][a6][a7]!a[13][a1][a2][a4][a5][a7]!a[14][a1][a2][a4][a5][a6]!a[15][a1][a2][a3][a6][a7]!a[16][a1][a2][a3][a5][a7]!a[17][a1][a2][a3][a5][a6]!a[18][a1][a2][a3][a4][a7]!a[19][a1][a2][a3][a4][a6]!a[20][a1][a2][a3][a4][a5]) {k--;if(!k) {printf(%x%x%x%x%x%x%x\n,a1,a2,a3,a4,a5,a6,a7);return 0;}a[0][a3][a4][a5][a6][a7]true;a[1][a2][a4][a5][a6][a7]true;a[2][a2][a3][a5][a6][a7]true;a[3][a2][a3][a4][a6][a7]true;a[4][a2][a3][a4][a5][a7]true;a[5][a2][a3][a4][a5][a6]true;a[6][a1][a4][a5][a6][a7]true;a[7][a1][a3][a5][a6][a7]true;a[8][a1][a3][a4][a6][a7]true;a[9][a1][a3][a4][a5][a7]true;a[10][a1][a3][a4][a5][a6]true;a[11][a1][a2][a5][a6][a7]true;a[12][a1][a2][a4][a6][a7]true;a[13][a1][a2][a4][a5][a7]true;a[14][a1][a2][a4][a5][a6]true;a[15][a1][a2][a3][a6][a7]true;a[16][a1][a2][a3][a5][a7]true;a[17][a1][a2][a3][a5][a6]true;a[18][a1][a2][a3][a4][a7]true;a[19][a1][a2][a3][a4][a6]true;a[20][a1][a2][a3][a4][a5]true;}}return 0;
}
