On July 21, 2010, we ordered production of your new card. - 未名空间MITBBS历史存档

On July 21, 2010, we ordered production of your new card.# Immigration - 落地生根

h*62010-07-21 07:07

1 楼

已知整数 m ，其二进制形式有 k 位为1，打印出 0≤x≤m 所有满足以下条件的 x
x^(m-x) = m，其中^是异或运算符。
在 0≤m<2^n 范围内对每一个 m ，打印出所有的 x ，并求总复杂度。

l*l2010-07-21 07:07

2 楼

Crying baby got the milk.
I cried twice to officer Garza.
Replied at 4:52 PM Yesterday
Good Afternoon
Thank you for your inquiry. These cases are being reviewed by an officer.
If the I485’s are not approvable at this time we will make every effort to
approve the travel documents and the work authorization document.
Thank You
Officer Garza
Replied at 3:22 PM Yesterday
Good Afternoon
Thank you for your inquiry. Everything has cleared. But we have not
assigned them to an officer yet.
Thank You
O

z*m2010-07-21 07:07

3 楼

只有当两个数完全一样的时候，异或才会为0.
那么 X == M-X
所以 X=M/2
Only one solution?

A*d2010-07-21 07:07

4 楼

GXGX

z*m2010-07-21 07:07

5 楼

怎么异或等于m了，我刚才看错题了？
两个数x,y，他们的和与异或的结果都是m，那么就是x,y两个数分m为1的位。
求出m有多少个1,如果是k个，那么x的个数就是2^k - 2。实际上就是枚举m的所有为1的
位的组合。

p*r2010-07-21 07:07

6 楼

GXGX, Baozi please!

b*h2010-07-21 07:07

7 楼

试了一下，似乎是所有为1的位的全部子集。比如10的二进制表示为1010，那么一共有
两个x，即10（2）和1000（8）。14的话是1110，那么一共有六个，分别是2,4,6,8,10,
12

【在 h**6 的大作中提到】

: 已知整数 m ，其二进制形式有 k 位为1，打印出 0≤x≤m 所有满足以下条件的 x
: x^(m-x) = m，其中^是异或运算符。
: 在 0≤m<2^n 范围内对每一个 m ，打印出所有的 x ，并求总复杂度。

k*e2010-07-21 07:07

8 楼

big gx

h*62010-07-21 07:07

9 楼

题目有错，已经再次编辑修改润色。

【在 z******m 的大作中提到】

: 怎么异或等于m了，我刚才看错题了？
: 两个数x,y，他们的和与异或的结果都是m，那么就是x,y两个数分m为1的位。
: 求出m有多少个1,如果是k个，那么x的个数就是2^k - 2。实际上就是枚举m的所有为1的
: 位的组合。

t*72010-07-21 07:07

10 楼

真快啊！恭喜！！Officer Garza很好的人啊！
等包子！

x*y2010-07-21 07:07

11 楼

The relation between m and x should be: every bit of m is bigger than or
equal to the corresponding bit of x. Otherwise, assume that lowest bit that
violates this relation is bit L, then there will be a carry for bit L+1 when doing m-x; Then in m, if bit L+1 is 1 originally, then it becomes 0 for the carry when doing m-x: if in x, bit L+1 is 1, then in m-x, bit L+1 is 1, the XOR result
is 0, not original 1; if in x, bit L+1 is 0, in m-x, it's 0, the XOR is 0,
not 1. It can be verified similarly when bit L+1 in m is 0 originally. So,
the relation must be true.
When the relation is true, x and m-x will be both 0 if m is 0 in the
corresponding bit or 1 and 0 or 0 and 1 if m is 1 in the corresponding bit.
So, the answer is that x is all the numbers whose bit is 0 if the bit in m
is 0 and whose bit can be 0 or 1 if the bit in m is 1.

【在 h**6 的大作中提到】

: 已知整数 m ，其二进制形式有 k 位为1，打印出 0≤x≤m 所有满足以下条件的 x
: x^(m-x) = m，其中^是异或运算符。
: 在 0≤m<2^n 范围内对每一个 m ，打印出所有的 x ，并求总复杂度。

y*62010-07-21 07:07

12 楼

GX, baozi please

n*y2010-07-21 07:07

13 楼

学理论的吧？
你说的也对，但二楼比你解释的直观多了。

that
when doing m-x; Then in m, if bit L+1 is 1 originally, then it becomes 0 for
the carry when doing m-x: if in x, bit L+1 is 1, then in m-x, bit L+1 is 1
, the XOR result
,

【在 x***y 的大作中提到】

: The relation between m and x should be: every bit of m is bigger than or
: equal to the corresponding bit of x. Otherwise, assume that lowest bit that
: violates this relation is bit L, then there will be a carry for bit L+1 when doing m-x; Then in m, if bit L+1 is 1 originally, then it becomes 0 for the carry when doing m-x: if in x, bit L+1 is 1, then in m-x, bit L+1 is 1, the XOR result
: is 0, not original 1; if in x, bit L+1 is 0, in m-x, it's 0, the XOR is 0,
: not 1. It can be verified similarly when bit L+1 in m is 0 originally. So,
: the relation must be true.
: When the relation is true, x and m-x will be both 0 if m is 0 in the
: corresponding bit or 1 and 0 or 0 and 1 if m is 1 in the corresponding bit.
: So, the answer is that x is all the numbers whose bit is 0 if the bit in m
: is 0 and whose bit can be 0 or 1 if the bit in m is 1.

l*t2010-07-21 07:07

14 楼

congrats

h*62010-07-21 07:07

15 楼

本题有三种方法可以解答：
1.直接筛选法：
for(int m=0; m{
for(int x=0; x<=m; x++)
{
if((x^(m-x)) == m)
cout<}
}
对于每一个固定的m，循环次数为 m+1 次，总循环次数为 2^(2n-1)+2^(n-1)，复杂度
为 O(2^(2n)) 或 O(4^n)。
2.按位枚举法：
int* one = new int[n];
for(int m=0; m{
int mask = 1, k = 0;
for(int i=0; i{
if(m & mask)
one[k++] = mask;
mask <<= 1;
}
for(int i=0; i{
int mask2 = 1, x = 0;
for(int j=0; j{
if(i & mask2)
x += one[j];
mask2 <<= 1;
}
cout<}
}
delete []one;
对于每一个固定的m，循环次数为 k*2^k 次，总循环次数为 2*n*3^(n-1)，复杂度为 O
(n*3^n)，当 n 较大时(实测为n≥9)，复杂度比上一种方法小。
3.位运算法：
for(int m=0; m{
for(int x=m; x>=0; x--)
{
x &= m;
cout<}
}
对于每一个固定的m，循环次数为 2^k 次，总循环次数为 3^n，复杂度为 O(3^n)，比
以上两种方法小。

z*o2010-07-21 07:07

16 楼

GXGX!!!
baozi please

A*92010-07-21 07:07

17 楼

Congrats, Baozi!

p*f2010-07-21 07:07

18 楼

congrats

to

【在 l**l 的大作中提到】

: Crying baby got the milk.
: I cried twice to officer Garza.
: Replied at 4:52 PM Yesterday
: Good Afternoon
: Thank you for your inquiry. These cases are being reviewed by an officer.
: If the I485’s are not approvable at this time we will make every effort to
: approve the travel documents and the work authorization document.
: Thank You
: Officer Garza
: Replied at 3:22 PM Yesterday

G*p2010-07-21 07:07

19 楼

GX

m*g2010-07-21 07:07

20 楼

GXGX

m*h2010-07-21 07:07

21 楼

big big GXGX!

to

【在 l**l 的大作中提到】

: Crying baby got the milk.
: I cried twice to officer Garza.
: Replied at 4:52 PM Yesterday
: Good Afternoon
: Thank you for your inquiry. These cases are being reviewed by an officer.
: If the I485’s are not approvable at this time we will make every effort to
: approve the travel documents and the work authorization document.
: Thank You
: Officer Garza
: Replied at 3:22 PM Yesterday

j*22010-07-21 07:07

22 楼

Congratulations!
So you immediately email Garza after the first email? I got an email at the
same time, but I haven't ask him/her further. I feel bother her/him too much
. But so happy you get it. They really do their work now.

k*n2010-07-21 07:07

23 楼

cong

to

【在 l**l 的大作中提到】

: Crying baby got the milk.
: I cried twice to officer Garza.
: Replied at 4:52 PM Yesterday
: Good Afternoon
: Thank you for your inquiry. These cases are being reviewed by an officer.
: If the I485’s are not approvable at this time we will make every effort to
: approve the travel documents and the work authorization document.
: Thank You
: Officer Garza
: Replied at 3:22 PM Yesterday

z*12010-07-21 07:07

24 楼

恭喜，好快呀！

to

【在 l**l 的大作中提到】

: Crying baby got the milk.
: I cried twice to officer Garza.
: Replied at 4:52 PM Yesterday
: Good Afternoon
: Thank you for your inquiry. These cases are being reviewed by an officer.
: If the I485’s are not approvable at this time we will make every effort to
: approve the travel documents and the work authorization document.
: Thank You
: Officer Garza
: Replied at 3:22 PM Yesterday

m*g2010-07-21 07:07

25 楼

GX again.
By the way, did you tell officer Garza some special reasons for you to get
GC ASAP. Although I asked her about our name check and FP, she did not give
me a Yes or No answer. Her last message said that once they get all the
files, they'll check everything, which is very confusing to me.

d*12010-07-21 07:07

26 楼

GXGX!

to

【在 l**l 的大作中提到】

: Crying baby got the milk.
: I cried twice to officer Garza.
: Replied at 4:52 PM Yesterday
: Good Afternoon
: Thank you for your inquiry. These cases are being reviewed by an officer.
: If the I485’s are not approvable at this time we will make every effort to
: approve the travel documents and the work authorization document.
: Thank You
: Officer Garza
: Replied at 3:22 PM Yesterday

A*T2010-07-21 07:07

27 楼

恭喜啊

to

【在 l**l 的大作中提到】

: Crying baby got the milk.
: I cried twice to officer Garza.
: Replied at 4:52 PM Yesterday
: Good Afternoon
: Thank you for your inquiry. These cases are being reviewed by an officer.
: If the I485’s are not approvable at this time we will make every effort to
: approve the travel documents and the work authorization document.
: Thank You
: Officer Garza
: Replied at 3:22 PM Yesterday

l*l2010-07-21 07:07

28 楼

I gave her my service request information and why I want to get approved
soon due to some family reason.

give

【在 m**g 的大作中提到】

: GX again.
: By the way, did you tell officer Garza some special reasons for you to get
: GC ASAP. Although I asked her about our name check and FP, she did not give
: me a Yes or No answer. Her last message said that once they get all the
: files, they'll check everything, which is very confusing to me.

l*l2010-07-21 07:07

29 楼

Yes. A desperate guy was sending her an email. :) You can understand that.

the
much

【在 j****2 的大作中提到】

: Congratulations!
: So you immediately email Garza after the first email? I got an email at the
: same time, but I haven't ask him/her further. I feel bother her/him too much
: . But so happy you get it. They really do their work now.

j*52010-07-21 07:07

30 楼

big cong!

u*92010-07-21 07:07

31 楼

GXGX

to

【在 l**l 的大作中提到】

: Crying baby got the milk.
: I cried twice to officer Garza.
: Replied at 4:52 PM Yesterday
: Good Afternoon
: Thank you for your inquiry. These cases are being reviewed by an officer.
: If the I485’s are not approvable at this time we will make every effort to
: approve the travel documents and the work authorization document.
: Thank You
: Officer Garza
: Replied at 3:22 PM Yesterday

t*62010-07-21 07:07

32 楼

gongxi!

CM2010-07-21 07:07

33 楼

lool, so you actually submitted a service request through 800 call? for 485
or EAD/AP stuff?

【在 l**l 的大作中提到】

: I gave her my service request information and why I want to get approved
: soon due to some family reason.
:
: give

l*l2010-07-21 07:07

34 楼

Yes. two SR: one for I485, one for I765.

485

【在 CM 的大作中提到】

: lool, so you actually submitted a service request through 800 call? for 485
: or EAD/AP stuff?

z*12010-07-21 07:07

35 楼

How you can do SR to I485 since it is not more than 4 months?

【在 l**l 的大作中提到】

: Yes. two SR: one for I485, one for I765.
:
: 485

k*n2010-07-21 07:07

36 楼

I also want to know that..

【在 z*****1 的大作中提到】

: How you can do SR to I485 since it is not more than 4 months?

l*l2010-07-21 07:07

37 楼

What you said is the last criterion to ask for SR.
The more top three criteria are (1) financial lose.... (Which are the same
with we applied for OPT and other visa expedite processing, if I remember
correctly. Sorry I did not remember the other two because I applied for this
one.)

【在 z*****1 的大作中提到】

: How you can do SR to I485 since it is not more than 4 months?

z*12010-07-21 07:07

38 楼

Thanks lool.

this

【在 l**l 的大作中提到】

: What you said is the last criterion to ask for SR.
: The more top three criteria are (1) financial lose.... (Which are the same
: with we applied for OPT and other visa expedite processing, if I remember
: correctly. Sorry I did not remember the other two because I applied for this
: one.)

t*r2010-07-21 07:07

39 楼

恭喜，baozi plz!

a*e2010-07-21 07:07

40 楼

GXGX！！！！

n*g2010-07-21 07:07

41 楼

gx :)

w*r2010-07-21 07:07

42 楼

Big congratulations.
It's great to see so many good news.

r*e2010-07-21 07:07

43 楼

GX!

to

【在 l**l 的大作中提到】

: Crying baby got the milk.
: I cried twice to officer Garza.
: Replied at 4:52 PM Yesterday
: Good Afternoon
: Thank you for your inquiry. These cases are being reviewed by an officer.
: If the I485’s are not approvable at this time we will make every effort to
: approve the travel documents and the work authorization document.
: Thank You
: Officer Garza
: Replied at 3:22 PM Yesterday