蚂蚁2022.9.15笔试题解
第一题挺简单的，略过。
第二题的话，建图跑一个dfs就好，对于每个点，如果其子节点的标记值大于它，则把差值累加到答案上，输出即可。（这里有个坑点，当出现任意一个父节点的标记值小于其子节点的标记值时，很明显是无法实现题目的情况的，也就是没有答案，这里应该输出-1，但是出题人没写，应该是题面漏放了）
第三题的话，由于我们只需要关心字母出现的奇偶性，那么我们可以对任意一个字符串，都用一个26位的数字来表示其26个字母的奇偶性状态。
我们先对整个字符串做个前缀和，那就得到了200001个状态，使用map记录每个状态出现了多少次，然后用auto for去遍历map里的每个状态，再for一遍26位字母，改变其奇偶性，也就是说把
M[now]*M[now^(1<<i)] （i取0到25)累加到ans上，最后输出ans/2即可
补贴个第三题的代码:
#include<bits/stdc++.h>
#define ll long long
using namespace std;
ll ans = 0;
map<int,int>M;
char s[200007];
int main(){
scanf("%s",s);
int len = strlen(s);
int now = 0;//初始状态为0，每个字母都出现了0（偶数）次
M[0] = 1;
for(int i = 0; i < len; i++){
int temp = s[i] - 'a';
now ^= (1 << temp);
if(M.find(now) == M.end()) M[now] = 1;
else M[now]++;
}
for(auto x:M){
int now = x.first;
for(int i = 0; i < 26; i++){
ans += M[now] * (ll)M[now ^ (1 << i)];
}
}
printf("%lld\n",ans/2);
} 
大哥可以帮忙看看吗，万分感谢！ ``` #include <bits/stdc++.h> using namespace std; unordered_set<int> st; int dfs(unordered_map<int, vector<int>>& mp, int idx, int offset) { st.emplace(idx); int newOff = idx - offset - 1; int cnt = newOff; for (int i : mp[idx]) { if (st.count(i)) continue; cnt += dfs(mp, i, newOff); } //cout << cnt << endl; return cnt; } int main() { int n; cin >> n; unordered_map<int, vector<int>> mp; int u, v; while (cin >> u >> v) { mp[u].emplace_back(v); } int ans = 0; // for (int i = 1; i <= n; ++i) { // if (st.count(i) == 0) { // ans += dfs(mp, i, 0); // } // } cout << dfs(mp, 1, 0); //cout << ans; return 0; } ```
