读书是为了去发现新知识而去读,并不是为了读完而去读。---Tanky Woo
年轻,让我们尽情的去实现自己的梦想。---Tanky Woo
随着我在BUCT OJ冲到ranklist的第一页,也标志着我的水题人生结束了,这一周来每天疯狂的A题,(其实还包括暑假),导致我开始有点健忘了~~~~
也好,水题人生终于结束了,没有了水题的干扰,我可以安安心心的向算法世界进军了!
偶尔累了,可以再找点水题消遣下。
又要回到HDOJ了,在HDOJ上再练习一个月,我就得开始在POJ和TC上试试了。
加油了!Tanky Woo!
题目地址:
http://acm.hdu.edu.cn/showproblem.php?pid=2200
| 解答 |
这道题可以看做从n个中选出2、3…n个人,然后选2个人有1种分发,3个人有2种分发…n个人有n-1种分法 注:这里说的3个人有2种分发只是1|23和12|3两种,以此类推. 那么任意选出两个人有C(n,2)种,选3个人有C(n,3)种…; 那么n个人的答案就是C(n,2)*1+C(n,3)*2+…C(n,n)*(n-1); |
|---|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 | #include <iostream> using namespace std; //f[n][m]代表从n个人中找出m个,即数学中的C(n,m); __int64 f[100][100],n,m=0; __int64 work(int n,int m) { if (f[n][m]) return f[n][m]; if (n==m||m==0) return 1; return f[n][m]=work(n-1,m)+work(n-1,m-1);//n人中任意选m个可能是第n个人没被选中和被选中,没选中就是n-1个人里选m个,选中了就是n-1个人里选m-1个 } int main() { while(scanf("%d", &n) != EOF) { m = 0; for (int i=2;i<=n;i++) m += work(n,i)*(i-1); printf("%I64d\n", m); } return 0; } |
题目链接:
http://coder.buct.edu.cn/oj/Problem.aspx?pid=1793
我第一次AC用的是cout,cout确实很只能,能实现:
without unnecessary decimal points and/or zeros
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 | #include <iostream> #include <cmath> using namespace std; int main() { int x, cnt; while(1) { int imax=-1, imin=11; int sum = 0; int flag=0; for(int i=0; i<6; ++i) { scanf("%d", &x); if(x) flag=1; if(x > imax) imax = x; if(x < imin) imin = x; sum += x; } if(flag==0) break; sum -= (imax+imin); cout << sum / 4.0 << endl; } return 0; } |
可是总觉得,printf也应该有这样的输出控制,于是看了其他人的代码,原来是用%g控制,这里就顺便把常用的控制输入输出贴出来:
| %A 浮点数、十六进制数字和p-记法(C99) %c 一个字符 %d 有符号十进制整数 %e 浮点数、e-记数法 %E 浮点数、E-记数法 %f 浮点数、十进制记数法 %g 根据数值不同自动选择%f或%e. %G 根据数值不同自动选择%f或%e. %i 有符号十进制数(与%d相同) %o 无符号八进制整数 %p 指针 %s 字符串 %u 无符号十进制整数 %x 使用十六进制数字0f的无符号十六进制整数 %X 使用十六进制数字0f的无符号十六进制整数 %% 打印一个百分号 使用printf ()函数 printf()的基本形式: printf(“格式控制字符串”,变量列表); |
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 | #include <iostream> #include <cmath> using namespace std; int main() { int x, cnt; while(1) { int imax=-1, imin=11; int sum = 0; int flag=0; for(int i=0; i<6; ++i) { scanf("%d", &x); if(x) flag=1; if(x > imax) imax = x; if(x < imin) imin = x; sum += x; } if(flag==0) break; sum -= (imax+imin); printf("%g\n", sum/4.0); } return 0; } |
题目链接:
http://coder.buct.edu.cn/oj/Problem.aspx?pid=1746
咋一看,以为又是水题,于是暴力之。。。。结果:TLE。。。。
再一看,可以优化:
先记录每个数,其后比其小的数。
再遍历每个数,其前面的比其大的数,加上先前的值,就OK了。。。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 | #include <iostream> #include <cmath> using namespace std; int arr[1005]; int ans[1005]; int nCases; int nNum; int main() { scanf("%d", &nCases); while(nCases--) { memset(ans, 0, sizeof(ans)); memset(arr, 0, sizeof(arr)); scanf("%d", &nNum); for(int i=0; i<nNum; ++i) scanf("%d", &arr[i]); for(int i=0; i<nNum; ++i) { for(int j=i+1; j<nNum; ++j) if(arr[j] < arr[i]) ans[i]++; } int cnt = 0; for(int i=1; i<nNum; ++i) for(int j=0; j<i; ++j) if(arr[j]>arr[i]) cnt += ans[i]; printf("%d\n", cnt); } return 0; } |
最新评论