2019.12.16

CF1B

这是一个暴力的模拟题，本来是不应该有什么问题的，但是奈何我菜，还是WA了一发，AA表示 27 ; Z表示26 所以需要对数字mod 26 然后特判取余结果为 0 的情况，感觉以后应该会用到，所以留一下。

CF2B

一道脑筋急转弯，最优解一定是最小的2出现次数或者5出现次数。不会出现自己想象的白痴情况。dp然后回溯。

CF1C

一道几何题，第一次领教到了精度和小数去模的魅力

其中acos（）函数是会在小于-1的时候爆掉的所以以后要小心？

然后小数取模操作 fmod() 第一次碰到，留个笔记

CF1271D

看了dalao的题解， dalao牛逼

贪心思想，对于每一个城池，我们一定是越晚派兵越好，这样人只会多不会少

然后利用优先队列，放弃收益小的城池局可以了

CF1271B

来自队友的提醒之后，真是妙啊

首先可以想一下，如果W的出现次数是奇数，那么是不可能把W给消掉的

然后结论就来了，我们每次保留没法消掉的，问题合理解决

CF1271E

定义一个函数g(x ) 表示x在path中的总出现次数

我们可以分类讨论一下

如果x是奇数，那么他一定来自一个偶数

如果x是偶数，那么可能来自偶数，可能来自x+1

　　我们可以考虑在在x后面添 0 / 1,（二进制情况下），然后问题愉快的解决了

　　参透dalao的代码之后，我再一次连声称妙。

　　拿个小本本记下来

CF2C

一道几何题，重点在于求圆的交点，留下个板子吧

需要特判圆变成线的情况

  1 #include <stdio.h>
  2 #include <math.h>
  3 struct node
  4 {
  5     double x, y, r;
  6 }a[4], ans;
  7 int flag = 0;
  8 double sqr(double x)
  9 {
 10     return x * x;
 11 }
 12 double dis(double x, double y, double x1, double y1)
 13 {
 14     return sqrt(sqr(x-x1) + sqr(y-y1));
 15 }
 16 double calk(double x, double y)
 17 {
 18     return a[1].r / dis(x, y, a[1].x, a[1].y);
 19 }
 20 
 21 int dcmp(double x)
 22 {
 23     if(fabs(x)<=1e-6) return 0;
 24     if(x<0) return -1;
 25     return 1;
 26 }
 27 void cir_line(double A, double B, double C, double D, double a, double b, double c)
 28 {
 29     if(b==0)
 30     {
 31         ans.x = -1 * c / a;
 32         double ta = A;
 33         double tb = C;
 34         double tc = A * sqr(ans.x) + B * ans.x + D;
 35         if(dcmp(tb * tb - 4 * ta * tc) < 0) return;
 36         double delt = sqrt(tb * tb - 4 * ta * tc);
 37         double y1 = (-1 * tb - delt) / (2 * ta);
 38         double y2 = (-1 * tb + delt) / (2 * ta);
 39         flag = 1;
 40         if(calk(ans.x, y1) > calk(ans.x, y2)) ans.y = y1;
 41         else ans.y = y2;
 42     }else
 43     {
 44         double link = -1 * a / b;
 45         double linb = -1 * c / b;
 46         double ta = A + A * link * link;
 47         double tb = 2 * A * link * linb + B + C * link;
 48         double tc = A * linb * linb + linb * C + D;
 49         if(dcmp(tb * tb - 4 * ta * tc) < 0) return ;
 50         double delt = sqrt(tb * tb - 4 * ta * tc);
 51         flag = 1;
 52         double x1 = (-1 * tb - delt) / (2 * ta);
 53         double x2 = (-1 * tb + delt) / (2 * ta);
 54         double y1 = link * x1 + linb;
 55         double y2 = link * x2 + linb;
 56         if(calk(x1, y1)>calk(x2, y2))
 57         {
 58             ans.x = x1; ans.y = y1;
 59         }else
 60         {
 61             ans.x = x2; ans.y = y2;
 62         }
 63     }
 64 }
 65 void line_line(double a1, double b1, double c1, double a2, double b2, double c2)
 66 {
 67     if(dcmp(a1)==0 && dcmp(a2)==0) 
 68     {
 69         if(dcmp(b1) != 0 && dcmp(b2) != 0 && dcmp(c1/b1 - c2/b2)==0)
 70             cir_line(1, -2*a[1].x, -2*a[1].y, sqr(a[1].x)+sqr(a[1].y)-sqr(a[1].r), a1, b1, c1);
 71         return;
 72     }
 73     if(dcmp(b1)==0 && dcmp(b2)==0) 
 74     {
 75         if(dcmp(a1) != 0 && dcmp(a2) != 0 && dcmp(c1/a1 - c2/a2)==0)
 76             cir_line(1, -2*a[1].x, -2*a[1].y, sqr(a[1].x)+sqr(a[1].y)-sqr(a[1].r), a1, b1, c1);
 77         return;
 78     }
 79     if(a1==0)
 80     {
 81         flag = 1;
 82         ans.y = -c1 / b1;
 83         ans.x = -1 * (b2 * ans.y + c2) / a2;
 84     }else if(a2==0)
 85     {
 86         flag = 1;
 87         ans.y = -c2 / b2;
 88         ans.x = -1 * (b1 * ans.y + c1) / a1;
 89     }else
 90     {
 91         flag = 1;
 92         ans.y = (a1 * c2 - a2 * c1) / (a2 * b1 - a1 * b2);
 93         ans.x = -1 * (b1 * ans.y + c1) / a1;
 94     }
 95 }
 96 
 97 double cir_cir(double A0, double B0, double C0, double D0, double A1, double B1, double C1, double D1)
 98 {
 99     double a = (B0 / A0 - B1 / A1);
100     double b = (C0 / A0 - C1 / A1);
101     double c = (D0 / A0 - D1 / A1);
102     cir_line(A0, B0, C0, D0, a, b, c);
103 }
104 int main()
105 {
106     double A0, B0, C0, D0, A1, B1, C1, D1, k;
107     for(int i = 1; i <= 3; i++)
108         scanf("%lf %lf %lf", &a[i].x, &a[i].y, &a[i].r);
109     
110     A0 = (sqr(a[1].r)/sqr(a[2].r) - 1);
111     B0 = 2 * (a[1].x - (sqr(a[1].r)/sqr(a[2].r)) * a[2].x);
112     C0 = 2 * (a[1].y - (sqr(a[1].r)/sqr(a[2].r)) * a[2].y);
113     D0 = (sqr(a[1].r)/sqr(a[2].r)) * (sqr(a[2].x) + sqr(a[2].y)) - (sqr(a[1].x) + sqr(a[1].y)); 
114     
115     A1 = (sqr(a[1].r)/sqr(a[3].r) - 1);
116     B1 = 2 * (a[1].x - (sqr(a[1].r)/sqr(a[3].r)) * a[3].x);
117     C1 = 2 * (a[1].y - (sqr(a[1].r)/sqr(a[3].r)) * a[3].y);
118     D1 = (sqr(a[1].r)/sqr(a[3].r)) * (sqr(a[3].x) + sqr(a[3].y)) - (sqr(a[1].x) + sqr(a[1].y)); 
119     
120     if(dcmp(A0) == 0&& dcmp(A1) == 0)
121     {
122         line_line(B0, C0, D0, B1, B1, D1);
123     }else if(dcmp(A0)==0)
124     {
125         cir_line(A1, B1, C1, D1, B0, C0, D0);
126     }else if(dcmp(A1)==0)
127     {
128         cir_line(A0, B0, C0, D0, B1, C1, D1);
129     }else{
130         cir_cir(A0, B0, C0, D0, A1, B1, C1, D1);
131     }
132     
133     if(flag) printf("%.5lf %.5lf
", ans.x, ans.y);
134     
135 }