博文
位操作技巧(2005-12-23 10:45:00)
摘要：
检测一个无符号数是不为2^n-1(^为幂)： x&(x+1)
将最右侧0位改为1位： x | (x+1)
二进制补码运算公式：
-x = ~x + 1 = ~(x-1)
~x = -x-1
-(~x) = x+1
~(-x) = x-1
x+y = x - ~y - 1 = (x|y)+(x&y)
x-y = x + ~y + 1 = (x|~y)-(~x&y)
x^y = (x|y)-(x&y)
x|y = (x&~y)+y
x&y = (~x|y)-~x
x==y: ~(x-y|y-x)
x!=y: x-y|y-x
x< y: (x-y)^((x^y)&((x-y)^x))
x<=y: (x|~y)&((x^y)|~(y-x))
x< y: (~x&y)|((~x|y)&(x-y))//无符号x,y比较
x<=y: (~x|y)&((x^y)|~(y-x))//无符号x,y比较
使用位运算的无分支代码：
计算绝对值
int abs( int x )
{
int y ;
y = x >> 31 ;
return (x^y)-y ;//or: (x+y)^y
}
符号函数：sign(x) = -1, x<0; 0, x == 0 ; 1, x > 0
int sign(int x)
{
return (x>>31) | (unsigned(-x))>>31 ;//x=-2^31时失败(^为幂)
}
三值比较：cmp(x,y) = -1, x<y; ......
寻找必败态 —— 一类博弈问题的快速解法(2005-12-23 10:42:00)
摘要：
博弈是信息学和数学试题中常会出现的一种类型，算法灵活多变是其最大特点，而其中有一类试题更是完全无法用常见的博弈树来进行解答。寻找必败态即为针对此类试题给出一种解题思路。
此类问题一般有如下特点：
1、博弈模型为两人轮流决策的非合作博弈。即两人轮流进行决策，并且两人都使用最优策略来获取胜利。
2、博弈是有限的。即无论两人怎样决策，都会在有限步后决出胜负。
3、公平博弈。即两人进行决策所遵循的规则相同。
&n......
qsort函数应用大全(转)(2005-12-08 09:29:00)
摘要：
七种qsort排序方法
<本文中排序都是采用的从小到大排序>
一、对int类型数组排序
int num[100];
Sample:
int cmp ( const void *a , const void *b )
{
return *(int *)a - *(int *)b;
}
qsort(num,100,sizeof(num[0]),cmp);
二、对char类型数组排序（同int类型）
char word[100];
Sample:
int cmp( const void *a , const void *b )
{
return *(char *)a - *(int *)b;
}
qsort(word,100,sizeof(word[0]),cmp);
三、对double类型数组排序（特别要注意）
double in[100];
int cmp( const void *a , const void *b )
{
return *(double *)a > *(double *)b ? 1 : -1;
}
qsort(in,100,sizeof(in[0]),cmp)；
四、对结构体一级排序
struct In
{
double data;
int other;
}s[100]
//按照data的值从小到大将结构体排序,关于结构体内的排序关键数据data的类型可以很多种，参考上面的例子写
int cmp( const void *a ,const void *b)
{
return (*(In *)a)->data > (*(In *)b)->data ? 1 : -1;
}
qsort(s,100,sizeof(s[0]),cmp);
五、对结构体......
ACM代码总结（续）(2005-10-06 19:41:00)
摘要：20、大数运算处理基本函数
#include
#include
using namespace std;
const int N = 1100;
struct big_num{
int ele[N];
int front;
};
typedef struct big_num bigNum;
void print_bigNum(const bigNum& num)
{
for(int i = num.front; i < N; ++i)
printf("%d", num.ele[i]);
}
void println_bigNum(const bigNum& num)
{
for(int i = num.front; i < N; ++i)
printf("%d", num.ele[i]);
printf("\n");
}
bigNum multi_bigNum(const bigNum& num1, const bigNum& num2)
{
bigNum temp;
bigNum num3;
int i, j, carry;
int temp_int;
num3.front = num1.front + num2.front - N;
for(i =......
ACM代码总结(2005-10-06 19:38:00)
摘要： 经过了一段时间的努力，我再Pku上也算是有了一个阶段性的总结拉，下面是我就这段时间搞ACM来的一些代码的总结，具体的一些题目类型的总结看本Blog的相关文章。
huicpc26 ACM_PKU 代码总结
1、DP（动态规划）
/*1080-HumanGeneFunctions.cpp*/
观察题目给出的一个最优解：
AGTGATG
-GTTA-G
将其从某一处切开，如果左边部分的分值不是最大，那么将其进行调整，使其分值变大，
则整个解分值变大，与已知的最优矛盾。所以左边部分的分值必是最大。
同理，右边也是。可见满足最优子结构的性质。考虑使用DP：
设两个DNA序列分别为s1，s2，长度分别为len1，len2，score为分值表。
f[i,j]表示子串s1[1..i]和s2[1..j]的分值。考虑一个f[i,j]，我们有：
1.s1取第i个字母，s2取“-”：f[i-1,j] + score[s1[i],''-'']
2.s1取“-”，s2取第j个字母：f[i,j-1] + score[''-'',s2[j]]
3.s1取第i个字母，s2取第j个字母：f[i-1,j-1] + score[s1[i],s2[j]]
即f[i,j] = max(f[i-1,j] + score[s1[i],''-''], f[i,j-1] + score[''-'',s2[j]], f[i-1,j-1] + score[s1[i],s2[j]]);
然后考虑边界条件，这道题为i或j为0的情况。
当i=j=0时，即为f[0,0]，这是在计算f[1,1]时用到的，根据f[1,1] = f[0,0] + score[s1[i], s2[j]]，明显有f[0,0] = 0。
当i=0时，即为f[0,1..len2]，有了f[0,0]，可以用f[0,j] = f[0,j-1] + table[''-'',s2[j]]来计算。
当j=0时，即为f[1..len1,0]，有了f[0,0]，可以用f[i,0] = f[i-1,0] +......
zju－1489－2^x mod n = 1(2005-10-06 19:30:00)
摘要：
#include<stdio.h>
int modular(int a,long b,int n)
{
long d,t ;
d=1 ;
t=a ;
while(b>0)
{
if(b%2==1)
d=d*t%n ;
b=b/2 ;
t=t*t%n ;
}
if(d==1)
return 1 ;
else return 0 ;
}
int main()
{
long n ;
long i ;
while(scanf("%ld",&n)!=EOF)
{
if((n%2==0)||(n==1))
{
&nbs......
比赛经验总结(2005-10-06 19:29:00)
摘要：摘录:
在天大，偶参加的比赛可以算是最多的了，说说比赛经验。
可能现在说早了点，需要大家在正式比赛之前再看一遍。
推荐此篇文章打印，与模板放在一起。
1. 比赛中评测会有些慢，偶尔还会碰到隔10分钟以上才返回结果的情况，这段时间不能等结果，必须开工其他题，如果WA，两道题同时做。交完每道题都要先打印。
2. 比赛时发的饭不是让你当时就吃的，那是给你赛后吃的。基本上比赛中前几名的队都没人吃，除非领先很多。
3. 很多选手，尤其是第一次参加比赛的，到一个新环境，全当旅游了，参观的参观，找同学的找同学，玩玩乐乐就把正事抛到脑后了，结果比赛自然没什么好成绩，这样的例子太多了。所以到参赛地后要时刻不忘自己是来比赛的，好好休息、备战。
4. 参赛前一天要睡10个小时以上，非常有助于保持比赛中的精力，很多时候比赛到3个多小时队员就没劲了就是这个原因。前一天晚饭与当天早饭要吃好，理由同上，要知道下顿饭得下午3点赛后才能吃。
5. 到新环境，时刻注意远离疾病，感冒肠炎病不大，却是成绩的天敌。
6. 英语不好，看不懂的，要勤查词典，懒一次就少一道题，远离奖牌。
7. 可以紧张，杜绝慌张，慌张是出题的敌人，任何时候，如果发现自己或者队友出现慌张的情况，提醒深呼吸。
8. 照着纸敲代码和sample数据时不要敲错，特别注意文字信息。
9. 第一道简单题交给队中最稳的人做，万一遇到麻烦也不要慌，如果有很多队都出了就更不必着急了，它必定是简单题，必定是可以很快做出来的，晚几分钟也比罚掉20分好。另外注意不要PE。
10. 最后一小时是出题高峰，谁松懈，谁落后。最后一小时出一道是正常，出两道更好。
以上各条均有出处，每条都包含着以往教训，每条都可能浪费掉你一年的努力，不可小视。
以下各条有些来自于其他学校，有些是总结：
11. 无论是否有人通过，所有题必须全读过，最好每道题都有两人以上读过，尽量杜绝讲题现象。要完全弄清题意，正确的判断出题目的难易，不要想当然。
12. 虽然讨论有助于出题，但是以往每赛区第一名基本都是各自为战，但是互相了解，觉得一道题适合其他人做就转手。
13. 保......
ACM题目分类总结(2005-09-21 02:05:00)
摘要：ACM-题型分类的代码
主流算法：
Ø 1.搜索 //回溯
Ø 2.DP（动态规划）
Ø 3.贪心
Ø 4.图论 //Dijkstra、最小生成树、网络流
Ø 5.数论 //解模线性方程
Ø 6.计算几何 //凸壳、同等安置矩形的并的面积与周长
Ø 7.组合数学 //Polya定理
Ø 8.模拟
Ø 9.数据结构 //并查集、堆
Ø 10.博弈论
1、 排序
1423, 1694, 1723, 1727, 1763, 1788, 1828, 1838, 1840, 2201, 2376, 2377, 2380, 1318, 1877, 1928, 1971, 1974, 1990, 2001, 2002, 2092, 2379,
1002（需要字符处理，排序用快排即可） 1007（稳定的排序） 2159（题意较难懂） 2231 2371（简单排序） 2388（顺序统计算法） 2418（二叉排序树......