m***k
发帖数: 946 | 1 这两道题感觉很难啊，有没有人能给出些思路？
1.对于一个整数矩阵，存在一种运算，对矩阵中任意元素加一时，需要其相邻（上下左
右）
某一个元素也加一，现给出一正数矩阵，判断其是否能够由一个全零矩阵经过上述运算
得到。
2.一个整数数组，长度为n，将其分为m份，使各份的和相等，求m的最大值
比如{3，2，4，3，6} 可以分成{3，2，4，3，6} m=1;
{3,6}{2,4,3} m=2
{3,3}{2,4}{6} m=3 所以m的最大值为3
请不要给brutal search的方法或code，希望能给出比较优化的时间、空间复杂度。 |
C***U
发帖数: 2406 | 2 第二题是NP hard的吧。。。。
【在 m***k 的大作中提到】
: 这两道题感觉很难啊，有没有人能给出些思路？
: 1.对于一个整数矩阵，存在一种运算，对矩阵中任意元素加一时，需要其相邻（上下左
: 右）
: 某一个元素也加一，现给出一正数矩阵，判断其是否能够由一个全零矩阵经过上述运算
: 得到。
: 2.一个整数数组，长度为n，将其分为m份，使各份的和相等，求m的最大值
: 比如{3，2，4，3，6} 可以分成{3，2，4，3，6} m=1;
: {3,6}{2,4,3} m=2
: {3,3}{2,4}{6} m=3 所以m的最大值为3
: 请不要给brutal search的方法或code，希望能给出比较优化的时间、空间复杂度。
|
m***k
发帖数: 946 | 3 背包问题也是NP hard的，但在合理使用内存的情况下，仍然有高效的解法。。。
【在 C***U 的大作中提到】
: 第二题是NP hard的吧。。。。
|
f*****e
发帖数: 2992 | 4 第一题可以解线性方程，无解，唯一解，多解，无穷解（impossible），
【在 m***k 的大作中提到】
: 这两道题感觉很难啊，有没有人能给出些思路？
: 1.对于一个整数矩阵，存在一种运算，对矩阵中任意元素加一时，需要其相邻（上下左
: 右）
: 某一个元素也加一，现给出一正数矩阵，判断其是否能够由一个全零矩阵经过上述运算
: 得到。
: 2.一个整数数组，长度为n，将其分为m份，使各份的和相等，求m的最大值
: 比如{3，2，4，3，6} 可以分成{3，2，4，3，6} m=1;
: {3,6}{2,4,3} m=2
: {3,3}{2,4}{6} m=3 所以m的最大值为3
: 请不要给brutal search的方法或code，希望能给出比较优化的时间、空间复杂度。
|
a******a
发帖数: 2646 | |
s****i
发帖数: 65 | 6
先算这些数的和Sum (sum能被m整除)，元素的个数n，排序
最大的份数<=n, 如果排序后1st= last element, 份数是m = n,都是相同的数
否则，从n开始递减算能被Sum整除的数m，有了Sum, m，就能算出如果份数是m，那每份
的和就是Sum/m，看看能不能凑成m份，每份Sum/m
我说的有没有问题？
【在 m***k 的大作中提到】
: 这两道题感觉很难啊，有没有人能给出些思路？
: 1.对于一个整数矩阵，存在一种运算，对矩阵中任意元素加一时，需要其相邻（上下左
: 右）
: 某一个元素也加一，现给出一正数矩阵，判断其是否能够由一个全零矩阵经过上述运算
: 得到。
: 2.一个整数数组，长度为n，将其分为m份，使各份的和相等，求m的最大值
: 比如{3，2，4，3，6} 可以分成{3，2，4，3，6} m=1;
: {3,6}{2,4,3} m=2
: {3,3}{2,4}{6} m=3 所以m的最大值为3
: 请不要给brutal search的方法或code，希望能给出比较优化的时间、空间复杂度。
|
b***e
发帖数: 1419 | 7 It's really a integer programming problem. You need solution to contain all
positive integers.
【在 f*****e 的大作中提到】
: 第一题可以解线性方程，无解，唯一解，多解，无穷解（impossible），
|
z****o
发帖数: 78 | 8 第一题直觉上可以直接逐行构造。
我证明一下这个贪心的正确性再贴上来。
【在 m***k 的大作中提到】
: 这两道题感觉很难啊，有没有人能给出些思路？
: 1.对于一个整数矩阵，存在一种运算，对矩阵中任意元素加一时，需要其相邻（上下左
: 右）
: 某一个元素也加一，现给出一正数矩阵，判断其是否能够由一个全零矩阵经过上述运算
: 得到。
: 2.一个整数数组，长度为n，将其分为m份，使各份的和相等，求m的最大值
: 比如{3，2，4，3，6} 可以分成{3，2，4，3，6} m=1;
: {3,6}{2,4,3} m=2
: {3,3}{2,4}{6} m=3 所以m的最大值为3
: 请不要给brutal search的方法或code，希望能给出比较优化的时间、空间复杂度。
|
z****o
发帖数: 78 | 9 比如某两行的情况是这样的:
上行剩余： 0 0 1 0 3 0 0 0 0 0 0 0 0
本行原有： 0 0 1 0 3 4 0 2 1 0 0 1 0
我们总是先竖消上行，横消本行，把剩余留到下一行。
本行剩余： 0 0 0 0 0 4 0 1 0 0 0 1 0
如果某次无法把上行全消完，那就是无解。
这个构造法的基础是，从左上往右下消除的唯一歧义状态是：
1 1
1 1
这个状态横消竖消是等价的。 |
d*****y
发帖数: 1365 | 10 how about
1 1 0
0 1 1
0 0 0
?
【在 z****o 的大作中提到】
: 比如某两行的情况是这样的:
: 上行剩余： 0 0 1 0 3 0 0 0 0 0 0 0 0
: 本行原有： 0 0 1 0 3 4 0 2 1 0 0 1 0
: 我们总是先竖消上行，横消本行，把剩余留到下一行。
: 本行剩余： 0 0 0 0 0 4 0 1 0 0 0 1 0
: 如果某次无法把上行全消完，那就是无解。
: 这个构造法的基础是，从左上往右下消除的唯一歧义状态是：
: 1 1
: 1 1
: 这个状态横消竖消是等价的。
|
|
|
z****o
发帖数: 78 | 11
这是一个极容易的例子啊，第一行横消，第二行横消，没有歧义。
【在 d*****y 的大作中提到】
: how about
: 1 1 0
: 0 1 1
: 0 0 0
: ?
|
z****o
发帖数: 78 | 12
我可能是对＂上行剩余＂没说清楚。对第一行，就假设有一个没有剩余的第零行。
【在 d*****y 的大作中提到】
: how about
: 1 1 0
: 0 1 1
: 0 0 0
: ?
|
d*****y
发帖数: 1365 | 13 我理解错了,还以为你每次都是先竖消,再横削.
实际上你每次都考虑两个可能,1)先横消,再竖消, 2)先竖消再横削?
【在 z****o 的大作中提到】
:
: 我可能是对＂上行剩余＂没说清楚。对第一行，就假设有一个没有剩余的第零行。
|
z****o
发帖数: 78 | 14
正好反了，每次都是先横后竖。 考虑两种就brute force了。
【在 d*****y 的大作中提到】
: 我理解错了,还以为你每次都是先竖消,再横削.
: 实际上你每次都考虑两个可能,1)先横消,再竖消, 2)先竖消再横削?
|
d*****y
发帖数: 1365 | 15 1 1 1
1 0 0
你先横削:第一行是把第一个和第二个先消掉呢?还是把第二个第三个先消掉?
你要是先把第二第三消掉,对下面的就不work.
1 1 1
0 0 1
我感觉你的方法不能避免指数复杂...
【在 z****o 的大作中提到】
:
: 正好反了，每次都是先横后竖。 考虑两种就brute force了。
|
z****o
发帖数: 78 | 16
嗯，你是对的。有反例。
【在 d*****y 的大作中提到】
: 1 1 1
: 1 0 0
: 你先横削:第一行是把第一个和第二个先消掉呢?还是把第二个第三个先消掉?
: 你要是先把第二第三消掉,对下面的就不work.
: 1 1 1
: 0 0 1
: 我感觉你的方法不能避免指数复杂...
|
s*****n
发帖数: 134 | 17 第一题就是一个用十字Kernal卷积的逆过程，最终的结果是需要检测的矩阵（m x n)，
输出是 (m-1 x n-1) 的矩阵。
我的笨方法是先用两层循环把每行和每列都转化成一个十进制的数，比如[1 2 1 5 4 3
2 1] 转化为 12154321, 如果这个数不能被 111整除，return false， 如果能整除，
把 Xi/111的结果再转化成一个行矢量Wi. 同理把 Yi/111的结果转化成列矢量 Vj。 把
Wi 和Vj 按行和列Cat成矩阵W 和V
如果第2到m-1行和2到n-1列都可以整除，就比较一下W 和V， 如果相同就return true。
【在 m***k 的大作中提到】
: 这两道题感觉很难啊，有没有人能给出些思路？
: 1.对于一个整数矩阵，存在一种运算，对矩阵中任意元素加一时，需要其相邻（上下左
: 右）
: 某一个元素也加一，现给出一正数矩阵，判断其是否能够由一个全零矩阵经过上述运算
: 得到。
: 2.一个整数数组，长度为n，将其分为m份，使各份的和相等，求m的最大值
: 比如{3，2，4，3，6} 可以分成{3，2，4，3，6} m=1;
: {3,6}{2,4,3} m=2
: {3,3}{2,4}{6} m=3 所以m的最大值为3
: 请不要给brutal search的方法或code，希望能给出比较优化的时间、空间复杂度。
|
a********k
发帖数: 13 | 18 给个第一题的解答
思路：
先证明对于任意非零元素A[i,j] ,
if sum（neighbor（A[i,j]））＝＝A[i,j]
then 矩阵能通过逆运算消减为0矩阵，
由此可以推广到对于任意相连的元素集合，改定理都成立
------------
伪代码：
Input：矩阵 A ,
定义neighor（x，y，z。。。）为相连矩阵元素x，y，z。。。的上下左右相邻元素的
集合，不包括x，y，z。。。本身
i = 0;
j = 0;
S = neighbor(A[i,j])
delta = Sum(neighbor(S)) - A[i,j ]
while ( sum（neighbor（S）） > delta )
{
delta＝sum（neighbor（S）） －delta
S = neighbor(S)
}
if(delta ＝＝0)
return true;
else
return false;
-----------------------
比如说给出下面这个矩阵
12
34
step 1： 2＋3 －1 ＝ 4
step 2： 4－4 ＝ 0
通过这两步可以构造出如下逆运算步骤
12 11 01
34 00 34
01 01 00
34 01 33
00 00 00
33 11 22
00 00 00
22 11 11
00 00 00
11 11 00 |
d*****y
发帖数: 1365 | 19 Your idea is great
【在 a********k 的大作中提到】
: 给个第一题的解答
: 思路：
: 先证明对于任意非零元素A[i,j] ,
: if sum（neighbor（A[i,j]））＝＝A[i,j]
: then 矩阵能通过逆运算消减为0矩阵，
: 由此可以推广到对于任意相连的元素集合，改定理都成立
: ------------
: 伪代码：
: Input：矩阵 A ,
: 定义neighor（x，y，z。。。）为相连矩阵元素x，y，z。。。的上下左右相邻元素的
|
g****y
发帖数: 240 | 20 neighbor（S）是什么？在你的例子中。
第一步 S = 【（0，1） （1，0）】
第二步 S = neighbor(S) = [(1,1)]?
【在 a********k 的大作中提到】
: 给个第一题的解答
: 思路：
: 先证明对于任意非零元素A[i,j] ,
: if sum（neighbor（A[i,j]））＝＝A[i,j]
: then 矩阵能通过逆运算消减为0矩阵，
: 由此可以推广到对于任意相连的元素集合，改定理都成立
: ------------
: 伪代码：
: Input：矩阵 A ,
: 定义neighor（x，y，z。。。）为相连矩阵元素x，y，z。。。的上下左右相邻元素的
|
t****a
发帖数: 1212 | 21 好思路阿。不过有非负整数的系数约束条件。还是只能DP。
等牛人出手！
【在 f*****e 的大作中提到】
: 第一题可以解线性方程，无解，唯一解，多解，无穷解（impossible），
|
t****a
发帖数: 1212 | 22 我想第2题可以背包或者拆硬币，反正总和s_n=S/n已知，拆完一个包扔掉继续拆剩下的
，直到拆完为止/拆不完就说明不能求解。
这个办法虽然不好看，但计算量应该不大。
【在 m***k 的大作中提到】
: 这两道题感觉很难啊，有没有人能给出些思路？
: 1.对于一个整数矩阵，存在一种运算，对矩阵中任意元素加一时，需要其相邻（上下左
: 右）
: 某一个元素也加一，现给出一正数矩阵，判断其是否能够由一个全零矩阵经过上述运算
: 得到。
: 2.一个整数数组，长度为n，将其分为m份，使各份的和相等，求m的最大值
: 比如{3，2，4，3，6} 可以分成{3，2，4，3，6} m=1;
: {3,6}{2,4,3} m=2
: {3,3}{2,4}{6} m=3 所以m的最大值为3
: 请不要给brutal search的方法或code，希望能给出比较优化的时间、空间复杂度。
|
