August 2017

2017ACM/ICPC广西邀请赛-重现赛

1001 A Math Problem
枚举\(k^k\),\(k \leq 15\)。

1002 Color it
线段树,按y排,存x坐标,维护min
按x排存y坐标也行的,
防止炸空间,可以离散化或者像我这样,用到哪建到哪,最多是nlogn的.

1003 Counting Stars
统计有多少\(V=(A,B,C,D)\),\(E=(AB,BC,CD,DA,AC)\)。
考虑一个边作为对角线时,如果有K个点跟这个边的两个端点都相连,那么有\(\textrm{C}_{K}^{2}\)中方案。
统计时,让边记录在度数比较少的点处,减少枚举次数,每次将3个边一起算贡献。

1004 Covering

Number of domino tilings of 4 X (n-1) board.

\(a_n = a_{n-1} + 5a{n-2} + a_{n-3} – a_{n-4}\),直接用杜教板子。。

1005 CS Course
求三种sum丢掉第k位
预处理出所有的前缀和后缀
黑康说:按位枚举???emmm

1006 Destroy Walls
国王的坐标给的那么恶心的数字,就是告诉你,国王不会在wall上,然后要让国王能到达任意地方,就要让这些wall无法形成环就可以了,所以,不是环,树嘛,要求删去的最少,求个最大生成树,然后\(ans = sum_{all} – sum_{tree}\)。

1007 Duizi and Shunzi
贪心:取i,i-1,i-2这个顺子的时候先把i-1,i-2的对子取掉,取完再取i的对子。

1008 Law of Commutation
开始打表的时候发现如果a是奇数的时候肯定是1。
然后a是偶数的时候,2的因子个数很多,枚举一下就行了,后面的就为0了。
开始打表发现,\(a \geq n\)的时候,几乎是所有的偶数,无脑了几发。发现\(a \leq n-1\)的时候答案不对。事实上,枚举一下较小的部分。加上后面0的部分。

1010 Query on A Tree
[BZOJ3261 最大异或和]
首先,如果是区间异或的话,可以用可持续化Trie树。对于树上的可以用dfs序做。查询就查询in[u]到out[u]的的区间就行了。

矩阵优化

51nod 1033
因为行数比较少,\(n\leq 5\)。我们用二进制表示当前状态,比如说\(10101\)表示第1,3,5行放了,第2,4没放。用数组\(a[i][j]\)表示状态\(i\)到状态\(j\)的方案数。最终求的是第\(0\)层\(0\)到第\(m\)层\(\underset{m}{1111…1}\)状态的方案数,相当于矩阵\(a^{n+1}\)。

2017 Multi-University Training Contest – Team 10

1001 Admiral
给一个样例样式的图形,每次只能移动0,与上下四个交换,问最少能到达目标的次数。
最多20步,每步大约4个状态,大约需要\(4^{20}\)的复杂度,爆炸。
考虑双向宽搜,每次只需要搜一半。\(4^{10}+T*4^{10}\)可以接受。

1002 Array Challenge
官方题解:

最后就是\({ans}_{n}=4{ans}_{n-1}+17{ans}_{n-2}-12{ans}_{n-3}\).

1008 Monkeys
f跟g算这个树最多有多少对点,f是用了,g是没用。因为数据给的是\(1\leq a_i \leq i\),所以树的方向是定的。妙实在是妙。

1010 Schedule
给一些任务。每个机器在同一时刻只能服务同一台机器。问最少需要多少台机器,并且在机器最少的情况下,时间最少是多少。前一个人物的最后时刻可以等于后一个人物的开始时刻。
用multiset维护机器的开始结束时间。当出现时间重叠时增加一个”机器”。否则查找upper_bound的那个机器接上去。


1011 Two Paths

实际上是求次短路。

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掉。