阿里4-12笔试，看别人发的题写的答案，有注释
第一题
#include <iostream>
#include <vector>
#include <string>
#include <deque>
#include <unordered_map>
#include <algorithm>
#include <unistd.h>
#include <fcntl.h>
using namespace std;
string s;//每个节点是什么颜色
vector<vector<int>> tree;//树
vector<pair<int,int>> dp;//记录每个节点下有多少R B
pair<int,int> dfs(int u){
//无子节点直接返回自己含有的RB数量
if(tree[u].size()==0){
dp[u] = {s[u]=='R',s[u]=='B'};
return dp[u];
}
//记忆化搜索
if(dp[u].first!=-1){
return dp[u];
}
pair<int,int> res{s[u]=='R',s[u]=='B'};//先加上自己节点的RB数量
for(auto v:tree[u]){//加上子节点的RB数量
auto&& cntv = dfs(v);
res.first += cntv.first;
res.second += cntv.second;
}
//记忆化搜索
if(dp[u].first==-1){
dp[u] = res;
}
return res;
}
int main(){
//输入重定向
int fd = open("../test.txt",O_RDONLY);
dup2(fd,0);
int n;
cin>>n;
cin>>s;
tree.resize(n);
dp.resize(n,{-1,-1});
for(int i=0;i<n-1;++i){
int u,v;
cin>>u>>v;
tree[u-1].emplace_back(v-1);//u父v子 - u子v父也可以，正反都一样就一个连接关系
}
//计算每个节点下的R B数
for(int u=0;u<n;++u){
dfs(u);
}
//计算所有点下的R B
pair<int,int> allRB;
for(auto c:s){
if(c=='R') ++allRB.first;
else ++allRB.second;
}
//遍历删除每个点的父边
int res=0;
for(int v=0;v<n;++v){
pair<int,int>& vRB = dp[v];
pair<int,int> alldelv{allRB.first - vRB.first,allRB.second - vRB.second};
//判断主树删了子v后，和子v，分别是否符合条件
if(alldelv.first > alldelv.second && vRB.first > vRB.second){
++res;
}
}
cout<<res;
return 0;
}
第二题
#include <iostream>
#include <vector>
#include <string>
#include <deque>
#include <unordered_map>
#include <algorithm>
#include <unistd.h>
#include <fcntl.h>
using namespace std;
int main(){
//输入重定向
int fd = open("../test.txt",O_RDONLY);
dup2(fd,0);
int n;
int cnt[32]={0};//所有数每位上1的个数和
cin>>n;
for(int i=0;i<n;++i){
uint32_t num;
cin>>num;
for(int pos=0;pos<=31;++pos){
if(((uint32_t)1<<pos)&num)//统计每1位1的个数，累加到cnt
cnt[pos] += 1;
}
}
int res=0;
for(int pos=0;pos<=31;++pos){
res += min(n-cnt[pos],cnt[pos]);
}
cout<<res;
return 0;
}
第三题
#include <iostream>
#include <vector>
#include <string>
#include <unistd.h>
#include <fcntl.h>
using namespace std;
int dp[100001][3];//dp[i][j]代表以i位为结尾，余数为j的串个数
int s[100001];//存每一位数字
int main(){
//输入重定向
int fd = open("../test.txt",O_RDONLY);
dup2(fd,0);
string ss;
cin>>ss;
int n=ss.length();
int sum=0;
for(int i=0;i<n;++i){
s[i]=ss[i]-'0';
sum+=s[i];
}
int need = sum%3;//sum为3n需要删除区间内余数为0,3n+1需要删除区间内余数为1,3n+2需要删除区间内余数为2 。问题简化为对删除区间内的余数要求。
int res = 0;
//删结尾[i,n-1]，讨论前一位i-1是5的倍数，且被删除部分对3余数是need
int suffix=0;
for(int i=n-1;i>0;--i){
suffix+=s[i];
if(s[i-1]%5==0 && suffix%3==need){
++res;
}
}
//保留末尾的情况，如果末尾是5或者0那只看前面是否是是3的倍数就行了
if(s[n-1]%5==0){
dp[0][0] = s[0]%3==0;
dp[0][1] = s[0]%3==1;
dp[0][2] = s[0]%3==2;
for(int i=1;i<n;++i){
if(s[i]%3==0){
dp[i][0] = dp[i-1][0]+1;//加自己本身也算一个
dp[i][1] = dp[i-1][1];
dp[i][2] = dp[i-1][2];
}else if(s[i]%3==1){
dp[i][0] = dp[i-1][2];
dp[i][1] = dp[i-1][0]+1;
dp[i][2] = dp[i-1][1];
}else{
dp[i][0] = dp[i-1][1];
dp[i][1] = dp[i-1][2];
dp[i][2] = dp[i-1][0]+1;
}
}
//最后一位不删
for(int i=0;i<n-1;++i){
res += dp[i][need];
}
}
cout<<res;
return 0;
}
