Chuanpai、Nihongo wa Muzukashii Desu、K-skip Permutation-海口c网

Chuanpai、Nihongo wa Muzukashii Desu、K-skip Permutation

article/2025/8/28 22:57:56

一、Chuanpai

题目描述

川牌是四川传统纸牌，每张牌标记两个整数 x 和 y（1≤x≤y≤6）。给定整数 k，要求统计满足 x+y=k 的不同牌型数量。两张牌类型不同当且仅当 (x1,y1) 和 (x2,y2) 不同（即 x1=x2 或 y1=y2）。

输入输出要求

输入：多组测试用例，第一行是测试用例数 T，后续每行一个整数 k（1≤k≤100）。
输出：每组测试用例输出满足条件的牌型数量。

解题思路

核心条件分析

x 和 y 的取值范围均为 [1,6]，且 x≤y（避免重复计数，如 (1,3) 和 (3,1) 视为同一类型）。
需满足 x+y=k，因此 y=k−x。
对于每个 x，需验证 y 是否满足 x≤y≤6。

算法思路

枚举 x：遍历 x 从 1 到 6 的所有可能值。
计算 y：根据 y=k−x 计算对应的 y。
条件筛选：检查 y 是否满足 x≤y≤6。若满足，则计数加 1。

代码实现

#include <iostream>
using namespace std;int count_cards(int k) {int count = 0;for (int x = 1; x <= 6; ++x) {int y = k - x;if (y >= x && y <= 6) {count++;}}return count;
}int main() {int T;cin >> T;while (T--) {int k;cin >> k;cout << count_cards(k) << endl;}return 0;
}

二、Nihongo wa Muzukashii Desu

题目分析

本题要求将日语一类动词的ます形转换为て形，需要根据不同的词尾规则进行处理。题目保证输入的动词词尾为以下类型之一：chimasu、rimasu、mimasu、bimasu、nimasu、kimasu、gimasu、shimasu。我们需要根据这些词尾对应的规则，编写程序实现转换。

规则总结

根据题目描述，转换规则可归纳为以下几类：

以chimasu或rimasu结尾：去掉词尾chimasu/rimasu，加tte。
- 例：machimasu → matte，kaerimasu → kaette。
以mimasu、bimasu、nimasu结尾：去掉词尾，加nde。
- 例：nomimasu → nonde，yobimasu → yonde。
特殊情况ikimasu：直接转换为itte（唯一例外）。
以kimasu结尾：去掉词尾，加ite。
- 例：kakimasu → kaite。
以gimasu结尾：去掉词尾，加ide。
- 例：isogimasu → isoide。
以shimasu结尾：去掉词尾，加shite。
- 例：kashimasu → kashite。

代码实现思路

1. 字符串处理

通过截取输入字符串的后缀，判断属于哪种规则，然后去除对应词尾并添加新的词尾。

2. 关键步骤

判断词尾长度：不同词尾长度不同（chimasu和shimasu为 7 个字符，其他为 6 个字符）。
特殊情况处理：ikimasu需单独判断，优先处理以避免与kimasu规则冲突。

3. 代码逻辑

函数convert：接收动词字符串，按规则返回转换后的て形。
- 先处理特殊情况ikimasu。
- 依次判断各词尾类型，截取前缀并添加对应后缀。
主函数：读取测试用例数T，逐个处理每个动词并输出结果。

完整代码

#include <iostream>
#include <string>
using namespace std;string convert(const string& verb) {if (verb.substr(verb.length() - 7) == "chimasu") {return verb.substr(0, verb.length() - 7) + "tte";} else if (verb.substr(verb.length() - 6) == "rimasu") {return verb.substr(0, verb.length() - 6) + "tte";} else if (verb.substr(verb.length() - 6) == "mimasu") {return verb.substr(0, verb.length() - 6) + "nde";} else if (verb.substr(verb.length() - 6) == "bimasu") {return verb.substr(0, verb.length() - 6) + "nde";} else if (verb.substr(verb.length() - 6) == "nimasu") {return verb.substr(0, verb.length() - 6) + "nde";} else if (verb == "ikimasu") {return "itte";} else if (verb.substr(verb.length() - 6) == "kimasu") {return verb.substr(0, verb.length() - 6) + "ite";} else if (verb.substr(verb.length() - 6) == "gimasu") {return verb.substr(0, verb.length() - 6) + "ide";} else if (verb.substr(verb.length() - 7) == "shimasu") {return verb.substr(0, verb.length() - 7) + "shite";}}int main() {int T;cin >> T;cin.ignore(); for (int i = 0; i < T; ++i) {string verb;getline(cin, verb);cout << convert(verb) << endl;}return 0;
}

K-skip Permutation

题目分析

给定一个整数 n 和 k，要求构造一个 1 到 n 的排列 P，使得满足 pi+k=pi+1 的相邻元素对数 f(P,k) 最大。我们需要找到一种排列方式，尽可能多地形成这样的相邻对。

解题思路

核心观察

若两个数 a 和 a+k 都在 1 到 n 的范围内，则它们可以形成一个满足条件的相邻对 (a,a+k)。
这样的数对可以看作是一个公差为 k 的等差数列。例如，以 a 为首项，公差为 k 的数列 a,a+k,a+2k,… 中的相邻元素都满足条件。

构造策略

分组构造等差数列：将 1 到 n 的数按首项分组，每组形成一个公差为 k 的等差数列。
组内顺序：在每组等差数列中，按顺序排列元素，这样相邻元素自然满足 pi+k=pi+1，贡献组内元素数−1 个有效对。
组间顺序：不同组的排列顺序不影响组内的有效对数量，因此可以按任意顺序拼接各组数列。为了简化实现，直接按首项从小到大依次拼接各组。

代码实现思路

算法步骤

标记已使用的数：使用布尔数组 used 记录每个数是否已被加入排列，避免重复处理。
遍历首项：从 1 到 n 遍历每个数作为首项，若未被使用，则生成以该首项为起点、公差为 k 的等差数列。
生成等差数列：对于每个首项 start，依次添加 start, start+k, start+2k, ... 到排列中，直到超过 n，同时标记这些数为已使用。
输出排列：将所有生成的等差数列按顺序拼接后输出。

最终代码：

#include <iostream>
#include <vector>
using namespace std;int main() {long long n, k;cin >> n >> k;vector<bool> used(n + 1, false);  vector<long long> per;for (long long start = 1; start <= n; ++start) {if (!used[start]) {long long current = start;// 生成以start为首项，k为公差的等差数列while (current <= n) {per.push_back(current);used[current] = true;current += k;}}}// 输出排列for (int i = 0; i < per.size(); ++i) {cout << per[i];if (i != per.size() - 1) {cout << " ";}}cout << endl;return 0;
}