一模拟与字符串处理题
Problem J. How Much Memory Your Code Is Using?
题意
计算一行C语言变量声明所占字节数（仅单变量或单数组）。
解题要点
输入处理难点：Linux环境下缺少`gets`/`getline`，需用`getchar`逐字符读取。类型判断直接匹配基础类型（`char`/`int`等）并映射字节数。特殊处理`long long`与`long double`（首字母均为`l`，需二次判断）。优化策略：改用`%s`读取单词，通过首字母快速分类（如`l`开头的进一步检查后缀）。关键点：边界样例如多维数组或含空格声明需完整解析。
二组合数学与规律题
Problem C. Insertion Sort
题意
对1-n的全排列执行k次冒泡排序（题目误写为插入排序）后，求最长上升子序列（LIS）长度≥n-1的排列数量（模mod）。
解题步骤
1. 打表找规律：
当k≥n时，结果为n!（排序后有序，LIS恒为n）。当k| n \\ k | k=1 | k=2 | k≥3 |
|--|--|--||
| n=1 | 1 |
| || n=2 | 2 | 2 |
|| n=3 | 5 | 6 | 6 |
| n=4 | 10 | 14 | 24 |
2. 公式推导：
前缀k!为基数。剩余部分满足：`ans = k! * [ data[n-k] + k*(n-k) + (n-k-1) ] % mod`，其中`data[i]`为打表数列（如data=5）。3. 边界处理：k=1时直接查表输出。
三数据结构与优化
Problem E. The Kouga Ninja Scrolls
题意
二维平面上n个点（位置+门派），支持点位置/门派修改，查询区间[l,r]内不同门派两点的最大曼哈顿距离。
解法
1. 曼哈顿转切比雪夫距离：
原坐标(x,y) → 新坐标(x+y, x-y)，距离转为切比雪夫距离`max(|x1-x2|, |y1-y2|)`。2. 线段树维护：
每个节点存储区间内各门派的最大/最小xy值及其门派标识。同时维护次大/次小值（防止最大值与最小值同门派）。3. 查询合并：
合并子区间时，优先取不同门派极值组合的最大差值。Problem M. Renaissance Past in Nancy
题意
n种物品（数量a体积b），m次询问：区间[l,r]物品组合成体积c的方案数（模1e9+7）。
解法
1. 生成函数与背包DP：
单个物品生成函数：`F(x) = (1 x^{(a+1)b}) / (1 - x^b)`前缀积`G_i(x) = ∏_{j=1}^{i} F_j(x)`，逆元`H_i(x) = 1/G_i(x)`。2. 可逆背包：
正序DP添加物品（完全背包+退背包），逆序DP处理逆元。3. 查询优化：
预处理`G_i(x)`的前缀和数组，查询时卷积`G_r(x) * H_{l-1}(x)`取第c项。️ 四图论
Problem D. Made In Heaven (网络赛)
题意
判断从S到E的k短路是否≤T。
解法
![2018icpc沈阳现场赛题解]( "2018icpc沈阳现场赛题解")
A*算法：1. 反向图求各点到E的最短路（估值函数h）。
2. 正向A*搜索，优先队列按`f = g + h`排序（g为当前路径长）。
3. 当终点第k次出队时，其g值即为k短路长度。
五总结与赛题特点
| 题目 | 知识点 | 难度关键点 |
||--||
| J | 字符串处理 | Linux输入限制处理 |
| C | 组合数学+打表规律 | k| E | 线段树+坐标系转化 | 切比雪夫距离转换与次极值维护 |
| M | 生成函数+可逆背包 | 前缀积逆元的DP实现 |
| D | A*+k短路 | 反向图预处理估值函数 |
比赛特点：
凯发k8国际首页登录模拟题（J）需注意环境细节，组合题（C）依赖暴力打表能力。数据结构题（EM）需掌握经典模型扩展（如坐标系变换可逆背包）。沈阳站题目强调多维问题转化（如曼哈顿→切比雪夫）与预处理优化（如背包前缀和）。> 完整代码参考：[CSDN题解1] [背包可逆DP] [打表规律]
