【题解】北京信息科技大学第十二届校赛题解

（本来感觉题太简单了，可能没多少人需要题解所以没有发，但还是有人私聊我要题解，于是顺便发一下）
比赛链接

题目难度：

签到题：K
简单题：A C
次简单题：B G I
中等题：D E F H
难题：J

level 0 玩具销售员

知识点：无
（本来没有这道题的，为了防止大家爆零就加了这道）
比较k*2和m的关系就可以了。
注意不要把Yes写成YES

level 1 打毛玉大赛

知识点：博弈。
容易发现，只有1 2和2 1这种情况，灵梦是必胜，否则灵梦必败。

level 1 爱丽丝的人偶（一）

知识点：构造算法。
有多种构造方法。最容易想到的是：1,n,2,n-1,3,n-2,......

level 2 魔界伊始

知识点：数论，思维
可以发现，每次称出的沙子一定是某些砝码进行求和或者作差得出。
那么有个推论：设G是所有砝码质量的GCD（最大公约数），那么质量m的沙子能被称出当且仅当m是G的倍数。

证明：充分性：首先根据欧几里得算法，两数不断相减得出差，那么直到减到0之前的那个数就是GCD，所以G一定能被称出来。既然G被称出来了，那么G的倍数也可以称出来。
必要性：用反证法，假设A不是G的倍数，那么A一定无法通过初始的两数相加或者相减得出。因为在计算G的过程中，所有的数一定也都是G的倍数。
其实这个不用证明，只要能猜到这个结论就能解决这道题了。
注意求gcd可以用辗转相除法的递归或者直接调用库函数__gcd。

level 3 永远亭的小游戏

知识点：概率论
独立事件乘积的期望等于期望的乘积。
如果不是很明白可以观察这个式子：
(a+b)/2(x+y)/2(i+j)/2
=(axi+axj+ayi+ayj+bxi+bxj+byi+byi)/8
可以看出来，对于长度为2的数组，可以用多项式乘法推出来。
扩展到长度任意也是可以的。
计算期望的时候，除法等价于乘以逆元。

level 3 爱丽丝的人偶（二）

知识点：组合数学
最后的答案是C(m,k)，其中m是数组中不重复的数的数量。
怎么得到这个m？
最方便的办法是扔进set里面（java是HashSet），自动就去重了。当然也可以排序后去重。（不要用冒泡排序，O(n^2)会超时！）
求C(m,k)的办法可以利用逆元的思想，将除法变成乘法。
C(m,k)=(m(m-1)...(m-k+1))/(1*2...*k)

level 4 贪玩的二小姐（续）

知识点：贪心
很明显，可以优先把左边的右括号变成左括号，把右边的左括号变成右括号
如果字符数量为奇数，直接输出-1
否则先让左右括号数量相等，然后统计“不合法程度”的最大值max。所谓不合法程度，即初始化为0，遇到左括号减一，遇到右括号加一。最后输出(max/2)向上取整再乘2就可以了。因为每操作2次，就可以让“不合法程度”减二。

level 4 游戏机本当下手

知识点：思维、字符串
本题要求找有多少子串有k个0或者1的连续段。假设k=3，我们观察下面的字符串：
1111111 000 11 0000 111
7 3 2 4 3
可以发现答案就是72+34+2*3。
所以只要预处理出每个连续段的长度，每隔k-1个让他们两两相乘求和就可以了。
注意要特判k=1的情况，每个连续段内部选择C(len+1,2)个子串均可。

level 4 宵暗的妖怪

知识点：dp（动态规划）
设dp[i]为前i部分所得的饱食度最大值。
那么如果要选择[i-2,i-1,i-0]这一段的话，所得的最大值应该是
dp[i-3]+a[i-1]
若不选[i-2,i-1,i-0]这一段，所得最大值就是dp[i-1]（前i-1部分的最大值）。
所以得到转移方程：dp[i]=max(dp[i-1],dp[i-3]+a[i-1])

level 5 芭芭拉冲鸭~

知识点：图论，搜索
首先抛出一个问题，树上最长路径（也就是树的直径）怎么求？
一种解法是，先任选一点求出离该点最远的点x，然后求离x最远的点y，x到y即为树的一个直径。
回到本题，这道题要求一个最长路径，路径上的相邻点颜色不能相同。
可以在建图的时候，只对相邻点颜色不同的边进行连边，这样就形成了很多连通块（也就是子树）
最后求所有子树的最大直径即可。复杂度O(n)

level 6 芭芭拉冲鸭~（续）

知识点：树形dp，lca
这道题如果只有一次询问，那么通过bfs找到路径就可以了。
但是有多次询问，所以需要一种快速获取路径的方式。
设两个点x，y的lca为p，dp[i][j-'a']代表点i到根的路径上字母j的数量，那么x到y路径上字母j的数量可以表示为dp[x][j]+dp[y][j]-2dp[p][j]+1。
其中lca是最近公共祖先的意思。可以用倍增或者树链剖分来求。
鉴于篇幅这里就不详细介绍了，如果不会的想去学可以百度一下~
总复杂度O(26*(n+q)log(n))
附树链剖分解法代码：

#include<bits/stdc++.h>
using namespace std;

const int N = 100005;
int Next[N<<1], to[N<<1], head[N], tol;
int fa[N], son[N], top[N], sz[N], dep[N];
int sum[N][26];
int n;
char s[N];
void addAdge(int u, int v){
    Next[++tol]=head[u];
    to[tol]=v;
    head[u]=tol;
    Next[++tol]=head[v];
    to[tol]=u;head[v]=tol;
}
void dfs1(int u, int f){
    sz[u]=1;fa[u]=f;
    for(int e=head[u];e;e=Next[e]){
        if(to[e]!=f){
            int v=to[e];
            dep[v]=dep[u]+1;
            dfs1(v,u);
            sz[u]+=sz[v];
            if(sz[v]>sz[son[u]])son[u]=v;
        }
    }
}
void dfs2(int u, int f, int t){
    top[u]=t;
    ++sum[u][s[u]-'a'];
    for(int e=head[u];e;e=Next[e]){
        if(to[e]!=f){
            int v=to[e];
            for(int i=0;i<26;++i)sum[v][i]=sum[u][i];
            if(v==son[u])dfs2(v,u,t);
            else dfs2(v,u,v);
        }
    }
}
int getLca(int u, int v){
    while(top[u]!=top[v]){
        if(dep[top[u]]<dep[top[v]])swap(u,v);
        u=fa[top[u]];
    }
    return dep[u]<dep[v]?u:v;
}
int main(){
    scanf("%d",&n);
    for(int i=1;i<n;++i){
        int u, v;
    scanf("%d%d",&u,&v);
    addAdge(u,v);
    }
    scanf("%s",s+1);
    dfs1(1,0);
    dfs2(1,0,1);
    int q;
    scanf("%d",&q);
    while(q--){
        int u, v;
        scanf("%d%d",&u,&v);
        vector<int> vec(26,0);
        int g=getLca(u,v);
        for(int i=0;i<26;++i){
            vec[i]+=sum[u][i];
            vec[i]+=sum[v][i];
        }
        vec[s[g]-'a']-=1;
        int t=fa[g];
        for(int i=0;i<26;++i){
            vec[i]-=2*sum[t][i];
        }
        int ans1=0, ans2=0;
        for(int i=0;i<26;++i){
            ans1+=vec[i]/2*2;
            ans2|=vec[i]&1;
        }
        cout<<ans1+ans2<<endl;
    }
    return 0;
}