Problem

Time limit : 2sec / Memory limit : 256MB

将$1-n$顺序加入双端队列（每次可加头可加尾），再删除（每次可删头可删尾），求有多少种删除序列，使得$1$是第$k$个被删的。

传送门

Problem

Time limit : 2sec / Memory limit : 256MB

题意简述：

有$n$个方块排成一行，从左到右编号为$1$到$n$。最初所有的方块都是白色的。我们还有$N-1$台涂漆机，编号为$1$至$N-1$。当操作时，第$i$号机器把第$i$和$i+1$号方块染黑。

Snuke将逐个操作这些机器。他操作它们的顺序是$(1,2,…,N-1)$的一个排列$P$,这意味着第$i$个操作的机器是机器$P_i$。

排列$P$的得分被定义为当机器以$P$指定的顺序操作时，在所有方块第一次被涂成黑色之前操作的机器的数量。找出他所有可能排列的得分总和。因为这可能非常大，计算模$10^9+7$。

door♂

Problem

Time limit : 2sec / Memory limit : 256MB

题意简述：给你一棵由$0$和$1$组成的树（就是每个点的权值为$0$或者$1$），让你求该树的一种排列，使得每个节点的孩子都排在这个节点的后面，并且逆序对数量最小。

door♂

Problem

Time limit : 2sec / Memory limit : 256MB

我们有一个整数序列$A$，其长度是$N$

请找出其总和为$0$的$A$的非空邻接子序列的数目。请注意，我们正在计算取出子序列的方法。也就是说，即使某些两个子序列的内容相同，如果它们取自不同的位置，则对它们进行单独计数。

door♂

代码：后缀排序

读入一个长度为 $n$ 的由小写英文字母组成的字符串，请把这个字符串的所有非空后缀按字典序从小到大排序，然后按顺序输出后缀的第一个字符在原串中的位置。位置编号为 $1$ 到 $n$。

除此之外为了进一步证明你确实有给后缀排序的超能力，请另外输出 $n−1$ 个整数分别表示排序后相邻后缀的最长公共前缀的长度。

『JZOJ 4669』【NOIP2016提高A组模拟7.19】弄提纲

Problem

link

窗函数

实在是无聊（主要是因为llc神犇在上学期提过窗函数，然而我当时并看不懂，这次把坑填上…)…然后看了几篇关于窗函数的资料…本文就权当抛砖引玉吧

数字信号处理的主要数学工具是傅里叶变换，而傅里叶变换是研究整个时间域和频率域的关系，当运用计算机实现测试信号处理时，不可能对无限长的信号进行测量和运算，而是取其有限的时间片段进行分析。

• 从信号中截取一个时间片段，然后用截取的信号时间片段进行周期延拓处理，得到虚拟的无限长信号，再进行傅里叶变换和相关分析。无限长信号被截断后，其频谱发生了畸变，我们称为频谱能量泄漏，为了减少频谱泄漏，可采用不同的截取函数对信号进行截断，截断函数称为窗函数，简称为窗。

基础乐理与数学（二）

Read before

阅读本文之前，您先需要阅读基础乐理与数学（一）

五线谱进阶

五线谱中的相对音程

上一讲我们已经知道了高音五线谱中，第二间的$A$的音高定为$440\rm Hz$，很自然地引出了一个问题，我们如何来确定其它音的音高？下面将会按照十二平均律的法则在五线谱中建立相对音高系统。

基础乐理与数学（一）

声学基础

　　乐理的基本内容包括：和声、调式、节奏、结构、曲式。主要来说，音乐的组成从简单到复杂依次是：纯音、谐波、拍音、和声、调式、曲式。下面只介绍前几种基本的音乐组成单元。

音与音的复合

• 音：

能被人类的听觉所感知的一段声波，通常可以用一个声波的波形来表示。

音的本质是一段声波（根据人耳辨别范围可知声波频率应在$20{\rm Hz} -20000\rm Hz$之内）。

一般音乐中的每个音都是周期性的，这在后面音的谐和部分会提到。

音是可以叠加的，后一个音出现时，前一个音可能尚未消失，这就关联到声波方面的傅立叶变换。音是音乐的最基本的组成单位。

• 音的复合：

说到声波最先想到的最简单的波形即是正弦波，即以某个固定频率进行简谐振动所产生的声波。

这种声波被称为纯音，比如音叉的声音或$220\rm Hz$正弦波。

纯音显然几乎没有音色可言，音与音的复合形成了复合音。

复合音一般分为两种：谐波叠加与拍音叠加。

『Codeforces 985D』Sand Fortress

Problem

窝不想抄题目了…

题目描述：

你有$n$堆沙子，最左边的沙子的最大高度不能超过$H$，让你在一个从$1$到$\infty$的一维平面内放沙子，且要满足相邻两个坐标的沙子的高度不能超过$1$。问沙子能够占用的最少坐标点的个数。

Solution

因为题目要求相邻两个坐标的沙子高度不能超过$1$，这代表最后一堆沙子的个数也必定为$1$。

而题目要我们求占用坐标点的最少个数，根据贪心的思想，要使占用的点最少，则我们必须要贪心地令沙子的高度尽可能高。

• 因为最后一堆的沙子的个数为$1$，所以沙子的高度所形成的曲线必定是先增后减的或者一直减小的曲线。

  • 沙子的高度存在单调性！
  • 二分答案

  • 不断二分占用坐标的个数即可。

    而二分的$\rm check$函数，我们因为最优的情况下，两两沙堆相差均为$1$，因此我们可以运用等差数列求和公式求出总的沙子堆数，并用它与$n$进行对比进行二分即可。

    值得一提的是，当枚举出$n$为奇数的时候，会出现有两个坐标的值均相当的情况，需要注意

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll n, h;
const ll cnt = 2000000000;
inline bool check(const ll &x)
{
	if (x <= h)
	{
		if (x >= cnt) return true;
		return (x * (x + 1) >> 1) >= n;
	}
	register ll a = ((x - h) >> 1) + h;
	if (a >= cnt) return true;
	if ((x - h) & 1)
		return ((a * (a + 1) >> 1) + ((a + h) * (a + 1 - h) >> 1)) >= n;
	return ((a * (a + 1) >> 1) + ((a - 1 + h) * (a - h) >> 1)) >= n;
}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	cin >> n >> h;
	register ll ln = 1, rn = n;
	while (ln <= rn)
	{
		ll mid = (ln + rn) >> 1ll;
		if (check(mid)) rn = mid - 1;
		else ln = mid + 1;
	}
	cout << rn + 1;
	return 0;
}