这把前四题都很简单，但也只做出来四题。。。第5题难道真的做不出来吗，F感觉可做，最后肝了半天还是出不来~_~,老老实实补题了。

补了E和F -----------10.24

A.小红的对错判断

给出一个不超过3的仅由小写或者大写的字符串 看看全为大写或者小写是否符合对应字符串

直接嗯做

void solve(){
    string s;
    cin>>s;
    if((s[0]=='y'|| s[0]=='Y') && (s[1]=='e' || s[1]=='E') && (s[2]=='S' || s[2]=='s')){
        cout<<"accept";
    }
    else{
        cout<<"wrong answer";
    }
}

B. 小红的幂表达

把给定的整数表示成 pow(a,b)的形式，按b从小到大输出

暴力即可，双for不会超时，因为pow(i,j)是指数级别的递增

using LL = long long;
void solve(){
    int x;
    cin>>x;
    cout<<x<<endl;
    for(int i=x;i>=2;i--){
        for(int j=1;pow(i,j)<=1e5;j++){
            if(pow(i,j)==x){
                cout<<"="<<i<<"^"<<j<<endl;
            }
        }
    }
}

C.小红的前缀询问

给定一个数组，求出每个前缀的不同数对的数量

考虑用map维护，当某个数已经出现了x次，再出现一次必然多出x个数对，累加即可。

using LL = long long;
void solve(){
    int n;
    cin>>n;
    vector<LL> a(n+1,0);
    map<LL,LL> q;
    for(int i=1;i<=n;i++){ 
        cin>>a[i];
    }
    LL sum = 0;
    for(int i=1;i<=n;i++){
        if(i==1){
            cout<<0<<" ";
            q[a[i]]++;
        }
        else{
            if(q[a[i]]){//如果a[i]值之前已经出现过
                sum+=q[a[i]];
                cout<<sum<<" ";
                q[a[i]]++;
            }
            else{//没出现过
                q[a[i]]++;
                cout<<sum<<" ";
            }
        }
    }
}

D.小红和小紫的博弈游戏

一眼博弈，因为无论怎么抓，肯定会抓到对角线的某一点，当两个人都抓一边的时候，肯定会有一个角为0，此时就看另一个对角，所以就看对角之和的最小是否为奇数或者偶数，，可以手搓一下

using LL = long long;
void solve(){
    vector<vector<int> > a(3,vector<int>(3,0));
    for(int i=1;i<=2;i++){
        for(int j=1;j<=2;j++){
            cin>>a[i][j];
        }
    }
    if(min(a[1][1]+a[2][2],a[1][2]+a[2][1])%2==0){
        cout<<"yukari"<<endl;
    }
    else{
        cout<<"kou"<<endl;
    }
}

E. 小红的字符串重排

如果某个字符超过了该串字符数量的一半，则无法实现

重排字符串，只需对字符串的字母进行排序，保留其所在原先自字符串的下标，再进行位移

符串：ababacc

下标：1234567

排序：aaabbcc

下表：1352467

若要换位，则取最大的字符数量来换，保证不会重复，例如上面就取3，如果超过了就取%n

位移：bccaaab

下标：1352467

此时再把下表对应改变后的字符放回原字符串即可

对应1234567

结果bacacab

#include <bits/stdc++.h>
using namespace std;
using LL = long long;
int a[27];
const int N = 1e5+10;
struct node{
    char t;
    int cnt;
}p[N];
bool cmp(node &x, node &y){
    if(x.t==y.t){
        return x.cnt < y.cnt;
    }
    else{
        return x.t < y.t;
    }
}
void solve(){
    string s;
    cin>>s;
    int n = s.length();
    for(int i=0;i<n;i++){
        a[s[i]-'a']++;
    }
    int m = 0;
    for(int i=0;i<26;i++){
        m = max(m,a[i]);
    }
    if(m>n/2){
        cout<<-1<<endl;
        return;
    }
    for(int i=0;i<n;i++){
        p[i].t = s[i];
        p[i].cnt = i+1;
    }
    sort(p,p+n,cmp);
    vector<char> q(n+1,0);
    for(int i=0;i<n;i++){
        q[p[i].cnt-1] = p[(i+m)%n].t;
    }
    for(int i=0;i<n;i++){
        cout<<q[i];
    }
}
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0); 
    int t = 1;
    while(t--){
        solve();
    }
}

F.小红的树上路径查询（easy）

说实话，这题是没有E难的，但由于是树

可惜解题的时候想到了方法实现不了，本来是想把路径找出来全赋值为0，然后再从根一个个扫下去，再统计最后值的相加，但是路径不知道怎么弄，就是不断找到对应节点，然后一层层将父亲节点定为0，今天找个一个大佬写的解法，又学到了^-^。

#include <bits/stdc++.h>
using namespace std;
using LL = long long;
vector<int> g[202020];
vector<int> vis(202020,1e9);
void dfs1(int x,int fa){
    for(int i=0;i<g[x].size();i++){
        int son = g[x][i];
        if(son==fa) continue;
        dfs1(son,x);
        if(vis[son]==0){ //核心：如果扫完发现子节点为0，而父节点也要为0，然后一层层扫上去
            vis[x]=0;
        }
    }
}
void dfs(int x,int fa,int cnt){//计算其他点距离简单路径的值，min保证0不会被改变
    vis[x] = min(vis[x],cnt);
    cnt = vis[x];
    for(int i=0;i<g[x].size();i++){
        int son = g[x][i];
        if(son==fa) continue;
        dfs(son,x,cnt+1);
    }
}
void solve(){
    int n,q;
    cin>>n>>q;
    for(int i=1;i<n;i++){
        int u,v;
        cin>>u>>v;
        g[u].push_back(v);
        g[v].push_back(u);
    }
    while(q--){
        int x,y;
        cin>>x>>y;
        vis[x]=0;
        vis[y]=0;
        dfs1(x,0);
        dfs(x,0,0);
        LL ans = 0;
        for(int i=1;i<=n;i++){
            ans += vis[i];
        }
        cout<<ans;
    }
}
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0); 
    int t = 1;
    while(t--){
        solve();
    }
}