l*a
2 楼
如果rim真卖的话
RIM + nokia + skype
这表示啥
RIM + nokia + skype
这表示啥
l*8
3 楼
上午刚去别处站岗上班, 还没进屋就看到跑来一只小白狗.
花脸出击, 把小白狗弄得鬼哭狼嚎地跑回家.
花脸出击, 把小白狗弄得鬼哭狼嚎地跑回家.
w*e
4 楼
找零问题？
a*x
5 楼
我还以为是“貌似要买轮圈”。。。。= =|||
r*a
6 楼
主人没说让咬就咬，该打了，哈哈
【在 l******8 的大作中提到】
: 上午刚去别处站岗上班, 还没进屋就看到跑来一只小白狗.
: 花脸出击, 把小白狗弄得鬼哭狼嚎地跑回家.
【在 l******8 的大作中提到】
: 上午刚去别处站岗上班, 还没进屋就看到跑来一只小白狗.
: 花脸出击, 把小白狗弄得鬼哭狼嚎地跑回家.
x*k
7 楼
a_1^2+a_2^2+...+a_k^=T 最后那个a_k^后面也是平方么？如果是，就从最大往小减去。
int p = 1;
while ( p * p < T ) {
p = p << 1;
}
while (T != 0) {
if (p * p <= T) {
T -= p * p;
System.out.println(p);
} else {
p = p >> 1;
}
}
int p = 1;
while ( p * p < T ) {
p = p << 1;
}
while (T != 0) {
if (p * p <= T) {
T -= p * p;
System.out.println(p);
} else {
p = p >> 1;
}
}
l*a
8 楼
咱太心有灵犀了
【在 a*********x 的大作中提到】
: 我还以为是“貌似要买轮圈”。。。。= =|||
【在 a*********x 的大作中提到】
: 我还以为是“貌似要买轮圈”。。。。= =|||
f*w
9 楼
去。
贪心没办法保证k最小吧
【在 x********k 的大作中提到】
: a_1^2+a_2^2+...+a_k^=T 最后那个a_k^后面也是平方么？如果是，就从最大往小减去。
: int p = 1;
: while ( p * p < T ) {
: p = p << 1;
: }
: while (T != 0) {
: if (p * p <= T) {
: T -= p * p;
: System.out.println(p);
: } else {
s*s
10 楼
ms买不起吧，skype都那么多钱，估计一下rim
f*w
11 楼
比如4^2 + 5^2 = 16 + 25 = 41
如果用贪心的结果就是41 = 36 + 4 + 1.
如果用贪心的结果就是41 = 36 + 4 + 1.
l*t
12 楼
应该可以dp吧
【在 w****g 的大作中提到】
: 听来的，
: 输入是一个自然数T， 输出是(a_1,a_2,...,a_k)
: 使得a_1^2+a_2^2+...+a_k^=T， 并且k尽可能小
【在 w****g 的大作中提到】
: 听来的，
: 输入是一个自然数T， 输出是(a_1,a_2,...,a_k)
: 使得a_1^2+a_2^2+...+a_k^=T， 并且k尽可能小
l*0
13 楼
bool isSquare(int n)
{
int num = 0;
while (n)
{
if (n&0x01)
num++;
n =>>1;
}
if (num >= 2)
return false;
else
return true;
}
int getComb(int n, int tmp[])
{
int l = n/2, r = n-l;
int min = tmp[l] + tmp[r];
while (l > 0 && r < n)
{
int cur = tmp[l] + tmp[r];
if (min > cur)
min = cur;
l--;
r++;
}
return min;
}
int getSmallestK(int n)
{
if (n <= 0)
return 0;
int *tmp = new int[n+1];
tmp[1] = 1;
for (int i=2; i<=n; i++)
{
if (isSquare(i))
tmp[i] = 1;
else
tmp[i] = getComb(i, tmp);
}
return tmp[n];
}
{
int num = 0;
while (n)
{
if (n&0x01)
num++;
n =>>1;
}
if (num >= 2)
return false;
else
return true;
}
int getComb(int n, int tmp[])
{
int l = n/2, r = n-l;
int min = tmp[l] + tmp[r];
while (l > 0 && r < n)
{
int cur = tmp[l] + tmp[r];
if (min > cur)
min = cur;
l--;
r++;
}
return min;
}
int getSmallestK(int n)
{
if (n <= 0)
return 0;
int *tmp = new int[n+1];
tmp[1] = 1;
for (int i=2; i<=n; i++)
{
if (isSquare(i))
tmp[i] = 1;
else
tmp[i] = getComb(i, tmp);
}
return tmp[n];
}
m*t
14 楼
楼上这个 是不是长年累月的写Java
g*y
15 楼
1. 拉格朗日定理：任何一个整数都可以分解成4个整数的平方和。
2. a_i <= sqrt(T)
3. BFS, search one square sum (0 ~ sqrt(T)), then two square sum, ... it
will end at most level 4.
程序可能可以更高效 －－
public List split(int N) {
int n = (int) Math.sqrt(N);
int[] square = new int[n];
for (int i=0; i
List[] res = new List[N];
res[0] = new ArrayList();
Queue queue = new ArrayDeque();
queue.add(0);
while (!queue.isEmpty()) {
int num = queue.poll();
for (int i=0; i
if (next == N) {
res[num].add(i + 1);
return res[num];
}
if (next > N) break;
if (res[next] == null) {
res[next] = new ArrayList(res[num]);
res[next].add(i + 1);
queue.add(next);
}
}
}
// According to Lagrange's theorem, every integer can be expressed
with 4 squares,
// satisfy compiler's curiosity here.
return null;
}
【在 w****g 的大作中提到】
: 听来的，
: 输入是一个自然数T， 输出是(a_1,a_2,...,a_k)
: 使得a_1^2+a_2^2+...+a_k^=T， 并且k尽可能小
2. a_i <= sqrt(T)
3. BFS, search one square sum (0 ~ sqrt(T)), then two square sum, ... it
will end at most level 4.
程序可能可以更高效 －－
public List
int n = (int) Math.sqrt(N);
int[] square = new int[n];
for (int i=0; i
List[] res = new List[N];
res[0] = new ArrayList
Queue
queue.add(0);
while (!queue.isEmpty()) {
int num = queue.poll();
for (int i=0; i
if (next == N) {
res[num].add(i + 1);
return res[num];
}
if (next > N) break;
if (res[next] == null) {
res[next] = new ArrayList
res[next].add(i + 1);
queue.add(next);
}
}
}
// According to Lagrange's theorem, every integer can be expressed
with 4 squares,
// satisfy compiler's curiosity here.
return null;
}
【在 w****g 的大作中提到】
: 听来的，
: 输入是一个自然数T， 输出是(a_1,a_2,...,a_k)
: 使得a_1^2+a_2^2+...+a_k^=T， 并且k尽可能小
r*7
16 楼
就是背包题吧，不知道有没有什么更高效的方法。
【在 w****g 的大作中提到】
: 听来的，
: 输入是一个自然数T， 输出是(a_1,a_2,...,a_k)
: 使得a_1^2+a_2^2+...+a_k^=T， 并且k尽可能小
【在 w****g 的大作中提到】
: 听来的，
: 输入是一个自然数T， 输出是(a_1,a_2,...,a_k)
: 使得a_1^2+a_2^2+...+a_k^=T， 并且k尽可能小
z*m
17 楼
会不会顺便让你证明这个定理啊？
【在 g**********y 的大作中提到】
: 1. 拉格朗日定理：任何一个整数都可以分解成4个整数的平方和。
: 2. a_i <= sqrt(T)
: 3. BFS, search one square sum (0 ~ sqrt(T)), then two square sum, ... it
: will end at most level 4.
: 程序可能可以更高效 －－
: public List split(int N) {
: int n = (int) Math.sqrt(N);
:
: int[] square = new int[n];
: for (int i=0; i
【在 g**********y 的大作中提到】
: 1. 拉格朗日定理：任何一个整数都可以分解成4个整数的平方和。
: 2. a_i <= sqrt(T)
: 3. BFS, search one square sum (0 ~ sqrt(T)), then two square sum, ... it
: will end at most level 4.
: 程序可能可以更高效 －－
: public List
: int n = (int) Math.sqrt(N);
:
: int[] square = new int[n];
: for (int i=0; i
Q*a
18 楼
写了两个解，一个n^2, 一个bfs, 10^5量级上bfs已经快上10倍了
vector breakDownToSquareSum(int n) {
vector> results(n+1);
results[1].push_back(1);
int maxSeed = 1;
for (int i = 2; i <= n; ++i) {
if ((maxSeed + 1) * (maxSeed + 1) <= i) ++maxSeed;
for (int j = maxSeed; j >= 1; --j) {
if (j * j == i) {
results[i].clear();
results[i].push_back(j);
break;
}
else {
if (results[i].empty() || results[i-j*j].size() + 1 <
results[i].size()) {
results[i].clear();
results[i].insert(results[i].end(), results[i-j*j].begin
(), results[i-j*j].end());
results[i].push_back(j);
}
}
}
}
return results.back();
}
vector breakDownToSquareSum1(int n) {
int maxSeed = (int)sqrt(n);
queue> queue;
vector visited(n+1, false);
for (int i = 1; i * i <= n; ++i) {
int k = i * i;
if (k == n) {
return vector(1, i);
}
vector v;
v.push_back(k);
v.push_back(i);
visited[k] = true;
queue.push(v);
}
while (!queue.empty()) {
vector v = queue.front();
queue.pop();
for (int i = 1; v.front() + i*i <= n; ++i) {
int k = v.front() + i*i;
if (visited[k]) {
continue;
}
visited[k] = true;
if (k == n) {
v[0] = i;
return v;
}
vector v1(v);
v1[0] = k;
v1.push_back(i);
queue.push(v1);
}
}
return vector();
}
vector
vector
results[1].push_back(1);
int maxSeed = 1;
for (int i = 2; i <= n; ++i) {
if ((maxSeed + 1) * (maxSeed + 1) <= i) ++maxSeed;
for (int j = maxSeed; j >= 1; --j) {
if (j * j == i) {
results[i].clear();
results[i].push_back(j);
break;
}
else {
if (results[i].empty() || results[i-j*j].size() + 1 <
results[i].size()) {
results[i].clear();
results[i].insert(results[i].end(), results[i-j*j].begin
(), results[i-j*j].end());
results[i].push_back(j);
}
}
}
}
return results.back();
}
vector
int maxSeed = (int)sqrt(n);
queue
vector
for (int i = 1; i * i <= n; ++i) {
int k = i * i;
if (k == n) {
return vector
}
vector
v.push_back(k);
v.push_back(i);
visited[k] = true;
queue.push(v);
}
while (!queue.empty()) {
vector
queue.pop();
for (int i = 1; v.front() + i*i <= n; ++i) {
int k = v.front() + i*i;
if (visited[k]) {
continue;
}
visited[k] = true;
if (k == n) {
v[0] = i;
return v;
}
vector
v1[0] = k;
v1.push_back(i);
queue.push(v1);
}
}
return vector
}
相关阅读