一亩三分地论坛

 找回密码
 获取更多干货,去instant注册!

扫码关注一亩三分地公众号
查看: 1906|回复: 15
收起左侧

Twitter OA 经

[复制链接] |试试Instant~ |关注本帖
anitamengzhuolu 发表于 2016-3-21 08:44:30 | 显示全部楼层 |阅读模式

注册一亩三分地论坛,查看更多干货!

您需要 登录 才可以下载或查看,没有帐号?获取更多干货,去instant注册!

x
下午昨晚的Twitter OA,感觉题不是很简单,发上来攒攒人品~
60min两道题,第一道是给两个数M和N,求从1到M和1到N之间的数有哪些组合满足两个数立方根的和的三次方是整数。
第二道感觉大家遇到的比较多一些,cutting stick,就是一堆stick,每次可以都切特定的长度直到切完,问每一次切完后还剩几根。
供大家参考~

评分

2

查看全部评分

本帖被以下淘专辑推荐:

sniffsky 发表于 2016-3-24 06:42:35 | 显示全部楼层
hison7463 发表于 2016-3-24 05:20
第一题先把式子展开,发现只要找到a^(1/3), b^(1/3), a^(2/3), b^(2/3)(其实也就是a^(1/3), b^(1/3))同时 ...
-google 1point3acres
感觉这是充分条件。比如3和24,立方根和的立方也是整数

评分

1

查看全部评分

回复 支持 1 反对 0

使用道具 举报

xiaojunji 发表于 2016-3-21 10:14:43 | 显示全部楼层
第一道怎么做?跪求代码和思路!谢谢好人
回复 支持 反对

使用道具 举报

lzb940214 发表于 2016-3-21 12:20:33 | 显示全部楼层
感觉第一题要用到一个数的质数分解吧,但具体还不知道怎么做。第二题排序用nlogn, 每次询问用logn,还有更好的方法吗?
回复 支持 反对

使用道具 举报

lzb940214 发表于 2016-3-21 12:21:31 | 显示全部楼层
对了,请教楼主,OA上用什么语言都可以吗?都有什么可用的语言?
回复 支持 反对

使用道具 举报

tldxk 发表于 2016-3-24 00:01:19 | 显示全部楼层
第一题暴力可以通过吗?O(MN)。。。
回复 支持 反对

使用道具 举报

hison7463 发表于 2016-3-24 05:20:06 | 显示全部楼层
第一题先把式子展开,发现只要找到a^(1/3), b^(1/3), a^(2/3), b^(2/3)(其实也就是a^(1/3), b^(1/3))同时为整数的情况就行了。
我的方法就是:
对于1 - n的情况O(n^(1/3))
int cur = 1;
List list1;
while(cur <= n) {
      if(cur * cur * cur < n) {
             list.add(cur * cur * cur);
      }
      else {
            break;
      }.1point3acres缃
      cur++;
}
对于1 - m的情况O(m^(1/3))
int cur = 1;
List list2;
.1point3acres缃while(cur <= m) {
      if(cur * cur * cur < m) {
             list.add(cur * cur * cur);
      }
-google 1point3acres      else {
            break;. from: 1point3acres.com/bbs
      }
      cur++;.1point3acres缃
}
再把list1和list2组合一下就行了
回复 支持 反对

使用道具 举报

kiss 发表于 2016-3-24 06:23:10 | 显示全部楼层
请问楼主自己投的还是内推的?
回复 支持 反对

使用道具 举报

tldxk 发表于 2016-3-24 06:36:02 | 显示全部楼层
hison7463 发表于 2016-3-24 05:20-google 1point3acres
第一题先把式子展开,发现只要找到a^(1/3), b^(1/3), a^(2/3), b^(2/3)(其实也就是a^(1/3), b^(1/3))同时 ...

(x+y)^3=x^3+y^3+3xy(x+y). visit 1point3acres.com for more.
这个3xy(x+y)不一定要求x, y都要是整数吧?比如x=1/3, y=3.
当然,当x,y都分别为某整数的1/3次幂时,是否还有这种特例,还需要求证。。。
回复 支持 反对

使用道具 举报

海盗包子 发表于 2016-3-24 09:52:11 | 显示全部楼层
lzb940214 发表于 2016-3-21 12:20
感觉第一题要用到一个数的质数分解吧,但具体还不知道怎么做。第二题排序用nlogn, 每次询问用logn,还有更 ...
. from: 1point3acres.com/bbs
第二题只用排序就好了吧,排序nlogn,肯定是先砍短的过一遍时间O(n), 每次输出 length-index
回复 支持 反对

使用道具 举报

hison7463 发表于 2016-3-25 02:03:45 | 显示全部楼层
tldxk 发表于 2016-3-24 06:36
(x+y)^3=x^3+y^3+3xy(x+y)
这个3xy(x+y)不一定要求x, y都要是整数吧?比如x=1/3, y=3.
当然,当x,y都分 ...

对诶,那就再加上一个限定条件,a^(1/3) = b^(1/3) * x (x为整数),满足这个式子,即a = b * x ^ 3的所有a,b组合
回复 支持 反对

使用道具 举报

hison7463 发表于 2016-3-25 04:42:37 | 显示全部楼层
我把我写的第一题的代码贴上来,大家看看有没有需要改的
大概的思路就是把式子展开发现只要a^(1 / 3) * b^(2 / 3)和a^(2 / 3) * b^(1 / 3)为整数就能保证结果为整数,如果a^(1 / 3) = b^(1 / 3) * X (X为整数)和b(1 / 3) = a ^ (1 / 3) * X (X为整数),那么a^(1 / 3) * b^(2 / 3) = b * X和a^(2 / 3) * b^(1 / 3) = a * X就肯定是整数,即找到满足a = b * X ^ 3和b = a * X ^ 3的所有a,b组合
  1. public List<int[]> cubeRoot(int m, int n) {
  2.                 List<int[]> res = new ArrayList<int[]>();
  3.                 List<Integer> listM = new ArrayList<Integer>();
  4.                 List<Integer> listN = new ArrayList<Integer>();
  5.                 int cur = 1;. From 1point 3acres bbs
  6.                 while(cur <= m / cur / cur) {
  7.                         listM.add(cur * cur * cur);
  8.                         cur++;
  9.                 }
  10.                 cur = 1;
  11.                 while(cur <= n / cur / cur) {
  12.                         listN.add(cur * cur * cur);
  13.                         cur++;
  14.                 }
  15.                 int a = 1;
  16.                 int b = 1;
  17.                 HashMap<Integer, HashSet<Integer>> map = new HashMap<Integer, HashSet<Integer>>();
  18.                 while(b <= n) {
  19.                         for(int numA : listM) {. from: 1point3acres.com/bbs
  20.                                 a = b * numA;
  21.                                 if(a <= m) {
  22.                                         if(!map.containsKey(a)) {
  23.                                                 map.put(a, new HashSet<Integer>());. from: 1point3acres.com/bbs
  24.                                         }
  25.                                         map.get(a).add(b);
  26.                                         res.add(new int[]{a, b});
  27.                                 }
  28.                                 else {
  29.                                         break;
  30.                                 }
  31.                         }
  32.                         b++;. more info on 1point3acres.com
  33.                 }
  34.                 a = 1;
  35.                 b = 1;.鏈枃鍘熷垱鑷1point3acres璁哄潧
  36.                 while(a <= m) {.1point3acres缃
  37.                         for(int numB : listN) {
  38.                                 b = a * numB;
  39.                                 if(b <= n) {
  40.                                         if(!map.containsKey(a)) {
  41.                                                 map.put(a, new HashSet<Integer>());. 鍥磋鎴戜滑@1point 3 acres
  42.                                         }
  43.                                         else {
  44.                                                 if(map.get(a).contains(b)) {.1point3acres缃
  45.                                                         continue;. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
  46.                                                 }. 1point3acres.com/bbs
  47.                                         }
  48.                                         map.get(a).add(b);
  49.                                         res.add(new int[]{a, b});
  50.                                 }
  51.                                 else {
  52.                                         break;
  53.                                 }
  54.                         }
  55.                         a++;.1point3acres缃
  56.                 }
  57.                 return res;. 1point3acres.com/bbs
  58.         }
复制代码
回复 支持 反对

使用道具 举报

zoufengboy 发表于 2016-3-29 09:06:50 | 显示全部楼层
hison7463 发表于 2016-3-25 04:42
我把我写的第一题的代码贴上来,大家看看有没有需要改的
大概的思路就是把式子展开发现只要a^(1 / 3) * b^ ...

这个最后的pair有重复的吧
回复 支持 反对

使用道具 举报

hison7463 发表于 2016-3-31 03:07:15 | 显示全部楼层
zoufengboy 发表于 2016-3-29 09:06
这个最后的pair有重复的吧

没有吧,我已经用map把遇见的pair存起来了,下次遇到的话会跳过
回复 支持 反对

使用道具 举报

jefferyy 发表于 2016-4-8 13:11:34 | 显示全部楼层
hison7463 发表于 2016-3-25 04:42
我把我写的第一题的代码贴上来,大家看看有没有需要改的
大概的思路就是把式子展开发现只要a^(1 / 3) * b^ ...

这个的时间复杂度是什么?
回复 支持 反对

使用道具 举报

UFO 发表于 2016-4-10 10:47:16 | 显示全部楼层
hison7463 发表于 2016-3-25 04:42
我把我写的第一题的代码贴上来,大家看看有没有需要改的
大概的思路就是把式子展开发现只要a^(1 / 3) * b^ ...

先求平方数的思路很好,不过a,b立方根并不一定要是整数,比如a=40=5*8, b=135=5*27,结果也是整数。
发一个代码吧
  1. int cubeNumbers(int M, int N) {. from: 1point3acres.com/bbs
  2.         List<Integer> lm = new ArrayList<Integer>();
  3.         List<Integer> ln = new ArrayList<Integer>();
  4.         int count = 0, i, a, b;
  5.         for (i = 1; i <= M / i/i; i ++) {
  6.             lm.add(i * i * i);
  7.         }
  8.         for (i = 1; i <= N / i/i; i ++) {. 1point3acres.com/bbs
  9.             ln.add(i * i * i);
  10.         }. from: 1point3acres.com/bbs
  11.         HashMap<Integer, HashSet<Integer>> map = new HashMap<Integer, HashSet<Integer>>();
  12.         for (int cubeA : lm) {
  13.             for (int cubeB : ln) {
  14.                 for (i = 1; i <= M; ++i) {
  15.                     if ((a = i * cubeA) > M || (b = i * cubeB) > N) break;. Waral 鍗氬鏈夋洿澶氭枃绔,
  16.                     if (!map.containsKey(a)) map.put(a, new HashSet<Integer>());. more info on 1point3acres.com
  17.                     if (!map.get(a).contains(b)) {-google 1point3acres
  18.                         map.get(a).add(b);
  19.                         count ++;
  20.                     }
  21.                 }
  22.             }
  23.         }
  24.         return count;
  25.     }
复制代码
回复 支持 反对

使用道具 举报

本版积分规则

请点这里访问我们的新网站:一亩三分地Instant.

Instant搜索更强大,不扣积分,内容组织的更好更整洁!目前仍在beta版本,努力完善中!反馈请点这里

关闭

一亩三分地推荐上一条 /5 下一条

手机版|小黑屋|一亩三分地论坛声明 ( 沪ICP备11015994号 )

custom counter

GMT+8, 2016-12-3 19:53

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

快速回复 返回顶部 返回列表