竞赛讨论区 > 【题解】北京信息科技大学第十二届校赛题解
头像
神崎兰子
编辑于 2020-11-27 11:43
+ 关注

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

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

题目难度:

签到题: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;
}

全部评论

(1) 回帖
加载中...
话题 回帖

等你来战

查看全部

热门推荐