一模拟与字符串处理题

Problem J. How Much Memory Your Code Is Using?

题意

计算一行C语言变量声明所占字节数（仅单变量或单数组）。

解题要点

关键点：边界样例如多维数组或含空格声明需完整解析。

二组合数学与规律题

Problem C. Insertion Sort

题意

对1-n的全排列执行k次冒泡排序（题目误写为插入排序）后，求最长上升子序列（LIS）长度≥n-1的排列数量（模mod）。

解题步骤

1. 打表找规律：

| n=2 | 2 | 2 |

| n=3 | 5 | 6 | 6 |

| n=4 | 10 | 14 | 24 |

2. 公式推导：

3. 边界处理：k=1时直接查表输出。

三数据结构与优化

Problem E. The Kouga Ninja Scrolls

题意

二维平面上n个点（位置+门派），支持点位置/门派修改，查询区间[l,r]内不同门派两点的最大曼哈顿距离。

解法

1. 曼哈顿转切比雪夫距离：

2. 线段树维护：

3. 查询合并：

Problem M. Renaissance Past in Nancy

题意

n种物品（数量a体积b），m次询问：区间[l,r]物品组合成体积c的方案数（模1e9+7）。

解法

1. 生成函数与背包DP：

2. 可逆背包：

3. 查询优化：

️ 四图论

Problem D. Made In Heaven (网络赛)

题意

判断从S到E的k短路是否≤T。

解法

1. 反向图求各点到E的最短路（估值函数h）。

2. 正向A*搜索，优先队列按`f = g + h`排序（g为当前路径长）。

3. 当终点第k次出队时，其g值即为k短路长度。

五总结与赛题特点

| 题目 | 知识点 | 难度关键点 |

||--||

| J | 字符串处理 | Linux输入限制处理 |

| C | 组合数学+打表规律 | k

| E | 线段树+坐标系转化 | 切比雪夫距离转换与次极值维护 |

| M | 生成函数+可逆背包 | 前缀积逆元的DP实现 |

| D | A*+k短路 | 反向图预处理估值函数 |

比赛特点：

> 完整代码参考：[CSDN题解1] [背包可逆DP] [打表规律]