Views

无语的智商题啊.居然没人写题解. 首先dp打个表.cnt[i]表示大小为i的二叉树的总个数.当然这个就是catlan数.然后son[i]表示大小为i的所有不同构的二叉树的叶子数的和. 然后经过找规律(翻oeis)发现son[i] = C(2n-2,n-1). 于是就没有于是了.推一下组合数发现answer=n2(n+1) / (n2) / (n*2-1). 代码好无语.

var n: double; begin readln(n); writeln(nn(n+1)/(2n-1)/(2n):0:9); end.

无语的考试ovo前几天见过原题ovo 第一题水fib数列的dp.然后还只求个位.找循环节都行啊. 第二题无语的树形dp.之前没有看见树的条件. 第三题算几啊.按面积排一下序然后扫描线啥的.然后mhy还有更厉害的扫描线虽然我不会. 所以mhy好强啊. 顺手粘一发考试的时候写的画图器ovo zao (zuo) fu (si) de hua tu qi JS not supported draw clear

终于还是忍不了把语言换成了英语.然后整个世界的画风都变了ovo不我是指字体变了. 一天考两场ovo虽然都是网赛不过还是mark一下喽. 下午的bop本来也是去玩的所以死得比较惨. 第一题数学渣直接再见.第二题似乎是比较无语的贪心.第三题写了老半天的按询问分块最后还是放弃了.感觉计算影响太麻烦. 晚上bc居然和gorgeous分在一个房间了.于是钱没了. 1001水.1002我随便写了个分块.似乎有人直接写朴素也黑不掉啊不开心. 1003被gorgeous秒了.我还是思考了一下才想到的.其实也就是mobius随便推一下的啦. 1004我写的是按左边区间莫队+按颜色大小分块.然后写完之后发现我开的怎么是c.cc?顺手mv c.cc d.cc然后duang的一声代码不见啦.于是只好重写一遍.然后排名就很惨了.于是orz gorgeous去了. 完了发现并不好hack.于是洗澡.于是在洗澡的时候发现我的4的做法居然乘起来的复杂度是O(n2 logn).这是怎么过pre的啊我类个去.肯定fst了.于是很久之后发现居然pre==final!?一脸捂脸ing.是不是我的rp要被吸光了. 所以我还是太弱啦!

#include #include #include #include using namespace std; const double eps = 1e-11; const int maxa = 23; const int maxn = 409; int n, m, t, pa, pb, mp[maxa][maxa], deg[maxn]; double p[maxa], a[maxn][maxn], s[maxn]; inline double transPsb(int a, int b) { if (a == b) return p[a]; else if (!mp[a][b]) return 0; else return (1.0 - p[a]) / deg[a]; } void guess() { for (int i = 0; i < t; ++ i) { int z; for (z = i; fabs(a[z][i]) < eps; ++ z); if (z > i) for (int k = i; k <= t; ++ k) swap(a[i][k], a[z][k]); for (int j = i + 1; j < t; ++ j) { double rat(a[j][i] / a[i][i]); for (int k = i; k <= t; ++ k) a[j][k] -= a[i][k] * rat; } } for (int i = t - 1; i >= 0; – i) { s[i] = - a[i][t]; for (int j = t - 1; j > i; – j) s[i] -= s[j] * a[i][j]; s[i] /= a[i][i]; } }...

比较基础的期望+高消的题.为了说明一下高消是what,我决定写一发题解. 首先题意是有个n个点m条边的无向图.有两个人初始位置是a和b.每个时刻每个人在一个点有p_i的概率不动,否则等概率移动到相邻的点.只有在同一时刻在同一个顶点上才算相遇.相遇了他俩就玩去了.求在第i号点相遇的概率. 首先方程很好列.定义一个状态f[i][j]表示第一个人在i,第二个人在j的概率.那么f[i][j] = ∑ f[k][l] * ptrans(k,i) * ptrans(j, l),其中ptrans(a,b)表示从a移动到b的概率. 然后这个东西就用高消嘛.(upd:才发现它叫gauss而不是guess.捂脸ing) 高消就是说每次把剩下的方程里的第一个系数不为0的未知数的系数全部通过减某一个方程来把这个系数都消成0.当然被减的方程得留下系数过会再用于推答案.然后就可以不管这个被留下的方程了. 换句话说,如果把方程组看成t*(t+1)的矩阵的话,其实就是消成一个右上三角. 然后再倒着推出每个未知数的值. 这个直接算比例就完了嘛.然后有一种情况是当前a[i][i]已经为0了,那么减不掉?反正所有方程的顺序没有关系啊.你就随便找一个不是0的到前面来消就好了啊.如果剩下方程的这一个系数都是0,那这个未知数取啥就无关了.也无所谓啦. 详见代码.

#include #include #include using namespace std; inline double sqr(const double& x) { return x * x; } struct opt { int t, i; double x, y; inline double f(double xo) { return x * xo + y; } inline void read() { scanf("%d%lf%lf", &t, &x, &y); } }; inline bool operator <(const opt& a, const opt& b) { if (a. x == b. x) return a. y < b. y; else return a....

#include #include #include #include using namespace std; typedef set rbt; typedef set :: iterator rbt_it; struct cus { int l, r, i; }; inline bool rCmp(const cus& a, const cus& b) { if (a. r == b. r) return a. l > b. l; else return a. r < b. r; } inline bool iCmp(const cus& a, const cus& b) { return a. i < b. i; } const int maxn = 400009; const int maxl = 19;...

apio的题也是比较有质量的.听说这题很难写但是我感觉难点在想上啊. 首先直接两遍Lis强行判断能不能扔进去是错的.至于为啥我也不造啊. 于是就是区间询问答案最大.然后每次看把当前询问加进去后会不会对最大答案产生影响. 然后发现有点像今年sctsc那个倍增?居然还真是倍增.先去掉包含有其它区间的区间.然后找每个点向右跨过的最近的一个区间.然后再倍增一发. 好神的做法啊ovo btw为啥bzoj第一页上充满了黑坨坨.不爽Ing.

之前在哪里听过的题啊.于是卡了一晚上. 就是缩个点然后看看哪些点必需自己去点第一把火就好了. 然后有一种情况是把剩下的都查完之后只剩下一个了.那么看存不存在这种情况.那就是某个第一把火的地方的scc大小为1,且它连出去的都不必需用它查. 然后我就卡在ans>1上了.我傻了ovo 然后非递归tarjan还是写得不熟啊.还要再加深一下对自己想出来的算法的印象.