之前觉得不可做的一道题.然后昨天听mhy一句话瞬间懂:几何反演.然后mhy说这题用cdq?骗我读书少呢? html写公式好郁闷.把设圆心是(p,q),点是(x,y),那么点在圆内的条件是 (p-x)2+(q-y)2 ≤ p2+q2 转化一下变成 q ≥ -(x/y) * p + (x2+y2) / (y*2) 然后就可以把(p,q)看作一个点,每个询问就是询问之前的所有点是否都在这条直线的上方. 那么直接归并排序喽.处理出左边的凸壳再单调扫一遍右边的所有直线.这样复杂度是O(n*logn),又短又快yeah. 然后还听说有精度误差?我全程double没用eps也没出事啊hhh
#include #include #include using namespace std; #define _l (long long int) const int maxc = 23; const int maxn = 50009; const int mod = 19940417; struct dat { int a[maxc], t; inline dat() { memset(a, 0, sizeof(a)); a[0] = 1; t = 0; } inline int& operator[](const int& x) { return a[x]; } inline int operator[](const int& x) const { return a[x]; } void add(int); void rev(); }; struct seg { int l, r, rv, a; dat d; seg *ch[2]; inline void update(); inline void catTag(int ta, int tr) { if (tr) { a = (mod - a) % mod; d....
最近整个人都被Sone1搞得头昏脑胀。不爽ing。 这个题其实就是线段树+维护的题。考虑给一个区间里每个数加C的时候的式子会变成什么样就好了。 然后要注意标记得随时下传，不能永久化。 然后感觉时间有点慢不过跑起来还将就。 然后我太弱了。
毫无违和感的一天. 第一题只会40分的O(n2)级别的东西.正解没看懂. 第二题想着想着就差点睡着.正解感觉比较神奇.自己还没有把sam吃透啊. 第三题好神ovo 下午总结交流感觉好像还是有好多之前想到的东西忘讲了ovo还忘卡时了ovo每次上台都会紧张,得多练. 所以窝还是太弱辣.
#include #include #include using namespace std; #define upMax(a,b) { if (a < b) a = b; } #define upMin(a,b) { if (a > b) a = b; } struct kdnode { int p[2], a[2][2], v, s; kdnode *ch[2]; inline void update() { a[0][0] = a[1][0] = p[0]; a[0][1] = a[1][1] = p[1]; s = v; if (ch[0]) { upMin(a[0][0], ch[0]-> a[0][0]); upMin(a[0][1], ch[0]-> a[0][1]); upMax(a[1][0], ch[0]-> a[1][0]); upMax(a[1][1], ch[0]-> a[1][1]); s += ch[0]-> s; } if (ch[1]) { upMin(a[0][0], ch[1]-> a[0][0]); upMin(a[0][1], ch[1]-> a[0][1]); upMax(a[1][0], ch[1]-> a[1][0]); upMax(a[1][1], ch[1]-> a[1][1]); s += ch[1]-> s; } } };...
import java.util.; import java.math.; class Main { static int n, m, a[], tp, pn[]; static BigInteger f[][]; static boolean pr[], fl[][]; static void pre() { int maxm = 30; pr = new boolean[maxm]; pn = new int[maxm]; pn[0] = 1; tp = 1; for (int i = 0; i < maxm; ++ i) pr[i] = false; for (int i = 2; i < maxm; ++ i) { if (!pr[i]) pn[tp ++] = i; for (int j = 1; j < tp && i * pn[j] < maxm; ++ j) { pr[i * pn[j]] = true; if (i % pn[j] == 0) break; } } } public static void main(String args[]) { Scanner cin = new Scanner(System....
ioi好神啊,居然写搜索.我显然是不想写高精的啦于是用java于是花费了整整两节课TT 我的想法是dp.设答案为f[m],那么f[m]只与fd有关.设f[i][j]表示i为m的第i小的约数,且已经用了前j个素数的答案.然后就可以转移辣. 然后得二分一下用多大的素数可以卡过.毕竟java自带大常数.而且bzoj坑爹在不管有多少组数据都只多给2秒总时限ovo
#include #include #include #include #include using namespace std; typedef long long dint; #ifdef WIN32 #define lld “%I64d” #else #define lld “%lld” #endif #define _l (long long int) struct range { int l, r; }; inline bool operator <(const range& a, const range& b) { return a. l + a. r < b. l + b. r; } struct bridge { static const int maxn = 200009; int ha[maxn], hb[maxn], ta, tb; dint sa, sb; inline void clr() { ta = tb = sa = sb = 0; } bridge() { clr(); } void balance() { while (ta > tb + 1) { hb[tb] = -ha[0]; sa -= ha[0]; sb += hb[tb]; pop_heap(ha, ha + ta –); push_heap(hb, hb + ++ tb); } while (ta < tb + 1) { ha[ta] = -hb[0]; sb -= hb[0]; sa += ha[ta]; pop_heap(hb, hb + tb –); push_heap(ha, ha + ++ ta); } } inline void ins(int x) { if (x <= ha[0]) { sa += x; ha[ta] = x; push_heap(ha, ha + ++ ta); } else { sb -= x; hb[tb] = -x; push_heap(hb, hb + ++ tb); } balance(); } inline dint qry() { return _l ha[0] * (ta - tb) - sa - sb; } };...
这是apio里我最自豪的一道题了.让三分党去…吧. k=1直接在所有坐标的中位数处建桥就行了不要问我为什么. 首先感受一下发现可以按(a+b)把序列分成两半,然后两半就是k=1的情况嘛.那直接处理一下每个前缀和后缀的答案就完了辣.
#include #include #include #include #include using namespace std; struct edge { int t, v; edge* next; }; const int maxn = 30009; const int bsz = 80; const int maxb = 83; const int maxnd = maxn * maxb; const int ebsz = 1000001; int n, m, st, te, d[maxnd], tnid, nid[maxb][maxn]; edge *head[maxnd]; inline void addEdge(int u, int v, int w) { static edge* ebuf; static int cnt(0); if (!...