西安交通大学校赛题解

写在前面

感觉,大家还是很厉害的,基本上难度还可以的题目都有人做出来了,第一名预计是八题的,七题稍微少了一点。

想变得更强么???

加入西安交通大学ACM队吧,我们即将开始集训队建设,和校队成员零距离交流的机会唾手可得!!!

题解

A

顺序扫一遍统计就好了

B

直接把高度+30数一下有几个不大于它就好

C

暴力一天天枚举计算就可以了

D

由于矩阵非常小,可以暴搜打表等等,同时也可以构造,大致是充分利用好1*4这个东西

E

无脑快速幂或者取个位数找循环节即可,后者要注意特判0次方的情况

F

$2^{13}$的枚举是可以过的,即每种价格的饭取或者不取

标准做法是计算每种价格的饭的贡献,假设价格为i的饭用x份,总共有n份饭。那么这一类价格的饭的贡献为$i \times (2^n-2^{n-x})$

复杂度是O(13)

G

不妨假设$a \lt b \lt c$,那么我们枚举C的系数,对于每个系数可以用拓展欧几里德log的时间检查是否存在a和b对应的非负整数解。

假设c的系数为x,考虑到若$x \gt a$,那么令x=a+p($p \gt 0$)

其产生的效果和x=p的是相同的,所以c的系数上界为a

故复杂度为O(alog)

H

我们存一下每个大写字母应该变成什么,对于每个操作都O(26)地去暴力替换

最后输出时对原串进行更改即可,复杂度O(26*1e5+length(s))

I

考虑使用LCA,对于每一类点,维护两个最远点x和y,若当前添加一个点z,则在(x,y)(x,z)(y,z)三个距离里面取最大的,并用两端点更新最远点即可。复杂度O(nlogn+n)

J

考虑每条边的权值都可以视作某个点到根的异或值,所以我们使用并查集check即可。

若有矛盾,impossible;若最后剩余不止一个并查集,no;否则check每个点到根的异或,取最大最小即可。

K

对于计算一棵树内的任意一对点的距离和,我们考虑算边的贡献

对于一个点v,其父边权为w,树根为k,size()为子树大小

那么这条父边的贡献为$(size(k)-size(v)) \times size(v) \times w$

我们对于每个点v维护$size(v) \times w$和$size(v) \times size(v) \times w$

然后利用dfs序,把树化归为序列,一棵子树对应序列里面的一个连续区间

然后用线段树维护即可