51Nod-1593 公园晨跑 题意 给定一个环，环上有$n$个点，每个点有一个权值$h$代表着如果从$i$到$j$的话，你必须加上$2h_i+2h_j$。并且加上他们之间的距离$L$。并且在环上会有一个区间被占用导致只能从另外一个方向走。 ...

最大子段和学习笔记 什么是最大子段和？ 给定$n$个整数(可以为负数)组成的序列$a_1,a_2,…,a_n$，求该序列连续的字段和最大值。显然如果都是负数最大值可以为0。 解决方案1 暴力枚举开始位置$i$和终止位置$j$，对每一种可能性计算和。 ...

[POJ3264]Balanced Lineup 题意 给一个数列，求数列中$l,r$范围内最大值和最小值的差。 题解 st表模板题。求两次rmq即可。 #include #include #include #include using #define #define #define #define typedef typedef const //head const int int int int int int rep(i,0 rep(j,0 st[i][j+1 st2[i][j+1 } } int int return } int int return } int #ifdef freopen("shui.in" #endif while rep(i,0 ST(); while int l--,r--; printf } } return } [POJ3264]Balanced Lineup ...

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)$求逆元 ll inv[maxn]; inv[1 rep(i,2 inv[i] = inv[mod%i] * (mod-mod/i) % mod; $O(n)$求阶乘 ll f[maxn]; ll f[1 rep(i,2 f[i] = f[i-1 求$n\choose k$ 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$ int return } 求逆元和组合数模板 https://www.cheasim.com/acm%E6%A8%A1%E6%9D%BF/2018/08/24/%E6%B1%82%E9%80%86%E5%85%83%E5%92%8C%E7%BB%84%E5%90%88%E6%95%B0%E6%A8%A1%E6%9D%BF.html 作者 CheaSim 发布于 2018-08-24 更新于 2018-08-24 许可协议

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

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

Age of Moyu 题解 标程的set+bfs貌似有漏洞。 5 1 2 3 4 1 1 这个数据就可以hack掉了。 所以我果断copy了dls队伍的代码。(用边做) #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过了。 ...