跳至正文

USACO 3.1.3 Humble Numbers 解题报告

  • OI路程

这个题目属于什么算法呢?我才疏学浅不知道,反正就是用num来记录丑数,假设1为丑数,代码实现会简单些,那么丑数必定就等于另外一个丑数乘以一个素数,那么再一个个的按大小找到前n个丑数,就可以了。 时间的话大概是O(nm),对每个素数都记录该和哪个丑数相乘start[i],如果sub[i](第i个素数)num[start[i]]是下一个丑数,那么start[i]就加一,如果sub[i]num[start[i]]和当前最大的丑数(就是才成为丑数的丑数)相等的话那start[i]也是要加一的,就这样循环。 / LANG: C ID: yylogoo1 PROG: humble / #include unsigned sub[100], num[100000]; int start[100]; int len; void add(int k) { num[len++] = k; } int main(void) { int i, j, k; int m, n; int min, in; freopen("humble.in", "r", stdin); freopen("humble.out", "w", stdout); scanf("%d%d", &m, &n); for(i = 0; i <m i scanfu subi add whilelen="n){" min="0xFFFFFFFF;" fori="0;" i m i ifsubi numstarti="= num[len" - starti ifmin> sub[i] num[start[i]]){ in = i; min = sub[i] * num[start[i]]; } } add(min); start[in]++; } printf("%u\n", num[n]); return 0; }

发表回复

您的电子邮箱地址不会被公开。