hihoCoder挑战赛14 A,B,C题解

转载请注明出处： http://www.cnblogs.com/fraud/          ——by fraud

题目1 : 不等式

时间限制:10000ms

单点时限:1000ms

内存限制:256MB

描述

给定n个关于X的不等式，问最多有多少个成立。

每个不等式为如下的形式之一：

X < C

X <= C

X = C

X > C

X >= C

输入

第一行一个整数n。

以下n行，每行一个不等式。

数据范围:

1<=N<=50,0<=C<=1000

输出

一行一个整数，表示最多可以同时成立的不等式个数。

样例输入

4
X = 1
X = 2
X = 3
X > 0

样例输出

2

枚举所有值，每隔0.5一个，这样就能取到所有情况了。少了小数部分，WA了两下才发现。。。真是惨

 /**
  * code generated by JHelper
  * More info: https://github.com/AlexeyDmitriev/JHelper
  * @author xyiyy @https://github.com/xyiyy
  */

 #include <iostream>
 #include <fstream>

 //#####################
 //Author:fraud
 //Blog: http://www.cnblogs.com/fraud/
 //#####################
 //#pragma comment(linker, "/STACK:102400000,102400000")
 #include <iostream>
 #include <sstream>
 #include <ios>
 #include <iomanip>
 #include <functional>
 #include <algorithm>
 #include <vector>
 #include <string>
 #include <list>
 #include <queue>
 #include <deque>
 #include <stack>
 #include <set>
 #include <map>
 #include <cstdio>
 #include <cstdlib>
 #include <cmath>
 #include <cstring>
 #include <climits>
 #include <cctype>

 using namespace std;
 #define XINF INT_MAX
 #define INF 0x3FFFFFFF
 #define mp(X, Y) make_pair(X,Y)
 #define pb(X) push_back(X)
 #define rep(X, N) for(int X=0;X<N;X++)
 #define rep2(X, L, R) for(int X=L;X<=R;X++)
 #define dep(X, R, L) for(int X=R;X>=L;X--)
 #define clr(A, X) memset(A,X,sizeof(A))
 #define IT iterator
 #define ALL(X) (X).begin(),(X).end()
 #define PQ std::priority_queue
 typedef long long ll;
 typedef unsigned long long ull;
 typedef pair<int, int> PII;
 typedef vector<PII> VII;
 typedef vector<int> VI;

 int getTheAnswer() {
     return ;
 }

 char a[];
 string str[];
 double num[];

 class TaskA {
 public:
     void solve(std::istream &in, std::ostream &out) {
         int n;
         while (in >> n) {
             rep(i, n)
                 in >> a[i] >> str[i] >> num[i];
             int ans = ;
             for (double i = -1.5; i < ; i += 1.0) {
                 int m = ;
                 rep(j, n) {
                     if (gao(i, j))m++;
                 }
                 ans = max(ans, m);
             }
             rep2(i, -, ) {
                 int m = ;
                 rep(j, n) {
                     if (gao(i, j))m++;
                 }
                 ans = max(ans, m);
             }
             out << ans << endl;

         }
     }

     bool gao(double x, int i) {
         if (str[i] == "<") {
             return x < num[i];
         } else if (str[i] == "<=") {
             return x <= num[i];
         } else if (str[i] == "=") {
             return x == num[i];
         } else if (str[i] == ">") {
             return x > num[i];
         } else if (str[i] == ">=") {
             return x >= num[i];
         }
     }
 };

 int main() {
     std::ios::sync_with_stdio(false);
     std::cin.tie();
     TaskA solver;
     std::istream &in(std::cin);
     std::ostream &out(std::cout);
     solver.solve(in, out);
     return ;
 }

代码君

题目2 : 赛车

时间限制:20000ms

单点时限:1000ms

内存限制:256MB

描述

幻想乡有一个赛车场。赛车场里有N个地点。同时地点之间还有单向的道路存在。

这些道路使得赛车场形成了一个外向树的结构。也就是说，道路将这N个地点连成了一个有根树。并且所有的边都是从父亲指向孩子的。

由于幽香喜欢刺激，每次她去赛车场都会从根节点出发，选择最长的一条路径来玩。

但是现在幽香感觉最长的路径还是太短了，她打算在赛车场里新建一条道路使得新的最长路径最长。

同时，如果道路形成了一个环，那么可能会出现交通事故，所以幽香新建的道路不能导致环的出现。

你能帮幽香算出新建一条道路后的最长路径吗？幽香知道根节点一定是1号点。

输入

一行一个数N，表示地点的数量。

接下来N-1行，每行两个数a和b，表示从点a到点b有一条单向路径。所有点从1到n标号。

数据范围：

n<=100000。

输出

一行表示新建一条边后的最长路径。

样例输入

5
1 2
2 3
1 4
4 5

样例输出

4

树形DP裸题，先dfs处理一下，然后枚举所有点，求出从根节点出发到这个点的路径长度，以及这个点往下的最长路以及次长路即可。

 /**
  * code generated by JHelper
  * More info: https://github.com/AlexeyDmitriev/JHelper
  * @author xyiyy @https://github.com/xyiyy
  */

 #include <iostream>
 #include <fstream>

 //#####################
 //Author:fraud
 //Blog: http://www.cnblogs.com/fraud/
 //#####################
 //#pragma comment(linker, "/STACK:102400000,102400000")
 #include <iostream>
 #include <sstream>
 #include <ios>
 #include <iomanip>
 #include <functional>
 #include <algorithm>
 #include <vector>
 #include <string>
 #include <list>
 #include <queue>
 #include <deque>
 #include <stack>
 #include <set>
 #include <map>
 #include <cstdio>
 #include <cstdlib>
 #include <cmath>
 #include <cstring>
 #include <climits>
 #include <cctype>

 using namespace std;
 #define XINF INT_MAX
 #define INF 0x3FFFFFFF
 #define mp(X, Y) make_pair(X,Y)
 #define pb(X) push_back(X)
 #define rep(X, N) for(int X=0;X<N;X++)
 #define rep2(X, L, R) for(int X=L;X<=R;X++)
 #define dep(X, R, L) for(int X=R;X>=L;X--)
 #define clr(A, X) memset(A,X,sizeof(A))
 #define IT iterator
 #define ALL(X) (X).begin(),(X).end()
 #define PQ std::priority_queue
 typedef long long ll;
 typedef unsigned long long ull;
 typedef pair<int, int> PII;
 typedef vector<PII> VII;
 typedef vector<int> VI;

 int getTheAnswer() {
     return ;
 }

 vector<int> G[];
 int dp[][];
 int pre[][];
 int dep[];
 int ans;

 class TaskB {
 public:
     void solve() {
         int n;
         while (scanf("%d",&n)!=EOF) {
             rep(i, n)G[i].clear();
             int u, v;
             rep(i, n - ) {
                 scanf("%d%d",&u,&v);//in >> u >> v;
                 u--;
                 v--;
                 G[u].pb(v);
             }
             dep[] = ;
             dfs(, -);
             ans = ;
             dfs2(, -);
             printf("%d\n",ans);//out << ans << endl;
         }
     }

     void dfs(int u, int fa) {
         dp[u][] = dp[u][] = ;
         pre[u][] = pre[u][] = -;
         int sz = G[u].size();
         rep(i, sz) {
             int v = G[u][i];
             dep[v] = dep[u] + ;
             dfs(v, u);
             if (dp[v][] +  > dp[u][]) {
                 dp[u][] = dp[v][] + ;
                 pre[u][] = v;
                 if (dp[u][] > dp[u][]) {
                     swap(dp[u][], dp[u][]);
                     swap(pre[u][], pre[u][]);
                 }
             }
         }
     }

     void dfs2(int u, int fa) {
         int sz = G[u].size();
         rep(i, sz) {
             int v = G[u][i];
             ans = max(ans, dp[u][] + dep[u] + dp[u][]);
             dfs2(v, u);
         }
     }
 };

 int main() {
     TaskB solver;
     solver.solve();
     return ;
 }

代码君

题目3 : 向日葵

时间限制:30000ms

单点时限:1500ms

内存限制:256MB

描述

幽香打算种一些向日葵，让自己的太阳花田更加的漂亮。

现在太阳花田上什么植物都没有。幽香搞到了一些向日葵的种子。不过幽香觉得如果直接种的话太无趣了，

她打算采取一种比较有趣的种法。

她在太阳花田上选择了n对点，分别为(a1,b1),(a2,b2),...,(an,bn)。然后对于每一对点(ai,bi)，她会以一半的概率在ai种一个向日葵，一半的概率在bi种一个向日葵。

种完向日葵以后，幽香需要将这些向日葵围起来建成花园。防止被其它小妖精踩踏。花园可以看成就是这些种了的向日葵的凸包。那么幽香想知道花园的期望大小是多少呢？

输入

第一行n，表示点对的个数。

接下来n行，每行4个数，第i行前两个数为ai的x,y坐标，后两个数为bi的x,y坐标。

数据范围:

n<=1000。

所有坐标都是绝对值小于1e9的整数。

输入中的2n个点不存在3点共线，或者2点重合的情况。

输出

一行答案。相对误差在1e-6以内就算正确。

样例输入

10
703 548 811 701
978 368 435 32
270 667 550 68
326 486 217 486
116 344 361 418
591 563 38 373
548 210 94 800
978 1000 169 278
362 32 899 331
401 339 399 334

样例输出

407253.2333984375

比赛的时候一直没想通每条边在凸包出现的概率怎么算。

因为边的概率其实就是有向三角形的概率，而所有有向三角形面积的和就是凸包的面积。

先枚举所有边，然后再枚举所有点，对于每个点， 看在其左边和右边的的可能性，那么其概率就是两个点中叉积小于0的概率，因为小于0的点才是在凸包内的，这样枚举的那条边才会对面积做出贡献。

 /**
  * code generated by JHelper
  * More info: https://github.com/AlexeyDmitriev/JHelper
  * @author xyiyy @https://github.com/xyiyy
  */

 #include <iostream>
 #include <fstream>

 //#####################
 //Author:fraud
 //Blog: http://www.cnblogs.com/fraud/
 //#####################
 //#pragma comment(linker, "/STACK:102400000,102400000")
 #include <iostream>
 #include <sstream>
 #include <ios>
 #include <iomanip>
 #include <functional>
 #include <algorithm>
 #include <vector>
 #include <string>
 #include <list>
 #include <queue>
 #include <deque>
 #include <stack>
 #include <set>
 #include <map>
 #include <cstdio>
 #include <cstdlib>
 #include <cmath>
 #include <cstring>
 #include <climits>
 #include <cctype>

 using namespace std;
 #define XINF INT_MAX
 #define INF 0x3FFFFFFF
 #define mp(X, Y) make_pair(X,Y)
 #define pb(X) push_back(X)
 #define rep(X, N) for(int X=0;X<N;X++)
 #define rep2(X, L, R) for(int X=L;X<=R;X++)
 #define dep(X, R, L) for(int X=R;X>=L;X--)
 #define clr(A, X) memset(A,X,sizeof(A))
 #define IT iterator
 #define ALL(X) (X).begin(),(X).end()
 #define PQ std::priority_queue
 typedef long long ll;
 typedef unsigned long long ull;
 typedef pair<int, int> PII;
 typedef vector<PII> VII;
 typedef vector<int> VI;

 int getTheAnswer() {
     return ;
 }
 //
 // Created by xyiyy on 2015/8/10.
 //

 #ifndef ICPC_P_HPP
 #define ICPC_P_HPP

 const double EPS = 1e-;

 int sig(double x) {
     if (fabs(x) < EPS)return ;
     return x <  ? - : ;
 }

 double add(double a, double b) {
     if (fabs(a + b) < EPS * (fabs(a) + fabs(b)))return ;
     return a + b;
 }

 class P {
 public:
     double x, y;

     P() { }

     P(double x, double y) : x(x), y(y) { }

     P  operator+(const P &p) {
         return P(add(x, p.x), add(y, p.y));
     }

     P operator-(const P &p) {
         return P(add(x, -p.x), add(y, -p.y));
     }

     P operator*(const double &d) {
         return P(x * d, y * d);
     }

     P operator/(const double &d) {
         return P(x / d, y / d);
     }

     double Dot(P p) {
         return x * p.x + y * p.y;
     }

     double dot(P p) {
         return add(x * p.x, y * p.y);
     }

     double Det(P p) {
         return x * p.y - y * p.x;
     }

     double det(P p) {
         return add(x * p.y, -y * p.x);
     }

     double abs() {
         return sqrt(abs2());
     }

     double abs2() {
         return dot(*this);
     }

     //绕原点旋转角度B（弧度值）产生新的点
     P rot(double rad) {
         return P(add(x * cos(rad), -y * sin(rad)), add(x * sin(rad), y * cos(rad)));
     }

     P rot90() {
         return P(-y, x);
     }

     bool equals(P p) {
         return compareTo(p) == ;
     }

     int compareTo(P p) {
         int b = sig(x - p.x);
         if (b != )return b;
         return sig(y - p.y);
     }

 };

 //判断点是否在线段上
 bool on_seg(P p1, P p2, P q) {
     return (p1 - q).det(p2 - q) ==  && (p1 - q).dot(p2 - q) <= ;
 }

 //求两条线段的交点
 P intersection(P p1, P p2, P q1, P q2) {
     return p1 + (p2 - p1) * ((q2 - q1).det(q1 - p1) / (q2 - q1).det(p2 - p1));
 }

 //线段相交判定
 bool crsSS(P p1, P p2, P q1, P q2) {
     if (max(p1.x, p2.x) + EPS < min(q1.x, q2.x))return false;
     if (max(q1.x, q2.x) + EPS < min(p1.x, p2.x))return false;
     if (max(p1.y, p2.y) + EPS < min(q1.y, q2.y))return false;
     if (max(q1.y, q2.y) + EPS < min(p1.y, p2.y))return false;
     /*(if((p1 - p2).det(q1 - q2) == 0){
         return (on_seg(p1,p2,q1) || on_seg(p1,p2,q2) || on_seg(q1,q2,p1) || on_seg(q1,q2,p2));
     }else{
         P r = intersection(p1,p2,q1,q2);
         return on_seg(p1,p2,r) && on_seg(q1,q2,r);

     }*/
     return (p2 - p1).det(q1 - p1) * (p2 - p1).det(q2 - p1) <=
            && (q2 - q1).det(p1 - q1) * (q2 - q1).det(p2 - q1) <= ;
 }

 //直线和线段相交判断
 bool crsLS(P l1, P l2, P s1, P s2) {
     return (s1 - l2).det(l1 - l2) * (s2 - l2).det(l1 - l2) <= ;
 }

 //直线相交判断
 //返回-1表示重合，0表示平行，1表示相交
 int crsLL(P p1, P p2, P q1, P q2) {
     if (sig((p1 - p2).det(q1 - q2)) != )return ;
     if (sig((p1 - q2).det(q1 - p2)) != )return ;
     return -;
 }

 //直线和直线的交点
 /*P isLL(P p1,P p2,P q1,P q2){
     double d = (q2 - q1).det(p2 - p1);
     if(sig(d)==0)return NULL;
     return intersection(p1,p2,q1,q2);
 }*/

 //点到直线的垂足
 P proj(P p1, P p2, P q) {
     return p1 + ((p2 - p1) * ((p2 - p1).dot(q - p1) / (p2 - p1).abs2()));
 }

 //直线到点的距离
 double disLP(P p1, P p2, P q) {
     return fabs((p2 - p1).det(q - p1)) / (p2 - p1).abs();
 }

 //线段到点的距离
 double disSP(P p1, P p2, P q) {
     if ((p2 - p1).dot(q - p1) <= )return (q - p1).abs();
     if ((p1 - p2).dot(q - p2) <= )return (q - p2).abs();
     return disLP(p1, p2, q);
 }

 //圆和线段相交的判定
 bool crsCS(P c, double r, P p1, P p2) {
     return disSP(p1, p2, c) < r + EPS && (r < (c - p1).abs() + EPS || r < (c - p2).abs() + EPS);
 }

 //圆与圆相交的判定
 bool crsCC(P c1, double r1, P c2, double r2) {
     double dis = (c1 - c2).abs();
     return dis < r1 + r2 + EPS && fabs(r1 - r2) < dis + EPS;
 }

 //四点共圆判定
 /*bool onC(P p1,P p2,P p3,P p4){
     P c = CCenter(p1,p2,p3);
     if(c == NULL) return false;
     return add((c - p1).abs2(), -(c - p4).abs2()) == 0;
 }*/

 //三点共圆的圆心
 /*P CCenter(P p1,P p2,P p3){
     //if(disLP(p1, p2, p3) < EPS)return NULL;//三点共线
     P q1 = (p1 + p2) * 0.5;
     P q2 = q1 + ((p1 - p2).rot90());
     P s1 = (p3 + p2) * 0.5;
     P s2 = s1 + ((p3 - p2).rot90());
     return isLL(q1,q2,s1,s2);
 }*/

 //求两圆的极角 以p为中心
 double polarangle(P p, P q) {
     return atan2(q.y - p.y, q.x - p.x);
 }

 bool cmp_x(const P &p, const P &q) {
     if (p.x != q.x) return p.x < q.x;
     return p.y < q.y;
 }

 vector<P> qs;

 void convex_hull(P *ps, int n) {
     sort(ps, ps + n, cmp_x);
     int k = ;
     qs.resize( * n);
     for (int i = ; i < n; qs[k++] = ps[i++]) {
         while (k >  && (qs[k - ] - qs[k - ]).det(ps[i] - qs[k - ]) < EPS)k--;
     }
     for (int i = n - , t = k; i >= ; qs[k++] = ps[i--]) {
         while (k > t && (qs[k - ] - qs[k - ]).det(ps[i] - qs[k - ]) < EPS)k--;
     }
     qs.resize(k - );
 }

 //求凸包的直径
 double convexDiameter() {
     int qsz = qs.size();
     if (qsz == )return ;
     if (qsz == ) {
         return (qs[] - qs[]).abs();
     }
     int i = , j = ;
     rep(k, qsz) {
         if (!cmp_x(qs[i], qs[k]))i = k;
         if (cmp_x(qs[j], qs[k])) j = k;
     }
     double res = ;
     int si = i, sj = j;
     while (i != sj || j != si) {
         res = max(res, (qs[i] - qs[j]).abs());
         if ((qs[(i + ) % qsz] - qs[i]).det(qs[(j + ) % qsz] - qs[j]) < ) i = (i + ) % qsz;
         else j = (j + ) % qsz;
     }
     return res;
 }

 #endif //ICPC_P_HPP

 P p[][];

 class TaskC {
 public:
     void solve(std::istream &in, std::ostream &out) {
         int n;
         in >> n;
         rep(i, n)
             rep(j, )in >> p[i][j].x >> p[i][j].y;
         double ans = ;
         rep(i, n)
             rep(l1, ) {
                 P p1 = p[i][l1];
                 rep(j, n) {
                     if (i == j)continue;
                     rep(l2, ) {
                         P p2 = p[j][l2];
                         double sum = p1.Det(p2) * 0.125;
                         p2 = p2 - p1;
                         rep(k, n) {
                             if (i == k || j == k)continue;
                             if (sig(sum) == )break;
                             int num = ;
                             rep(l3, ) {
                                 if (p2.Det(p[k][l3] - p1) > );
                                 else num++;
                             }
                             sum *= num/2.0;
                         }
                         ans += sum;
                     }
                 }
             }
         out << fixed << setprecision() << fabs(ans) << endl;
     }
 };

 int main() {
     std::ios::sync_with_stdio(false);
     std::cin.tie();
     TaskC solver;
     std::istream &in(std::cin);
     std::ostream &out(std::cout);
     solver.solve(in, out);
     return ;
 }

代码君

当然，对于这题你也可以对于每个点先求出所有点的极角，排个序然后来做。这样就可以从O(n^3)变成O(n^2logn)了

还剩下D题还是不会做，待以后再补