Chinaunix

标题: 刚看到了这样一道题 [打印本页]

作者: zmy235 时间: 2014-07-31 10:32
标题: 刚看到了这样一道题
本帖最后由 zmy235 于 2014-07-31 10:38 编辑

给定一个正整数x，我们定义函数w(x)表示x的各个数位之和，例如w(1)=1 w(11)=2 w(223)= 7。
我们定义一种顺序，对正整数x和y, 如果w(x)<w(y) 或者w(x) == w(y)并且x的字典序比y小（按字符串算），则认为x“小于”y。
例如我们认为100 “小于” 2 因为w(100) = 1 w(2) = 2我们认为 370 ”小于” 55 这是因为字符串w(370) = w(55) = 10 但是”370” < “55”。
给定正整数n和k,1<=k<=n，我们把1-n之间全部的正整数按上述关系由“小”到“大”排好顺序，请问k在第几个位置？另外，第k个位置的数是几？

输入格式
多组数据，每组数据一行包含两个整数n和k，(1<=k<=n<=10^18 )
输出格式
每组数据一行，包含两个空格分隔的整数，第一个是k的位置，第二个是第k个整数

作者: super皮波 时间: 2014-07-31 10:39
兄弟你看错题了把
按你说的
n限制在10之内，并且你只排到n-1，也就是9

所以结果1 2 3 .. k...n-1

作者: super皮波 时间: 2014-07-31 10:40
蛋疼的问题，像脑筋急转弯，前边说了半天要求都没用。。。

作者: cobras 时间: 2014-07-31 10:47
不要想当然。按照题目要求进行排序。而非数字大小排序。
数据存储是一个要考虑的问题，否则会严重影响运行效率。

作者: zmy235 时间: 2014-07-31 10:47
回复 3# super皮波

你没有见过"10^x"这样的表示方式？

作者: super皮波 时间: 2014-07-31 11:35
发的帖子还能改？？？？？？？

你刚发的时候明明是10^1
回复 5# zmy235

作者: super皮波 时间: 2014-07-31 11:37
本帖最后由 zmy235 于 2014-07-31 10:38 编辑
本帖最后由 zmy235 于 2014-07-31 10:38 编辑
本帖最后由 zmy235 于 2014-07-31 10:38 编辑

你改动过这个帖子把？？？
回复 5# zmy235

作者: super皮波 时间: 2014-07-31 11:39
是我眼睛瞎了还是你耍小聪明自己改帖子？

作者: cjaizss 时间: 2014-07-31 14:41

super皮波发表于 2014-07-31 11:39
是我眼睛瞎了还是你耍小聪明自己改帖子？

我找到了题目的出处
http://hero.csdn.net/Question/Details?ID=623&ExamID=618

作者: super皮波 时间: 2014-07-31 14:55
lz自己写错了题目，我看的时候就是10^1 我就随便说了一句，你看他帖子发表的时间和1楼帖子编辑的时间
回复 9# cjaizss

作者: super皮波 时间: 2014-07-31 14:57
你居然能找到题目

回复 9# cjaizss

作者: littledick 时间: 2014-07-31 19:59
本帖最后由 littledick 于 2014-07-31 20:00 编辑

做出来啥奖励？

作者: zmy235 时间: 2014-08-01 08:49
回复 9# cjaizss

哎呀，被你找到了。

作者: zmy235 时间: 2014-08-01 08:53
再试一下 8）

作者: zmy235 时间: 2014-08-01 08:54
回复 12# littledick

做出来了？送你大牛称号！

作者: littledick 时间: 2014-08-01 11:39

zmy235 发表于 2014-08-01 08:54
回复 12# littledick

不用保证执行时间效率的话又不难。

作者: littledick 时间: 2014-08-01 12:14
本帖最后由 littledick 于 2014-08-01 12:36 编辑

复制代码

作者: tklist 时间: 2014-08-01 12:52
你这肯定是不行，太暴力了，会超时的。回复 18# littledick

作者: littledick 时间: 2014-08-01 13:44

tklist 发表于 2014-08-01 12:52
你这肯定是不行，太暴力了，会超时的。回复 18# littledick

毕业后高等数学几乎都还给老师了。

作者: littledick 时间: 2014-08-01 13:50

tklist 发表于 2014-08-01 12:52
你这肯定是不行，太暴力了，会超时的。回复 18# littledick

先用暴力的方法找下规律。暴力的代码写起来快。

作者: jonas_mao 时间: 2014-08-01 16:53
用 hash list应该可以，先hash出一样和的数，然后用链表组装这些碰撞的。

作者: tklist 时间: 2014-08-01 16:56
这个不是用高等数学。
这应该是一个动态规划+构造的题目
回复 20# littledick

作者: tklist 时间: 2014-08-01 16:57
应该是没有什么规律的。答案是构造出来的。
回复 21# littledick

作者: zmy235 时间: 2014-08-01 17:25
本帖最后由 zmy235 于 2014-08-01 17:26 编辑

#include <iostream>
using namespace std;
int w(long long x)
{
int value=0;
for(int i=x; i>=1; i/=10)
value = value+x%10;
return value;
}
int main ()
{
long long n,k;
cin>>n>>k;
int p_of_k=0;
for(long long i=1; i<n; i++)
{
if(w(i)<=w(k))
p_of_k++;
}
cout<<p_of_k;
return 0;
}

复制代码

做了前半，效率太低了

作者: zmy235 时间: 2014-08-01 17:31
回复 22# jonas_mao

不明觉厉

作者: zmy235 时间: 2014-08-01 17:33
回复 24# tklist

赞同，求具体方法

作者: starwing83 时间: 2014-08-02 03:41
回复 27# zmy235

这道题没办法用模拟的方法的。必须要动态规划加构造。

首先问自己这样的一个问题：假设我们不考虑n的大小，我们构建一个函数f(x, y)，设这个函数的值是：对于一个长度为x的数字，其weight为y的有多少个？

这样的一个函数如何求解呢？

从题设我们知道，x取值在(0~19)（n和k最大1后面18个0，即19位），而y取值在9×18+1（即18位都是9，最高位是1），因此，本质上来说，求解这个函数，就是在填充一个20×163的二维数组。

我们先看这个数组怎么填：
首先，很显然的，如果weight是0，那么无论长度是多少，都只会有一种情况，即：
f(x, 0) == 1
然后，如果长度是0，那么显然一种情况都不会有，即：
f(0, y) == 0
最后，如果长度是1，且y在1～9的范围内，则也最多就一种情况，即：
f(1, [1-9]) == 1

这是初始情况。
然后，如果我们要求f(x,y)，应该怎么办呢？我们注意到，对于x位长度的数字，我们要求其权重为y的数字的总数，只需要分别在最高位取1～9（不能是0，这相当于长度只有x-1位），然后我们可以通过f函数得到在这9种情况下的数字总数，将它们加起来就可以了，即：

f(x, y) = f(x-1, y-i) （其中1<=i<=9，且y-i>=0）

由上面的四个方程，我们很容易写出求f函数（或数组）的代码了。这个f是跟n无关的，因此可以复用。
为了方便计算f本身，也是为了方便我们后续的计算，我们还可以定义一个函数F(n,x,y)，这个函数的值为，对于一个x位的数字，如果第一位是n，那么权重为y的数组有多少个。这个函数可以直接定义成一个函数，方便f(x,y)数组本身的计算。

求得f函数，我们很容易通过f函数求得g(weight)函数，即权值为weight的所有数组的总和。注意在求总和的时候，应该考虑n，因此这时需要跟n有关系了。所以，每个不同的n，都需要求得一个不同的g函数（或数组）。具体求法很简单：首先我们遍历n的每一位，假设就从最高位开始吧，比如说n是1236，我们设n(i)是n的第i位数字，比如n(1) == 1，对于最高位取1~n(i)，通过函数F可以得到一系列值，然后对于接下来的每一位，都可以得到一系列值累加到g上，最后我们就可以求得g函数（数组）的值了。

上面有的说f是函数，有的说f是数组，那么f到底是什么呢？实现上，F应该是一个基于f的工具函数，而f和g应该是数组。我们应该按照递推的顺序，逐层地填充这个数组的值。这样的处理手法，就叫动态规划。

有了f，F和g这三个函数，我们可以做什么事情呢？我们就可以构造出题目所需要求的解了。比如“第k位的数字是什么？”，首先我们可以求得这个数组k的权值了。我们对g数组进行累加，直到累加的结果大于k，这时当前累加的是g数组的第几位，则k的weight就应该为多少。然后我们就可以逐步试出k的每一位数组是多少，比如最高位是0吗？如果是0，则加上F(0, x, weight)的数值。反复这样加上去，直到我们算的位数刚刚好就是k，这时我们选取的所有的位数组成的那个数字就是k了，这种一位一位求得答案的方法，就是构造法。

再比如，数字k是第几位？首先可以求得k的weight，那么k的排名肯定不会高于weight比k小的数字。根据g数组很容易得到k的基础排名。现在在相同的weight里面了。利用和上面相同的试验法，我们就可以推出这个排名的精确数字是多少。

另外要注意一些细节：
- 对于数组f，第一位是不能取0的，否则就是x-1位，这点要注意，因此，如果真需要取0（比如不是第一位），那么记得取到f(x,y)时，要加上f(x-1,y)再用。
- 在构造的时候，时刻要当心不要把大于n的数组给构造进去了。这点很容易，当前试验的数字不能超过n当前的位数即可。另外，在操作f(x,y)的时候，也要小心不要加过头了。如果不能保证x位数组都能在1.....0～9.....9取值，则应该用f(x-1, y)累加的方法得到值，避免多加。

这题目，构造出f来，剩下的就是大把的细节问题了，不注重细节很容易出错的。

可以看出这种解题目的方法和你以前了解的应该相差很远，这就是不同于模拟方法的算法方式求解，如果不习惯/适应这种方法，那还是不要看这种题目了。

选择这种方法的一个原因是题目的输入范围，1的18次方，这种数量级决定了几乎只有贪心、动规等少数几种方法有效。

最后就是，这种算法在工作中的应用不是特别广，不理解的话也无所谓。另外，代码就不贴了，细节太多不一定写的对囧

作者: zmy235 时间: 2014-08-02 09:09
回复 28# starwing83

有个细节，那个二维数组的y最大可取到的值是18*9，取不到18*9+1的。
写了这么多，基本上可以看得懂你的意思，谢谢你的解答！

作者: folklore 时间: 2014-08-02 09:22
回复 28# starwing83

在我看来，就是一个普通的排序题。
排完序后再Scan一遍，做个Index（map)。
好像没有必要用到什么特别处理。。。

难道我就是传说的是中文不好？

作者: starwing83 时间: 2014-08-02 09:24
回复 29# zmy235

恩，的确是9×18，因为是数组下标，所以声明的时候要加1，所以就直接写了囧……

你既然看懂了，可以尝试一下写一下代码，会对你理解复杂的算法很有帮助的，这道题同时考察了动规，搜索，应该算是学习算法很好的入门题。

注意一个细节上的难点：5和50哪个小？肯定是5，但是5肯定比41要大，这就意味着顺序就不能是05，14，23，32，41，50了，而必须是14，23，32，41，5，50，即f(x-1, y)需要根据开头选的值，分散插入到f(x-2, y)里面去，这个地方的顺序需要注意。

自己写写吧～

作者: starwing83 时间: 2014-08-02 09:26
回复 30# folklore

这么说是没错，但是亲，1e18啊……你有这么多内存sort？

作者: zmy235 时间: 2014-08-02 09:33
回复 30# folklore

如果是数量级在可以接受的范围内，那就没有什么意思了，连排序都不用自己写，自己直接#include<algorithm> 然后sort(XXX)就可以了。
但是现在题目给出的数量级是1000000000000000000，这样就根本不能考虑排序了。取最大的话一般的个人计算机要运行个数万年吧。

作者: folklore 时间: 2014-08-02 09:33
回复 32# starwing83

那也只能说要用到外部排序（？？外部归并排序比较好？？），
依然是排序，
这个只要抄教科书上老掉牙的算法就可以了，
除非已发展出新的排序理论。

作者: folklore 时间: 2014-08-02 09:35
回复 33# zmy235

数据结构和算法里面有教一种叫做外部归并排序的无上**～～～

作者: zmy235 时间: 2014-08-02 09:38
回复 34# folklore

要用排序的话，个人感觉可以用桶排

作者: starwing83 时间: 2014-08-02 09:55
本帖最后由 starwing83 于 2014-08-02 09:56 编辑

回复 35# folklore

可是效率上怎么办呢？就算是O(nlogn)的排序吧，n是1e18的话结果也是不能接受的。就算是快速选择（不排序），也是O(n)的复杂度，如果一次比较需要1ms（考虑到需要字符串操作，这个时间还是很正常的），那么1e18就需要31688764年，就算只需要1纳秒就可以比较完（不太可能吧？）那也需要三万多年，这怎么搞？

作者: cjaizss 时间: 2014-08-02 09:59
本帖最后由 cjaizss 于 2014-08-02 10:01 编辑

folklore 发表于 2014-08-02 09:22
回复 28# starwing83

你想排到猴年马月去?
存储打算开多大?

作者: starwing83 时间: 2014-08-02 10:00
回复 35# folklore

我们就算不考虑时间（三万多年），就假设这忍得，那1e18至少也需要占用1e18的内存，一个数字至少需要8个字节（long long），那么这就是8e18个字节，折合7275957TB，这个没法搞吧？

作者: starwing83 时间: 2014-08-02 10:04
回复 36# zmy235

我提的这个动规算法其实本质上就是压缩式桶排——因为只需要一个数字，因此就直接压缩到只存储数量了，但是又需要构造，所以需要存储各个级数的数量，这就是二维数组的来历。

本质上来说，动态规划的另一个名字就是记忆化搜索，本质上也跟排序占了那么点儿关系= =

作者: folklore 时间: 2014-08-02 10:07
回复 37# starwing83

理解题义错了，果然中文不好～～

作者: folklore 时间: 2014-08-02 10:09
回复 38# cjaizss

好像只能用数学方法做了，看起来应该可以搞出一个公式来

作者: cjaizss 时间: 2014-08-02 10:13

folklore 发表于 2014-08-02 10:09
回复 38# cjaizss

题目考的就是你如何构造递归啊

作者: cjaizss 时间: 2014-08-02 10:44
本帖最后由 cjaizss 于 2014-08-02 11:24 编辑

一个递归关系:
sum是所有位数的和,cap是最大多少位
返回这样的数有多少个
uint64_t func(uint16_t sum,uint16_t cap)
{
      uint16_t i,j;
      uint64_t ret;
      assert(sum>0 && cap>0);

      if(sum == 1)
            return (uint64_t)cap;
      if(cap==1)
            return (uint64_t)1;
      ret = 0;
      for(i=1;i<sum;i++)
            ret += func(sum-i,cap-1);
      return ret;
}

作者: cjaizss 时间: 2014-08-02 11:21

cjaizss 发表于 2014-08-02 10:44
一个递归关系:
sum是所有位数的和,cap是最大多少位
返回这样的数有多少个

由以上,我的想法是第一步先做张表格,所有的递归关系全部修改为表格之间的依赖.
第二步,遇到具体的值,查找,缩减范围.查找中应该也存在递归缩减范围.

作者: tklist 时间: 2014-08-03 18:02
这个是典型的acm题目。工作了，好几不写题了，要实现出来有点难度，只能看出题目解法。
回复 27# zmy235

作者: tklist 时间: 2014-08-03 18:06
牛逼。搞acm的？
回复 28# starwing83

作者: littledick 时间: 2014-08-04 09:01
ND10 - (1+M) 的结果正太分布公式

作者: bskay 时间: 2014-08-06 15:57
显然要用动态规划, starwing83 想到构造的阶段很巧妙

作者: bskay 时间: 2014-08-07 09:19
本帖最后由 bskay 于 2014-08-07 09:26 编辑

回复 28# starwing83

用(C++)++  == python 代码试图实现这个算法,觉得你对 f的规划好像有点问题
  觉得除了
   f(l-1, w-j) j=1...9
  应该还有这种情况吧(第一个数字后是i个0的情况):

   f(l-i, w-j) j=1...9, i=1,l

      #
@staticmethod
def count_lw(nlen, nweight):
      '''长度位数为nlen的，权重为nweight的数字有多少个？'''
      # len(str(10 ** 18 ))=19 w(int('1'+'9' * 18 ))= 163
      if num_weight.res_f is None:
         #最长支持19位,权重最大163的数组
         num_weight.res_f = [[0]*163 for i in range(19)]
         res = num_weight.res_f
         #
         # f(l, 0) = 0 权重为0的没有
         # f(0, w) = 0
         # 下面动态规划
         # 对于长度l,权重w的数字，为f(l,w), 应该求和:
         #  f(l-i, w-j) j=1...9, i=1,l
         #  i       f(l-1,w-i)
         #  i 0       f(l-2,w-i)
         #  i 0 0    f(l-3,w-i)
         #  i 0 0 0 f(l-4,w-i)
         #  i 0 0 ...0 f(  1,w-i)  l-(l-1)
         #  i 0 0 ...0 0          l-(l)

作者: starwing83 时间: 2014-08-07 17:58
回复 50# bskay

我也考虑过这个问题，但是不能用你这样的方法。首先看f的定义，f(x,y)是长度为x的时候，权重为y的时候的数字的数目。既然长度为x，那么后面接0的可能性也就只有一种，比如第一位是5，长度是3，那么唯一一种可能是500，而5,50,5000这种都是属于f(1,5), f(2,5), f(4,5)的，不属于f(3,5)的情况，从这点来说，f的定义是清楚正确的。

现在的问题有两个：
1. 在统计的时候，需要考虑n，但是f不考虑n
2. 在统计的时候，需要考虑数位，但是f不考虑数位（即，f是把数位给定死了的）

对于第一点，处理起来很容易，我们在构造k的时候，保证k的每一位数字都不大于n即可，比如n是513，则k的第一位取0,1,2,3,4,5，第二位在5之前都可以取0-9，但是当第一位是5的时候就最多只能取到1，而在十位是0的时候能取0-9，但是当十位是1并且百位是5的时候只能取到3，在这种情况下构造，就能保证所有取到的f中的计数是不超过n的（因为f限定死了位数）。注意的是，这种构造在程序处理起来很麻烦，这需要很巧妙的代码书写技巧。我的建议是采用mask，即如果当前位达到了n的位数，且前一位的mask被置位，则该位mask被置位，并退出尝试（如果是统计，则直接返回1，因为毕竟这也是一种情况）。

在第二点的时候，我们首先要注意这样的一些事实，在不限定位数的情况下，实际上weight为一个定数的数字的数量是无限的。然而，即使限定了位数，weight中数字的排序也是不定的，为什么这么说呢？我们考虑一下weight为5，但是不超过500的数字是什么结构，首先我们把所有的可能性从小到大列出来：
104,113,122,131,14,140,203,212,221,23,230,302,311,32,320,401,41,410,5,50,500

如果我们计算总数，应该是分一位，两位，三位，计算，即f(1,5), f(2,5), ((f(2,4)+f(1,4))+(f(2,3)+f(1,3))+(f(2,2)+f(1,2))+(f(2,1)+f(1,1))+1)（根据上面的算法算得），
结果是1+5+((4+1)+(3+1)+(2+1)+(1+1)+1) = 21, 数量是对的（虽然顺序不对，但是这里既然只计算数量，自然不考虑顺序）。

可以看到，直接这么计算是很繁琐的，因此我们引入了F，之前我的定义F是F是等于x长度的，但是这样就不方便，之前定义F等于x长度是为了防止取F时误取到大于n的数字，但是显然这不可能，因此这里我们修改F的定义，让F(n,x,y)取得：第一位是n，小于等于x长度，权值为y的数字。

F的定义是这样的：F(n,x,y) = f(x-1,y-n)+f(x-2,y-n)*2+..+f(1,y-n)*(x-1)，注意乘法是为了取到小于x的数字。

根据这个定义，计算weight为5切不超过500的数字的方法就是F(1,3,5)+F(2,3,5)+F(3,3,5)+F(4,3,5)+【F(5,3,5)】=6+5+4+3+3=21，结果是对的。

但是，这里我还是打了方括号，为什么呢？计算从500-500范围内的数量是困难的，根据我们的观察，这里应该是F(5,3,5)，问题是，一般的情况怎么办呢？

这里要么就写一个函数，用于计算从（举例，n是513，weight这里是7）500~513范围的函数（需要仔细分析情况和递归，算法按最上面的mask算法），或者是简单粗暴一点，先直接就计算F(5,3,7)，这实际上计算了从500~599所有的可能性，然后再减去514~519、520~599，这些应该也能通过F得到，只是需要很小心不能减重了。

总而言之，这里分析了weight数组即数组g的计算方法，从而看到了构造过程中可能遇到的困难，这里还是让f还是纯粹的只算长度精确为x，让F去计算1到x-1好了，我觉得这样比较安全。而且可能除了F，还需要一个F'(n,x,y)，其中n是x位的数字，计算x位数字中最高位和n的最高位相同，且小于等于n，且权值是y的数字的数量。具体的解法上面也提到了（不过要提取出一个通项公式有点麻烦），那么，下面还留了几个问题：

1. 如果f(x,y)真的考虑第一位是0的情况（即加上f(x-1,y)），会不会让整个计算简单一点儿，并且不会导致重复计算的情况？
2. 在这种情况下，F函数应该会比较简单，那么F'函数如何计算？
3. F'有没有公式？怎么组织数据能让F'的计算最简单？

作者: starwing83 时间: 2014-08-07 18:02
上面回的就是一堆的细节问题了，真写代码了这些你都得考虑，核心的算法肯定是没错的，但是某些变换也是要的，我觉得原则是这样的：

只要计算最终结果会变得简单，那么就加上这样的情况。

我很担心f的计算如果加上了f(x-1,y)，会不会导致最后去重的时候出现麻烦（即上面说的F’函数的求值），这事儿得干过以后才知道，所以你可以考虑一下，如果能得到简单的计算F'函数的方法，那即使修改f的定义也是可以的。

不过你要注意的是，f在【我的定义之下】的计算方法是没有问题的。

作者: bskay 时间: 2014-08-09 08:50
本帖最后由 bskay 于 2014-08-09 09:02 编辑

回复 51# starwing83

我的意思是说，你可能漏了 503这样的情况

按你的定义
我们先看这个数组怎么填：
首先，很显然的，如果weight是0，那么无论长度是多少，都只会有一种情况，即：
f(x, 0) == 1 // 这里好像只能x=1时才为1，其他情况为0 （取0的话）
然后，如果长度是0，那么显然一种情况都不会有，即：
f(0, y) == 0
最后，如果长度是1，且y在1～9的范围内，则也最多就一种情况，即：
f(1, [1-9]) == 1

这是初始情况。
然后，如果我们要求f(x,y)，应该怎么办呢？我们注意到，对于x位长度的数字，我们要求其权重为y的数字的总数，只需要分别在最高位取1～9（不能是0，这相当于长度只有x-1位），然后我们可以通过f函数得到在这9种情况下的数字总数，将它们加起来就可以了，即：

f(x, y) = f(x-1, y-i) （其中1<=i<=9，且y-i>=0） // 这里会漏了 503 这样的只考虑了512， 521

作者: starwing83 时间: 2014-08-09 16:08
问题是503是需要前提的，前提是第一个得是5而不是0，不然就是重复，所以后面的一堆处理都是为了把503加回去，而这里不加就是怕加重了，因为这里是不知道第一位到底是5还是0的，所以最好还是等到知道的时候再加

作者: starwing83 时间: 2014-08-09 16:08
问题是503是需要前提的，前提是第一个得是5而不是0，不然就是重复，所以后面的一堆处理都是为了把503加回去，而这里不加就是怕加重了，因为这里是不知道第一位到底是5还是0的，所以最好还是等到知道的时候再加

作者: bskay 时间: 2014-08-10 05:22
本帖最后由 bskay 于 2014-08-10 05:32 编辑

不理解你后面的思路了，开始理解的是觉得需要这样累加（没用到F(i,l,w)）
         #  f(l-i, w-j) j=1...9, i=1,l
         #  i             f(l-1,w-j)  1    i=1时,由1到9为第一位加上长度为l-1位序列的所有元素拼起来
         #  i 0          f(l-2,w-j)  2    i=2时,中间空一格0,    加上长度为l-2位序列的所有元素拼起来
         #  i 0 0       f(l-3,w-j)  3
         #  i 0 0 0    f(l-4,w-j)  4
         #  i 0 0 ...0 f(  1,w-j)  l-(l-1)
         #  i 0 0 ...0 0 f(  0,w-j)  l-(l)
这个是有点繁？

F(n,x,y) 其实就是 f(x-1,y-n) 吧，相当于递归，本质和上面0到x的累加应该是一样的

欢迎光临 Chinaunix (http://bbs.chinaunix.net/)

Powered by Discuz! X3.2