南京大学一流学科专题营
计算机科学&人工智能
NJUSC 2019游记
本文谢绝任何形式的转载
写在前面
说是说游记，其实就是记录一下题目。
题面可能会有错误，所有配图都是自己画的。
学业繁忙，告辞。
数学争先活动
物理争先活动
创新编程活动一
T1
出原题，有一位同学五分钟切了
[AGC018C]
Coins
T2
题意：
\(n\) 个点 \(m\) 条边的无向图上有 \(k\) 个必经点，起点终点任意，求走 \(d\) 步的方案数。
题解：
\(k\) 很小，容斥+矩阵快速幂
T3
已知平面范围 \(x,y \in [-1000,1000]\)，给定你到平面上 \(100\) 个确定点的距离，其中 \(40\) 个不准确，剩余 \(60\) 个有 \(\pm 1\) 的误差，请求出你的坐标。\(20\) 次询问。
创新编程活动二
T1
又是原题，连样例也不改，让人angry
[AGC013C]
Ants on a Circle
T2
题意：
序列 \(x_1,x_2,\cdots,x_n\)，每个元素等于 \(0\) 或 \(1\)。
现在取出 \(n-3\)
个元素构成一个方程，\(x_{i_1}+x_{i_2}+ \cdots
+x_{i_{n-3}}=2\)，其中 \(1 \leq i_1
< i_2 < \cdots < i_{n-3} \leq n\)
从这些方程里挑出 \(4\)
个组成方程组。方程组中方程顺序不同但是方程相同，认为是同一个方程组。
求有解的方程组数量。
题解：
据说 \(n\le13\) 打表，\(n \ge14\) 有组合数规律
T3
题意：
求大小在十进制数 \(a,b\)
之间的所有三进制数，数位上 \(1\)
的出现的次数之和。 \(1 \leq a,b \leq
10^{350000}\)
题解（skyline tql）：
分治fft进制转换，然后状压dp。100分要压位，90分不用。维护前后两半部分的三进制还有
10 的幂的三进制，然后就只用算乘法了。