# 1.错排数（HDU 2068）
具体思想与HDU 2049类似（见coding 13），属于M个数错排的思路。
分别递推C和D，累加位置对的数的个数，从(n +1) / 2 到 n即可

AC代码为：
```cpp
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main()
{
    int n;
    while (cin >> n && n != 0)
    {

        vector<vector<long long>> c(n + 1, vector<long long>(n + 1));
        for (int i = 0; i <= n; i++)
        {
            c[i][0] = 1;
            c[i][i] = 1;
            for (int j = 1; j < i; j++)
            {
                c[i][j] = c[i - 1][j] + c[i - 1][j - 1];
            }
        }

        vector<long long> d(n + 1);
        d[0] = 1;
        d[1] = 0;
        for (int i = 2; i <= n; i++)
        {
            d[i] = (i - 1) * (d[i - 1] + d[i - 2]);
        }

        long long ans = 0;
        for (int k = (n + 1) / 2; k <= n; k++)
        {
            ans += c[n][k] * d[n - k];
        }
        cout << ans << endl;
    }

    return 0;
}
```



#2.二维费用完全背包 （HDU 2069）

本题的难点在于：
>**"not more than 100 coins"** —— 硬币总数不能超过 100 枚。
- **题目要求**：必须同时满足 `金额 == n` 且 `硬币数 <= 100`。


----
### 2. 状态定义：从一维到二维

为了记录硬币的数量，我们需要在 DP 状态中增加一根“计数轴”。
- **状态表示**：`dp[k][m]`
	- `k`：当前使用的**硬币总个数** ($0 \le k \le 100$)
	- `m`：当前达到的**总金额** ($0 \le m \le 250$)
- **含义**：使用 $k$ 个硬币凑出金额 $m$ 的不同组合方案数。


----
### 3. 转移方程推导

当我们考虑放入一枚面值为 `v` 的硬币时：
如果我们现在想凑出 `dp[k][m]`（用 $k$ 个硬币凑 $m$ 元），它一定是从“用 $k-1$ 个硬币凑出 $m-v$ 元”的状态转移过来的。
$$dp[k][m] = \sum dp[k-1][m - \text{cents}[i]]$$


----
### 4. 算法实现步骤


|**步骤**|**操作内容**|**目的**|
|:-:|:-:|:-:|
|**1. 初始化**|`dp[0][0] = 1`，其余为 0|0 个硬币凑 0 元是唯一的起始合法状态|
|**2. 遍历硬币**|`for v in {1, 5, 10, 25, 50}`|依次处理每种面值的硬币|
|**3. 遍历数量**|`for k from 1 to 100`|限制硬币总数不超过 100|
|**4. 遍历金额**|`for m from v to n`|计算当前硬币加入后的新方案数|
|**5. 统计答案**|`sum(dp[0...100][n])`|将所有符合硬币数限制的方案相加|


AC代码为：
```cpp
#include <iostream>
#include <vector>
#include <cstring>

using namespace std;

// 题目给出 n 最大 250
const int MAX_N = 251;
const int MAX_COINS = 101;

int main() {
    int n;
    int cents[] = {1, 5, 10, 25, 50};
    
    // dp[k][j]：用了 k 个硬币凑成金额 j 的方案数
    // 注意：这里使用 long long 防止溢出，虽然本题数据范围 int 也能过
    static long long dp[MAX_COINS][MAX_N]; 

    // 预处理：因为输入有多个 case，且硬币种类固定，
    // 我们可以在 while 外先计算好所有可能的 n 的答案
    memset(dp, 0, sizeof(dp));
    dp[0][0] = 1;

    for (int i = 0; i < 5; i++) {
        int v = cents[i];
        for (int k = 1; k < MAX_COINS; k++) { // 限制硬币个数
            for (int m = v; m < MAX_N; m++) { // 限制总金额
                dp[k][m] += dp[k - 1][m - v];
            }
        }
    }

    while (cin >> n) {
        long long ans = 0;
        // 题目要求硬币数 <= 100，所以要把 dp[0...100][n] 全部加起来
        for (int k = 0; k < MAX_COINS; k++) {
            ans += dp[k][n];
        }
        cout << ans << endl;
    }
    return 0;
}
```


#3.字符串处理 HDU（2072）
使用stringstream 可以格式化操作字符串
`stringstream` 是 C++ `<sstream>` 库中一个非常强大的类，它允许你**像操作输入输出流（如 `cin` 和 `cout`）一样操作字符串**。
简单来说，它就像一个“中转站”：你可以把一堆数据塞进去，然后再按需格式化地取出来，它会自动过滤掉空格、制表符（`\t`）和换行符。

## 🛠️ 核心用法分类

### 1. 自动拆分字符串（最常用）

```cpp
string s = "  hello    world   c++  ";
stringstream ss(s);
string word;

while (ss >> word) {
    cout << "单词: " << word << endl;
}
/* 输出：
单词: hello
单词: world
单词: c++
*/
```
### 2. 任意类型转换

在 C++11 之前，这是将 `int`、`double` 与 `string` 互相转换最稳妥的方法。
- **数值转字符串**：
	```cpp
	int num = 1024;
	stringstream ss;
	ss << num;
	string s = ss.str(); // s 变成了 "1024"
	```
- **字符串转数值**：
	```cpp
	string s = "3.1415";
	stringstream ss(s);
	double pi;
	ss >> pi; // pi 变成了 3.1415
	```

## 原理解析：流的运作方式

`stringstream` 维护了一个内部缓冲区。当你使用 `<<` 时，是在向缓冲区写数据；使用 `>>` 时，是从缓冲区读数据，并根据目标变量的类型自动解析。

## 进阶技巧：自定义分隔符

如果你想按 `,` 或 `;` 拆分字符串，配合 `getline` 会更好用：
```cpp
string data = "apple,banana,orange";
stringstream ss(data);
string item;

while (getline(ss, item, ',')) { // 第三个参数指定分隔符
    cout << item << endl;
}
```


假设你有一个日期时间字符串 `"2026-02-11,10:57:42"`，你想分别把年、月、日、时、分、秒提取到不同的 `int` 变量中。如果用 `string::find` 或 `substr` 会写得很痛苦，但用 `stringstream` 配合 `getline` 就像剥洋葱一样简单。
### 🛠️ 进阶示例：解析复杂格式字符串

```cpp
#include <iostream>
#include <vector>
#include <string>
#include <sstream>

using namespace std;

int main() {
    string data = "2026-02-11,10:57:42";
    stringstream ss(data);
    string segment;
    
    int year, month, day, hour, minute, second;
    char dummy; // 用来“吃掉”中间的符号

    // 方法 A：配合 getline 灵活提取（适合分隔符不同的情况）
    // 先按 '-' 拿年、月
    getline(ss, segment, '-'); year = stoi(segment);
    getline(ss, segment, '-'); month = stoi(segment);
    
    // 再按 ',' 拿日
    getline(ss, segment, ','); day = stoi(segment);

    // 方法 B：直接利用流操作符提取（适合固定格式）
    // 此时 ss 的读取指针已经到了 "10:57:42"
    ss >> hour >> dummy >> minute >> dummy >> second;

    cout << "解析结果：" << endl;
    cout << year << "年" << month << "月" << day << "日 " 
         << hour << ":" << minute << ":" << second << endl;

    return 0;
}
```


----
### 🧠 深度理解：为什么 `ss >> hour >> dummy >> minute` 能行？

当你执行 `ss >> hour` 时，`stringstream` 会尝试读取数字，直到遇到非数字字符（这里是 `:`）。然后你用一个 `char dummy` 去接收这个 `:`，流的指针就会跳过它，继续读取下一个 `int`。
### 💡 常见的三个小技巧

1. **判断转换是否成功**：
	`stringstream` 可以像 `cin` 一样放在 `if` 里。

	```cpp
	if (!(ss >> num)) { 
	    // 说明缓冲区里的内容不是数字，转换失败了！
	}
	```
2. **获取处理后的剩余部分**：
	如果你读走了一个单词，想看剩下还没读的部分，可以用 `.str()` 配合流指针，或者直接读入 `ss.rdbuf()`。但最简单的办法通常是 `getline(ss, remaining)`。
3. **十六进制转换**：
	它甚至能处理进制：
	```cpp
	stringstream ss;
	ss << hex << 255;
	string s = ss.str(); // s 变成 "ff"
	```
	
	### ⚠️ 注意一个小陷阱

`hex`、`oct` 这些操纵符是**状态持续**的。也就是说，一旦你执行了 `ss << hex`，除非你手动改回 `ss << dec`（十进制），否则之后塞进这个 `ss` 的所有数字都会变成十六进制。




AC代码为：
```cpp
#include <iostream>
#include <sstream>
#include <string>
#include <set>
using namespace std;

int main()
{

    string s = "";

    while (getline(cin, s) && s != "#")
    {
        stringstream ss(s);
        string temp;
        set<string> v;
        while (ss >> temp)
        {
            v.insert(temp);
        }
        cout << v.size() << endl;
    }
    return 0;
}
```


#4.折线路径


这条折线的路径非常像我们数学里的 **斜坐标系遍历**。观察点的顺序：
$(0,0) \to (0,1) \to (1,0) \to (0,2) \to (1,1) \to (2,0) \to (0,3) \dots$
我们可以发现两个关键特征：
1. **分层现象**：点 $(x, y)$ 属于第 $L = x + y$ 层。
2. **层内移动**：在同一层内，点是沿着斜线从左上角 $(0, L)$ 往右下角 $(L, 0)$ 移动的。
3. **跨层连接**：当到达右下角的 $(L, 0)$ 后，下一段路径会跳到上一层的起点 $(0, L+1)$。

设点为 $(x, y)$，总层数 $L = x + y$。
#### A. 计算前 $L-1$ 层的完整长度

- **斜线段长度**：第 $i$ 层斜线的长度是 $\sqrt{i^2 + i^2} = \sqrt{2} \cdot i$。
- **跨层连接段长度**：从 $(i, 0)$ 到 $(0, i+1)$ 的距离是 $\sqrt{i^2 + (i+1)^2}$。
- 你可以用一个循环从 $i=0$ 累加到 $L-1$。

#### B. 计算当前层（第 $L$ 层）的残余长度

- 点 $(x, y)$ 是该层的第几个点？从 $(0, L)$ 开始走，走到了 $(x, y)$，走过的斜线长度就是 $\sqrt{x^2 + x^2} = \sqrt{2} \cdot x$。



AC代码为：
```cpp
#include <iostream>
#include <sstream>
#include <string>
#include <cmath>
#include <iomanip>
using namespace std;

double getDist(int x, int y)
{
    if (x == 0 && y == 0)
        return 0.00;
    int L = x + y;
    double dist = 1;
    for (int i = 1; i < L; i++)
    {
        dist += hypot(i, i);
        dist += hypot(i, i + 1);
    }

    dist += hypot(x, x);

    return dist;
}

int main()
{
    int n;
    cin >> n;
    while (n--)
    {
        int x1, y1, x2, y2;
        cin >> x1 >> y1 >> x2 >> y2;
        cout << fixed << setprecision(3) << abs(getDist(x1, y1) - getDist(x2, y2)) << endl;
    }

    return 0;
}
```





具体思想与HDU 2049类似（见coding 13），属于M个数错排的思路。分别递推C和D，累加位置对的数的个数，从(n +1) / 2 到 n即可

Coding day 17

算法

编程语言

后端

本文讲解C++编程题解，包括错排数算法（HDU2068）、二维费用完全背包（HDU2069）、字符串处理技巧（HDU2072）和折线路径计算。涵盖动态规划、组合数学、字符串流操作等核心算法，提供AC代码实现和详细解题思路，适合算法竞赛选手参考学习。

文章

问答

视频

教程

学习中心

腾讯云实验室

直播

竞赛

腾讯云代码分析专区

腾讯iOA零信任安全管理系统专区

腾讯云架构师技术同盟交流圈

腾讯云数据库专区

腾讯云智能顾问专区

腾讯云原生专区

腾讯混元专区

腾讯云TCE专区

腾讯云Lighthouse专区

腾讯云HAI专区

腾讯云Edgeone专区

腾讯云存储专区

腾讯云智能专区

腾讯轻联专区 

腾讯云开发专区

TAPD专区

腾讯轻量云游戏服专区

腾讯云最具价值专家

腾讯云架构师技术同盟

腾讯云创作之星

腾讯云开发者先锋

腾讯云代码助手

云原生构建

TAPD 敏捷项目管理

Cloud Studio

SDK中心

API中心

命令行工具

涵盖代码开发、场景应用、自动测试全流程，助你从零构建专属AI助手

一站式MCP教程库，解锁AI应用新玩法

聚焦“写作效率、视觉美观与运行性能”三方面进行全面升级，为您提供更高效、稳定的创作环境

社区富文本&Markdown编辑器全新改版上线，欢迎大家体验!

诚挚邀请您参与本次调研，分享您的真实使用感受与建议。您的反馈至关重要，感谢您的支持与参与！

社区新版编辑器体验调研

Coding day 17-腾讯云开发者社区-腾讯云

Coding day 17

Coding day 17

社区

活动

圈层

关于

腾讯云开发者

热门产品

热门推荐

更多推荐