六道联赛题的感想

· · 个人记录

第一道 神奇的幻方 水题 不说了(模拟);

第二道 子串 主要考虑 dp[] 先留在这 第三道 换教室 还没做 第四道 组合数 主要考虑 预处理

循环求组合数 c[i][j]=c[i-1][j-1]+c[i-1][j]； 这是组合数的递推公式 处理c[i][0]和c[i][i]的初始值==1

前缀和记忆化 先谈谈杨辉三角 杨辉三角与组合数的关系如图

   1     c[0][0]=1    c[i][j]
   1 1    c[1][0]=1 c[1][1]=1
   1 2 1   c[2][0]=1 c[2][1]=2 c[2][2]=1
   1 3 3 1  c[3][0]=1 c[3][1]=3 c[3][2]=3 c[3][3]=1
   1 4 6 4 1 c[4][0]=1 c[4][1]=4 c[4][2]=6 c[4][3]=4 c[4][4]=1
    ......

前缀和(二维) s[i][j]记录c[i][j]及之前所有的和 故s[i][j]=s[i][j-1]+s[i-1][j]-s[i-1][j-1]; if(c[i][j]满足条件) s[i][j]++; 算是半个矩阵 矩阵和也可以用类似的方法节约查询时间

第五道 逛公园 这道题真的很伤啊 dijkstra+dfs莫名其妙就全挖了

事实证明spfa 是做题的前提条件 写完spfa再详细说明

第六道 列队 根据数据 三十分 手动二维数组模拟 n==1和只有第一排的队员出队 算是类似一位数组、 看完题解 再做说明