随笔-21  评论-10  文章-21  trackbacks-0
 
每天看8页 计算几何--算法与应用,在比赛前看完
每天做三道题(数学和计算几何)
我们的队伍只要赢,不要输

题目

计算几何--算法与应用


posted @ 2009-03-05 15:32 wangzhihao 阅读(76) | 评论 (0)编辑 收藏
floodfill 单独理解就是搜索,但加上离散化却可以很好的解决一些问题

pku 1371 Tin Cutter

他就是要找到有多少个hole,floodfill用于找有多少个区间很好,
但我们必须先把图形离散化变形成等价的形式,然后其余的就好做了


floodfill的其它题目

UVA
260 280 352 469 572 601 657 776 782 784 785 871 10267 10336 10946

pku
3338

黑书上有幅笑脸,我记得他也是有floodfill做的


posted @ 2009-03-04 17:07 wangzhihao 阅读(781) | 评论 (0)编辑 收藏
 名称  日期  本星期
 tc SRM
 3月11号Wes 19:00
sgu&petr第四场
 3月15号Sun  16:00
  The 9th Zhejiang University Programming Contest  3月22号 Sun  14:00
     Izhevsk State Technical University Contest 3 3月22号 Sun 15:00

posted @ 2009-03-03 11:51 wangzhihao 阅读(127) | 评论 (0)编辑 收藏
今天比赛真多,凌晨1点是TCO, 中午12点又是浙大7周年庆典赛,傍晚又有sgu上petr的题。。。

1  a^p-1 = 1 mod p  和  a^p = a mod p 不等价

当 gcd(a,p) > 1时  例如 161038 2



2  浙大月赛做了两道题,只做出一道
第一题是要知道 某个数是M的次方,而且它的第k位是 7 ,求他的最小次数
类似大数乘法
黑书上有一题是已知一个二进制数的前面一半(高位),求他可能的位数,有些不一样,
其中在于一个是从高位考虑,一个是从低位考虑
第二题是一个关于二叉树的,想不通为什么wa

3 sgu上的题好短,一题是问你有 n 个硬币,告诉你他们的面值,现在要凑成 刚好 M 块钱,不管怎么选,
有哪些硬币是一定需要的, 感觉题目很经典,以为有什么经典算法, 但结果后来直接枚举背包爆过了

还一题是个构造题,找找规律



 
posted @ 2009-03-01 22:16 wangzhihao 阅读(107) | 评论 (0)编辑 收藏
     摘要:    这道题显然考察积分,但有些积分是困难的(所以要平时多做题,能判断哪些是自己能够手算积出来的),能积出来当然尽量算出来,但对于那些困难的,就可以模拟积分的过程, 这里微元可以选择横截面,对于每一个横截面的面积 S 是 一个弓形,这是好求的,再沿轴线方向积分却困难了,边看代码边解释:waterloo的标程 Code highlighting produced by Acti...  阅读全文
posted @ 2009-02-27 22:45 wangzhihao 阅读(372) | 评论 (1)编辑 收藏
pku 2461 Magic Bitstrings


Start by proving that in the square matrix (like the one, shown in the table in the problem statement),
the diagonal elements are always 0's if the first bit of the bitstring is 0.
这段话就可以构造出答案,猜出答案

The diagonal consists of the elements that are quadric residues modulo n. There are (n-1)/2 such distinct elements. When we mark them as 0, there are (n-1)/2 elements left. But a magic bitstring has equal number of 0's and 1's, so the remaining elements are 1.
这段话是证明猜想是对的,我还不太清楚


pku 2856 medals

仔细观察,发现 j, k, l 太大了和 他们小的时候本质上没什么区别,用n进制去理解,先假设 j, k, l 不相同那么只是需要三位数(n进制)就可枚举出所有的情况 ,相同的时候用三位数(n进制)绰绰有余, 所以 用三位数就足够枚举了


posted @ 2009-02-25 22:49 wangzhihao 阅读(293) | 评论 (0)编辑 收藏
这应该属于几何分布里的东西,标程的意思尚未理解


 1 #include <iostream>
 2 #include <cstdio>
 3 
 4 using namespace std;
 5 
 6 int n;
 7 double d[1001], Pl, Pr;
 8 
 9 main() {
10     while( cin >> n >> Pl >> Pr && n) {
11         d[0= 0.0;
12         forint i = 1; i <= n; i++ ) {
13             d[i] = 1e50;
14             forint j = 0; j < i; j++ )
15                 d[i] <?= d[j] + d[i-j-1+ 1 +    // do left, right, then middle
16                         (1/(1-Pl-Pr) - 1*        // E(knocking down middle)
17                         ((Pl*d[j] + Pr*d[i-j-1])/(Pl+Pr) + 1);
18                                                 // cost of knocking down middle
19         }
20         printf( "%.2lf\n", d[n] );
21     }
22 }
23 

标程2

 1 #include <math.h>
 2 #include <stdio.h>
 3 
 4 double Pl, Pr, C[1100], c;  // C[m] is cost to build m in a row
 5 
 6 int i,l,k,m,n,r;
 7 
 8 main(){
 9    while (3 == scanf("%d%lf%lf",&n,&Pl,&Pr)) {
10       if (Pl+Pr == 0) {
11          printf("%d.00\n",n);
12          continue;
13       }
14       C[0= 0;
15       for (i=1;i<=n;i++) C[i] = 1e19;
16       for (m=1;m<=n;m++) { 
17          for (l=0;l<m;l++) {   // l dominoes on the left
18             r = m-l-1;
19             c = 1 + C[l] + C[r] + 
20                 (1/(1-Pr-Pl)-1* (1+ Pl/(Pr+Pl)*C[l] + Pr/(Pr+Pl)*C[r]);
21             if (c < C[m]) C[m] = c;
22          }
23       }
24       printf("%0.2lf\n",C[n]);
25    }
26 }
27 

对概率太陌生,一些概率题先放这

So you want to be a 2n-aire?

Dumb Bones

Practice

posted @ 2009-02-21 12:54 wangzhihao 阅读(281) | 评论 (0)编辑 收藏


原题是求直线与多边形的相交部分的长度
如果题中的线有了宽度 w ,那如何求他们相交部分的面积呢?

想法1:离散化
假设长直条的斜率为 l ,过多边形每个顶点作一条斜率为 l 的直线,这些直线将多边形离散化,
对于在长直条范围内的单位直条进行统计,可以求得面积



posted @ 2009-02-21 12:29 wangzhihao 阅读(80) | 评论 (0)编辑 收藏
题目大意是两个城市飞机通航,航线选择最短的球面距离,给你两个城市的经纬度,求航线途中经过的纬度最大值是多少? 以北纬为正,南纬为负

这道题求球面坐标的方法让人印象深刻。绝对经典。不是常见的二分,这道题Advanced Causal Measurements (ACM)是常见的二分,二分答案,

回到主题
1 经纬度的转换是基本功Brookebond s'en va en guerre...
2 我掌握了二分圆弧的方法,管他二维还是三维的。
 



posted @ 2009-02-20 22:23 wangzhihao 阅读(115) | 评论 (0)编辑 收藏
问题问题问题问题问题问题 问题问题问题问题问题问题 问题问题问题问题问题问题 问题问题问题问题问题问题

高斯消元

Rectilinear polygon

CDVII

Snap

Subway

Adventures in Moving - Part V

Return of the Jedi

Dumb Bones

Practice



问题问题问题问题问题问题 问题问题问题问题问题问题 问题问题问题问题问题问题 问题问题问题问题问题问题
posted @ 2009-02-16 08:06 wangzhihao 阅读(93) | 评论 (0)编辑 收藏
仅列出标题
共3页: 1 2 3