¶ 概述

你有一个字符串 $s$ 你有一个神奇的函数 $f$ 可以使

• $f(s)\in R$
• $s_1 \neq s_2$ 时基本上不会出现 $f(s_1)=f(s_2)$

一种常见的 $f$ 构造方法是

题意

当一个数组 $b$ 至少有一个长度为奇数的连续回文子串时，称 $b$ 是坏的，否则称 $b$ 是好的。

给你长度为 $n$ 的数组 $a$，其中 $−1$ 可替换为任意从 $1$ 到 $k$ 的整数。

求好数组的个数，对 998244353 取模。

简介

对于这样一类题目：给定一棵 $n$ 点树，有 $q$ 个询问，每个询问关于树上 $k_i$ 个点， $n,q,\sum k \leq 10^5$

朴素做法 $O(qn)$

由于一些题目的特殊，发现求解只需保留树的结构，故可以重构一棵虚树

虚树包含了所有的 $k$ 个关键点和它们两两之间的 LCA，这样可以保证这虚树的节点个数 $< 2k$，保证了复杂度

flag: 我有一天我会写出两个头文件

• advanced_data_structure.h
• algorithm++.h

A simple terminal OI/ACM answer checker on Linux/UNIX

acejudge 是一个命令行的 judger

因为没有文档，所以写了一个指南

安装

1
2

git clone [email protected]:laekov/acejudge.git && cd acejudge
make && sudo make install

使用

¶ 配置文件

假定配置文件名为 w.cfg

1
2
3
4

一个 printf 式的格式化字符串作为输入文件
一个 printf 式的格式化字符串作为答案文件
第一个数据编号 最后一个数据编号 时间(ms) 内存(MB)
源程序名 

¶ 前置技能

¶ 虚数

¶ 复数

任意复数 $z$ 都可表示为 $a+bi(a,b\in R)$

$a$ 叫做实部，定义 $\mathrm{Re}(z) = a$

$b​$ 叫做虚部，定义 $\mathrm{Im}(z) = b​$

线段树原理非常简单，但如何优雅的实现却是一个问题

¶ 线段树简介

线段树就是把一个序列原有 $n$ 个点扩充为 $n\log n$ 个点，保持一定结构进行加速

每个点有

• 自己管辖的区域
• 两个拼起来是自己的子节点（ $self = lson \cup rson$ ）
• 子节点不交（ $lson \cap rson = \varnothing$ ）
• 可以快速的区间合并

我写这一题是因为 BZOJ 的讨论

线段树（动态开点）裸题，讨论有点烦

题目链接

题目非常简单，只要实现不带修改的区间个数查询就可以了（还有适当剪枝

题目链接

首先观察求平均数的公式

所以我们要么改变 $sum$ 要么改变 $n$

如果忽略 $k$ 这个条件，我们有以下解法