Center of Gravity

潇潇枫1987 — 2007-04-27 19:28:00

Center of Gravity Given a sector of radius R, central angle P. You are to calculate the distance between the center of gravity and the center of the circle. InputThere multiple test cases. Each case contains only one line containing 2 real numbers R and P(in radian), representing the radius and central angle of the sector. 0 #include #define PI 3.1415926; int main() { double r,p; double dis; while(scanf("%lf%lf",&r,&p)!=EOF) { p/=2; dis=double(((2.0/3)*r*sin(double(p)))/p); printf("%.6lf\n",dis); } return 0; }

Number lengths

潇潇枫1987 — 2007-04-27 10:57:00

Number lengths N! (N factorial) can be quite irritating and difficult to compute for large values of N. So instead of calculating N!, I want to know how many digits are in it. (Remember that N! = N * (N - 1) * (N - 2) * ... * 2 * 1) Input: Each line of the input will have a single integer N on it 0 < N < 1000000 (1 million). Input is terminated by end of file. Output: For each value of N, print out how many digits are in N!. Sample Input: 1 3 32000 Sample Output: 1 1 130271 /* n!=1*2*3*....*n → lg(n!)=lg(1*2*3*....*n)=lg(1)+lg(2)+ lg(3)+..+lg(n) → n!=10^(lg(1)+lg(2)+ lg(3)+..+lg(n)) */ #include #include using namespace std; int main() { long n,i; double sum; long temp; while(scanf("%d",&n)!=EOF) { sum=0.0;

最大公约数

潇潇枫1987 — 2007-04-17 10:47:00

//求最大公约数int gcd(int a,int b) { if (a%b==0) return b; return gcd(b,a%b);}

洗牌问题

潇潇枫1987 — 2007-04-12 14:09:00

设2n张牌分别标记为1, 2, ..., n, n+1, ..., 2n，初始时这2n张牌按其标号从小到大排列。经一次洗牌后，原来的排列顺序变成n+1, 1, n+2, 2, ..., 2n, n。即前n张牌被放到偶数位置2, 4, ..., 2n，而后n张牌被放到奇数位置1, 3, ..., 2n-1。可以证明对于任何一个自然数n，经过若干次洗牌后可恢复初始状态。现在你的的任务是计算对于给定的n的值(n≤10^5)，最少需要经过多少次洗牌可恢复到初始状态。输入输出格式输入数据由多组数据组成。每组数据仅有一个整数，表示n的值。对于每组数据，输出仅一行包含一个整数，即最少洗牌次数。样例输入10 样例输出6 Original: FZUPC 2005 #include int main(){/*(2＾m)%(2n+1)=1,m即为所求*/ int n,m,temp; int num; while(scanf("%d", &n)!=EOF) { m=1; num=2;temp=n*2; while(num!=1) { if(num<=n)num*=2; else num=num*2-(temp+1); m++; } printf("%d\n", m); } return 0;} /*数论写法：2^m = 1(mod 2n+1)，C语言写法：(2＾m)%(2n+1)=1 解上述方程，m即为所求。*/

分解素因子

潇潇枫1987 — 2007-04-05 12:30:00

分解素因子 Time Limit:1s Memory limit:32M Accepted Submit:227 Total Submit:439 假设x是一个正整数，它的值不超过65535(即1#includeusing namespace std; bool is_prime(int test){ int i; for(i=2;i>data[i]; for(i=0;i

中国剩余定理

潇潇枫1987 — 2007-04-03 21:48:00

我国古代算书《孙子算经》中，有这样一个问题：“今有物不知其数：三三数之剩二，五五数之剩三，七七数之剩二，问物几何．”这个问题一般称孙子问题．这个问题可译成：求被3除余2，被5除余3，被7除余2的最小正整数．《孙子算经》中记载了这个问题的解法，有人将其解法编成歌诀：“三人同行七十稀，五树梅花廿一支，七子团圆正半月，除百零五便得知．”它的意思是用3除的剩余数乘70，用5除的剩余数乘21，用7除的剩余数乘15，将所得的结果相加再减去105的倍数，即可得所求数．算式是2×70＋3×21＋2×15=233，233－105×2＝23，所以，最小的正整数解是23．这种解法，实际上是特殊的一次同余式组的求解定理．1801年，德国数学家高斯在《算术探究》中明确提出一次同余式组的求解定理．西方数学著作中将一次同余式的求解定理称为中国剩余定理．

catalan数在数据结构中的应用

潇潇枫1987 — 2007-04-03 17:28:00

catalan数在数据结构中的应用什么是catalan数？在网上找了n久，各种关于catalan数列的资料都残缺不堪，弄了半天才理解什么是catalan数。所以干脆自己梳理一番。原理：令h(1)＝1，catalan数满足递归式：h(n)= h(1)*h(n-1) + h(2)*h(n-2) + ... + h(n-1)h(1) (其中n>=2)该递推关系的解为：h(n)=c(2n-2,n-1)/n (n=1,2,3,...) 我并不关心其解是怎么求出来的，我只想知道怎么用catalan数分析问题。我总结了一下，最典型的三类应用：（实质上却都一样，无非是递归等式的应用，就看你能不能分解问题写出递归式了）1.括号化问题。矩阵链乘： P=a1×a2×a3×……×an，依据乘法结合律，不改变其顺序，只用括号表示成对的乘积，试问有几种括号化的方案？(h(n)种) 2.出栈次序问题。一个栈(无穷大)的进栈序列为1,2,3,..n,有多少个不同的出栈序列? 类似：有2n个人排成一行进入剧场。入场费5元。其中只有n个人有一张5元钞票，另外n人只有10元钞票，剧院无其它钞票，问有多少中方法使得只要有10元的人买票，售票处就有5元的钞票找零？(将持5元者到达视作将5元入栈，持10元者到达视作使栈中某5元出栈) 3.将多边行划分为三角形问题。将一个凸多边形区域分成三角形区域的方法数? 类似：一位大城市的律师在她住所以北n个街区和以东n个街区处工作。每天她走2n个街区去上班。如果他从不穿越（但可以碰到）从家到办公室的对角线，那么有多少条可能的道路？类似：在圆上选择2n个点,将这些点成对连接起来使得所得到的n条线段不相交的方法数? 不过下面这个问题似乎不好归类，它怎么来应用这个catalan递归方程呢？你说说：n个结点可构造多少个不同的二叉树? 看的人倒是不少,愿意想一想的倒是不多,唉 h(n)=c(2n-2,n-1)/n 是什么意思哈 C代表什么呀 c代表组合数,即2n-2个体种选取n-1个的种类 re: catalan数在数据结构中的应用 2006-11-10 13:19 不过好像有些问题还不是那么好处理呵例如“有2n个人排成一行进入剧场。入场费5元。其中只有n个人有一张5元钞票，另外n人只有10元钞票，剧院无其它钞票，问有多

重要定理和公式

潇潇枫1987 — 2007-04-03 17:25:00

重要定理和公式一、常见递推关系 1.Fibonacci 数列 A(1)=1; A(2)=1; A(n)=A(n-1) + A(n-2); 2.Catalan数：考虑具有n个结点不同形态的二叉树的个数 H(n) H (0) = 1; H (n) = H (0) H (n-1) + H (1) H (n-2) + H (2) H (n-3) … + H (n-2) H (1) + H (n-1) H (0) ; -> H (n) = (1/ (n+1)) * C (n, 2n) 3. 第二类Stirling数： s(n,k)表示含n个元素的集合划分为k个集合的情况数 A.分类：集合{An}存在，则有s(n-1,k-1); 不存在则An和放入k个集合中的任意一个，共k*s(n-1,k)种。 0 (k=0 or nk>=1) *:求一个集合总的划分数即为 sigema(k=1..n) s(n,k) . 4．数字划分模型 *NOIP2001数的划分将整数n分成k份，且每份不能为空，任意两种分法不能相同(不考虑顺序)。 d[0,0]:=1; for p:=1 to n do for i:=p to n do for j:=k downto 1 do inc(d[i,j],d[i-p,j-1]); writeln(d[n,k]); *变形1：考虑顺序 d[ i, j] : = d [ i-k, j-1] (k=1..i) *变形2：若分解出来的每个数均有一个上限m d[ i, j] : = d [ i-k, j-1] (k=1..m) 5．错位排列 d[1] = 0; d[2] = 1; d[n] = (n-1) * (d[n-1] + d[n-2]) 6. 二、图论与计算几何 1．度边定理： sigema di = 2*E 2．.三角形面积 |x1 y1 1| s=|x2 y2 1|=x1y2+x2y3+x3y1-x3y2-x2y1-x1y3 |x3 y3 1| *海

进制转化

潇潇枫1987 — 2007-04-01 16:06:00

R进制转化成十进制公式：举例： 101.101(B)= 1*22+0*21+1*20+1*2-1+0*2-2+1*2-3 = 4+0+1+0.5+0+0.125 = 5.625 715(O)= 7*82+1*81+5*80 = 461 A01B(H)= 10*163+0*162+1*161+11*160 = 40987 2、十进制转化成 r 进制方法：整数部分：除以 r取余数，直到商为0，第一个余数是r进制数的最低位，最后的余数是最高位。小数部分：乘以 r取整数，第一个整数是r进制数的最高位，最后的整数是最低位。举例： 100.345(D)=1100100.01011(B) 100(D)=144(O)=64(H) 2 |100 余数 0.345 取整 8 |100 2 |50 余0 最低位 * 00002 8 |12 余4 最低位 2 |25 余0 0.690 0 最高位 8 |1 余4 2 |12 余1 * 00002 2 |0 余1 最高位 2 |6 余0 1.380 1 2 |3 余0 * 00002 16 |100 2 |1 余1 0.760 0 16 |6 余4 最低位 0 余1 最高位 * 00002 16 |0 余6 最高位 2 | 1.520 1 * 00002 01.04 1 最低位 100(D)=144(O)=64(H)=1100100(B) 3、八进制和十六进制转化成二进制每一个八进制数对应二进制的三位。每一个十六进制数对应二进制的四位。 2C1D(H)= 0010 1100 0001 1101(B) 7123(O)= 111 001 010 011(B) 2 C 1 D 7 1 2 3 4、二进制转化成八进制和十六制整数部分：从右向左进行分组。小数部分：从左向右进行分组。转化成八进制三位一组。转化成十六进制四位一组。位数不足一组时用零补够。 11 0110 1110. 1101 01(B) 0011 0110 1110. 1101 0100(B) =36F.D4(H) 3 6 F D 4 1 101 101 110. 110 1(B) 001 101 101 110. 110 100(B) =1556.64(O) 1 5 5 6 6 4

进制转化

潇潇枫1987 — 2007-04-01 16:04:00

进制转化 Time Limit:1s Memory limit:32M Accepted Submit:18 Total Submit:26 输入十进制数n（0<=n<=10000），请输出它对应的k（2<=k<=36）进制数。 10,11…分别用A, B … 代替。输入数据本题有多组输入数据，你必须处理到EOF为止. 每组数据占一行，有2个整数n,k 输出数据输出n对应的k进制数，一个数一行。输入样例3 2 4 3 15 16 输出样例11 11 F Original: FOJ月赛-2007年3月 #includeusing namespace std; void ten_to_r(int n,int r,char a[]){ int i,temp=1; char c; if(n==0){a[0]='0';a[1]='\0';} else{ for(i=0;n!=0;i++) { temp=n%r; n/=r; c=char(temp); if(temp>=10)c+=55; else c+=48; a[i]=c; } a[i]='\0'; }} int main(){ int n,r,i; char a[100000]; while(scanf("%d%d",&n,&r)!=EOF) { ten_to_r(n,r,a); for(i=strlen(a)-1;i>=0;i--) cout<

不同的单词

潇潇枫1987 — 2007-04-01 16:03:00

同的单词 Time Limit:1s Memory limit:32M Accepted Submit:25 Total Submit:36 给出一个英文单词的列表，计算有多少不同的单词在列表中。输入数据本题有多组输入数据，你必须处理到EOF为止每组数据的第一行有一个整数n, 1<=n<=1000.下面的n行每行一个单词，每个单词的长度不超过20。单词大小写忽略。输出数据每组数据输出一个整数，表示不同的单词数。输入样例5 FZU FzU LOY BNh FZU 输出样例3 Original: FOJ月赛-2007年3月 #include#includeusing namespace std; void do_with(char a[]){ int x; for(x=0;x=65&&a[x]<=90)a[x]+=32;} int main(){ int n,i,j,count; char (*word)[20]; while(scanf("%d",&n)!=EOF) { count=0; word=new char[n][20]; for(i=0;i>word[i]; do_with(word[i]); } for(i=0;i

矩形的个数

潇潇枫1987 — 2007-04-01 15:34:00

矩形的个数 Time Limit:1s Memory limit:32M Accepted Submit:18 Total Submit:38 在一个3*2的矩形中，可以找到6个1*1的矩形，4个2*1的矩形3个1*2的矩形，2个2*2的矩形，2个3*1的矩形和1个3*2的矩形，总共18个矩形。给出A，B,计算可以从中找到多少个矩形。输入数据本题有多组输入数据，你必须处理到EOF为止输入2个整数A,B(1<=A,B<=1000) 输出数据输出找到的矩形数。输入样例1 2 3 2 输出样例3 18 Original: FOJ月赛-2007年3月 #includeint main(){ int a,b,i,j; unsigned __int64/*long long*/ count=0; while(scanf("%d%d",&a,&b)!=EOF) { count=0; for(i=1;i<=a;i++) for(j=1;j<=b;j++) count+=(a+1-i)*(b+1-j); printf("%I64d \n",count); /*%lld*/ } return 0;} //注释中表示的是提交程序到Judge时的写法//在vc里定义变量用_int64 ,读入与输出是用%I64d //judge提交是将_int64改成long long ,同时读入与输出改成%lld

数据溢出处理

潇潇枫1987 — 2007-04-01 15:29:00

6.0用__int64. 8过我们的judge是不支持的。做完改过来再交吧。就是在vc里定义变量用_int64 ,读入与输出是用%I64d judge提交是将_int64改成long long ,同时读入与输出改成%lld

＊菱形

潇潇枫1987 — 2007-03-30 12:13:00

＊菱形问题描述：对给定的一个数n输出下列图形。当n=1 时，输出 .*.*.*.*. 当n=2时，输出 ..*...*.*.*.*.*.*.*...*.. 当n=4时，输出 ....*.......*.*.....*.*.*...*.*.*.*.*.*.*.*.*.*.*.*.*...*.*.*.....*.*.......*.... 输入：一个数n。(1<=n<=100) 输出：如图所示。（每行末尾没有多余的空格！） #includeusing namespace std;int main(){ int n,count=0,flag=0; while(cin>>n) {//处理前n+1行 for(int i=1;i<=n+1;i++) { flag=0; count=0; for(int j=1;j<=2*n+1;j++) { if(j<=n+1-i||count==i){cout<<'.';continue;} if(flag==1){cout<<'.';flag=0;continue;} else { if(count

判断浮点数等于0

潇潇枫1987 — 2007-03-12 16:30:00

浮点数不要直接判断等于0，要用fabs(a)<1e-9来判断等于0，浮点数用!号也很不好。

Power Strings

潇潇枫1987 — 2007-03-02 22:35:00

Power Strings Time Limit:5s Memory limit:32M Accepted Submit:166 Total Submit:491 Given two strings a and b we define a*b to be their concatenation. For example, if a = "abc" and b = "def" then a*b = "abcdef". If we think of concatenation as multiplication, exponentiation by a non-negative integer is defined in the normal way: a^0 = "" (the empty string) and a^(n+1) = a*(a^n). Each test case is a line of input representing s, a string of printable characters. For each s you should print the largest n such that s = a^n for some string a. The length of s will be at least 1 and will not exceed 1 million characters. A line containing a period follows the last test case. Sample Inputabcd aaaa ababab . Sample Output1 4 3 #include #include char s[1000001];short next[1000000]; int main(){ int i, j, len; while (1) {

阶层和

潇潇枫1987 — 2007-03-02 21:31:00

下面是1！+2！+3！+4！+4！+！+6！……+N！的源代码里面有很大数的阶乘的算法主要是按位算，那么大的数，肯定不能几个字节来存放 #include /*注释，对算法可能还表达还不是很完全*/#define N 2500 /*为了方便，把两个空间设为一样大，可以调整，以提高速度。不一定*/long int a[N]={0}; /*运算阶乘的空间*/long int b[N]={0}; /*盛放最后的结果*/long int m; /*特殊算法产生的中间量，表示进位*/long int g=0; /*输入的数*/main(){ headprint(); /*调用头输出*/ yunsuan(); /*运算*/ print(); &nb

变位词

潇潇枫1987 — 2007-03-02 20:43:00

福州大学第三届程序设计竞赛网上赛变位词时限:1秒内存:32M 通过:7 提交:35 Mr. Right有一个奇怪的嗜好，就是看见一个单词就有找它所有的变位词的冲动。一个单词的变位词就是该单词所有字母的一个排列。输入输出格式输入数据第一行为一个整数n，1<=n<=10^5，之后n行每行只包含一个单词，不含词组。这些单词构成了Mr. Right的字典。每个单词长度不大于9个字母。接着一行为一个整数m，1<=m<=100，表示Mr. Right将看见的单词数。之后m行每行包含一个单词。（题目中出现的每个单词都只由小写字母组成）对应Mr. Right看到的每个单词，输出落在字典里的它的变位词的个数。输入样例3 tea ate eat 3 ate abc tea 输出样例3 0 3 #include#includeusing namespace std;void ssort(char a[]) //对字符进行排序{ int i,j,l=strlen(a); char c; for(i=0;ia[j]) { c=a[i]; a[i]=a[j]; a[j]=c; }} int main(){ long n; int m,i,j; char (*cp)[9]; cin>>n; cp=new char[n][9]; for(i=0;i>cp[i]; ssort(cp[i]);////对Mr. Right

动态申请二维数组

潇潇枫1987 — 2007-03-02 12:34:00

//申请n个对象数组cp[9][8] int n; float (*cp)[9][8]; cin>>n; cp=new float[n][9][8]; delete []cp;

Peter's smokes

潇潇枫1987 — 2007-02-25 11:05:00

Peter has n cigarettes. He smokes them one by one keeping all the butts. Out of k > 1 butts he can roll a new cigarette. How many cigarettes can Peter have? Input is a sequence of lines. Each line contains two integer numbers giving the values of n and k. For each line of input, output one integer number on a separate line giving the maximum number of cigarettes that Peter can have. Sample input4 3 10 3 100 5 Output for the sample input5 14 124 Original: Albert 2001 #includeusing namespace std;int main(){ int n,k,num,left; while(cin>>n>>k) { num=n; left=n%k;//n butts并制成新烟后剩下的butts. n/=k; //用k butts做成新的n根烟 num+=n; //n根烟抽完又有n butts. n+=left; //新的n butts加上前面多出来的butts.(下同) while(n>=k) { num+=n/k; left

编程爱好者 潇潇枫

Center of Gravity

Number lengths

最大公约数

洗牌问题

分解素因子

中国剩余定理

catalan数在数据结构中的应用

重要定理和公式

进制转化

进制转化

不同的单词

矩形的个数

数据溢出处理

＊菱形

判断浮点数等于0

Power Strings

阶层和

变位词

动态申请二维数组

Peter's smokes

编程爱好者潇潇枫