创作计划#ACGO编程挑战赛全题解
在ACGO编程挑战赛中，我遇到了一系列富有挑战性的题目，这些题目不仅考验了我的编程技巧，还锻炼了我的逻辑思维。以下是我对这些题目的详细题解，希望对正在准备类似竞赛的你有所帮助。
T1：数字频率统计
题目描述：给定一个数字序列，统计每个数字出现的次数，并按题意输出结果。
解题思路：使用map数据结构记录每个数字出现的次数，然后遍历map，按题目要求的格式输出结果。
代码实现：
#include <iostream>
#include <map>
using namespace std;
int main() {
map<int, int> freq; // 用于存储每个数字的出现次数
int n, num;
cin >> n;
for (int i = 0; i < n; i++) {
cin >> num;
freq[num]++; // 更新数字出现的次数
}
for (auto &p : freq) {
cout << p.first << " " << p.second << endl; // 输出数字及其出现次数
}
return 0;
}
原创zzz
T2：回文字符串检查
题目描述：给定一个字符串，判断它是否为回文字符串。如果是，输出"Yes"；否则输出"No"。
解题思路：将字符串的第一个字符移到末尾，然后检查新字符串是否为回文。
代码实现：
cpp复制
#include <iostream>
#include <string>
using namespace std;
bool isPalindrome(const string &s) {
int left = 0, right = s.size() - 1;
while (left < right) {
if (s[left] != s[right]) {
return false; // 如果左右字符不相等，返回false
}
left++;
right--;
}
return true; // 如果所有字符都相等，返回true
}
int main() {
string s;
cin >> s;
char first = s[0];
s = s.substr(1) + first; // 将第一个字符移到末尾
if (isPalindrome(s)) {
cout << "Yes" << endl;
} else {
cout << "No" << endl;
}
return 0;
}
原创zzz
T3：无重复字符的最长子串
题目描述：给定一个字符串，找到其中不含有重复字符的最长子串，并返回该子串的长度。
解题思路：使用滑动窗口技术，通过两个指针表示一个窗口，该窗口内的字符串不包含重复字符。移动右指针扩展窗口，当遇到重复字符时，移动左指针缩小窗口。
代码实现：
#include <iostream>
#include <string>
#include <unordered_set>
using namespace std;
int lengthOfLongestSubstring(string s) {
unordered_set<char> chars; // 用于存储窗口内的字符
int left = 0, right = 0, maxLength = 0;
while (right < s.size()) {
if (chars.find(s[right]) == chars.end()) {
chars.insert(s[right]); // 如果字符不在窗口内，插入字符
maxLength = max(maxLength, right - left + 1); // 更新最大长度
right++;
} else {
chars.erase(s[left]); // 如果字符在窗口内，移除左指针的字符
left++;
}
}
return maxLength;
}
int main() {
string s;
cin >> s;
cout << lengthOfLongestSubstring(s) << endl;
return 0;
}
原创zzz
T4：区间子串统计
题目描述：给定一个字符串，统计其中所有不含有重复字符的子串数量。
解题思路：使用滑动窗口技术，通过两个指针表示一个窗口，该窗口内的字符串不包含重复字符。移动右指针扩展窗口，当遇到重复字符时，移动左指针缩小窗口，并统计子串数量。
代码实现：
#include <iostream>
#include <string>
#include <unordered_set>
using namespace std;
int countUniqueSubstrings(string s) {
unordered_set<char> chars; // 用于存储窗口内的字符
int left = 0, right = 0, count = 0;
while (right < s.size()) {
if (chars.find(s[right]) == chars.end()) {
chars.insert(s[right]); // 如果字符不在窗口内，插入字符
count += right - left + 1; // 更新子串数量
right++;
} else {
chars.erase(s[left]); // 如果字符在窗口内，移除左指针的字符
left++;
}
}
return count;
}
int main() {
string s;
cin >> s;
cout << countUniqueSubstrings(s) << endl;
return 0;
}
原创zzz
T5：区间修改与查询
题目描述：给定一个数组，支持两种操作：1) 将区间内的所有元素修改为1；2) 查询区间内1的个数。
解题思路：使用线段树进行区间修改和查询。在修改时，如果发现一个子树内的元素都为1，就不再继续搜索该子树；查询时按普通线段树的方式进行。
代码实现：
#include <iostream>
#include <vector>
using namespace std;
class SegmentTree {
public:
vector<int> tree;
int n;
};
int main() {
int n, q;
cin >> n >> q;
vector<int> arr(n);
for (int i = 0; i < n; i++) {
cin >> arr[i];
}
SegmentTree st(n);
st.build(arr, 1, 0, n - 1);
while (q--) {
int type, l, r;
cin >> type >> l >> r;
if (type == 1) {
st.update(1, 0, n - 1, l, r);
} else {
cout << st.query(1, 0, n - 1, l, r) << endl;
}
}
return 0;
}
原创zzz
T6：最短Hamilton路径
题目描述：给定一个图，找到从起点到终点的最短Hamilton路径，路径中的每个节点只能访问一次。
解题思路：使用状态压缩动态规划（状压DP）解决。定义dp[i][j][k]表示从节点i出发，状态为j，最后一个点为k是否可能实现。通过枚举每个时间和所有点，判断当前时间和选取的点是否可行。
代码实现：
#include <iostream>
#include <vector>
#include <climits>
using namespace std;
const int INF = INT_MAX;
int main() {
int n, m;
cin >> n >> m;
vector<vector<int>> graph(n
