1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 | #include <cstdio> #include <cstdlib> #include <algorithm> #include <iostream> #include <vector> #include <cmath> typedef long double ld; const ld EPS = 1e-8; const ld SIM_EPS = 1e-8; const ld INF = 1e100; using std::vector; struct Vect { ld x, y; Vect(ld _x, ld _y) { x = _x, y = _y; } Vect() {} }; struct Line { ld y; bool ch; Line(ld _y, bool _ch) { y = _y, ch = _ch; } Line() {} bool operator<(const Line &b) const { return y > b.y; } }; typedef std::pair<ld, ld> Pair_t; typedef vector<Vect> VectArr_t; typedef vector<Pair_t> PairArr_t; typedef vector<Line> LineArr_t; ld lfabs(ld x) { return x < 0 ? -x : x; } struct Poly { VectArr_t arr; Pair_t bound; void get_seg(ld x0, PairArr_t *seq) { if (x0 - bound.first < -EPS || x0 - bound.second > EPS) return; static LineArr_t res; res.clear(); Vect o(x0, 0); for (VectArr_t::iterator it = arr.begin(); it != arr.end() - 1; it++) { Vect st = *it, ed = *(it + 1); ld dl = x0 - st.x, dr = x0 - ed.x; ld dd = dl * dr; if (dd < EPS) { ld dx = ed.x - st.x; if (lfabs(dx) > EPS) { res.push_back( Line(st.y + (ed.y - st.y) * dl / dx, (lfabs(dd) < EPS ? (dl > EPS || dr > EPS) : 1) ) ); } } } if (res.begin() == res.end()) return; std::sort(res.begin(), res.end()); bool t = res.begin() -> ch; for (LineArr_t::iterator it = res.begin() + 1; it != res.end(); it++) { ld prev = (it - 1) -> y, now = it -> y; t ^= it -> ch; if (!(t & 1)) seq -> push_back(Pair_t(now, prev)); } } }; typedef vector<Poly> PolyArr_t; PolyArr_t polys; ld f(ld x) { static PairArr_t seq; seq.clear(); Pair_t t; for (PolyArr_t::iterator it = polys.begin(); it != polys.end(); it++) it -> get_seg(x, &seq); std::sort(seq.begin(), seq.end()); ld res = 0, inc = 0, r = -INF; for (PairArr_t::iterator it = seq.begin(); it != seq.end(); it++) if (it -> second > r) { if (it -> first > r) { res += inc; inc = it -> second - it -> first; } else inc += it -> second - r; r = it -> second; } return res + inc; } ld s(ld l, ld r, ld fl, ld fm, ld fr) { return (r - l) / 6.0 * (fl + 4 * fm + fr); } ld sim(ld l, ld r, ld fl, ld fm, ld fr) { ld m = (l + r) / 2; ld flm = f((l + m) / 2), frm = f((m + r) / 2); ld al = s(l, r, fl, fm, fr), sl = s(l, m, fl, flm, fm), sr = s(m, r, fm, frm, fr); if (lfabs(sl + sr - al) < SIM_EPS) return al; return sim(l, m, fl, flm, fm) + sim(m, r, fm, frm, fr); } ld L = INF, R = -INF; PairArr_t interv; void pre_work() { int N, n; ld x, y, x0, y0; double alpha = 0 / 180 * M_PI; scanf("%d", &N); for (int i = 1; i <= N; i++) { Poly t; ld l = INF, r = -INF; scanf("%d", &n); for (int j = 1; j <= n; j++) { scanf("%Lf %Lf", &x0, &y0); x = x0 * cos(alpha) + y0 * sin(alpha); y = y0 * cos(alpha) - x0 * sin(alpha); l = std::min(l, x); r = std::max(r, x); t.arr.push_back(Vect(x, y)); } t.arr.push_back(*t.arr.begin()); t.bound = Pair_t(l, r); polys.push_back(t); interv.push_back(t.bound); L = std::min(L, l); R = std::max(R, r); } } void work() { ld ans = 0; ld fl = f(L), fm = f((L + R) / 2), fr = f(R); ans += sim(L, R, fl, fm, fr); printf("%.2Lf\n", ans); } int main() { freopen("simpson.in", "r", stdin); pre_work(); work(); return 0; } |
Archive for the ‘OI’ Category
用Simpson求多边形面积并
神一般的Dinic
啥也不解释,直接上代码:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 | #include <cstdio> #include <cstring> #include <cstdlib> #include <algorithm> const int MAXVTX = 200000 + 2; const int MAXE = 100000 + MAXVTX * 2; const int MAXPE = MAXE * 2; const int INF = 0x3f3f3f3f; struct Edge { int to, ca; Edge *next, *inv; } edges[MAXPE + 1], *head[MAXVTX + 1]; int N, M, S, T, vcnt, ecnt; Edge *add_edge(int st, int ed, int ca) { Edge *ptr = edges + (++ecnt); ptr -> next = head[st]; ptr -> to = ed; ptr -> ca = ca; return head[st] = ptr; } void add_pair(int st, int ed, int ca) { Edge *e1 = add_edge(st, ed, ca); Edge *e2 = add_edge(ed, st, 0); e1 -> inv = e2; e2 -> inv = e1; } #define RPART(x) ((x) << 1) #define LPART(x) (RPART(x) - 1) void pre_work() { int st, ed; scanf("%d %d", &N, &M); S = RPART(N) + 1, T = S + 1; vcnt = T; for (int i = 1; i <= M; i++) { scanf("%d %d", &st, &ed); add_pair(LPART(st), RPART(ed), 1); } for (int i = 1; i <= N; i++) { add_pair(S, LPART(i), 1); add_pair(RPART(i), T, 1); } } int dist[MAXVTX + 1]; bool relabel() { static int q[MAXVTX], v; memset(dist + 1, -1, sizeof(int) * vcnt); dist[*q = S] = 0; for (int l = 0, r = 1; l != r; l++) { int u = q[l]; for (Edge *i = head[u]; i; i = i -> next) if (i -> ca && dist[v = i -> to] == -1) q[r++] = v, dist[v] = dist[u] + 1; } return dist[T] != -1; } int find_aug(int u, int flow) { if (u == T) return flow; int res = 0, v, t; Edge *i; for (i = head[u]; i; i = i -> next) if (i -> ca && (dist[v = i -> to] == dist[u] + 1)) { res += t = find_aug(v, std::min(i -> ca, flow)); i -> ca -= t, i -> inv -> ca += t; if (!(flow -= t)) break; } if (!i) dist[u] = -1; return res; } int dinic() { int res = 0; while (relabel()) res += find_aug(S, INF); return res; } void work() { printf("%d\n", N - dinic()); } int main() { pre_work(); work(); return 0; } |
最BT的数论题——解高次同余方程
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 | #include <cstdio> #include <cstring> #include <cstdlib> #include <algorithm> #include <cmath> #include <map> typedef long long ll; const int MAXP = 100000; int p[MAXP], pcnt; int T, ans, N; void get_primes(int R) { bool comp[MAXP]; for (int i = 2; i <= R; i++) { if (!comp[i]) p[++pcnt] = i; int bound = R / i; for (int j = 1; j <= pcnt && p[j] <= bound; j++) { comp[i * p[j]] = 1; if (!(i % p[j])) break; } } } ll pow(ll b, ll p, ll m) { ll res = 1, e = b; while (p) { if (p & 1) res = (res * e) % m; e = (e * e) % m; p >>= 1; } return res; } ll inv(ll x, ll m) { return pow(x, m - 2, m); } bool check_proot(ll m, ll r) { ll x = m - 1; get_primes(int(sqrt(x))); for (int i = 1; i <= pcnt; i++) if (!(x % p[i])) { if (pow(r, (m - 1) / p[i], m) == 1) return 0; while (!(x % p[i])) x /= p[i]; } if (x != 1 && pow(r, (m - 1) / x, m) == 1) return 0; return 1; } ll get_proot(ll m) { if (m == 2) return 1; for (int i = 2; i < m; i++) if (check_proot(m, i)) return i; } typedef std::map<int, int> Hash_t; int discrete_log(int b, int a, int m) { Hash_t hash; int d = int(sqrt(m - 2)); for (int j = 0; j < d; j++) hash[int((a * inv(pow(b, j, m), m)) % m)] = j; int t = 1; for (int i = 0; i * d <= m - 2; i++) { if (hash.count(t)) return hash[t] + d * i; t = (t * pow(b, d, m)) % m; } } ll ext_gcd(ll a, ll b, ll &x, ll &y) { if (b == 0) { x = 1, y = 0; return a; } int ret = ext_gcd(b, a % b, x, y); int ox = x; x = y, y = ox - a / b * y; return ret; } ll get_ft(ll t) { if (t == 1) return 2; int bound = int(sqrt(t)); for (int i = 2; i <= bound; i++) if (!(t % i)) return 2; return t; } int sol[100000], scnt; int solve(int m) { ll r = get_proot(m); ll p = N, d = m - 1, c = discrete_log(r, ans, m); ll x, y, lb, rb; ll g = ext_gcd(p, d, x, y); if (c % g) return -1; // no solution x = c * x / g, y = c * y / g; // find a special solution lb = ll(ceil(double(x - (m - 2)) * g / d)); rb = ll(floor(double(x) * g / d)); for (int t = lb; t <= rb; t++) sol[++scnt] = x - d / g * t; // generate all solutions return r; } void pre_work() { int A, s, w; scanf("%d %d %d %d", &N, &ans, &T, &A); for (int i = 1; i < N; i++) scanf("%d %d", &s, &w); // read rubbish } int cmp_int(int a, int b) { return a < b; } void work() { int m = get_ft(T); if (ans == 0) sol[scnt = 1] = 0; else { int r = solve(m); if (r != -1) for (int i = 1; i <= scnt; i++) sol[i] = pow(r, sol[i], m); } for (int i = 1; i <= scnt; i++) sol[i] = ((sol[i] + 1) * pow(sol[i], N - 1, m)) % m; std::sort(sol + 1, sol + scnt + 1, cmp_int); scnt = std::unique(sol + 1, sol + scnt + 1) - sol - 1; printf("%d\n", scnt); for (int i = 1; i <= scnt; i++) printf("%d ", sol[i]); printf("\n"); } int main() { freopen("WA.in", "r", stdin); freopen("WA.out", "w", stdout); pre_work(); work(); return 0; } |
Summary for SCTSC
对我来说最后一次的省选已经结束了, 有一些遗憾,但我无悔。
第一试一般,第二试爆了,于是就与正式名额无缘了。
如果总的来说,总分弱弱,是由于没有把自己的水平发挥出来。
什么叫“发挥出水平呢”,我不禁自问。
其实也很好衡量,坐时光机去拉来去年的我来考今年的试,分数基本也不会比110低。
差分约束暑假就学会了。去年的我,剩下就裸点分,说不定还因为学插头DP不久,一咬牙把一试二题做了。
事实是,今年的我肯定比去年的牛x多了。但是多的这些东西,也就是说一年来的练习,思考做题,最终没有在考场上转化为生产力。
Theo的一句话点到了本质:“看你做了那么多题,没有什么效果啊。”
对,目前的问题就是这个。
不谈和别人的比较,单单就自己而言,水平是可以进队的,使使劲NOI也是可以拿银牌的。
如果说会的占1,那么我能尽多大限度发挥,是10%,还是50%, 抑或是90%,甚至200%?
在比赛前固然可以提高那个1来保证即使是10%也能因为1的扩大而扩大。但是事实是,提高百分比更为有效,它能让自己努力立竿见影,也能完全显露自己几斤几两。
我们不能总期待题有所谓的高区分度,能做的是在相同情况下,把自己的十八般武艺展现无疑,那么自然就没有遗憾了。
善,为之奈何?
就拿一试二题来说,这道题虽说是一个典型的插头DP,却并不是基于连通性的,讨论的情况也相当清晰明了,况且联赛前的暑假专门练习了4、5道相关的题目。但是因为我考前曾经对自己说过,如果有插头DP就果断裸搜,于是就放弃了进一步的思考。我在这一刻害怕了。相反,一些没有做过连通性插头DP的同学反而想得简单明了,得了相当可观的分数。
如果学会做一个自己都不敢在考场写的东西,那还不如学些别的。换而言之,在这个特殊时期,知识一定要设法让它变成生产力。
另外在考试中暴露出来的一个问题是,我临场思维时间太长了,容易陷进去,这是在考前就知道的,但是即便是知道,临场时也难逃厄运。虽然说二试一题,我在读完题后就断定这题我能拿80分,但是在思考实现的问题上,不断的修改原来的想法,一时间很多想法以及问题涌上来,等我按照想法写好,却发现考虑漏了,于是就在原来繁琐的算法基础上修修改改。(把某些部分变得更裸)但是这个是导致我二试爆掉的直接原因,本来应该推翻重来,写个平衡树和并差集就轻松拿到80,但是我当时思维已经陷进去,不能自拔,在原来的基础上反反复复修改,脑袋一度一片空白。
看了三题,想的时候又始终不忘一题。原本制定好的先做80分一题,再使劲强攻三题的计划已被打乱。败局已定。
虽然我在前段时间的训练中,对自己编码时间进行了缩短,但是有很多题是我想来想去,想了好一会儿,
然后再敲出来的。我并没有把思考的这部分时间进行刻意压缩,而是信马由缰,想够。虽然这对我思考能力提升有帮助,但是比赛是在有一定压力和紧张的情况下进行的,平时那种闲庭信步的坦然在临场时就可能会荡然无存。而进入状态越快,思维不会随思考加深而迟钝的人才会在考场上从容不迫。在一个思路已经复杂繁琐难以琢磨了以后真的要学会舍弃,有舍才有得。
今后的考试就要努力调整,给自己制造紧张感,把每场考试当作省选或是NOI。
在八中OJ上做题,要进行思考和实现的双重控时,并虚心听取他人意见和新思路,不断改进,做最好的自己。
Yesterday && TOMORROW
5月的时光在机翼和奔走脚步间流逝。简而言之,CTSC乱考,APIO纯windows无vim环境吃不消故二题不敢展开写,在FDU举办的Google杯ACM全国邀请赛被江苏的各种神队虐。最终结果是:CTSC无奖,APIO Cu牌,ACM目前不确定铜奖还是银奖(75名,只做了3题,其实后来发现有5道都是可做的)。
在APIO及其不爽的考试过后,我果断在windows下写题,至于对拍的问题,在北京最后几天我们和lrj的闲谈中我提及此事,他说他写的一本书上有可用的bat脚本,于是看了一下发现可以用,但是linux的管道在windows下不知道有没有替代品。
明天就是传说中的省选了。近来经历为我指明了考试方向:
1.我不是神牛,把会做的做起,不会做的暴力,然后喝点水开始研究不会做的,骗个什么分。
2.前几名不是咱的,不要去想
3.当一道题的想法开始“收敛”,猜想的做法开始变得繁琐而ws时,继续思考已经失去意义,即便是想出来了,不见得能在短时间写出来。所以思考要用EPS来剪枝。
4.拿到题无论某道题多么简单,都要通读全题
bless all