由于作者水平就只能到模板，所以笔记也就写到这里。 FFT简介FFT是干啥的？它是用来加速多项式乘法的。我们平时经常求多项式乘法，比如$(x+1)(x+3)=(x^2+4x+3)$。假设两个式子都是$n$项（不足的补0），那朴素的算法是$O(n^2)$的。那么，我们能做到$O(nlogn)$做么？你也 ...

前言我叫zps，准考证号JS-00810，来自苏州。今年我AK了CSP-J。总体感觉还是很水的，但是似乎没什么人AK。我表示不理解。总之，写个博客好了。 T1 数字游戏(number)题面给定一个保证长度为$8$的01字符串，求这个字符串中有多少1。 题解这还要解？签到题好吧…只要会打文件就能过。 ...

题意简述若干的序列，长度和不超过$2e5$。请你选择两个序列，从两个序列中恰好各删除一个数，使得两个序列的和相等。如果珂以，输出”Yes”，并输出是从哪两个序列中删除了编号为多少的元素。多解输出任意一个。无解输出”No”。 思路框架STL的map维护 具体思路对于每个序列，对于不同的元素，每个都把（ ...

题意简述给定$n,k$，求一个长度为$n$的数列，使得对它进行归并排序要调用$k$次$MergeSort$函数。 注：$MergeSort$：对$l,mid$和$mid,r$进行分治操作，如果有序，直接返回（不过也是要算一次调用）。否则就合并一下再返回。 思路（水题，一句解决）初始化为$1,2,3… ...

题意简述给定一个序列，长度$1e5$，每个数的绝对值小于$1e9$，还有一个$-10<=k<=10$，请你求出有多少个区间的和是$k^a$的形式，其中$a$为自然数。 思路框架开个平衡树记录一下即珂。 具体思路$k=\pm 1$的情况特判。 首先，区间和$[l,r]$珂以拆成$sum[r ...

题意简述给定一颗无根树，每个点有颜色，请确定一个点，使得以这个点为根，则所有子树中都是一个颜色。为防歧义，良心插图。 如图： 思路设c为满足链接的两个点颜色不一样的边（简称“异色边”）的个数。找到一个点，使得这个点连出去的异色边数量==C，那么这个点就是我们要找的根。否则就没有这样的根。 具体思路这 ...

题意简述 维护一个序列，支持两个操作： 区间加某个数 求区间斐波那契的和。形式的说，设f_i表示斐波那契的第i项，f_1=f_2=1,f_n=f_{n-1}+f_{n-2}。设原序列为a。则区间[l,r]的斐波那契和为：f_{a_l}+f_{a_{l}+1}+f_{a_{l}+2}...+f_{a ...

题意简述一个岛屿上有$a$只A类生物，$b$只B类生物,$c$只C类生物。其中A吃B，B吃C，C吃A。每个时刻，每一对动物相遇的概率都是等概率的。若干时刻后，岛屿上应该只剩下一种动物。对于A,B,C，求出剩下的最后一种动物是A，B，C的概率。$1<=a,b,c<=100$ 思路设状态由于 ...

题意简述$n(<=2000)$个人上电梯。每一秒，队列的第一个人都有$p$（每个时刻都是$p$，不会变,$0<=p<=1$）的概率上电梯。请求出$t(<=2000)$秒时电梯上人数的期望值。 思路框架dp[i][j]表示第$i$时刻有$j$个人在电梯上的概率。最后用概率乘以数 ...

题意简述给定n(个数a_1,a_2...a_n，2，把这n个数分成几组，使得每组中能排出一个序列，并且相邻两个和都是质数。输出方案。 思路注意：2。所以，我们将a按奇偶分类，只有奇数能和偶数在一块，奇数和奇数不能一块，偶数和偶数不能一块。所以我们把它们按奇偶分类，又注意到n，考虑网络流。 对于偶数 ...