Acm

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

[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$。 ...

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

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过了。 ...