2018年上海金马五校程序设计竞赛部分题解

全场梦游,被kblack踩了4题QAQ。

A. King is a Dull Boy

  • 首先考虑单种括号的情形,是个卡特兰数。
  • 两种括号就是再乘上一个组合数。
  • PS:由于数据范围$n+m≤8$,故可以本地暴力枚举全排列打表。最慢的一组也只要跑半分钟左右。
  • 时间复杂度:$O(1)$

B. Ball Game

  • 四维DP。$dp[i][j][k][l]$表示每种球分别取$i,j,k,l$个时的最大获利,暴力转移即可。
  • 时间复杂度:$O(ABCD)$

C. Summer Camp

  • 签到题,直接判断对应位置是否相同。
  • 时间复杂度$O(n)$

D. Kermit II

Unsolved

E. Grid

  • 枚举长宽暴力统计即可。
  • 时间复杂度:$O(nm)$

F. Painting

Upsolved

  • DP可以求出相邻不同色的方案数。
  • 有两种颜色必须要用,所以容斥一下就好了。
  • 时间复杂度:$O(n)$

G. Can I Find You

  • 求出原图$S→T$的最小割$c$,如果$c>k$就一定能连通。
  • 时间复杂度:$O(n m ^ 2)$

H. Pick up Candles

  • 容易想到DP,令$dp[i]$表示以第$i$个结尾的合法子序列个数。
    $$dp[i]=\sum_\limits{\substack{j < i \\ |a_j - a_i| ≤ d}} dp[j] + 1$$
  • 离散化后用数据结构(树状数组)优化转移即可。
  • 时间复杂度:$O(n \log n)$

I. Game

Unsolved

J. Data Cube

Unsolved

K. Segments Touching

Unsolved

L. Mountain Climbing

Upsolved

  • 将原序列差分后求本质不同的子串个数。
  • 后缀数组即可,答案为$\frac{n(n+1)}{2} - \sum_\limits{i=2}^n height[i]$。
  • 时间复杂度$O(n)$

M. Lucky Digits

  • 贪心构造出一个比它小的和一个比它大的,比较一下就好了。
  • 时间复杂度:$O(\log n)$

N. Ball Game 3

  • 对每个点,二分其所在区域,用叉积判断。
  • PS:有点迷,比赛的时候各种调参才rush过去。
  • 时间复杂度:$O(m\log n)$

O. $±1$ Matrix

Upsolved

  • 把$-1$当做$0$,$1$当做$1$。对第一个矩阵的每一行和第二个矩阵的每一列分别构造$n$个和$k$个大小为$m$的std::bitset
  • 这样两个bitset异或一下就得到了对应行列向量点乘时同号和异号的个数。
  • 时间复杂度:$O(nmk/bit)$
捐助作者
0%