Posts

2018 Multi-University Training Contest 8 D.Parentheses Matrix 传送门 题目大意 一个由左括号和右括号组成的矩阵，定义矩阵的权值是矩阵中匹配的行数和列数的和。 题解 一道比较典型的构造题。 如果行数或者列数是奇数那么矩阵显然是奇数的行或列匹配不了。 ...

A. Rikka with Nash Equilibrium 题解： 神仙dp题 将数字从大到小一次排列，从大往小取. 构造一个三维$dp[now][j][k]​$,表示放入$now​$数字的时候有$i​$行和$j​$列有数字下的情况。为了防止数字成为平衡位置，每次放置的位置都要放置在之前放置元素所在的列或者行上，如果不这么放置的话，他就会成为剩下当前行和当前列最大的(就没能有比他大的数字了)。 ...

Generation I 题解 首先放$k$种数字的情况，有$A_n^k$中可能。 由于操作后，前面的球就无法放置,就可以第一个放置该数字的点来确定该结果的区别。相当于将$k$种放在$n$个格子里面。使用隔板法$n\choose k$。 ...

求逆元 $O(n)$求逆元 1 2 3 4 ll inv[maxn]; inv[1 rep(i,2 inv[i] = inv[mod%i] * (mod-mod/i) % mod; $O(n)$求阶乘 1 2 3 4 ll f[maxn]; ll f[1 rep(i,2 f[i] = f[i-1 求$n\choose k$ 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 ll cur,p[maxn],q[maxn],inv[maxn]; ll C return } ll c if if return } void p[0 for inv[i] = (mod-mod/i)*inv[mod%i]%mod; q[i] = q[i-1 p[i] = p[i-1 } } //在每次的时候就得cur初始化为1 求$A^k_n$ 1 2 3 int return } 求逆元和组合数模板 ...

Appleman and Tree 链接 如果觉得我的题解看不懂可以去看 大佬的题解 题目大意 将一颗树节点染成白色或者黑色，减去几条变使得每个联通分支都有一个黑色节点，问有多少种减边方案。 ...

ST表学习笔记 功能 ST表示用来求解给定区间RMQ的最值问题。 预处理复杂度:$O(nlongn)$，查询复杂度$O(1)$。 详解 原理 将原数组分成以2幂次的区间块，用$mn[i][j]$表示从$j$到$j-2^i-1$的最小值，最小值显然等于$$min(前半段最小值,后半段中最小值)$$从而得到递推式子 ...

Age of Moyu 题解 标程的set+bfs貌似有漏洞。 1 2 3 4 5 6 7 5 1 2 3 4 1 1 这个数据就可以hack掉了。 所以我果断copy了dls队伍的代码。(用边做) 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 #include #include #include #include #include #include using inline return } inline char while ch = inputchar(); ret = ch - '0' ch = inputchar(); while { ret = ret * 10 ch = inputchar(); } } const int class { public int }e[MAXM * 2 int int deque void int // scanf("%d%d%d", &u, &v, &c); inputnum(u); inputnum(v); inputnum(c); e[++en].to = v; e[en].c = c; e[en].next = head[u]; head[u] = en; e[++en].to = u; e[en].c = c; e[en].next = head[v]; head[v] = en; } bool if return memset en = 1 for insert(); memset for dis[i / 2 while { int q.pop_front(); for if { if dis[i / 2 } else { if dis[i / 2 } for if { if dis[i / 2 } else { if dis[i / 2 } } int for if ans = dis[i / 2 if ans = -1 printf return } int #ifdef freopen("a.in" #endif while return } 时间卡的非常紧。优化了很多终于2.4s过了。 ...

求逆元模板 递推求逆元 1 2 3 4 5 int int rep(i,2 inv[i] = inv[mod%i]*(mod-mod/i)%mod; } 费马小定理求逆元 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 ll extend_gcd if if x = 1 return } ll d = extend_gcd(b,a%b,y,x); y -= a/b*x; return } ll mod_reverse ll x,y; ll d = extend_gcd(a,n,x,y); if else } 逆元模板 https://www.cheasim.com/acm%E6%A8%A1%E6%9D%BF/2018/08/19/%E9%80%86%E5%85%83%E6%A8%A1%E6%9D%BF.html 作者 CheaSim 发布于 2018-08-19 更新于 2018-08-19 许可协议

codeforcesPoints 题意 给出几个点，让你求出在某个点的右边和上面最接近他的点是哪一个点。 题解 线段树+set应用 对$x$进行离散化处理，对于每一个$x$进行建一个set，用线段树维护$x$之间的$y$的最大值。对于给出点的右上点，我们可以用二分来set搜索，还有在线段树中优先搜索左边靠近给出点的点。 ...