2017 Multi-University Training Contest – Team 9

1002 Ch’s gift
树链剖分然后暴力的线段树查询,不优雅的做法,尽管过了。

事实上,这种写法的线段树查询遭到了唾弃。如果不是随机数据很容易就被卡了。

1004 Dying Light
给一些镜子,围成一个凸包。给一束射线,初始能量为1。每次碰撞会损失能量。经过多少次碰撞会变成\(10^{-4}\)以下。如果碰到边缘就GG。


有\(\underset{x}{\rightarrow} \times \underset{t}{\rightarrow}\)与\(\underset{y}{\rightarrow} \times \underset{t}{\rightarrow}\)不异号。
\(\underset{x}{\rightarrow} \times \underset{t}{\rightarrow}\)与\(\underset{x}{\rightarrow} \times \underset{y}{\rightarrow}\)不同号,
\(\underset{y}{\rightarrow} \times \underset{t}{\rightarrow}\)与\(\underset{y}{\rightarrow} \times \underset{x}{\rightarrow}\)不同号。
方向线段关于线段的反射点可以为\((x-2a\frac{ax+by+c}{a^2+b^2},y-2b\frac{ax+by+c}{a^2+b^2})\)(a,b,c)为镜面的直线方程\(ax+by+c=0\).

1005 FFF at Valentine
1000个点,6000个边,给了3秒,差不多能过就暴力了。

1008 Numbers
取出最小的两个,删除两个之和。然后取第三个,删除前两个跟第三个的和。以此类推。

1010 Two strings
一开始\(n^2\)(后来退化成了\(n^3\))的dp超时。后来索性贪心,从末尾开始贪心。

来一发正则表达式的,低版本的编译器会有BUG,似乎要c++14的标准。

2017中国大学生程序设计竞赛 – 网络选拔赛

1001 Vertex Cover
左边30个点,右边大于90个点。题目所给的贪心方法是选择度数大的点进行贪心。这里我们使得答案集合是左边的30,而用贪心会选择右边的90+。首先得保证度数最大的点在右边,然后取完之后减度数,仍然保证度数最高的在右边,这样贪心就只会选择右边的点。

1003 Friend-Graph

1004 A Secret
给定两个串s1、s2,求s2每个后缀在s1中出现的次数*长度之和。
将两个串倒置一下,将问题变成求前缀的问题。
对s2做一下Next,Next[j]表示s2中j位置前最长前缀等于后缀的长度。
当前匹配时,当前匹配的贡献是长度+前缀匹配的的数目,用一个数组记录前缀的和。

1005 CaoHaha’s staff
四种情况如图构造。
$$n=4k$$

$$n=4k+1$$

$$n=4k+2$$

$$n=4k+3$$

然后可以二分答案了。

1007 Palindrome Function
直接算\(1-n\)有多少个回文数字,枚举进制分解n,然后统计就行了。分解下来求个一半的数位和,用flag判断以高位是否可以形成回文串,这里求到的是和原来数位(奇数或者偶数位一样回文数的个数)。再加上小于该位数的位数奇偶性不同的回文数。
答案就是\(cnt * (k – 1) + n\).

1009 The Designer
Pappus Chain
根据公式\(r_n=\frac{r(1-r)}{n^2(1-r)^2+r}\)等比例转换得到第N个圆的半径,但是这个式子几乎是\(\frac{1}{n^2}\)当n较大的时候明显值是很小以至于对结果没有影响,从中break掉。

2017 Multi-University Training Contest – Team 8

1002 Battlestation Operational
求\(\sum_{i=1}^{n}\sum_{j=1}^{i}\left \lceil \frac{i}{j} \right \rceil\).
设\(F(n)=\sum_{i=1}^{n}\left \lceil \frac{n}{i} \right \rceil\),那么有\(F(n) = \left \lceil \frac{n}{1} \right \rceil + \left \lceil \frac{n}{2} \right \rceil + \left \lceil \frac{n}{3} \right \rceil + … + \left \lceil \frac{n}{n} \right \rceil\),\(F(n-1) = \left \lceil \frac{n-1}{1} \right \rceil + \left \lceil \frac{n-1}{2} \right \rceil + \left \lceil \frac{n-1}{3} \right \rceil + … + \left \lceil \frac{n-1}{n-1} \right \rceil\)。首先\(\left \lceil \frac{n}{2} \right \rceil = \left \lceil \frac{n-1}{2} \right \rceil + 1\)当且仅当\(n\)是奇数,也就是说\(2\)是\(n-1\)的约数,其余一样。那么对于\(F(n-1)\)来说,\(F(n)\)多了\(n-1\)的约数个\(1\)以及\(\frac{n}{n}\)。所以有\(F(n) = F(n-1) + d(n-1) + 1\)。那么\(f(n)=\sum_{d|n}\mu(d)*F(\left \lfloor \frac{n}{d} \right \rfloor)\)。用减法就把\(\mu(d)\)给迭掉了。

1008 Hybrid Crystals
题目中有2个条件:\(a_1=1,b_1=N\),\(a_i \leq \sum_{j=1}^{i}a_j[b_j=N]+\sum_{j=1}^{i}a_j[b_i=L\ and\ b_j=L]+\sum_{j=1}^{i}a_j[b_i=D\ and \ b_j=D](2\leq i\leq n)\).
根据这个公式可以得到顺序取必定可以得到一个连续区间。
统计NLD的和,然后只要\(-sumn-sumd \leq k \leq sumn+suml\)即可。

1011 Killer Names
第二类斯特林数,答案是\(\sum_{i=2}^{m}\sum_{j=1}^{i-1}S[n][j]*S[n][i-j]*\textrm{C}_{m}^{i}\),\(S[n][k]\)表示把从1到n标号的n个球放到k个无区别的盒子里,要求每个盒子里至少有一个小球不同的放法数量。

2017 Multi-University Training Contest – Team 7

1002 Build a tree
实际上是一个K叉数,可以通过递归求解,\(a \ xor \ b \ xor \ a = a\)。
特判\(k=1\)的时候:\(n \% 4 = 0,1,2,3\)时分别为\(n,1,n+1,0\).

1005 Euler theorem
\(a \geq b\)时,\(a \% b \leq \frac{a}{2}\)。再加上\(a < b\)时,\(a \% b = a\)。共\((n+1)/2+1\).

1008 Hard challenge
按角度排个序,然后用尺取法取就行了。用sum1、sum2统计两边的和,乘法和就相当于两边和相乘。

Just do it
一开始手画4-12发现,m的4进制中,如果那位不为0,那么就要异或几次。其实异或1次和异或3次一样,异或2次和异或0次一样,所以规律直接换为2就好了🙄。
\(a_{i,j}=a_{i-1,j} \ xor \ a_{i,j-1}\),然后继续写一下就有\(a_{i,j}=a_{i-2,j} \ xor \ a_{i,j-2}\),继续写会有\(a_{i,j}=a_{i-2^n,j} \ xor \ a_{i,j-2^n}\)也就是说相隔\(k=2^n\)的就要异或\(1\)次。

1011 Kolakoski
按照题意的规律做就行了,不是循环节😫。

路径交

hdu 6110
求路径交。
考虑路径\(a_1 \rightarrow b_1\)和\(a_2 \rightarrow b_2\),如何快速合并这两条路径的交。
先分别求出\(lca\),\(c_1\)和\(c_2\)。再求出\(lca(a_1,a_2)\)和\(lca(b_1,b_2)\),将四个\(lca\)升序排好放在数组\(d\)中。设\(deep[c_1] \leq deep[c_2] \),两路径有交当且经当\(deep[d_4] \geq deep[d_3] \geq deep[c_2]\)且\(deep[c_1]\)最小,且路径交就是\(d_3 \rightarrow d_4\)。对于一个区间就可以用线段树合并这些路径交了。

2017″百度之星”程序设计大赛 – 初赛(B)

Chess
假设\(n \geq m\),最多放\(m\)个车。那么就相当于\(n\)行中选择\(m\)行,然后按规则放好就行了。即答案是\(\textrm{C}_{n}^{m}\).

Factory
给一颗树。然后给一些公司,这些公司的办公室在树上的某些节点。给出\(q\)组询问,查询两个公司间的距离(公司的距离定义为最近的两个办公室)。
树上求距离用lca求最近公共祖先就行了。然后数据的G不是很大,可以直接暴力。

度度熊的交易计划
最小费用流的模板题。S跟i建一个容量为b费用为-a,i跟T建一个容量为d费用为c的边,城市ab之间建立容量为inf费用为-dist的边。跑一边最小费用流。

小小粉丝度度熊
维护f跟r两个指针,中间为选中的区间,如果这些区间需要的签到卡大于m那么队首出队即f++,否则每次朝后r++。记录max。

2017″百度之星”程序设计大赛 – 初赛(A)

小C的倍数问题
求\(p-1\)的约数个数…

数据分割
给定一些\(x y z\)的关系,判断\(a_x=a_y|z=1 \ or \ 0\)能否成立。
首先来看,不符合的条件只有\(a_x=a_y\)且\(z=0\)或者\(a_x \neq a_y\)且\(z=1\).
考虑用并查集维护,并查集不能维护不等的关系只能维护相等的关系。考虑一个set维护不等的关系。S[x]存放与集合x不等的集合。
两个集合合并等号的时候选择较小的集合合并到大集合上。

今夕何夕
蔡勒公式(菜了公式)。

度度熊的01世界
dfs求联通块数量,这算哪门子数字识别。

Codeforces Round #428 (Div. 2)

A – Arya and Bran

B – Game of the Rows

1 2|3 4 5 6|7 8

给出这样的座位表,以及座位的排数,给出N组士兵每组的人数,不同组的士兵不能连坐。判断是否可以找出这样的安排(中间四个是连座)。
优先排中间四个的座儿,然后安排旁边两个的座儿。对于余3的,有4的用4先,不然用两个2座。最后排一座的。
(太刺激了)

C – Journey
dfs式走路,走到头算一条路的结束。求能走的期望长度。
期望的算法是\(\sum d_i*e_i\)(长度*概率).
dfs即可。

D – Winter is here
枚举\(GCD\),统计数字为\(GCD\)倍数的数字的个数为\(n\)。
假设这些数字任意组合的最大公约数为\(GCD\)。
那么总贡献为\(f(n)=\textrm{C}_{n}^{0}+2\textrm{C}_{n}^{2}+…+n\textrm{C}_{n}^{n}=n2^{n-1}\),
那么贡献就是\(GCD*f(n)\)。
然而\(4,8\)的最大公约数是\(4\)却被统计了\(2\)又被统计了\(4\),所以在这里只需要处理一下\(GCD\)有多少大于\(2\)且小于等于\(\left \lfloor \frac{n}{2} \right \rfloor\)。这样处理就相当于枚举\(4\)的时候,把部分算在\(2\)中的贡献给去掉了,其他的以此类推,这部分可以用线性筛预处理出来。
复杂度\(O(nlogn)\).