2018CCPC吉林赛区 | 部分题解 (HDU6555 HDU6556 HDU6559 HDU6561)

港控/mmm° 2021-10-26 18:26 205阅读 0赞

// 杭电上的重现赛：[http://acm.hdu.edu.cn/contests/contest\_show.php?cid=867][http_acm.hdu.edu.cn_contests_contest_show.php_cid_867]

// 杭电6555~6566可交题

## A - [The Fool][]  ##

### 题目大意： ###

求∑(1,n) \[n/i\] 的奇偶性。

### 分析及代码： ###

这个求和可以**分块**计算，复杂度O(√N)，完全可行。

我觉得是水题就打表找规律了，发现前3项1~3结果是奇数，接着5项4~8结果是偶数，再接着7项是奇数，再然后9项时偶数......如此交替。

那么只需要计算n在哪一段就能确定奇偶性了，时间复杂度O(1)。

AC代码：

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

#include<iostream>
    #include<cstdio>
    #include<cmath>
    using namespace std;
    
    int main() {
        int t = 0, T; cin>>T;
        while(t<T) {
            int n;
            scanf("%d", &n);
            int k = sqrt(n+1);
            if(k*k<n+1) ++k;
    
    
            printf("Case %d: ", ++t);
            if(k&1) printf("even\n");
            else printf("odd\n");
        }
    
        return 0;
    }

## B - [The World][] ##

### 题目大意： ###

世界时间换算问题，本题只考虑4个城市，每次给两个城市和其中一个城市的时间，求另一城市的时间。

### 分析及代码： ###

听说队友A不掉，然后又看不懂样例了，遂尝试解题。

本题还是有点坑的，如果给定的时间都是标准24小时制，那就非常简单了，加加减减就完事了。

看了百度百科才明白什么是真正的[12小时制][12]：

> 十二小时制是一个时间规则把一日二十四小时分为两个时段，分别为上午（拉丁文ante meridiem表示中午之前）和 下午（拉丁文post meridiem表示中午之后）。每个时段由十二个小时构成，以数字**12、1、2、3、4、5、6、7、8、9、10、11**依次序表示。

所以12小时制里是不存在 0:30 AM 和 0:30 PM 的！！！

注意24小时制与12小时的转化后，就没什么问题了O.O

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

#include<iostream>
    #include<cstdio>
    #include<cmath>
    #include<string>
    #include<map>
    using namespace std;
    map<string, int> mp;
    int main() {
    
        mp["Beijing"] =  8;
        mp["Washington"] = -5;
        mp["London"] = 0;
        mp["Moscow"] = 3; 
    
        string city1, city2;
        int h, min;
        string ap;
        int t = 0, T; cin>>T;
        while(t<T) {
            scanf("%d:%d", &h, &min);
            cin>>ap;
            cin>>city1;
            cin>>city2;
    
            if(ap=="PM" && h!=12) h += 12;   // 转化成24小时制
            if(ap=="AM" && h==12) h = 0;
    
            h += mp[city2] - mp[city1];
            printf("Case %d: ", ++t);
    
            if(h>=24) {
                printf("Tomorrow ");
                h -= 24;
            }else if(h<0) {
                printf("Yesterday ");
                h += 24;
            } else {
                printf("Today ");
            }
    
            if(h>=12) printf("%d:%02d PM\n", h==12?12:h-12, min);
            else 
                printf("%d:%02d AM\n", h==0?12:h, min);
            
            
        }
    
        return 0;
    }

## E - [The Tower][] ##

### 题目大意： ###

** 计算几何**题。给你一个高h，底面半径r的圆锥体，以及一个点(x0, y0, z0)和速度(vx, vy, vz)，求什么时候落到圆锥面上。

### 分析及代码： ###

一看很简单啊，求直线方程与圆锥面的交点就完事了。

整了半天把圆锥面的方程写出来了（开始写错WA了一发）：

(z - h)^2 = h^2/r^2 \* (x^2+y^2)

直线方程

(x-x0)/vx = (y-y0)/vy = (z-z0)/vz

联立消去x, y

解一元二次方程求出z

注意z的范围**0<=z<=h，**筛选过后选距离z0近的一点，fabs((z-z0)/vz)就是答案。

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

#include<iostream>
    #include<cstdio>
    #include<cmath>
    #include<algorithm>
    using namespace std;
    #define sqr(x) ((x)*(x))
    
    int main() {
        double r, h;
        double x0, y0, z0, vx, vy, vz;
        int t = 0, T; cin>>T;
        while(t<T) {
    
            scanf("%lf %lf", &r, &h);
            scanf("%lf %lf %lf", &x0, &y0, &z0);
            scanf("%lf %lf %lf", &vx, &vy, &vz);
            printf("Case %d: ", ++t);
    
            if(fabs(vz)<1e-8) { // 一定要特殊处理，后面的计算vz作了分母
                if(fabs(vy)<1e-8) {
                    double xx = sqr((z0-h)*(r/h)) - y0*y0;
                    xx = sqrt(xx);
                    printf("%.10lf\n", min(fabs(xx-x0), fabs(-xx-x0))/fabs(vx));
                } else {
                    double a = 1 + sqr(vx/vy);
                    double b =2*vx/vy*(x0-vx/vy*y0);
                    double c = sqr(x0-vx/vy*y0) - sqr(r/h)*sqr(z0-h);
    
                    double y1 = (-b+sqrt(b*b-4*a*c))/2/a;
                    double y2 = (-b-sqrt(b*b-4*a*c))/2/a;
                    printf("%.10lf\n",  min(fabs(y1-y0), fabs(y2-y0))/fabs(vy));
                }
                continue;
            }
            double a = (vx*vx+vy*vy)/(vz*vz) - r*r/(h*h);
            double b = 2*(vx/vz*(x0-vx/vz*z0)+vy/vz*(y0-vy/vz*z0)) + 2*r*r/h;
            double c = sqr(x0-vx/vz*z0) + sqr(y0-vy/vz*z0) - r*r;
        //    printf("%lf %lf %lf\n", a, b, c);
            
            if(fabs(a)<1e-8) { // 实际没用，可以删掉
                printf("%.10lf\n", fabs((-c/b-z0)/vz));
                continue;
            }
            double z1 = (-b+sqrt(b*b-4*a*c))/2/a;
            double z2 = (-b-sqrt(b*b-4*a*c))/2/a;
    
        //    double zz = fabs(z1-z0)<fabs(z2-z0)?z1:z2;
        //    double xx = x0 + vx/vz*(zz-z0);
        //    double yy = y0 + vy/vz*(zz-z0);
            double zz;
            if(z1>h) zz = z2;
            else if(z2>h) zz = z1;
            else zz = fabs(z1-z0)<fabs(z2-z0)?z1:z2;
            
            printf("%.10lf\n", fabs((zz-z0)/vz));
    
        }
        
        return 0;
    }

PS: 看到题解令(x-x0)/vx = (y-y0)/vy = (z-z0)/vz = t， 用t分别表示x, y, z再带入圆锥方程，直接解出t，貌似可以不用特殊处理（vz=0的情况）。

## G - [High Priestess][] ##

### 题目大意： ###

给你数量10^4个阻值为1欧的电阻，求通过串并联得到一个阻值为r的等效电阻的方案，精度至少为1e-8。

### 分析及代码： ###

将阻值r转化为连分数的形式，然后根据串并联公式将分式里的+合理转化成相应形式。

具体来说，连分数的数位ki有奇数个的时候：

1.  最后一个数字先*并联*（如1/3就是三个1欧并联）；
2.  将接下来的数字*串联*，并且接着与前一个电路*串联*；
3.  再将接下来的数字*并联*，并且接着与前一个电路*并联*；
4.  交替进行2-3两步，直到数位枚举完毕。

连分数的数位为偶数时，跟上面过程相似，不同的是第一步为串联，以后步骤的串联与并联交换即可。

例如组成 r = 0.33 = 1/(3 + 1/33)

1.  33个1欧电阻*串联*得到33欧
2.  3个1欧*并联*得到1/3欧，1/3与33*并联*得到 33/100，即0.33。
3.  两个数字枚举完，结束。

* *

代码WA了，还在debug...

--------------------

（未完待续。。。）

转载于:https://www.cnblogs.com/izcat/p/11204500.html

[http_acm.hdu.edu.cn_contests_contest_show.php_cid_867]: http://acm.hdu.edu.cn/contests/contest_show.php?cid=867
[The Fool]: http://acm.hdu.edu.cn/showproblem.php?pid=6555
[ContractedBlock.gif]: https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif
[ExpandedBlockStart.gif]: /images/20211026/8a9d3a59f8c1407097964528235742af.png
[The World]: http://acm.hdu.edu.cn/showproblem.php?pid=6556
[12]: https://baike.baidu.com/item/%E5%8D%81%E4%BA%8C%E5%B0%8F%E6%97%B6%E5%88%B6
[The Tower]: http://acm.hdu.edu.cn/showproblem.php?pid=6559
[High Priestess]: http://acm.hdu.edu.cn/showproblem.php?pid=6561