发现自己真的好久没写游记了啊。。。倒是各式各样的其他小作文写了不少。。。

题目大意

  给定两个长度为 $n$ 的 01 串 $s,t$，每个串都不会有连续三个相同的字符。现在每次操作可以将 $s$ 的一位反转，但反转之后也要保证没有连续三个相同的字符，求最少的步数使得 $s$ 变成 $t$。

  $n \le 5000$
  2s

题目大意

  设 $x$ 的质因数分解为 $p_1^{c_1}p_2^{c_2}\cdots p_m^{c_m}$，记 $f(x) = c_1^{p_1}c_2^{p_2}\cdots c_m^{p_m}$，给定 $n$，求 $\sum_{i=1}^n f(n) \bmod 10^9+7$。

  $n \le 10^{14}$
  10s

大概就随便记一记读过的有亮点的东西，觉得很牛逼的东西就分享一下，随缘更新。

当然也不是教程或者阅读笔记。

TCS 是指 Theoretical Computer Science。

题目大意

  有一幅 $n$ 个点 $m$ 条边的有向图，边有边权（代表通过所需时间），你在 $1$ 号点，女朋友在 $n$ 号点。
  你可以选择在 $1$ 号点延迟任意时间之后，选定一条路线开始游走，一旦开始游走就不能停下来。你的女朋友会在时间区间 $[a,b]$ 中的任意一个实数时间点 call 你，你一旦被 call 就要马上过去 $n$ 号点，女朋友的等待时间就是她 call 了之后到你到达所用的时间。
  求女朋友的最坏等待时间最小。

  $n,m \le 10^5,\ \ 0 \le a \le b \le 10^{12}$，边权 $\le 10^6$
  保证每个点至少有一条出边，即总是可以无限游走的。

  6s

题目大意

  定义一个序列的 average 为 $\frac{最大值+最小值}{2}$。
  给定一个序列 $a_1,\cdots,a_n$，有 $m$ 次询问，每次问这个区间的所有子区间的 average 期望。

  $n,m \le 2 \times 10^5,\ 1 \le a_i \le 10^9$
  多测，$\sum n,\sum m \le 3 \times 10^5$
  8s

题目大意

  给定一个排列 $a_1,\cdots,a_n$，求极长上升子序列的数量。

  $n \le 10^5$

题目大意

  定义一个序列是好的，当且仅当能把这个序列里的数划分成两个非空集合，使得一个集合的 and 等于另一个集合的 or。
  给定 $a_1,\cdots,a_n$，有 $q$ 个询问，每次询问 $a_l,\cdots,a_r$ 是否是好的。

  $n,q \le 10^5,\ 0 \le a_i < 2^{30}$
  3s

  咕得有点久了
  这是编译原理大作业的第二步：进行语义分析，生成三地址码。

题目大意

  给定一个 $a$ 和一个奇质数 $p$（$1 \le a<p$），令 $b_x=ax\bmod p,\ x=1,2,\cdots,p-1$，则 $b$ 序列形成一个 $1$ 到 $p-1$ 的排列，求这个排列的逆序对数量 $\bmod 2$。

  $p \le 10^{18}$
  多测，$T \le 10^5$
  1s

题目大意

  给定一个 $H\times W$ 的矩阵，每个格子要么是红色要么是蓝色。每次可以选择一个红色格子，然后把这一列或者这一行染白。问最多能染白多少格子，并输出一种方案。

  $H,W \le 2500$
  2s

题目大意

  给出一个序列 $a_1,\cdots,a_n$，你可以选择一段区间 $[l,r]$ 然后翻转 $a_l,\cdots,a_r$，使得 $\sum_{i=1}^{n-1} |a_i-a_{i+1}|$ 最小。

  $n \le 3\times 10^5,\ 1 \le a_i \le 10^9$
  2s

  好像又快过了一星期了。。。简要记一下好了。

  这是编译原理大作业的第一步：词法分析与语法分析，最终效果是构建出语法树。