2020蓝桥C++B组题解(省赛)

总结：emm…

（略及题目大意待会更新…）

A

略 答案 $353$

B

略 答案 $1008$

C

略 答案 $4002750$

D

题目大意：

开个堆模拟就可…经典题了
答案：$41269$

E

题目大意：每个格子只能向自己四相邻的格子移动，问共有多少种路径满足：格子中权值单调递增。

考虑$dp[i][j]$为$(i,j)$位置开始的序列数量，然后直接记忆化搜索就可

答案：$3623938190$

F

题目大意：略

没手就行的模拟题

G

题目大意：打印p进制下的乘法表
$p<=36$

日常没手就行的进制转换

H

题目大意：给出一张图，有些边为关键边，求只能走两条关键边的最短路长度。
$n<=10000,m<=100000$

直接建分层图跑最短路即可…是没意思的板子题。（手写Dijkstra倒是写了好久hhh）

I

题目大意：初始给出一个数d，单次操作可以将自己+1或-1，要求自己一直>0，问进行a次+1操作，b次-1操作的方案种数。
$d,a,b<=3000$

考虑$dp[i][j]$为进行了i次操作，现在在j点的方案数，然后直接转移即可。

顺便可以开个滚动数组优化空间。

J

题目大意：

首先$O(n^2)$的dp大家都会…根距定义写出即可

然后推推式子就能发现是个斜率的形式，然后开个队列处理下就能做到$O(n)$了。