9.15 蚂蚁笔试编程题题解
1. 给定一个操作次数n，输出一个字符串，满足刚好这么多次操作可以使字符串中所有字母变换成全是'a'。
对于每次操作，你可以将字母变为两个字典序中更小的字符。
如给定n=5，输出ca。经过一次操作变为bba，再经过两次操作变为baaa，再经过两次操作变为aaaaa.
#include <bits/stdc++.h>
using namespace std;
int main() {
int n; cin >> n;
string ans;
while (n) {
int t = n&-n;
int i = 0;
while (!(t&(1<<i))) i++;
ans += 'a'+i;
n &= n-1;
}
reverse(ans.begin(), ans.end());
cout << ans << endl;
return 0;
} 2. 给你一棵树，每棵树上的节点有一个节点编号1~n，每个节点有一个初始值 1. 其中编号为1的节点为根节点。
对于每次操作，你可以将某棵子树上的所有节点的值都加1, 求最少需要操作多少次可以使所有节点的值等于其编号。
第一行输入一个节点总数n。
接下来 n-1 行，每一行两个整数u, v，表示 u 和 v 中有一条边。
示例：
输入：3
1 2
1 3
输出：
3
这题有个坑，如果没有满足题意的操作要输出-1，但是题目没说。
我当时考虑到了，我以为题目没说就默认都有合法解，最后死活只通过90%。下边的题解加上了。
// 思路：DFS
#include <bits/stdc++.h>
using namespace std;
int main() {
int n; cin >> n;
vector<vector<int>> son(n+1);
for (int i = 0; i < n-1; i++) {
int u, v; cin >> u >> v;
if (u > v) swap(u, v);
son[u].push_back(v);
}
long long ans = 0;
function<void(int, int)> dfs = [&] (int node, int val) {
if (node > val) {
cout << -1 << endl;
return 0;
}
ans += node-val;
for (auto s: son[node]) {
dfs(s, node);
}
};
dfs(1, 1);
cout << ans << endl;
return 0;
}
3. 给定一个只包含小写字母的字符串，求满足以下条件的子串数：子串中只有一个字符出现奇数次，其他字符都出现偶数次。
实例： ababa
输出9，满足条件的长度为1、3、5的子串分别为 5，3，1个。
思路：前缀和+位运算
#include <bits/stdc++.h>
using namespace std;
int main(){
string s; cin >> s;
unordered_map<int, int> cnt;
cnt[0] = 1;
int n = s.length();
int res = 0;
int ans = 0;
for(int i = 0; i < n; ++i){
res ^= 1<<(s[i]-'a');
for (int j = 0; j < 26; ++j){
int mask = res^(1<<j);
if (cnt.count(mask)) {
ans += cnt[mask];
}
}
cnt[res]++;
}
cout << ans << endl;
return 0;
} 
