题目大意

  有一个长度为 $n$ 的数轴（看作是 $n$ 个格子排成一行），其中有 $m$ 个交界位置被标记了。你要用若干正方形去覆盖这个数轴（如下图），有 3 个规定：
  1、正方形边长必须是正整数
  2、数轴要被恰好覆盖，即不能有空、不能有地方被多个正方形覆盖。
  3、被标记的位置不能是正方形的交界。
  一种方案的价值是所有正方形的面积的积。求所有合法方案的价值和。
  $n \le 10^9,\ m \le 10^5$

题目大意

  $n$ 个点的树，进行点分，每次随机选择分治中心，求期望复杂度。
  例如长度为 $3$ 的链，期望复杂度是 $\frac{2}{3}(3+(2+1))+\frac{1}{3}(3+(1+1))=\frac{17}{3}$
  $n \le 30000$

题目大意

  有 n 个宇宙，每个宇宙都连出去一条单向边。边的长度都是 1。
  现在要新加一些单向边（长度为 1），使得从 1 号节点出发到任意节点的最短路长度不超过 k。求最少加多少边。
  n<=5e5， k<=2e4

认真做，模拟最真实的退役情况

简单的场拿不够分，难的场分差被拉大，最终分数越排越后，D类都没有。
题目都很有gdoi的风格，就是要等考完之后才发现是水题。

这几场脑子很空。
day1，t2想到扫描线但不知道要用线段树维护什么，t3看到k很小只是想状压没想容斥，t4环上的部分就没想过枚举起点。
day2 做慢了，t1想到SA没时间想下去，t4点剖以后不会处理。
day3 就是都不知道应该往哪去想，t4暴力复杂度证错了写都不敢写。

很多东西就是，想到了觉得不可做然后就不想了，或者说不知道用什么方法解决就在乱想。想到了很多思路，都是正解靠边的，就是整理不起来。要加强的是分析题目性质的能力，需要一定的套路积累，也要很强的灵活性，又不能过于灵活不然容易想偏。

现在有个问题就是，我无法把握正解或者部分分的方向，想问题的深度和广度总是错误的，包括简单题也包括难题。做别人推荐给我的题，有些很显然的性质摆在眼前，我也会想偏。这个问题我不会解决，但我也不相信只有多刷题能解决。谁会解决谁教我吧，反正我跟正常人的思维周期性地合不在一起我也不知道为什么。我也不想老是追求大神的思维，然而靠自己确实是很多时候想不到正路。

我觉得说来说去都是现在想的东西太乱了，要睡个觉冷静一下，然后不带任何情绪地做题。

题目大意

  给定一个长度为 n 的小写字符串，问有多少个子串没有循环节。
  n<=1e5

题目大意

  如果一个序列，长度为偶数，从中间劈开之后左边跟右边是相同的，则称这个序列是好的。例如 {1, 2, 3, 1, 2, 3} 是好的，{1, 2, 3, 1, 2, 4} 是不好的。
  现在要你构造一个序列，满足三个条件：

1. 序列长度 <=200
2. 元素大小 <=100
3. 恰有 n 个子序列是好的。

  $n<=10^{12}$

题目大意

  有三个 $n\times n$ 的矩阵 $A$、$B$、$C$，问 $A\times B$ 是否等于 $C$。
  元素在模 $10^9+7$ 意义下。
  $n \leq 1000$

前言

  江苏，感觉规模比广东小，但是也是很有质量的地方。

  大概是最后一次跑到别人的省选去了。。。
  然后跟省队好像差了 30 分？？

  那么几趟练兵下来，都挂彩了。ZJOI 爆 0，JSOI 进不了队，接下来 GDOI。。。退役？？？

题目大意

  有一棵树，有 $n$ 个点。现在将所有距离为 $2$ 的点对也连一条边。
  给出最终的图，请构造一棵原来的树。

  多组数据，$T \leq 10,\ \ n \leq10^4,\ \ m \leq 10^5$

题目出自北方大学acm多校训练赛第四场

V1（原题）

题目大意

  定义函数 $f(n,0)=1$， $f(n,m)=\sum_{d|n}f(d,m-1) \cdot f(\frac{n}{d},m-1)$
  给定 $n,m$，求 $f(n,m) \bmod 10007$
  多组数据，$T \le 10,\ n \le 10^9,\ m \le 50$

  （这题我想了十几分钟没想出来，然后jasonvictoryan走过来，想了10秒钟，想出了V2解法。。。）

V1（【COCI 2016/2017 #5】Poklon）

题目大意

  给出一个长度为 $n$ 的序列 $a_1...a_n$。
  有 $Q$ 次询问，每次询问序列中的一个区间，有多少个数恰好出现两次。
  $n,Q \leq 5 \times 10^5$

转载自 ZYQN's Database，但是原文找不到了。

设我们要分解 $n$，$n=n_1n_2(n_1<=n_2)$，我们构造的序列为 $a_i$，$a_i~mod~n_1=b_i$

因为 $a_i$ 可近似看为随机序列，根据生日悖论可以推出其出现循环的期望步数为 $\sqrt n$，$b_i$ 同理。

因为 $n>n_1$，所以在 $b_i$ 循环之后，$a_i$ 有很大可能没有进入循环，此时 $a_i-a_j=(k_in_1+b_i)-(k_jn_1+b_j)=(k_i-k_j)n_1+(b_i-b_j)=(k_i-k_j)n_1$。于是求 gcd 即可求出 $n_1$。

因为 $b_i$ 的循环期望是 $\sqrt n_1$，而 $n_1<=\sqrt n$，所以最后是 $O(n^{\frac{1}{4}})$

题目大意

  有 n 个工人，每个工人的工作时间为 l[i]...r[i]。
  你要把工人分成 p 个组，每个组的贡献是该组工人的 min(r)-max(l)，即工作时间的交集。
  你的分组要保证每组的贡献是正数，且每个人都要有分组。
  求最大总贡献。
  p<=n<=1000（原题是 200）， l, r<=1e6， 保证有解。

题目大意

  你要构造 $n$ 个数，满足 $m$ 个限制，每个限制条件给出两个长度相等的区间，表示这两个区间的数要一样。比如限制是 [1, 3] 和 [3, 5]，那 {1, 2, 1, 2, 1} 就是满足条件的。
  求方案数。
  $n \le 10^5$

题目

  $k \leq n \leq 50$，方案数 $\bmod 998244353$