A：年龄统计

知识点：桶思想(标记)

思路：由于题目已知外星人年龄为万的倍数，故将外星人的年龄除以10000，然后用数组统计数量，若遇到年龄为x的，除以10000以后放在桶数组a中，最后若遇到查询直接在桶里查找即可。

代码：

#include<bits/stdc++.h>
using namespace std;
int n,a[100001];
int main(){
    scanf("%d",&n);
    while(n--){
        int op,x;
        scanf("%d%d",&op,&x);
        x/=10000;
        if(op==1) a[x]++;
        else printf("%d\n",a[x]);
    }
    return 0; 
}

B：高精度吗

知识点：高精度乘低精度

思路：由于题目需要找出kx有可能的最大值与最小值的差，最小一定为0，最大为9，故我们可以统计出问号的个数，然后用9补齐，再给每位乘k，再进位，最后若高位有数据，记得长度加长。输出倒序的数组。

代码：

#include<bits/stdc++.h>
using namespace std;
string s;
int k,a[505];//统计有a[0]个9 
int main(){
    cin>>s>>k;
    for(int i=0;i<s.size();i++){
        if(s[i]=='?'){
            a[0]++;
        }        
    }
    if(!a[0]){
        cout<<0;
        return 0;
    } 
    for(int i=1;i<=a[0];i++){
        a[i]=9*k;
    }
    for(int i=1;i<=a[0];i++){
        if(a[i]>9){
            a[i+1]+=a[i]/10;
            a[i]%=10;
        }
    }
    if(a[a[0]+1]) a[0]++;
    for(int i=a[0];i>=1;i--){
        cout<<a[i];
    }
    return 0; 
}

C：切绳子

知识点：二分

思路：1.本题在读入的时候，最好不要用浮点数，不然枚举麻烦。可以把每个数乘100；2.在读入的时候，找最大的绳子长当作二分的right，可以不用单独排序。时间省一点是一点。3.之后不断二分长度，判断当前长度是否可行。可行的话就接着二分，不可行的话退出，打印。4.打印的时候要把100乘回去

代码:

#include<bits/stdc++.h>
using namespace std;
int n,k,a[10001],lef=1,mid,righ,ans;
bool check(int x){//看看x够不够分成k份 
    int g=0;
    for(int i=1;i<=n;i++){
        g+=a[i]/x;
    } 
    return g>=k;
}
int main(){
    cin>>n>>k;
    for(int i=1;i<=n;i++){
        double d;cin>>d;
        a[i]=d*100;
        righ=max(righ,a[i]);
    }
    while(lef<=righ){
        mid=(lef+righ)/2;
        if(check(mid)){
            ans=mid;
            lef=mid+1;
        }else{
            righ=mid-1;
        }
    }
    printf("%.2lf",ans/100.0); 
    return 0;
}

D：平衡路径

知识点：深度优先搜索

思路：数据大小为5000，故可以从每个点进行深度优先搜索，由于起点和终点颜色不同，事先先统计起点颜色，然后在搜索的过程中随时记录当前遍历到的节点颜色以及个数，若是满足红色个数多并且起始位置和终止位置颜色不同即可统计一次答案。最后答案需要除以2，因为从每个点进行搜索是双向的，答案会累加2倍，所以答案需要除以2。

参考代码：

#include<bits/stdc++.h>
using namespace std;
int n,st,en,ans;
string s;
vector<int> v[5001];
bool b[5005];
void dfs(int now,int red,int blue) { //求当前节点满足条件的平衡路径
    b[now]=1;//自己先标记
    if(s[now]=='R') red++,en=1;
    else blue++,en=0;
    if(red>=blue&&(st&&!en||!st&&en))ans++;
    //开始搜索自己的儿子或者父亲
    for(int i=0; i<v[now].size(); i++) 
        if(!b[v[now][i]]) dfs(v[now][i],red,blue);
}
int main() { 
    cin>>n>>s;
    s=" "+s;
    for(int i=1; i<n; i++) {
        int x,y;
        cin>>x>>y;
        v[x].push_back(y);
        v[y].push_back(x);
    }
    for(int i=1; i<=n; i++) {
        memset(b,0,sizeof(b));
        if(s[i]=='R') st=1;//起点为红色 
        else st=0;//起点为蓝色 
        dfs(i,0,0);
    }
    cout<<ans/2;
    return 0;
}