跳至正文

USACO 3.4.3 Electric Fence 解题报告

  • OI路程

题目本质:相似三角形+枚举 算法描述:题目给出的三角形比较特殊,所以可以直接枚举,当然也不能说是直接枚举咯。我的算法是,对于每一行进行枚举,但是很快就到瓶颈了,无法确定坐标,虽然能够画出相似三角形,因为三角形的一条边在x轴上,所以从y等于(-)1(看情况而定是1还是-1)至m,每一行做与x轴平行的线就有相似三角形了,但是只能确定长短,不能确定坐标,后来想了好阵子,才想到,用高来确定坐标,用两个三角形,(n, m)(n, 0)(0, 0),(m, n)(n, 0)(p, 0),分别可以把新坐标求出来,然后一个向上取整,一个向下取整,相减+1就可以了,接下来就是细节了。 Pay attention:y=0 不计算,x轴上所有的点都在线上,不符合要求;如果在某个y上,x1, x2(相似三角形求出的两个坐标), x1, x2为整数的话, 那么x1, x2连点都不能取。 复 杂 度:这题不会分析,不知道什么是N。 de lang="c">/ LANG: C ID: yylogoo1 PROG: fence9 / #include #include #include

#define swap(a, b) do{\ int t;\ t = a;\ a = b;\ b = t;\ }while(0) int main(int argc, char argv[]) { int i; int x[2] = {0}; int a, b, k; int x1, x2; double t; int ans = 0; freopen("fence9.in", "r", stdin); freopen("fence9.out", "w", stdout); scanf("%d%d%d", &a, &b, &x[1]); if(x[0] < x[1]){ swap(x[0], x[1]); } k = b / abs(b); for(i = 1; i != b; i += k){ //向上取整 x1 = ceil(1.0 (b – i) / b (x[0] – a) + a); //自动向下取整 x2 = floor(1.0 (b – i) / b (x[1] – a) + a); ans += x2 – x1 + 1; t = 1.0 (b – i) / b (x[0] – a) + a; if(t <0 x t>= x1 – 0.00001){ ans–; } t = 1.0 (b – i) / b * (x[1] – a) + a; if(t <0 x t>= x1 – 0.00002){ ans–; } } printf("%d\n", ans); return 0; } de>

发表评论

您的电子邮箱地址不会被公开。