2013多校训练赛第三场总结

HDU 4621~4631

　　今天的多校好变态，是IOI冠军出的题，把我们虐的半死了。

　　简单讲一下今天的情况，今天就只做了两道水题，算是签了个到，然后就卡1011（HDU 4631）一个下午了。其实感觉今天1009的几何是可以做的，因为我之前也做过类似的题，不过最后还是因为没信心做，所以放弃了。目测是可以用PSLG来做1009的，不过当时计算了一下最坏复杂度，觉得会超时，一直没做。

　　1011啱看上去是kd树，不过当时搞了好久都还是超时。开始的时候我直接上标准kd树，不带平衡功能的，各种超时。然后我就改成预处理整棵树，然后就用标记法来搞点的插入，理论上平均能达到O(log n)每次操作的，因为树的结点是固定下来的。不过最意想不到的是，这样做的kd树最后还是退化了，随便搞一组case就跑了个本地21s，虽然很多500k的数据还是能12s内出答案的。

　　然后我就加上更多的标记，原来12s的变成7s了，优化了不少。然后还是被我找到要20s+才能出答案的数据。。。_(:з」∠)_这题就一直卡到最后了。

今天0贡献，代码不用队友的，重写了一遍：

4631 ( Sad Love Story )

　　居然用set能过，真是大开眼界了。

 1 #include <iostream>
 2 #include <set>
 3 #include <algorithm>
 4 #include <cstring>
 5 #include <cstdio>
 6 #include <ctime>
 7 
 8 using namespace std;
 9 
10 typedef long long LL;
11 typedef pair<int, int> PII;
12 template<class T> T sqr(T x) { return x * x;}
13 LL dist(PII a, PII b) { return sqr((LL) a.first - b.first) + sqr((LL) a.second - b.second);}
14 #define ITOR iterator
15 set<PII> pts;
16 
17 int main() {
18     int T, n;
19     int ax, bx, cx, ay, by, cy;
20     cin >> T;
21     while (T--) {
22         cin >> n >> ax >> bx >> cx >> ay >> by >> cy;
23         //time_t t1 = clock();
24         pts.clear();
25         int x = 0, y = 0;
26         LL sum = 0, mn = 1ll << 62, dis;
27         set<PII>::ITOR si, c;
28         PII cur;
29         for (int i = 0; i < n; i++) {
30             x = ((LL) ax * x + bx) % cx;
31             y = ((LL) ay * y + by) % cy;
32             cur = PII(x, y);
33             if (mn == 0) break;
34             if (pts.find(cur) != pts.end()) { mn = 0; break;}
35             pts.insert(cur);
36             c = si = pts.find(cur);
37             c++;
38             while (c != pts.end()) {
39                 dis = dist(cur, *c);
40                 mn = min(mn, dis);
41                 if (sqr((LL) (*c).first - cur.first) >= mn) break;
42                 c++;
43             }
44             c = si;
45             while (true) {
46                 if (c == pts.begin()) break;
47                 c--;
48                 dis = dist(cur, *c);
49                 mn = min(mn, dis);
50                 if (sqr((LL) (*c).first - cur.first) >= mn) break;
51             }
52             if (i) sum += mn;
53         }
54         cout << sum << endl;
55         //cout << "time " << (double) (clock() - t1) / CLOCKS_PER_SEC << endl;
56     }
57     return 0;
58 }

View Code

4628 ( Pieces )

　　直接状态压缩然后暴力dp枚举子集，for (int j = i; j; j = (j - 1) & i) ;

 1 #include <iostream>
 2 #include <algorithm>
 3 #include <cstdio>
 4 #include <cstring>
 5 
 6 using namespace std;
 7 
 8 const int N = 1 << 16;
 9 bool vis[N];
10 int dp[N], top;
11 char str[22], cur[22];
12 
13 bool check() {
14     int s = 0, t = top;
15     while (s < t) if (cur[s++] != cur[t--]) return false;
16     return true;
17 }
18 
19 void dfs(int p, int len, int st) {
20     if (p >= len) {
21         if (check()) vis[st] = true;
22         return ;
23     }
24     cur[++top] = str[p];
25     dfs(p + 1, len, st | 1 << p);
26     top--;
27     dfs(p + 1, len, st);
28 }
29 
30 int DP(int len) {
31     memset(dp, 127, sizeof(dp));
32     dp[0] = 0;
33     for (int i = 1, e = 1 << len; i < e; i++) {
34         for (int j = i; j; j = (j - 1) & i) {
35             if (vis[j]) dp[i] = min(dp[i ^ j] + 1, dp[i]);
36         }
37     }
38     return dp[(1 << len) - 1];
39 }
40 
41 
42 int main() {
43     int T;
44     cin >> T;
45     while (T-- && cin >> str) {
46         memset(vis, 0, sizeof(vis));
47         top = -1;
48         dfs(0, strlen(str), 0);
49         //for (int i = 0; i < (1 << strlen(str)); i++) cout << i << ' ' << vis[i] << endl;
50         cout << DP(strlen(str)) << endl;
51     } 
52     return 0;
53 }

View Code

4627 ( The Unsolvable Problem )

　　分3种情况，一种是奇数的时候，直接分解成n/2和n/2+1相乘即可，偶数有两种，其实就是枚举(n/2-1)和(n/2+1)、(n/2-2)和(n/2+2)两个的gcd。

 1 #include <cstdio>
 2 #include <iostream>
 3 #include <algorithm>
 4 #include <cstring>
 5 
 6 using namespace std;
 7 
 8 typedef long long LL;
 9 inline LL gcd(LL a, LL b) { return b ? gcd(b, a % b) : a;}
10 inline LL lcm(LL a, LL b) { return a / gcd(a, b) * b;}
11 
12 int main() {
13     int T;
14     LL n;
15     cin >> T;
16     while (T-- && cin >> n) {
17         if (n & 1) cout << (n >> 1) * ((n >> 1) + 1) << endl;
18         else {
19             LL m = n >> 1, ans = m;
20             for (int i = 1; i <= 2; i++) {
21                 if (m - i <= 0) break;
22                 ans = max(ans, lcm(m + i, m - i));
23             }
24             cout << ans << endl;
25         }
26     }
27     return 0;
28 }

View Code

　　总的来说，这次就是被惨虐。一个原因是最近在恶补基础，没有锻炼思维的灵活性，题目稍微变形就只会死板的解题是不行的。在补完基础以后再加强一下！

UPD：

4629（Burning）

　　PSLG简单模型。

  1 #include <iostream>
  2 #include <algorithm>
  3 #include <cstdio>
  4 #include <cstring>
  5 #include <cmath>
  6 #include <ctime>
  7 #include <vector>
  8 #include <map>
  9 #include <set>
 10 
 11 using namespace std;
 12 
 13 const int N = 11111;
 14 const double EPS = 1e-8;
 15 template<class T> T sqr(T x) { return x * x;}
 16 inline int sgn(double x) { return (x > EPS) - (x < -EPS);}
 17 struct Point {
 18     double x, y;
 19     int id;
 20     Point() {}
 21     Point(double x, double y) : x(x), y(y) {}
 22     Point operator + (Point a) { return Point(x + a.x, y + a.y);}
 23     Point operator - (Point a) { return Point(x - a.x, y - a.y);}
 24     Point operator * (double p) { return Point(x * p, y * p);}
 25     Point operator / (double p) { return Point(x / p, y / p);}
 26     bool operator < (Point a) const { return sgn(x - a.x) < 0 || sgn(x - a.x) == 0 && y < a.y;}
 27     bool operator == (Point a) const { return sgn(x - a.x) == 0 && sgn(y - a.y) == 0;} 
 28 } ips[N];
 29 
 30 inline double cross(Point a, Point b) { return a.x * b.y - a.y * b.x;}
 31 inline double dot(Point a, Point b) { return a.x * b.x + a.y * b.y;}
 32 inline double veclen(Point x) { return sqrt(dot(x, x));}
 33 inline Point vecunit(Point x) { return x / veclen(x);}
 34 inline Point normal(Point x) { return Point(-x.y, x.x) / veclen(x);}
 35 
 36 struct Line {
 37     Point s, t;
 38     Line() {}
 39     Line(Point s, Point t) : s(s), t(t) {}
 40     Point vec() { return t - s;}
 41     Point point(double d) { return s + vec() * d;}
 42 } ;
 43 
 44 inline Point llint(Line a, Line b) { return a.point(cross(b.vec(), a.s - b.s) / cross(a.vec(), b.vec()));}
 45 inline bool onseg(Point x, Point a, Point b) { return sgn(cross(a - x, b - x)) == 0 && sgn(dot(a - x, b - x)) <= 0;}
 46 
 47 int ptinpoly(Point p, Point *pt, int n) {
 48     int wn = 0;
 49     pt[n] = pt[0];
 50     for (int i = 0; i < n; i++) {
 51         if (onseg(p, pt[i], pt[i + 1])) return -1;
 52         int k = sgn(cross(pt[i + 1] - pt[i], p - pt[i]));
 53         int d1 = sgn(pt[i].y - p.y);
 54         int d2 = sgn(pt[i + 1].y - p.y);
 55         if (k > 0 && d1 <= 0 && d2 > 0) wn++;
 56         if (k < 0 && d2 <= 0 && d1 > 0) wn--;
 57     }
 58     return wn != 0;
 59 }
 60 
 61 Point tri[55][4], pts[222];
 62 typedef pair<double, int> PDI;
 63 typedef pair<int, int> PII;
 64 vector<PDI> rel[N];
 65 map<int, int> nxp[N];
 66 set<PII> vis;
 67 double ans[55];
 68 
 69 inline double angle(Point x) { return atan2(x.y, x.x);}
 70 bool operator < (PDI a, PDI b) { return sgn(a.first - b.first) < 0 || sgn(a.first - b.first) == 0 && a.second < b.second;}
 71 bool operator == (PDI a, PDI b) { return sgn(a.first - b.first) == 0 && a.second == b.second;}
 72 
 73 int main() {
 74     //freopen("in", "r", stdin);
 75     int T, n, m;
 76     scanf("%d
", &T);
 77     while (T-- && ~scanf("%d", &n)) {
 78         m = 0;
 79         for (int i = 0; i < n; i++) {
 80             for (int j = 0; j < 3; j++) {
 81                 scanf("%lf%lf", &tri[i][j].x, &tri[i][j].y);
 82                 ips[m++] = tri[i][j];
 83             }
 84             tri[i][3] = tri[i][0];
 85         }
 86         Line a, b;
 87         for (int i = 0; i < n; i++) {
 88             for (int j = 0; j < 3; j++) {
 89                 a = Line(tri[i][j], tri[i][j + 1]);
 90                 for (int x = i + 1; x < n; x++) {
 91                     if (i == x) continue;
 92                     for (int y = 0; y < 3; y++) {
 93                         b = Line(tri[x][y], tri[x][y + 1]);
 94                         if (sgn(cross(a.vec(), b.vec()))) {
 95                             ips[m] = llint(a, b);
 96                             if (onseg(ips[m], a.s, a.t) && onseg(ips[m], b.s, b.t)) m++;
 97                         }
 98                     }
 99                 }
100             }
101         }
102         sort(ips, ips + m);
103         m = (int) (unique(ips, ips + m) - ips);
104         for (int i = 0; i < m; i++) ips[i].id = i, rel[i].clear(), nxp[i].clear();
105         for (int i = 0; i < n; i++) {
106             for (int j = 0; j < 3; j++) {
107                 int t = 0;
108                 for (int k = 0; k < m; k++) {
109                     if (onseg(ips[k], tri[i][j], tri[i][j + 1])) pts[t++] = ips[k];
110                 }
111                 sort(pts, pts + t);
112                 for (int i = 1; i < t; i++) {
113                     rel[pts[i].id].push_back(PDI(angle(pts[i - 1] - pts[i]), pts[i - 1].id));
114                     rel[pts[i - 1].id].push_back(PDI(angle(pts[i] - pts[i - 1]), pts[i].id));
115                 }
116             }
117         }
118         for (int i = 0; i < m; i++) {
119             sort(rel[i].begin(), rel[i].end());
120             int t = (int) (unique(rel[i].begin(), rel[i].end()) - rel[i].begin());
121             while (rel[i].size() > t) rel[i].pop_back();
122             if (t) {
123                 rel[i].push_back(rel[i][0]);
124                 for (int j = 0; j < t; j++) nxp[rel[i][j + 1].second][i] = rel[i][j].second;
125                 rel[i].pop_back();
126             }
127         }
128         vis.clear();
129         memset(ans, 0, sizeof(ans));
130         Point mid, nor;
131         for (int i = 0, t; i < m; i++) {
132             int sz = rel[i].size();
133             for (int j = 0; j < sz; j++) {
134                 if (vis.find(PII(i, rel[i][j].second)) != vis.end()) continue;
135                 double tmp = 0;
136                 int c = i, nx = rel[i][j].second;
137                 while (vis.find(PII(c, nx)) == vis.end()) {
138                     tmp += cross(ips[c], ips[nx]);
139                     vis.insert(PII(c, nx));
140                     t = c, c = nx, nx = nxp[t][c];
141                 }
142                 c = i, nx = rel[i][j].second;
143                 nor = normal(ips[nx] - ips[c]) * 1e-4;
144                 mid = (ips[c] + ips[nx]) / 2 + nor;
145                 int cnt = 0;
146                 for (int i = 0; i < n; i++) {
147                     if (ptinpoly(mid, tri[i], 3)) cnt++;
148                 }
149                 ans[cnt] += tmp;
150             }
151         }
152         for (int i = 1; i <= n; i++) printf("%.6f
", ans[i] / 2);
153     }
154     return 0;
155 }

View Code

——written by Lyon

2013多校训练赛第三场 总结

2013多校训练赛第三场总结