JSOI2015

本文主要是介绍JSOI2015，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目大意
- 定义全集为 $\{1,2,\cdots,n\}$ ,要求构成一个m*m的三角形,使得三角形 $(i,j)$ 所代表的集合是 $(i-1,j)和(i,j-1)$ 的子集(如果 $(i-1,j)$ 或 $(i,j-1)$ 不存在就不考虑)
题解
- 打表可知 $ans=2^{nm}$ (最近除了打表暴力就没用啥了……)
CODE

题目大意
- 给定一棵树,每个点有权值,给定每个点经过的次数,从1开始走询问最大权值和,以及方案是否唯一
题解
- 跟之前一道POI很像,树形DP+贪心
- 至于方案判断,从某个点开始走最后一次走的点后面是否还有与其权值相等的点,有就有多解
- 第一次交WA了,因为忘了如果走某个子树权值为0,方案也不唯一
CODE

题目大意
- 给定n*m的方格,用t种颜色去染色,要求满足
  - 每个格子用t种颜色染或不染
  - 每一行至少一个格子染色
  - 每一列至少一个格子染色
  - 所有颜色必须都被用到过
- 询问方案数
题解
- 狂喷自己的容斥原理!!!!辣鸡!!!!
- $a n s = = = = \sum i = 0 n \sum j = 0 m \sum k = 0 t (n i) (m j) (t k) (- 1) n + m + t - i - j - k * (k + 1) i j \sum i = 0 n \sum k = 0 t (n i) (t k) (- 1) n + m + t - i - k \sum j = 0 m (m j) (- 1) - j ((k + 1) i) j \sum i = 0 n \sum k = 0 t (n i) (t k) (- 1) n + t - i - k \sum j = 0 m (m j) (- 1) m - j ((k + 1) i) j \sum i = 0 n \sum k = 0 t (n i) (t k) (- 1) n + t - i - k ((k + 1) i - 1) m$ $\begin{eqnarray*}ans&=&\sum_{i=0}^n\sum_{j=0}^m\sum_{k=0}^t{{n}\choose{i}}{{m}\choose{j}}{{t}\choose{k}}(-1)^{n+m+t-i-j-k}*(k+1)^{ij}\\&=&\sum_{i=0}^n\sum_{k=0}^t{{n}\choose{i}}{{t}\choose{k}}(-1)^{n+m+t-i-k}\sum_{j=0}^m{{m}\choose{j}}(-1)^{-j}((k+1)^i)^j\\&=&\sum_{i=0}^n\sum_{k=0}^t{{n}\choose{i}}{{t}\choose{k}}(-1)^{n+t-i-k}\sum_{j=0}^m{{m}\choose{j}}(-1)^{m-j}((k+1)^i)^j\\&=&\sum_{i=0}^n\sum_{k=0}^t{{n}\choose{i}}{{t}\choose{k}}(-1)^{n+t-i-k}((k+1)^i-1)^m\end{eqnarray*}$
CODE

题目大意
- 给定一个序列 $\{x\}$
- 定义一个连续子序列的权值为 $(r-l+1)*gcd(x_l,x_{l+1},\cdots,x_r)$
- 询问最大权值
题解
- 同BZOJ 4052 Cerc2013 Magical GCD
- 整个序列的 $gcd$ 个数不超过 $NlogN$ 个,所以从左往右存一个右端点为 $i,gcd=?$ 的最远左端点位置,然后暴力求解即可
CODE

这篇关于JSOI2015的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！