BYR Achieve · 镜像论坛

☆─────────────────────────────────────☆ dby (Soso) 于 (Wed Oct 18 19:10:09 2006) 提到: 有几个有意思的~ 1，T[0]=1,T[1]=1,T[2]=2;T[N]=T[N-1]+T[N-2]+T[N-3];求T[N]； 2，给出一个所有边长都为1的无向图，判断任意2个点之间是否存在长度为K的路径，路经上的点可以重复。 ☆─────────────────────────────────────☆ ilovekitchen (荔水之浦|又上征程) 于 (Wed Oct 18 19:44:41 2006) 提到: 【在 dby 的大作中提到: 】 : 有几个有意思的~ : 1，T[0]=1,T[1]=1,T[2]=2;T[N]=T[N-1]+T[N-2]+T[N-3];求T[N]； : 2，给出一个所有边长都为1的无向图，判断任意2个点之间是否存在长度为K的路径，路经上的点可以重复。写程序? ... ☆─────────────────────────────────────☆ linandmin (八闽玲珑||北邮的浣熊喜欢北师的乌鸦) 于 (Wed Oct 18 22:46:35 2006) 提到: 1.解差分方程? 2.搜？ ☆─────────────────────────────────────☆ sunmoonstar (秀) 于 (Wed Oct 18 23:21:15 2006) 提到: 根据不同的数据,设计不同地算法 ☆─────────────────────────────────────☆ earl (天籁之星) 于 (Thu Oct 19 13:47:46 2006) 提到: 2 可以用0 1 矩阵表示的图相乘k次吧, a[i,j]!=0就是有路径了 ☆─────────────────────────────────────☆ humanjustic (SぜG) 于 (Thu Oct 19 23:01:41 2006) 提到: 楼上莫非在说传递闭包,O(n^3)吧. 应该可以优化的,分支界定(剪枝)+深搜(如果当前路径大于K就不用往下搜了) ☆─────────────────────────────────────☆ ai (≮雪域≯之風箏與風) 于 (Fri Oct 20 08:48:07 2006) 提到: 两题都可以用矩阵乘优化吧~ 1, O(logN) 2, O(n^3logK) ? ☆─────────────────────────────────────☆ dby (Soso) 于 (Fri Oct 20 09:19:11 2006) 提到: re~ 【在 ai 的大作中提到: 】 : 两题都可以用矩阵乘优化吧~ : 1, O(logN) : 2, O(n^3logK) : ................... ☆─────────────────────────────────────☆ sansi (三思) 于 (Sat Oct 21 16:20:50 2006) 提到: 第一题像是费比数列吧，那个程序用递归比较容易实现， PS：第一次来这个版，挺好， ☆─────────────────────────────────────☆ StarFallLuna (Fall in your Shadow) 于 (Sat Oct 21 17:23:55 2006) 提到: 恩，我就是那么写得1分呵呵【在 sansi (三思) 的大作中提到: 】 : 第一题像是费比数列吧，那个程序用递归比较容易实现， : PS：第一次来这个版，挺好， ☆─────────────────────────────────────☆ sunmoonstar (秀) 于 (Sun Oct 22 12:43:31 2006) 提到: 递推好吧表示成 (0 1) 的矩阵 (1 0) 【在 sansi 的大作中提到: 】 : 第一题像是费比数列吧，那个程序用递归比较容易实现， : PS：第一次来这个版，挺好， ☆─────────────────────────────────────☆ sunmoonstar (秀) 于 (Sun Oct 22 12:47:44 2006) 提到: 动态规划, opt[i][j][k], 点i, j 之间有长为k的路径, 如果是多次判断可行么, 如果点数比较大的话就不行了【在 dby 的大作中提到: 】 : 有几个有意思的~ : 1，T[0]=1,T[1]=1,T[2]=2;T[N]=T[N-1]+T[N-2]+T[N-3];求T[N]； : 2，给出一个所有边长都为1的无向图，判断任意2个点之间是否存在长度为K的路径，路经上的点可以重复。 ☆─────────────────────────────────────☆ sunmoonstar (秀) 于 (Sun Oct 22 13:13:14 2006) 提到: 这样, 只要先预处理出任意两点之间是否存在长度为奇数和偶数的路径就行了估计n^3就够了这样可以么? 【在 dby 的大作中提到: 】 : 有几个有意思的~ : 1，T[0]=1,T[1]=1,T[2]=2;T[N]=T[N-1]+T[N-2]+T[N-3];求T[N]； : 2，给出一个所有边长都为1的无向图，判断任意2个点之间是否存在长度为K的路径，路经上的点可以重复。 ☆─────────────────────────────────────☆ Mariah (北邮人) 于 (Sat Dec 9 14:45:01 2006) 提到: 不懂,可以解释一下么?..... 动态规划明白: for(int i=0; i<n; i++) for(int j=0; j<n; j++) for(int k=2; k<=K; k++) for(int step = 1; step<=k-1; step++) for(int mid = 1;mid<n;mid++) { a[i][j][k] = a[i][mid][step] && a[mid][j][k-step]; if (a[i][j][k] )>0 break; } O( n^3 * k^2) ? 好像不是您想的那个方法.... 奇数和偶数的路径是什么意思呢? 【在 sunmoonstar 的大作中提到: 】 : 这样, 只要先预处理出任意两点之间是否存在长度为奇数和偶数的路径就行了 : 估计n^3就够了 : 这样可以么? ☆─────────────────────────────────────☆ jeeper (我的2006) 于 (Sat Dec 9 17:15:26 2006) 提到: 奇数偶数是因为某个考场加了个边权为1的条件【在 Mariah (北邮人) 的大作中提到: 】 : 标题: Re: 昨天google的笔试题 : 发信站: 北邮人论坛 (Sat Dec 9 14:45:01 2006), 站内 : : 不懂,可以解释一下么?..... : 动态规划明白: : for(int i=0; i<n; i++) : for(int j=0; j<n; j++) : for(int k=2; k<=K; k++) : for(int step = 1; step<=k-1; step++) : for(int mid = 1;mid<n;mid++) : { : a[i][j][k] = a[i][mid][step] && a[mid][j][k-step]; : if (a[i][j][k] )>0 break; : } : O( n^3 * k^2) ? 好像不是您想的那个方法.... : 奇数和偶数的路径是什么意思呢? : : : : 【在 sunmoonstar 的大作中提到: 】 : : 这样, 只要先预处理出任意两点之间是否存在长度为奇数和偶数的路径就行了 : : 估计n^3就够了 : : 这样可以么? : : -- : : ※ 来源:·北邮人论坛 http://forum.byr.edu.cn·[FROM: 59.64.221.*] ☆─────────────────────────────────────☆ sunmoonstar (秀) 于 (Mon Dec 11 18:59:02 2006) 提到: jeeper好牛啊【在 jeeper 的大作中提到: 】 : 奇数偶数是因为某个考场加了个边权为1的条件

[合集] 昨天google的笔试题