acm竞赛位运算简介及实用技巧
位运算简介及实用技巧
转载者注：最近在论坛上看到些十分空虚、空大的帖子。觉得编程还是要讲点实践，实践出真知。
众所周知，人和电脑处理的方式究竟还是不同的，否则人人都是计算机程序员了。有些东西对人说很容易，而对计算机来说很难，反之
亦然。
位操作就是人和电脑处理方式不同的体现，有些人认为这个东西有些BT，但其实非常高效的程序大多都是用位操作优化，因为它十分底层，速度极快。其实位操作也有他自己独特的性质，只要我们能熟练得掌握，就可以更好得驾驭我们的程序，这也是我转此帖的目的。
PS：不要把注意力集中在语言上，所有语言都是一样的，只是工具而已。
去年年底写的关于位运算的日志是这个Blog里少数大受欢迎的文章之一，很多人都希望我能不断完善那篇文章。后来我看到了不少其它的资料，学习到了更多关于位运算的知识，有了重新整理位运算技巧的想法。从今天起我就开始写这一系列位运算讲解文章，与其说是原来那篇文章的follow-up，不如说是一个remake。当然首先我还是从最基础的东西说起。
什么是位运算？
程序中的所有数在计算机内存中都是以二进制的形式储存的。位运算说穿了，就是直接对整数在内存中的二进制位进行操作。比如，and运算本来是一个逻辑运算符，但整数与整数之间也可以进行and运算。举个例子，6的二进制是110，11的二进制是1011，那么6 and 11的结果就是2，它是二进制对应位进行逻辑运算的结果（0表示False，1表示True，空位都当0处理）：
110
AND 1011
----------
0010 --> 2
由于位运算直接对内存数据进行操作，不需要转成十进制，因此处理速度非常快。当然有人会说，这个快了有什么用，计算6 and 11没有什么实际意义啊。这一系列的文章就将告诉你，位运算到底可以干什么，有些什么经典应用，以及如何用位运算优化你的程序。
Pascal和C中的位运算符号
下面的a和b都是整数类型，则：
C语言 | Pascal语言
-------+-------------
a &
b | a and b
a |
b | a or b
a ^
b | a xor b
~a | not a
a <<
b | a shl b
a >>
b | a shr b
注意C中的逻辑运算和位运算符号是不同的。520|1314=1834，但520||1314=1，因为逻辑运算时520和1314都相当于True。同样
的，!a和~a也是有区别的。
各种位运算的使用
=== 1. and运算 ===
and运算通常用于二进制取位操作，例如一个数 and 1的结果就是取二进制的最末位。这可以用来判断一个整数的奇偶，二进制的
最末位为0表示该数为偶数，最末位为1表示该数为奇数.
=== 2. or运算 ===
or运算通常用于二进制特定位上的无条件赋值，例如一个数or 1的结果就是把二进制最末位强行变成1。如果需要把二进制最末位变成0，对这个数or 1之后再减一就可以了，其实际意义就是把这个数强行变成最接近的偶数。
=== 3. xor运算 ===
xor运算通常用于对二进制的特定一位进行取反操作，因为异或可以这样定义：0和1异或0都不变，异或1则取反。
xor运算的逆运算是它本身，也就是说两次异或同一个数最后结果不变，即(a xor b) xor b = a。xor运算可以用于简单的加密，比如我想对我MM说1314520，但怕别人知道，于是双方约定拿我的生日19880516作为密钥。1314520 xor 19880516 = 20665500，我就把20665500告诉MM。MM再次计算20665500 xor 19880516的值，得到1314520，于是她就明白了我的企图。
下面我们看另外一个东西。定义两个符号#和@（我怎么找不到那个圈里有个叉的字符），这两个符号互为逆运算，也就是说(x # y)
@ y = x。现在依次执行下面三条命令，结果是什么？
复制内容到剪贴板
x <- x # y
y <- x @ y
x <- x @ y
执行了第一句后x变成了x # y。那么第二句实质就是y <- x # y @ y，由于#和@互为逆运算，那么此时的y变成了原来的x。第三句中x实际上被赋值为(x # y) @ x，如果#运算具有交换律，那么赋值后x就变成最初的y了。这三句话的结果是，x和y的位置互换了。（转
载者注：怪不得有些东西可以这么用，这才是实质啊！）
加法和减法互为逆运算，并且加法满足交换律。把#换成+，把@换成-，我们可以写出一个不需要临时变量的swap过程(Pascal)。
复制内容到剪贴板
procedure swap(var a,b:longint);
begin
b:=a - b;
a:=a - b;
end;
好了，刚才不是说xor的逆运算是它本身吗？于是我们就有了一个看起来非常诡异的swap过程：
复制内容到剪贴板
procedure swap(var a,b:longint);
begin
a:=a xor b;
b:=a xor b;
a:=a xor b;
end;
=== 4. not运算 ===
not运算的定义是把内存中的0和1全部取反。使用not运算时要格外小心，你需要注意整数类型有没有符号。如果not的对象是无符号整数（不能表示负数），那么得到的值就是它与该类型上界的差，因为无符号类型的数是用$0000到$FFFF依次表示的。下面的两个
程序（仅语言不同）均返回65435。
复制内容到剪贴板
var
a:word;
begin
a:=100;
a:=not a;
writeln(a);
end.
复制内容到剪贴板
#include
int main()
{
unsigned short a=100;
printf( "%d\n", a );
return 0;
}
如果not的对象是有符号的整数，情况就不一样了，稍后我们会在“整数类型的储存”小节中提到。
=== 5. shl运算 ===
a shl b就表示把a转为二进制后左移b位（在后面添b个0）。例如100的二进制为1100100，而110010000转成十进制是400，
那么100 shl 2 = 400。可以看出，a shl b的值实际上就是a乘以2的b次方，因为在二进制数后添一个0就相当于该数乘以2。
通常认为a shl 1比a * 2更快，因为前者是更底层一些的操作。因此程序中乘以2的操作请尽量用左移一位来代替。
定义一些常量可能会用到shl运算。你可以方便地用1 shl 16 - 1来表示65535。很多算法和数据结构要求数据规模必须是2的幂，
此时可以用shl来定义Max_N等常量。
=== 6. shr运算 ===
和shl相似，a shr b表示二进制右移b位（去掉末b位），相当于a除以2的b次方（取整）。我们也经常用shr 1来代替div 2，比如二分查找、堆的插入操作等等。想办法用shr代替除法运算可以使程序效率大大提高。最大公约数的二进制算法用除以2操作来代
替慢得出奇的mod运算，效率可以提高60%。
位运算的简单应用
有时我们的程序需要一个规模不大的Hash表来记录状态。比如，做数独时我们需要27个Hash表来统计每一行、每一列和每一个小九宫格里已经有哪些数了。此时，我们可以用27个小于2^9的整数进行记录。例如，一个只填了2和5的小九宫格就用数字18表示（二进制为000010010），而某一行的状态为511则表示这一行已经填满。需要改变状态时我们不需要把这个数转成二进制修改后再转回去，而是直接进行位操作。在搜索时，把状态表示成整数可以更好地进行判重等操作。这道题是在搜索中使用位运算加速的经典例子。以后
我们会看到更多的例子。
下面列举了一些常见的二进制位的变换操作。
功能 | 示例 | 位运算
----------------------+---------------------------+--------------------
去掉最后一位 | (101101->10110) | x shr 1
在最后加一个0 | (101101->1011010) | x shl 1
在最后加一个1 | (101101->1011011) | x shl 1+1
把最后一位变成1 | (101100->101101) | x or 1
把最后一位变成0 | (101101->101100) | x or 1-1
最后一位取反 | (101101->101100) | x xor 1
把右数第k位变成1 | (101001->101101,k=3) | x or (1 shl (k-1))
把右数第k位变成0 | (101101->101001,k=3) | x and not (1 shl (k-1))
右数第k位取反 | (101001->101101,k=3) | x xor (1 shl (k-1))
取末三位 | (1101101->101) | x and 7
取末k位 | (1101101->1101,k=5) | x and (1 shl k-1)
取右数第k位 | (1101101->1,k=4) | x shr (k-1) and 1
把末k位变成1 | (101001->101111,k=4) | x or (1 shl k-1)
末k位取反 | (101001->100110,k=4) | x xor (1 shl k-1)
把右边连续的1变成0 | (100101111->100100000) | x and (x+1)
把右起第一个0变成1 | (100101111->100111111) | x or (x+1)
把右边连续的0变成1 | (11011000->11011111) | x or (x-1)
取右边连续的1 | (100101111->1111) | (x xor (x+1)) shr 1
去掉右起第一个1的左边 | (100101000->1000) | x and (x xor (x-1))
最后这一个在树状数组中会用到。
Pascal和C中的16进制表示
Pascal中需要在16进制数前加$符号表示，C中需要在前面加0x来表示。这个以后我们会经常用到。
整数类型的储存
我们前面所说的位运算都没有涉及负数，都假设这些运算是在unsigned/word类型（只能表示正数的整型）上进行操作。但计算机如何处理有正负符号的整数类型呢？下面两个程序都是考察16位整数的储存方式（只是语言不同）。
复制内容到剪贴板
var
a,b:integer;
begin
a:=$0000;
b:=$0001;
write(a,' ',b,' ');
a:=$FFFE;
b:=$FFFF;
write(a,' ',b,' ');
a:=$7FFF;
writeln(a,' ',b);
end.
复制内容到剪贴板
#include
int main()
{
short int a, b;
a = 0x0000;
b = 0x0001;
printf( "%d %d ", a, b );
a = 0xFFFE;
b = 0xFFFF;
printf( "%d %d ", a, b );
a = 0x7FFF;
b = 0x8000;
printf( "%d %d\n", a, b );
return 0;
}
两个程序的输出均为0 1 -2 -1 32767 -32768。其中前两个数是内存值最小的时候，中间两个数则是内存值最大的时候，最后输出的两个数是正数与负数的分界处。由此你可以清楚地看到计算机是如何储存一个整数的：计算机用$0000到$7FFF依次表示0到32767的数，剩下的$8000到$FFFF依次表示-32768到-1的数。32位有符号整数的储存方式也是类似的。稍加注意你会发现，二进制的第一位是用来表示正负号的，0表示正，1表示负。这里有一个问题：0本来既不是正数，也不是负数，但它占用了$0000的位置，因此有符号的整数类型范围中正数个数比负数少一个。对一个有符号的数进行not运算后，最高位的变化将导致正负颠倒，并且数的绝对值会差1。也就是
说，not a实际上等于-a-1。这种整数储存方式叫做“补码”。
===== 真正强的东西来了！ =====
二进制中的1有奇数个还是偶数个
我们可以用下面的代码来计算一个32位整数的二进制中1的个数的奇偶性，当输入数据的二进制表示里有偶数个数字1时程序输出0，有奇数个则输出1。例如，1314520的二进制101000000111011011000中有9个1，则x=1314520时程序输出1。
复制内容到剪贴板
var
i,x,c:longint;
begin
readln(x);
c:=0;
for i:=1 to 32 do
begin
c:=c + x and 1;
x:=x shr 1;
end;
writeln( c and 1 );
end.
但这样的效率并不高，位运算的神奇之处还没有体现出来。
同样是判断二进制中1的个数的奇偶性，下面这段代码就强了。你能看出这个代码的原理吗？
复制内容到剪贴板
var
x:longint;
begin
readln(x);
x:=x xor (x shr 1);
x:=x xor (x shr 2);
x:=x xor (x shr 4);
x:=x xor (x shr 8);
x:=x xor (x shr 16);
writeln(x and 1);
end.
为了说明上面这段代码的原理，我们还是拿1314520出来说事。1314520的二进制为101000000111011011000，第一次异或操作的结果如
下：
00000000000101000000111011011000
XOR 0000000000010100000011101101100
---------------------------------------
00000000000111100000100110110100
得到的结果是一个新的二进制数，其中右起第i位上的数表示原数中第i和i+1位上有奇数个1还是偶数个1。比如，最右边那个0表示原数末两位有偶数个1，右起第3位上的1就表示原数的这个位置和前一个位置中有奇数个1。对这个数进行第二次异或的结果如下：
00000000000111100000100110110100
XOR 000000000001111000001001101101
---------------------------------------
00000000000110011000101111011001
结果里的每个1表示原数的该位置及其前面三个位置中共有奇数个1，每个0就表示原数对应的四个位置上共偶数个1。一直做到第五次异或结束后，得到的二进制数的最末位就表示整个32位数里有多少个1，这就是我们最终想要的答案。
计算二进制中的1的个数
同样假设x是一个32位整数。经过下面五次赋值后，x的值就是原数的二进制表示中数字1的个数。比如，初始时x为1314520（网友抓狂：能不能换一个数啊），那么最后x就变成了9，它表示1314520的二进制中有9个1。
复制内容到剪贴板
x := (x and $55555555) + ((x shr 1) and $55555555);
x := (x and $33333333) + ((x shr 2) and $33333333);
x := (x and $0F0F0F0F) + ((x shr 4) and $0F0F0F0F);
x := (x and $00FF00FF) + ((x shr 8) and $00FF00FF);
x := (x and $0000FFFF) + ((x shr 16) and $0000FFFF);
为了便于解说，我们下面仅说明这个程序是如何对一个8位整数进行处理的。我们拿数字211（我们班某MM的生日）来开刀。211的二
进制为11010011。
+---+---+---+---+---+---+---+---+
| 1 | 1 | 0 | 1 | 0 | 0 | 1 | 1 | <---原数
+---+---+---+---+---+---+---+---+
| 1 0 | 0 1 | 0 0 | 1 0 | <---第一次运算后
+-------+-------+-------+-------+
| 0 0 1 1 | 0 0 1 0 | <---第二次运算后
+---------------+---------------+
| 0 0 0 0 0 1 0 1 | <---第三次运算后，得数为5
+-------------------------------+
整个程序是一个分治的思想。第一次我们把每相邻的两位加起来，得到每两位里1的个数，比如前两位10就表示原数的前两位有2个1。第二次我们继续两两相加，10+01=11，00+10=10，得到的结果是00110010，它表示原数前4位有3个1，末4位有2个1。最后一次我们把0011和0010加起来，得到的就是整个二进制中1的个数。程序中巧妙地使用取位和右移，比如第二行中$33333333的二进制为00110011001100....，用它和x做and运算就相当于以2为单位间隔取数。shr的作用就是让加法运算的相同数位对齐。
二分查找32位整数的前导0个数
这里用的C语言，我直接Copy的Hacker's Delight上的代码。这段代码写成C要好看些，写成Pascal的话会出现很多begin和end，搞得代码很难看。程序思想是二分查找，应该很简单，我就不细说了。
复制内容到剪贴板
int nlz(unsigned x)
{
int n;
if (x == 0) return(32);
n = 1;
if ((x >> 16) == 0) {n = n +16; x = x <<16;}
if ((x >> 24) == 0) {n = n + 8; x = x << 8;}
if ((x >> 28) == 0) {n = n + 4; x = x << 4;}
if ((x >> 30) == 0) {n = n + 2; x = x << 2;}
n = n - (x >> 31);
return n;
}
只用位运算来取绝对值
这是一个非常有趣的问题。假设x为32位整数，则x xor (not (x shr 31) + 1) + x shr 31的结果是x的绝对值，x shr 31是二进制的最高位，它用来表示x的符号。如果它为0（x为正），则not (x shr 31) + 1等于$00000000，异或任何数结果都不变；如果最高位为1（x为负），则not (x shr 31) + 1等于$FFFFFFFF，x异或它相当于所有数位取反，异或完后再加一。
高低位交换
这个题实际上是我出的，做为学校内部NOIp模拟赛的第一题。题目是这样：
给出一个小于2^32的正整数。这个数可以用一个32位的二进制数表示（不足32位用0补足）。我们称这个二进制数的前16位为“高位”，后16位为“低位”。将它的高低位交换，我们可以得到一个新的数。试问这个新的数是多少（用十进制表示）。
例如，数1314520用二进制表示为0000 0000 0001 0100 0000 1110 1101 1000（添加了11个前导0补足为32位），其中前16位为高位，即0000 0000 0001 0100；后16位为低位，即0000 1110 1101 1000。将它的高低位进行交换，我们得到了一个新的二进制数0000 1110 1101 1000 0000 0000 0001 0100。它即
是十进制的249036820。
当时几乎没有人想到用一句位操作来代替冗长的程序。使用位运算的话两句话就完了。
复制内容到剪贴板
var
n:dword;
begin
readln( n );
writeln( (n shr 16) or (n shl 16) );
end.
而事实上，Pascal有一个系统函数swap直接就可以用。
二进制逆序
下面的程序读入一个32位整数并输出它的二进制倒序后所表示的数。
输入： 1314520 （二进制为00000000000101000000111011011000）
输出： 460335104 （二进制为00011011011100000010100000000000）
复制内容到剪贴板
var
x:dword;
begin
readln(x);
x := (x and $55555555) shl 1 or (x and $AAAAAAAA) shr 1;
x := (x and $33333333) shl 2 or (x and $CCCCCCCC) shr 2;
x := (x and $0F0F0F0F) shl 4 or (x and $F0F0F0F0) shr 4;
x := (x and $00FF00FF) shl 8 or (x and $FF00FF00) shr 8;
x := (x and $0000FFFF) shl 16 or (x and $FFFF0000) shr 16;
writeln(x);
end.
它的原理和刚才求二进制中1的个数那个例题是大致相同的。程序首先交换每相邻两位上的数，以后把互相交换过的数看成一个整体，继续进行以2位为单位、以4位为单位的左右对换操作。我们再次用8位整数211来演示程序执行过程：
+---+---+---+---+---+---+---+---+
| 1 | 1 | 0 | 1 | 0 | 0 | 1 | 1 | <---原数
+---+---+---+---+---+---+---+---+
| 1 1 | 1 0 | 0 0 | 1 1 | <---第一次运算后
+-------+-------+-------+-------+
| 1 0 1 1 | 1 1 0 0 | <---第二次运算后
+---------------+---------------+
| 1 1 0 0 1 0 1 1 | <---第三次运算后
+-------------------------------+
Copyright也很强
复制内容到剪贴板
writeln('Matrix' , 42 XOR 105 , '原创，转贴请注明出处');
今天我们来看两个稍微复杂一点的例子。
n皇后问题位运算版
n皇后问题是啥我就不说了吧，学编程的肯定都见过。下面的十多行代码是n皇后问题的一个高效位运算程序，看到过的人都夸它牛。初始时，upperlim:=(1 shl n)-1。主程序调用test(0,0,0)后sum的值就是n皇后总的解数。拿这个去交USACO，0.3s，暴爽。（转载
者注：MS我用C++只有0.108s）
复制内容到剪贴板
procedure test(row,ld,rd:longint);
var
pos,p:longint;
begin
{ 1} if row<>upperlim then
{ 2} begin
{ 3} pos:=upperlim and not (row or ld or rd);
{ 4} while pos<>0 do
{ 5} begin
{ 6} p:=pos and -pos;
{ 7} pos:=pos-p;
{ 8} test(row+p,(ld+p)shl 1,(rd+p)shr 1);
{ 9} end;
{10} end
{11} else inc(sum);
end;
乍一看似乎完全摸不着头脑，实际上整个程序是非常容易理解的。这里还是建议大家自己单步运行一探究竟，实在没研究出来再看下面
的解说。
和普通算法一样，这是一个递归过程，程序一行一行地寻找可以放皇后的地方。过程带三个参数，row、ld和rd，分别表示在纵列和两个对角线方向的限制条件下这一行的哪些地方不能放。我们以6x6的棋盘为例，看看程序是怎么工作的。假设现在已经递归到第四层，前三层放的子已经标在左图上了。红色、蓝色和绿色的线分别表示三个方向上有冲突的位置，位于该行上的冲突位置就用row、ld 和rd中的1来表示。把它们三个并起来，得到该行所有的禁位，取反后就得到所有可以放的位置（用pos来表示）。前面说过-a相当于
not a + 1，这里的代码第6行就相当于pos and (not pos + 1)，其结果是取出最右边的那个1。这样，p就表示该行的某个可以放子的位置，把它从pos中移除并递归调用test过程。注意递归调用时三个参数的变化，每个参数都加上了一个禁位，但两个对角线方向的禁位对下一行的影响需要平移一位。最后，如果递归到某个时候发现row=111111了，说明六个皇后全放进去了，此时程序从第1行跳到第
11行，找到的解的个数加一。
~~~~====~~~~===== 华丽的分割线 =====~~~~====~~~~
Gray码
假如我有4个潜在的GF，我需要决定最终到底和谁在一起。一个简单的办法就是，依次和每个MM交往一段时间，最后选择给我带来的“满意度”最大的MM。但看了dd牛的理论后，事情开始变得复杂了：我可以选择和多个MM在一起。这样，需要考核的状态变成了2^4=16种（当然包括0000这一状态，因为我有可能是玻璃）。现在的问题就是，我应该用什么顺序来遍历这16种状态呢？
传统的做法是，用二进制数的顺序来遍历所有可能的组合。也就是说，我需要以0000->0001->0010->0011->0100->...->1111这样的顺序对每种状态进行测试。这个顺序很不科学，很多时候状态的转移都很耗时。比如从0111到1000时我需要暂时甩掉当前所有的3个MM，然后去把第4个MM。同时改变所有MM与我的关系是一件何等巨大的工程啊。因此，我希望知道，是否有一种方法可以使得，从没有MM这一状态出发，每次只改变我和一个MM的关系（追或者甩），15次操作后恰好遍历完所有可能的组合（最终状态不一定是1111）。
大家自己先试一试看行不行。
解决这个问题的方法很巧妙。我们来说明，假如我们已经知道了n=2时的合法遍历顺序，我们如何得到n=3的遍历顺序。显然，n=2
的遍历顺序如下：
00
01
11
10
你可能已经想到了如何把上面的遍历顺序扩展到n=3的情况。n=3时一共有8种状态，其中前面4个把n=2的遍历顺序照搬下来，然
后把它们对称翻折下去并在最前面加上1作为后面4个状态：
你可能已经想到了如何把上面的遍历顺序扩展到n=3的情况。n=3时一共有8种状态，其中前面4个把n=2的遍历顺序照搬下来，然
后把它们对称翻折下去并在最前面加上1作为后面4个状态：
000
001
011
010↑
--------
110↓
111
101
100
用这种方法得到的遍历顺序显然符合要求。首先，上面8个状态恰好是n=3时的所有8种组合，因为它们是在n=2的全部四种组合的基础上考虑选不选第3个元素所得到的。然后我们看到，后面一半的状态应该和前面一半一样满足“相邻状态间仅一位不同”的限制，而“镜面”处则是最前面那一位数不同。再次翻折三阶遍历顺序，我们就得到了刚才的问题的答案：
0000
0001
0011
0010
0110
0111
0101
0100
1100
1101
1111
1110
1010
1011
1001
1000
这种遍历顺序作为一种编码方式存在，叫做Gray码（写个中文让蜘蛛来抓：格雷码）。它的应用范围很广。比如，n阶的Gray码相当于在n维立方体上的Hamilton回路，因为沿着立方体上的边走一步，n维坐标中只会有一个值改变。再比如，Gray码和Hanoi塔问题等价。Gray码改变的是第几个数，Hanoi塔就该移动哪个盘子。比如，3阶的Gray码每次改变的元素所在位置依次为1-2-1-3-1-2-1，这正好是3阶Hanoi塔每次移动盘子编号。如果我们可以快速求出Gray码的第n个数是多少，我们就可以输出任意步数后Hanoi塔的移动步骤。现在我告诉你，Gray码的第n个数（从0算起）是n xor (n shr 1)，你能想出来这是为什么吗？先自己想想吧。
下面我们把二进制数和Gray码都写在下面，可以看到左边的数异或自身右移的结果就等于右边的数。
二进制数 Gray码
000 000
001 001
010 011
011 010
100 110
101 111
110 101
111 100
从二进制数的角度看，“镜像”位置上的数即是对原数进行not运算后的结果。比如，第3个数010和倒数第3个数101的每一位都正好相反。假设这两个数分别为x和y，那么x xor (x shr 1)和y xor (y shr 1)的结果只有一点不同：后者的首位是1，前者的首位是0。而这正好是Gray码的生成方法。这就说明了，Gray码的第n个数确实是n xor (n shr 1)。
今年四月份mashuo给我看了这道题，是二维意义上的Gray码。题目大意是说，把0到2^(n+m)-1的数写成2^n * 2^m的矩阵，使得位置相邻两数的二进制表示只有一位之差。答案其实很简单，所有数都是由m位的Gray码和n位Gray码拼接而成，需要用左移操作
和or运算完成。完整的代码如下：
复制内容到剪贴板
var
x,y,m,n,u:longint;
begin
readln(m,n);
for x:=0 to 1 shl m-1 do begin
u:=(x xor (x shr 1)) shl n; //输出数的左边是一个m位的Gray码
for y:=0 to 1 shl n-1 do
write(u or (y xor (y shr 1)),' '); //并上一个n位Gray码
writeln;
end;
end.
acm竞赛位运算简介及实用技巧~
位运算简介及实用技巧 转载者注：最近在论坛上看到些十分空虚、空大的帖子。觉得编程还是要讲点实践，实践出真知。 众所周知，人和电脑处理的方式究竟还是不同的，否则人人都是计算机程序员了。有些东西对人说很容易，而对计算机来说很难，反之亦然。 位操作就是人和电脑处理方式不同的体现，有些人认为这个东西有些BT，但其实非常高效的程序大多都是用位操作优化，因为它十分底层，速度极快。其实位操作也有他自己独特的性质，只要我们能熟练得掌握，就可以更好得驾驭我们的程序，这也是我转此帖的目的。 PS：不要把注意力集中在语言上，所有语言都是一样的，只是工具而已。 去年年底写的关于位运算的日志是这个Blog里少数大受欢迎的文章之一，很多人都希望我能不断完善那篇文章。后来我看到了不少其它的资料，学习到了更多关于位运算的知识，有了重新整理位运算技巧的想法。从今天起我就开始写这一系列位运算讲解文章，与其说是原来那篇文章的follow-up，不如说是一个remake。当然首先我还是从最基础的东西说起。 什么是位运算？
程序中的所有数在计算机内存中都是以二进制的形式储存的。位运算说穿了，就是直接对整数在内存中的二进制位进行操作。比如，and运算本来是一个逻辑运算符，但整数与整数之间也可以进行and 运算。举个例子，6的二进制是110，11的二进制是1011，那么6 and 11的结果就是2，它是二进制对应位进行逻辑运算的结果（0表示False，1表示True，空位都当0处理）： 110 AND 1011 ---------- 0010 --> 2 由于位运算直接对内存数据进行操作，不需要转成十进制，因此处理速度非常快。当然有人会说，这个快了有什么用，计算6 and 11没有什么实际意义啊。这一系列的文章就将告诉你，位运算到底可以干什么，有些什么经典应用，以及如何用位运算优化你的程序。 Pascal和C中的位运算符号 下面的a和b都是整数类型，则： C语言 | Pascal语言 -------+------------- a & b | a and b a | b | a or b
ACM经典算法及配套练习题
POJ上的一些水题(可用来练手和增加自信) (poj3299,poj2159,poj2739,poj1083,poj2262,poj1503,poj3006,p oj2255,poj3094) 初期: 一.基本算法: (1)枚举. (poj1753,poj2965) (2)贪心(poj1328,poj2109,poj2586) (3)递归和分治法. (4)递推. (5)构造法.(poj3295) (6)模拟法.(poj1068,poj2632,poj1573,poj2993,poj2996) 二.图算法: (1)图的深度优先遍历和广度优先遍历. (2)最短路径算法(dijkstra,bellman-ford,floyd,heap+dijkstra) (poj1860,poj3259,poj1062,poj2253,poj1125,poj2240) (3)最小生成树算法(prim,kruskal) (poj1789,poj2485,poj1258,poj3026) (4)拓扑排序(poj1094) (5)二分图的最大匹配(匈牙利算法) (poj3041,poj3020) (6)最大流的增广路算法(KM算法). (poj1459,poj3436) 三.数据结构. (1)串(poj1035,poj3080,poj1936) (2)排序(快排、归并排(与逆序数有关)、堆排) (poj2388,poj2299) (3)简单并查集的应用. (4)哈希表和二分查找等高效查找法(数的Hash,串的Hash) (poj3349,poj3274,POJ2151,poj1840,poj2002,poj2503) (5)哈夫曼树(poj3253) (6)堆 (7)trie树(静态建树、动态建树) (poj2513) 四.简单搜索 (1)深度优先搜索(poj2488,poj3083,poj3009,poj1321,poj2251) (2)广度优先搜索(poj3278,poj1426,poj3126,poj3087.poj3414) (3)简单搜索技巧和剪枝(poj2531,poj1416,poj2676,1129) 五.动态规划 (1)背包问题. (poj1837,poj1276) (2)型如下表的简单DP(可参考lrj的书page149): 1.E[j]=opt{D+w(i,j)} (poj3267,poj1836,poj1260,poj2533) 2.E[i,j]=opt{D[i-1,j]+xi,D[i,j-1]+yj,D[i-1][j-1]+zij} (最长公共子序列) (poj3176,poj1080,poj1159) 3.C[i,j]=w[i,j]+opt{C[i,k-1]+C[k,j]}.(最优二分检索树问题) 六.数学 (1)组合数学:
(2020年编辑)ACM必做50题的解题-数论
poj 1061 青蛙的约会 这题用的是解线性同余方程的方法，之前没接触到过，搜索资料后看到一个人的博客里面讲的很好就拷贝过来了。内容如下： 对于方程：ax≡b(mod m)，a，b，m都是整数，求解x 的值，这个就是线性同余方程。符号说明： mod表示：取模运算 ax≡b(mod m)表示：(ax - b) mod m = 0，即同余 gcd(a,b)表示：a和b的最大公约数 求解ax≡b(mod n)的原理：对于方程ax≡b(mod n)，存在ax + by = gcd(a,b)，x，y是整数。而ax≡b(mod n)的解可以由x，y来堆砌。具体做法如下： 第一个问题：求解gcd(a,b) 定理一：gcd(a,b) = gcd(b,a mod b) 欧几里德算法 int Euclid(int a,int b) { if(b == 0) return a; else return Euclid(b,mod(a,b)); } 附：取模运算 int mod(int a,int b) { if(a >= 0) return a % b; else return a % b + b; } 第二个问题：求解ax + by = gcd(a,b) 定理二：ax + by = gcd(a,b)= gcd(b,a mod b) = b * x' + (a mod b) * y' = b * x' + (a - a / b * b) * y' = a * y' + b * (x' - a / b * y') = a * x + b * y 则：x = y' y = x' - a / b * y' 以上内容转自https://www.wendangku.net/doc/b88103095.html,/redcastle/blog/item/934b232dbc40d336349bf7e4.html
实验五SRIM程序使用指南
实验五 SRIM计算重离子在材料中的剂量分布 一、实习目的和要求 （一）实习目的： 1、熟悉SRIM程序的基本使用方法，以及在辐射剂量和防护计算中的应用。 2、通过此程序仿真模拟重带电粒子入核的过程，获得离子在材料中的剂量分布。 3、通过进一步自学，利用SRIM程序解决实际工作中的碰到的一些实际问题。 （二）实习要求： 1、掌握SRIM软件的基本组成、操作方法； 2、利用SRIM对离子在不同物质中的射程进行计算分析； 3、对质子在不同固体靶中的径迹及剂量分布进行简单的计算，并对计算结果进行分析并绘图，得出结论。 二、SRIM程序简介 1、SRIM软件介绍 SRIM是模拟计算离子在靶材中能量损失和分布的程序组。它采用Monte Carlo方法，利用计算机模拟跟踪一大批入射粒子的运动。粒子的位置、能量损失以及次级粒子的各种参数都在整个跟踪过程中存储下来，最后得到各种所需物理量的期望值和相应的统计误差。该软件可以选择特定的入射离子及靶材种类，并可设置合适的加速电压。可以算不同粒子，以不同的能量，从不同的位置，以不同的角度入射到靶中的情况。SRIM中包含一个TRIM运算软件。 TRIM（Transport of Ions in Matter）是一个非常复杂的程序。它不仅可以描述离子在物质中的射程，还可以详细计算注入离子在慢化过程中对靶产生损伤等其他信息。它可以使用动画让你看到离子注入到靶中的全过程，并给你展示级联反冲粒子和靶原子混合在一起的情形。为了精确估计每个离子和靶原子间相遇时的物理情形，程序只能一次对一个粒子进行计算。这样的话，计算可能消耗可观的时间——计算每个离子花费的时间从一秒到几分钟不等。而精确度由模拟采用的离子数来决定。典型的情况是，应用1000个离子进行计算将得到好于10%的精确度。 软件特点：
ARCGIS教程：图斑整理之字段计算器使用技巧
ArcGIS教程：图斑整理之字段计算器使用技巧 1.字段计算器简介 在数据整理过程中经常要用到对属性表的处理，即为字段进行赋值或运算。字段计算器(Field Calculator)是一个强大的处理字段值的工具，不仅可以实现快速批量赋值，还支持Python和VBScript，可以通过代码进行复杂条件的赋值工作，并且字段计算器还可以在Model Builder中调用，构建空间模型。 在某个属性字段的右键菜单中即可调出字段计算器，在该界面中即可对该字段进行统一批量赋值，如果勾选Show Codeblock可以编写代码实现条件赋值、复杂计算或是几何体的计算。下面我们就以国土行业的图斑数据整理为例，看看灵活而强大字段计算器是如何应用的。 2.应用实例 已有的图斑数据的属性表如下，两个字段分别代表二级地类的编码(DLBM)和名称(DLMC)。 截取拼接字符串 问题描述：从已有的DLBM(二级地类编码)中提取一级地类的编码，由于前两位即是一级地类编码，我们可以通过字符串的截取来实现 解决方法：创建字段YJDL，在字段计算器内选择Python，输入!DLBM![0:2] 注：Python中对字符串的处理非常简单，直接通过下标位置的索引来提取，拼接字符串则可使用加号来连接字段即可。
条件赋值 问题描述：根据一级地类的代码为其增加具体描述信息 解决方法：创建字段YJDLMC(一级地类名称)，勾选Show Codeblock，根据YJDL的代码为其赋值，在YJDLMC=下面输入CalDLMC(!YJDL!)，在上面的Pre-Logic Script Code空白处输入代码如下： def CalDLMC(code): if(code==’01’): return“耕地” elif(code==’02’): return“园地” else: return“” 为重复记录进行编号 问题描述：将同一地类图斑自动编号(标记重复记录)，例如根据DLBM字段，把具有相同值的记录标出来，并且按照从小到大的排序自动增加一个编号，实现如下效果： 解决方法：增加DLCOUNT字段，计算每种用地类型有多少块，即同类型的DLBM按顺序从1开始赋值，勾选ShowCodeblock，编写代码： UniqueDict={} defisDuplicateIndex(inValue): UniqueDict.setdefault(inValue,0) UniqueDict[inValue]+=1 return str(UniqueDict[inValue]) 计算几何体信息 计算图斑面积：!Shape.Area! 质心X坐标：!Shape.CENTROID.X! 质心Y坐标：!Shape.CENTROID.Y! 字段间运算 在上一步计算得到的面积基础上进行单位转换，如将平方米转换为平方公里 !Area!/1000000 顺序赋值，即为每条记录进行唯一值编号
集成运算放大器的应用实验报告
集成运算放大器的应用实验报告 一、实验目的 1. 了解运算放大器的特性和基本运算电路的组成； 2. 掌握运算电路的参数计算和性能测试方法。 二、实验仪器及器件 1 .数字示波器； 2. 直流稳压电源； 3. 函数信号发生器； 4. 数字电路实验箱或实验电路板； 5. 数字万用表； 6. 集成电路芯片UA741 2块、电容个，各个阻值的电阻若干个。 三、实验内容 1、在面包板上搭接卩A741的电路。首先将+12V和-12V直流电压正确接入卩A741的Vcc+（7脚）和Vcc- （4脚）。 2、用卩A741组成反比例放大电路，放大倍数自定，用示波器观察输入和输出波形，测量放大器的电压放大倍数。 3、用卩A741组成积分电路，用示波器观察输入和输出波形，并做好记录。 四、实验原理 （1）集成运放简介 集成电路运算放大器（简称集成运放或运放）是一个集成的高
增益直接耦合放大器，通过外接反馈网络可构成 各种运算放大电路和 其它应用电路。集成运放uA741 的 引脚图下图所示 uA741电路符号及引脚图 任何一个集成运放都有两个输入端，一个输出端以及正、负电源端，有的品种还有补偿端和调零端等。 (a)电源端：通常由正、负双电源供电，典型电源电压为土15V、±12V等。如：uA741的7脚和4脚。 (b)输出端：只有一个输出端。在输出端和地(正、负电源公共端) 之间获得输出电压。如：uA741的6脚。最大输出电压受运放所接电源的电压大小限制，一般比电源电压低1?2V;输出电压的正负也受电源极性的限制；在允许输出电流条件下，负载变化时输出电压几乎不变。这表明集成运放的输出电阻很小，带负载能力较强。 (c)输入端：分别为同相输入端和反相输入端。如：uA741的3脚和2脚。输入端有两个参数需要注意：最大差模输入电压V id max和最大共模输入电压V ic max 。 两输入端电位差称为“差模输入电压” V id ：V id V V 。两输入端电 位的平均值，称为“共模输入电压”V ic ： 任何一个集成运放，允许承受的V d max和V c max都有一定限制。两输入端的输入电流i + 和i - 很小，通常小于1?A ，所以集成运放的输入电阻很大。 (2)集成运放的主要参数
ACM必做50题——数学
1、POJ 2249 Binomial Showdown 组合数学。 高精度，也可把分子分母的数组进行两两约分 #include
有一个溢出问题；比如64位全是p的序列，那么max会溢出，值为-1；同理min在全是n 时也会溢出，为1；显然是max>=0,min<=1,溢出时产生异常，依次可以判断； ②是否是最大限和最小限之间的数都能表示呢？ 都可以，而且能够表示的数是2^k个，这个原始2进制是一样的；因为每个位上要么是0，要么是1，而且每个位上的权重唯一的，不能通过其他位的01组合获得；最后，我们就可以仿照原始二进制来算在类2进制下的表示；不断求N的二进制最后一位和右移；如果取余是1，则该位上一定是1，如果该位对于字母为‘n’，则高位应该再加1；这里对2取余可能会出错，因为对于负数，补码的表示，最后一位一定是和原码一样的每次的右移后(有时需先加1）补码表示正好符合要求（可找实例验证）； #include
ArcGis的拓扑关系运算功能介绍
ArcGis的拓扑关系运算功能介绍 ArcGISEngine将拓扑关系运算功能函数方法封装在ITopologicalOperator接口，以便进行拓扑关系运算。 属性：Boundary Boundary:几何图形的边界属性。面的边界是多条折线；线的边界是与起始终止点相一致的多点；多点边界是空对象。
属性：IsKnownSimple IsKnownSimple：如当前几何图形是简单对象返回true，否则返回false；它反映了图形是否进行了拓扑纠正。 下面情况返回False u 新创建的非空对象 u 图形经过投影、一般化处理 下面情况返回True u 空几何对象 u 直接从要素类中获得的 u 执行过ITopologicalOperator接口方法后得到的几何图形 属性：IsSimple IsSimple:当图形还没被认定为简单对象，返回是否已经进行拓扑纠正。可调用Simply方法强制修正。 方法：Buffer Buffer：根据指定的几何图形生成缓冲区，返回Polygon对象。缓冲区的距离
Distance可以为“正”，也可以为“负”；为负数时，只适用于Polygon对象生成缓冲区。缓冲区的距离单位与生成缓冲区源几何图形坐标单位一致。 方法：Clip Clip：裁剪指定区域内的图形。 方法：ClipDense ClipDense：裁剪指定区域内的图形 方法：ConstructUnion ConstructUnion：合并一组几何图形同时创建一个新的对象 方法：ConvexHull ConvexHull：创建一个能够包含一组图形的最小边界多边形
方法：Cut Cut：分割一个几何图形（线、面）为左右两部分（相对于分割线来说）。 ITopologicalOperator.Cut(splitLine, sleftGeom, srightGeom); 分割线绘制的方向决定了被分割后的对象属于左边还是右边。如下图所示，分割线至上而下将图形分割为左、右两部分，所以原图形的左半部分是作为结果的右边对象返回的。 当几何图形与分割线没有相交时，几何图形将作为右边部分返回，左边部分为空。 方法：Difference Difference：获得原始图形除去相交部分之外的图形部分。
CMOS运算放大器设计毕业设计
目录 摘要 (5) Abstract (6) 0 文献综述 (6) 0.1 集成电路概述 (7) 0.2 集成电路的发展 (7) 0.3 集成电路应用领域 (8) 0.4 CMOS集成电路 (11) 0.5 运算放大器 (11) 0.6 CMOS运算放大器 (12) 1 引言 (13) 1.1 运算放大器简介 (13) 1.2 本文研究内容 (14) 2 CMOS运算放大器 (14) 2.1 CMOS运算放大器简介 (14) 2.2 CMOS运算放大器的设计流程 (14) 3 CMOS运算放大器电路设计 (15) 3.1 电路的PSpice模拟及理论计算 (15) 3.2 电路结构分析及参数调试 (17) 3.3 电路仿真 (17) 4 CMOS 运算放大器版图设计 (27) 4.1 版图设计流程 (27) 4.2 工艺设计规则 (28) 4.3 单元器件的绘制——图元 (29) 4.4 CMOS放大器的版图设计 (34) 4.5 T-Spice仿真 (37) 5 总结 (41) 参考文献 (42)
致谢 (44)
毕业设计（论文）原创性声明和使用授权说明 原创性声明 本人郑重承诺：所呈交的毕业设计（论文），是我个人在指导教师的指导下进行的研究工作及取得的成果。尽我所知，除文中特别加以标注和致谢的地方外，不包含其他人或组织已经发表或公布过的研究成果，也不包含我为获得及其它教育机构的学位或学历而使用过的材料。对本研究提供过帮助和做出过贡献的个人或集体，均已在文中作了明确的说明并表示了谢意。 作者签名：日期： 指导教师签名：日期： 使用授权说明 本人完全了解大学关于收集、保存、使用毕业设计（论文）的规定，即：按照学校要求提交毕业设计（论文）的印刷本和电子版本；学校有权保存毕业设计（论文）的印刷本和电子版，并提供目录检索与阅览服务；学校可以采用影印、缩印、数字化或其它复制手段保存论文；在不以赢利为目的前提下，学校可以公布论文的部分或全部内容。 作者签名：日期：
ACM数论方面十道基础题目详解
1、公约数和公倍数 https://www.wendangku.net/doc/b88103095.html,/JudgeOnline/problem.php?pid=40 这道题目是非常基础的题目，在学习了欧几里德算法之后，应该很好就能做的出来了。注意两个数的最小公倍数和最大公约数之间有关系为： a*b=gcd(a,b)*lcm(a,b); 代码如下： #include ?????≡≡≡)33(mod ) 28(mod )23(mod d n e n p n 那么找到k1、k2、k3满足： k1：k1%23==0&&k1%28==0&&k1%33==1 k2：k2%33==0&&k2%28==0&&k2%23==1 k3：k3%33==0&&k3%23==0&&k3%28==1 则n=k2*p+k3*e+k1*i+k*21252； 代码如下： #include 数论50题 1．由1，3，4，5，7，8这六个数字所组成的六位数中，能被11整除的最大的数是多少？ 【分析】各位数字和为1+3+4+5+7+8=28 所以偶数位和奇数位上数字和均为14 为了使得该数最大，首位必须是8，第2位是7，14-8=6 那么第3位一定是5，第5位为1 该数最大为875413。 2．请用1，2，5，7，8，9这六个数字（每个数字至多用一次）来组成一个五位数，使得它能被75整除，并求出这样的五位数有几个？ 【分析】75=3×25 若被3整除，则各位数字和是3的倍数，1+2+5+7+8+9=32 所以应该去掉一个被3除余2的，因此要么去掉2要么去掉8 先任给一个去掉8的，17925即满足要求 1）若去掉8 则末2位要么是25要么是75，前3位则任意排，有3！=6种排法 因此若去掉8则有2*6=12个满足要求的数 2）若去掉2 则末2位只能是75，前3位任意排，有6种排法 所以有6个满足要求 综上所述，满足要求的五位数有18个。 3．已知道六位数20□279是13的倍数，求□中的数字是几？ 【分析】根据被13整除的判别方法，用末三位减去前面的部分得到一个两位数，十位是7，个位是（9-□），它应该是13的倍数，因为13|78,所以9-□=8 □中的数字是1 4．某自然数，它可以表示成9个连续自然数的和，又可以表示成10个连续自然数的和，还可以表示成11个连续自然数的和，那么符合以上条件的最小自然数是？（2005全国小学数学奥赛） 【分析】可以表示成连续9个自然数的和说明该数能被9整除，可以表示成连续10个自然数的和说明该数能被5整除，可表示成连续11个自然数的和说明该数能被11整除 因此该数是[9,5,11]=495，因此符合条件的最小自然数是495。 5．一次考试中，某班同学有考了优秀，考了良好，考了及格，剩下的人不及格，已知该班同学的人数不超过50，求有多少人不及格？ 【分析】乍一看这应该是一个分数应用题，但实际上用到的却是数论的知识，由于人数必须是整数，所以该班同学的人数必须同时是2，3，7的倍数，也就是42的倍数，又因为人数不超过50，所以只能是42人，因此不及格的人数为（1---）×42=1人 6．（1）从1到3998这3998个自然数中，有多少个能被4整除？ （2）从1到3998这3998个自然数中，有多少个数的各位数字之和能被4整除？ （第14届迎春杯考题） 【分析】（1）3998/4=999….6所以1-3998中有996个能被4整除的 （2）考虑数字和，如果一个一个找规律我们会发现规律是不存在的 因此我们考虑分组的方法 我们补充2个数，0000和3999，此外所有的一位两位三位数都在前面加上0补足4位 然后对这4000个数做如下分组 国库集中支付系统3.0 ( 预算单位) 操 作 手 册 黄石市财政局 目录 第一部分背景介绍 (3) 第二部分初始安装 (4) 1. 配置软件安装 (4) 第三部分预算单位简明操作手册 (6) 1．系统初始登陆 (6) 1.1用户登录 (6) 1.2单位用户名和密码修改 (8) 1.3基础信息管理 (9) 2．单位集中支付操作说明 (11) 概述 (11) 2.1单位用户、岗位一览表 (11) 2.2系统业务操作页面介绍 (11) 2.3用款计划录入 (11) 2.4单位用款计划审核 (15) 2.5用款申请录入 (19) 2.6直接支付申请上报单生成/打印 (24) 2.7授权支付申请审核 (28) 2.8授权支付凭证生成/打印 (29) 3．公务卡支付操作说明 (31) 3.1公务卡持卡人信息维护 (31) 3.2确认公务卡报销 (31) 3.3公务卡支付申请生成 (33) 3.4审核公务卡支付申请 (35) 3.5公务卡支付凭证生成 (35) 3.6公务卡支付凭证打印 (36) 第一部分背景介绍 伴随财政国库集中支付改革的进一步深入，原有集中支付管理系统2.0在技术架构、业务承载力等等因素上，已渐渐不能满足财政科学化、精细化管理的要求，2010年湖北省财政厅进行了多次需求调研，召开业务讨论会，集思广益，经过近一年的周密部署，国库集中支付管理系统3.0应运而生。 本次3.0系统升级不仅涵盖了原有2.0系统中所有资金支付业务，并拓展了单位实有资金支付业务等，整体业务流程主体基本参照、延用原有2.0系统设置，存在冗余的地方进行了简化，达到方便预算单位系统操作，简化业务办理流程，提高单位和财政的信息互动，高效办公的目的。 站在预算单位的角度来看，3.0系统主要变化概括如下： 1）将预算单位所用资金纳入系统进行管理 2）系统采用C/S/S架构，单位无需安装客户端软件，直接通过IE浏览器访问财政应用服务器，登陆后便可以办理本单位支付业务。 3）取消预算单位客户端数据库，所有业务数据全部纳入财政数据库管理。 详细的业务操作方法请看后面章节。 断断续续的学习数论已经有一段时间了，学得也很杂，现在进行一些简单的回顾和总结。学过的东西不能忘啊。。。 1、本原勾股数： 概念：一个三元组(a,b,c)，其中a,b,c没有公因数而且满足：a^2+b^2=c^2 首先，这种本原勾股数的个数是无限的，而且构造的条件满足： a=s*t,b=(s^2-t^2)/2,c=(s^2+t^2)/2 其中s>t>=1是任意没有公因数的奇数！ 由以上概念就可以导出任意一个本原勾股数组。 2、素数计数（素数定理） 令π(x)为1到x中素数的个数 19世纪最高的数论成就就是以下这个玩意儿： lim(x->∞){π(x)/(x/ln(x))}=1 数论最高成就，最高成就！！！有木有！！！ 3、哥德巴赫猜想(1+1) 一个大偶数(>=4)必然可以拆分为两个素数的和，虽然目前还没有人能够从理论上进行证明，不过我根据科学家们利用计算机运算的结果，如果有一个偶数不能进行拆分，那么这个偶数至少是一个上百位的数！！ 所以在ACM的世界中（数据量往往只有2^63以下）哥德巴赫猜想是成立的！！所以拆分程序一定能够实现的 4、哥德巴赫猜想的推广 任意一个>=8的整数一定能够拆分为四个素数的和 证明： 先来说8=2+2+2+2，（四个最小素数的和）不能再找到比2小的素数了，所以当n小于8，就一定不可能拆分为四个素数的和！ 那么当n大于等于8，可以分情况讨论： （1）n&1==0(n为偶数)，那么n就一定可以拆分为两个偶数的和 那么根据哥德巴赫猜想，偶数可以拆分为两个素数的和，于是，n一定可以拆分为四个素数的和 （2）n&1==1(n为奇数)，n一定可以拆分为两个偶数+1 由于有一个素数又是偶数，2，那么奇数一定有如下拆分：2+3+素数+素数 得证。 ACM入门之新手入门 1.ACM国际大学生程序设计竞赛简介 1)背景与历史 1970年在美国T exasA&M大学举办了首次区域竞赛，从而拉开了国际大学生程序设计竞赛的序幕。1977年，该项竞赛被分为两个级别：区域赛和总决赛，这便是现代ACM竞赛的开始。在亚洲、美国、欧洲、太平洋地区均设有区域赛点。1995至1996年，来自世界各地的一千多支s代表队参加了ACM区域竞赛。ACM大学生程序设计竞赛由美国计算机协会（ACM）举办，旨在向全世界的大学生提供一个展示和锻炼其解决问题和运用计算机能力的机会，现已成为全世界范围内历史最悠久、规模最大的大学生程序设计竞赛。 2)竞赛组织 竞赛在由各高等院校派出的3人一组的队伍间进行，分两个级别。参赛队应首先参加每年9月至11月在世界各地举行的“区域竞赛(Regional Contest)”。各区域竞赛得分最高的队伍自动进入第二年3月在美国举行的“总决赛(Final Contest)”，其它的高分队伍也有可能被邀请参加决赛。每个学校有一名教师主管队伍，称为“领队”(faculty advisor)，他负责选手的资格认定并指定或自己担任该队的教练(coach)。每支队伍最多由三名选手(contestant)组成，每个选手必须是正在主管学校攻读学位的学生。每支队伍最多允许有一名选手具有学士学位，已经参加两次决赛的选手不得再参加区域竞赛。 3)竞赛形式与评分办法 竞赛进行5个小时，一般有6~8道试题，由同队的三名选手使用同一台计算机协作完成。当解决了一道试题之后，将其提交给评委，由评委判断其是否正确。若提交的程序运行不正确，则该程序将被退回给参赛队，参赛队可以进行修改后再一次提交该问题。 程序运行不正确是指出现以下4种情况之一： (1)运行出错(run-time error)； (2)运行超时〔time-limit exceeded〕； (3)运行结果错误(wrong answer)； (4)运行结果输出格式错误(presentation error)。 竞赛结束后，参赛各队以解出问题的多少进行排名，若解出问题数相同，按照总用时的长短排名。总用时为每个解决了的问题所用时间之和。一个解决了的问题所用的时间是竞赛开始到提交被接受的时间加上该问题的罚时(每次提交通不过，罚时20分钟)。没有解决的问题不记时。美国英语为竞赛的工作语言。竞赛的所有书面材料(包括试题)将用美国英语写出，区域竞赛中可以使用其它语言。总决赛可以使用的程序设计语言包括PASCAL，C，C++及Java，也可以使用其它语言。具体的操作系统及语言版本各年有所不同。 4)竞赛奖励情况 总决赛前十名的队伍将得到高额奖学金：第一名奖金为12000美元，第二名奖金为 6000美元，第三名奖金为3000美元，第四名至第十名将各得到l500美元。除此之外还将承认北美冠军、欧洲冠军、南太平洋冠军及亚洲冠军。 2.ACM竞赛需要的知识 语言是最重要的基本功 无论侧重于什么方面，只要是通过计算机程序去最终实现的竞赛，语言都是大家要过的第一道关。亚洲赛区的比赛支持的语言包括C/C++与JAVA。首先说说JAVA，众所周知，作为面向对象的王牌语言，JAVA在大型工程的组织与安全性方面有着自己独特的优势，但是对于信息学比赛的具体场合，JAVA则显得不那么合适，它对于输入输出流的操作相比于C++要繁杂很多，更为重要的是JAVA程序的运行速度要比C++慢10倍以上，而竞赛中对于JAVA程序的运行时限却往往得不到同等比例的放宽，这无疑对算法设计提出了更高的要求，是相当 ACM部分习题答案： A + B Problem Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others) Total Submission(s): 100972 Accepted Submission(s): 33404 Problem Description Calculate A + B. Input Each line will contain two integers A and B. Process to end of file. Output For each case, output A + B in one line. Sample Input 1 1 Sample Output 2 # include LM741/UA741运算放大器使用说明及应用 物理量的感测在一般应用中，经常使用各类传感器将位移、角度、压力、与流量等物理量转换为电流或电压信号，之后再由量测此电压电流信号间接推算出物理量变化，以达成感测、控制的目的。但有时传感器所输出的电压电流信号可能非常微小，以致信号处理时难以察觉其间的变化，故需要以放大器进行信号放大以顺利测得电流电压信号，而放大器所能达成的工作不仅是放大信号而已，尚能应用于缓冲隔离、准位转换、阻抗匹配、以及将电压转换为电流或电流转换为电压等用途。现今放大器种类繁多，一般仍以运算放大器(Operational Amplifier, Op Amp)应用较为广泛，本文即针对741运算放大器的使用加以说明。 1. 运算放大器简介ab126计算公式大全 放大器最初被开发的目的是运用于类比计算器之运算电路，其内部为复杂的集成电路(Integrated Circuit, IC)，亦即在单一电子组件中整合了许多晶体管与二极管，图1为一般放大器之内部等值电路。 1. 运算放大器内部等值电路图 运算放大器属于使用反馈电路进行运算的高放大倍率型放大器，其放大倍率完全由外界组件所控制，透过外接电路或电阻的搭配，即可决定增益（即放大倍率）大小。图2为运算放大器于电路中的表示符号，可看出其包含两个输入端，其中（＋）端为非反相(Non-Inverting)端，而（－）端称为反相(Inverting)端，运算放大器的作动与此二输入端差值有关，此差值称为「差动输入」。通常放大器的理想增益为无穷大，实际使用时亦往往相当高（可放大至105或106倍），故差动输入跟增益后输出比较起来几乎等于零。838电子 -北大poj acm题目推荐50题 POJ == 北京大学ACM在线评测系统https://www.wendangku.net/doc/b88103095.html,/JudgeOnline 1. 标记难和稍难的题目大家可以看看，思考一下，不做要求，当然有能力的同学可以直接切掉。 2. 标记为A and B 的题目是比较相似的题目，建议大家两个一起做，可以对比总结，且二者算作一个题目。 3. 列表中大约有70个题目。大家选做其中的50道，且每类题目有最低数量限制。 4. 这里不少题目在BUPT ACM FTP 上面都有代码，请大家合理利用资源。 5. 50个题目要求每个题目都要写总结，养成良好的习惯。 6. 这50道题的规定是我们的建议，如果大家有自己的想法请与我们Email 联系。 7. 建议使用C++ 的同学在POJ 上用G++ 提交。 8. 形成自己编写代码的风格，至少看上去美观，思路清晰(好的代码可以很清楚反映出解题思路)。 9. 这个列表的目的在于让大家对各个方面的算法有个了解，也许要求有些苛刻，教条，请大家谅解，这些是我们这些年的经验总结，所以也请 大家尊重我们的劳动成果。 10. 提交要求：一个总文件夹名为bupt0xx (即你的比赛帐号), 这个文件夹内有各个题目类别的子目录(文件夹)，将相应的解题报告放入对应 类别的文件夹。在本学期期末，小学期开始前，将该文件夹的压缩包发至buptacm@https://www.wendangku.net/doc/b88103095.html,。 对于每个题目只要求一个POJxxxx.cpp 或POJxxxx.java (xxxx表示POJ该题题号) 的文件，注意不要加入整个project 。 11. 如果有同学很早做完了要求的题目，请尽快和我们联系，我们将指导下一步的训练。 下面是一个解题报告的范例： 例如：POJ1000.cpp NE5532： 确实有点胆味，解析力一般，高频比较燥，低频比较糊且肥。价廉物美足已弥补一切! op275: 和5532比，胆性还重一点，解析力、低频、音场更好一点，可以买贴片的来打磨声卡用（特别是创新的），可以改善硬冷的数码声。 EL2244： 音色中性，音场比较宽，高频还可以，中频音乐味差，有人说解析力很高，其实是因为低频量感少，中频薄，高频显得突出而已。要用好比较难。 LT1057： 两端延伸不错，速度、动态和解析力也挺好，就是属冷色调，放出的音乐好象有种不食人间烟火的味道，让你可以静静的听，却燃不起对音乐的那份激情。 AD827： 延伸非常好，解析力高，高频华丽，中频纯厚，低频下潜和力度都不错，音场向前后左右拓展，有了凹凸感（这一点比其它运放强），速度快，动态好，感觉很大气，初换上此运放后确实有让人为之一振的感觉。但久听之下，也发现很多问题，1虽然三频段、音场很宽，气势足，大开大合，但总感觉结构有点松，不够紧溱，2人声部份一般，有时大动态时，人声被配乐声淹没3不够细腻，属于激情有余而柔情不足，4音乐味不够。不过很多的人喜欢这种风格。当然买两片来换换口味听还是可以的，按我的感觉，用在A V功放上看DVD大片应该很适合。 OPA2604： 感觉象5532的升级版，各方面都有很大提高，解析力不错，音乐味更好，有胆味，声底属于较纯厚且有点刚性，综合素质很不错。 DY649： 和2604比，解析力更好，高频部份纤细而又柔美且泛音丰富，声底没2604厚，很清澈、细致的感觉，音乐画面异常清晰，人声部份圆润通透、有种甜甜的感觉，人声（特别是女声）是它的强项。 DY639： 整体性稍弱于649，但更具备胆机特性，胆味更浓。 DY669： 和2604差不太多，纯厚的声音。 AD712： 解析力很好，清晰而又没有音染的声音，一种很透明的感觉，声底细致，低频量稍少。属于典型的监听风格。不过可能很多人都不大喜欢这种纯净水的感觉，还是加点味精好，大概是我比较喜欢听纯人声音乐的原因吧，习惯了这种纯纯的监听味道，挺感兴趣。 AD712（金封）： 一时好奇，第二天又去弄了个金封的，和陶封比，感觉解析力更好，声底更纯厚点，低频弹跳感下潜度都有所加强，音场定位感不错。...刚开始听时感觉好象人声清淅度还不如陶封的，吃了一惊，后来反复比较才发现，因为陶封的高频比较冲、直白、声底薄，人声显得亮，所以有这种感觉，还是金封的耐听度更高。不过，不太推荐使用，因为现在金封的找不到拆机件了，只有买全新的，要75元，这个价位可以买到更好的型号了。 AD797： 值得试试的东东，人声很亲切，在朋友家测完后立刻被扣下来了。拆机件45元 AD828AR： AD设计制造的高性能运放AD828AR，性能指标比著名的发烧运放AD827JN更好。音质全数论50题
国库集中支付系统3.0预算单位操作技巧介绍材料
数论
ACM入门之新手入门
ACM部分练习题目答案
741运算放大器
北大 poj acm题目推荐50题
各种运放简介