Views

#include #include #include using namespace std; struct edge { int t; edge *next; }; const int maxn = 100009; const int maxe = 600009; const int maxst = 800009; int n, m, vis[maxn], dfn[maxn], low[maxn], tscc, fs[maxn], ssz[maxn], ind[maxn]; edge ebuf_arr[maxe], *ebuf(ebuf_arr), *head[maxn], *hg[maxn]; inline void addEdge(edge** head, int u, int v) { ebuf-> t = v; ebuf-> next = head[u]; head[u] = ebuf ++; } void tarjanDFS(int po) { static int stc[maxst], stv[maxn], stt[maxn], fr[maxn], d[maxn]; int tsc(1), tsv(0), tst(0), dfi(0); d[stc[tsc] = po] = 1; vis[po] = 1; while (tsc) { int p(stc[tsc –]); if (dfn[p]) continue; for (; tsv && d[p] <= d[stv[tsv]]; – tsv) { low[fr[stv[tsv]]] = min(low[fr[stv[tsv]]], low[stv[tsv]]); if (low[stv[tsv]] == dfn[stv[tsv]]) { ssz[++ tscc] = 0; do { vis[stt[tst]] = 2; ++ ssz[fs[stt[tst]] = tscc]; } while (stt[tst –] !...

#include #include #include using namespace std; struct edge { int t; edge *next; }; const int maxn = 100009; int n, m, ind[maxn], hp[maxn], q[maxn]; edge ebuf_arr[maxn], *ebuf, *head[maxn]; inline void addEdge(int u, int v) { ebuf-> t = v; ebuf-> next = head[u]; head[u] = ebuf ++; } void sov() { memset(ind, 0, sizeof(ind)); memset(head, 0, sizeof(head)); ebuf = ebuf_arr; scanf("%d%d", &n, &m); for (int i = 0; i < m; ++ i) { int u, v; scanf("%d%d", &u, &v); addEdge(v, u); ++ ind[u]; } int th(0), tq(0); for (int i = 1; i <= n; ++ i) if (!...

bzoj都3k道题了ovo hnoi的题好强. 这个题就建反图然后跑topsort就行了.每次选能选的里最大的扔进去.最后倒过来输出. 我也是猜的然后交上去居然是对的. 为什么呢?好神奇?

#include #include #include #include #include using namespace std; #ifdef WIN32 #define randInt ((rand()«16)|rand()) #else #define randInt (rand()) #endif const double eps = 1e-11; const double pi = acos(-1); inline double sqr(const double& x) { return x * x; } inline int sgn(const double& x) { return (x > eps) - (x < -eps); } typedef struct triobj { double x, y, z; triobj() {} triobj(const double& xo, const double& yo, const double& zo) { x = xo, y = yo, z = zo; } inline void read() { scanf("%lf%lf%lf", &x, &y, &z); } } point, vect; inline triobj operator +(const triobj& a, const triobj& b) { return triobj(a....

三维算几ovo给mhy和idy跪烂. 三维凸包算是一种比较简单的三维算几吧.首先有一些基本的公式比如算四个点的体积就是一个底*高.不过变成了一个面的法向量点乘另一个向量. 然后就用随机增量法每次替掉一些面就好了. 然后有一种可能是所有点都共面.这种时候就随机把一些点乱移动一下让它们形成一个高度和纸一样薄的凸包再来算就行了. 感觉也不是特别恶心啊ovo

#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) const int maxn = 50009; dint n, s; int tp, pn[maxn], u[maxn], fc[maxn], tf; bool pr[maxn]; void pre() { memset(pr, 0, sizeof(pr)); u[1] = 1; tp = 0; for (int i = 2; i < maxn; ++ i) { if (!pr[i]) { pn[tp ++] = i; u[i] = -1; } for (int j = 0, v; j < tp && i * pn[j] < maxn; ++ j) { pr[v = i * pn[j]] = 1; if (i % pn[j] == 0) { u[v] = 0; break; } else u[v] = -u[i]; } } }...

在颓废了一天之后决定写一个题解.因为我觉得这题挺有意思. 我们需要转化一下式子.把原来的a,b改成A,B.设d=gcd(A,B),A=ad,B=bd. 那么(a+b)d | abd2,即(a+b)|ab*d. 又因为gcd(a,b)=1,所以(a+b)一定与a,b都互质.于是(a+b)|d. 设t*(a+b)=d.那么因为bd≤n,所以t(a+b)*b≤n.那么b是sqrt(n)级别的.且我们只需要统计三元组(a,b,t)的个数就行了. answer=∑b∑a(n/b)/(a+b)(gcd(a,b)=1)然后这个玩意看上去好像是个长得怪异一点的狄利克雷卷积啊. 于是就是要求[l, r]中与b互质的数的个数?这个玩意等于∑i|bu(i)*(r/i).然后发现可以把b分解质因数.而且只留下u不为0的.于是就能出奇迹辣好厉害ovo

居然这么快.然后就完了.感觉好像是做了一场梦 或者玩了一场游戏ovo 既然是diary那就先diary一下吧. day1早上起来在拥挤的餐厅里吃了面包加面包然后走去考试. 然后就开考了.第一题好神不会.第二题好水选敲.第三题想了想就是半平面交啊敲敲敲.然后发现第一题似乎取值是连续的?那就随便打个dinic乱二分一下吧.然后就完了估分200应该过2和3. 然后下午看分居然220.居然过了1和2然后3tle.居然被高一的虐.然后进去申诉居然连数据都不给那玩ball.于是要数据顺便被某负责人怒斥.然后下午果断去看电影.速7还不错. 晚上开会感觉就是flag大会. 然后就day2了昨天晚上好像被毒蚊子咬了,惨.看题发现第一题好神.第二题好神.第三题好水敲30分钟.然后发现第二题似乎可做然后去敲.然后发现第一题还是不会于是乱骗.考试结束前15分钟发现第二题题意看错试图改朴素未果.心痛ing 下午看分果然只有100虽然还是进队了不过被虐惨于是心痛回家. diary得好水.那么再重新说一下题的做法吧ovo day1a把≥某个数的东西当作1来跑二分图最大匹配就可以得到最多有多少个≥这个数的选择方案然后直接二分. day1b是个水水的倍增.每个战士肯定传给最远的一个然后没有覆盖于是倍增一下看要多远才能盖一圈.然后这题数据好难造. day1c是个半平面交.可以证明任意一边和01边都会划分成一个半平面.扔一起跑半平面交就好了.然后求那个的时候可以用数据公式不过我二分所以被卡常了不开心. day2a似乎是树形dp反正我还没想出来.大概反正先走左先走右dp一下.因为是完全二叉树所以很多看上去不靠谱的复杂度在这里都是靠谱的. day2b听说是线段树.其实直接维护每个0区间的左右端点扔进set里就好了.然后黑白转换的时候分情况讨论一下.每次询问的时候先把某个点的值更新一下.然后查询左右能控制到的最远的端点.如果是连在一起的话还要再找第二近的因为有可能另一边会造成答案变小. day2c水水的链剖+持久化线段树.其实询问就是在某个时刻前就被感染的人在某条链上有多少.我比较懒就直接链剖了其实直接dfs序区间修改也能做还少一个log.不过反正链剖比较快嘛. 虽然这样但是我也只过了3题而已看来我还是太弱啊. 似乎还有总结的部分. 最后一次省选了吧.也是唯一的一次机会.以为自己会很厉害,其实还是不厉害.也算是一种成长吧.发现自己还有很长的路要走. 这回没有倒在ds怎么写上,而倒在了ds的题面上.也算是倒在自己最得意的地方了吧.成长总是痛苦的ovo dp啥的的确比较弱.不能偏科啊. 世事无常吧.有人翻盘也有人第二天倒下了.4个a类居然没有一个人两天都发挥正常.然后女a也暴冷了.yjq差点就进队了可惜了.然后就有一些熟悉的面孔退役了. 反正就是各种奇怪的事情.其实也早就知道有这一天吧.其实也早就准备好了这一天吧.至少i survived. 于是今年省队好像更整齐了. 所以我还是太弱了啊.

奇怪的一天ovo然后发现后天就省选了. 考试ovo然后发现整个高二都不太高兴. 第一题想了半个小时之后写了半个小时ovo充分证明思考的重要性.做法大概就是正解线段树二分.然后还卡常数无语了喽. 第二题不是做过的usaco原题么.然后就按当时的想法敲了个上凸壳下面下凸壳上面的东西.最后交之前想起没改过点的范围于是造了个109的数据.然后发现自己wa掉了.整个人都吓到了.不过也没有时间改了只好硬着头皮交上去了.结果下午发现居然过了ovo数据又水了么.讲的时候知道不用那么麻烦.找出凸多边形的核之后直接在里面找个点极角排序就完了. 第三题一直在想.想了一下dp发现应该是自动机.于是一直在想怎么建一个点数不会炸的dfa.最后才发现我没有注意到dp数组相邻两数差只能是1或者0这个性质ovo. 考成这个鬼样子居然还是rank1,被发了大洋若干.这是要我省选rp下溢直接退役的节奏啊.然后仔细一看发现有人没交ovo妈呀他们都是坏银ovo 然后就花了一个下午+一个晚上在群里水. 所以我还是太弱了.

#include #include #include using namespace std; #define mInc(x,y) { x += y; if (x >= mod) x -= mod; } #define _l (long long int) const int maxn = 20009; const int mod = 1004535809; const int wo = 3; int n, m, mz, l, x, a[maxn], g[maxn], ss; int wm, wp[maxn]; int modPow(int a, int x, int tmod = mod) { int s(1); for (; x; x »= 1, a = _l a * a % tmod) if (x & 1) s = _l s * a % tmod; return s; }...