我的生命已如风中残烛...
思维好题 问题等价于\(m\)个数和为0,
求所有前缀和都不小于零的排列的个数.
将所有权值 \(-1\) 就可以了.
可以在最后添加一个\(-1\),
这样就是求前\(m\)个大于, 把排列连成环,
这样就有一个很好的性质, 每个圆排列只有一种断开的方法.
这个画个图比较好理解, 假设当前已经是合法的方案,
左右移动一下再断开都是不合法的.
圆排列的排列数是\(m!\), 因为\(-1\)要钦定一个, 所以除以\(-1\)的个数.
最后答案就是\(\frac{m!}{m+1-n}\)
1 |
|
luogu: P6372
区间加区间sin和 线段树上只维护\(sin\)和是很难更新的，想到和角公式，维护\(cos\)的和。 \[sin(x+y)=sin(x)*cos(y)+cos(x)*sin(y)\]
\[cos(x+y)=cos(x)*cos(y)-sin(x)*sin(y)\]
这道题卡常，所以要尽量减少\(sin\)和\(cos\)的运算。
注意一下懒标记用\(long
long\)存就可以了。
时间复杂度\(O((n+m)log n)\)
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
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
using namespace std;
const int N = 5e5 + 10;
int n, m;
long long tag[N << 2];
double sinx, cosx, b[N], a[N], Sin[N << 2], Cos[N << 2];
int read() {
int w = 0;
char ch = getchar();
while(ch > '9' || ch < '0') ch = getchar();
while(ch <= '9' && ch >= '0') {
w = w * 10 + ch - 48;
ch = getchar();
}
return w;
}
void build(int l,int r,int p) {
if(l == r) {
Sin[p] = a[l];
Cos[p] = b[l];
return;
}
build(l, mid, lson);
build(mid + 1, r, rson);
Sin[p] = Sin[rson] + Sin[lson];
Cos[p] = Cos[rson] + Cos[lson];
}
void add(int p, long long v, double sv, double cv) {
double Sumsin = Sin[p];
Sin[p] = Sin[p] * cv + Cos[p] * sv;
Cos[p] = Cos[p] * cv - Sumsin * sv;
tag[p] += v;
}
void pushdown(int p) {
if(tag[p] != 0) {
add(lson, tag[p], sin(tag[p]), cos(tag[p]));
add(rson, tag[p], sin(tag[p]), cos(tag[p]));
tag[p] = 0;
}
}
void modify(int p, int l, int r, int L, int R, long long v) {
if(l > R || r < L) return;
if(l >= L && R >= r) {
add(p, v, sinx, cosx);
return;
}
pushdown(p);
modify(lson, l, mid, L, R, v);
modify(rson, mid + 1, r, L, R, v);
Sin[p] = Sin[lson] + Sin[rson];
Cos[p] = Cos[lson] + Cos[rson];
}
double query(int p, int l, int r, int L, int R) {
if(l > R || r < L) return 0.0;
if(l >= L && R >= r) return Sin[p];
pushdown(p);
return query(lson, l, mid, L, R) + query(rson, mid + 1, r, L, R);
}
int main() {
n = read();
for(int i = 1; i <= n; i++) {
int x = read();
a[i] = sin(x), b[i] = cos(x);
}
build(1, n, 1);
m=read();
while(m--) {
int opt, l, r, v;
opt = read();
if(opt == 1) {
l = read(); r = read(); v = read();
sinx=sin(v),cosx=cos(v);
modify(1, 1, n, l, r, (long long)(v));
} else {
l = read(); r = read();
printf("%.1lf\n",query(1, 1, n, l, r));
}
}
return 0;
}
题目链接：LOJ 2143
好像是循环矩阵一样的东西。
今天早上才做过一道用矩阵的[题目][https://www.luogu.com.cn/problem/P2886]
按照题目去算显然是会超时的， 可以按\(\bmod
k\)的余数分类。
设\(f[i][j]\)表示从\(i\)个数中选若干个数，余数为\(j\)的方案数。
转移是\(f[i][j]=f[i][j]+f[x][j-1]*f[y][j-2]\),\(((j-1+j-2)\bmod k=j)\).
因为只和\(j\)有关，
所以可以用矩阵快速幂优化。
注意\(k\)可能等于1，初始化的时候注意一下。
时间复杂度\(\mathjaxcal{O}(k^{2\log
{nk}})\)。
1 |
|
虽然构造数据只能拿来骗分，有时候作为辅助工具是比较方便的。
只用讲基本的操作。
大概是把相同的元素合并成一个块以减少时间复杂度。
1 | struct Node-t { |
注意 set 自带的 lower-bound 和 upper-bound 的时间复杂度为\(\mathjaxcal{O}(log n)\)。 但使用 algorithm
库中的 lower-bound 和 upper-bound 函数对 set
中的元素进行查询，时间复杂度为 \(\mathjaxcal{O}(n)\)。似乎是 set
不支持随机访问的原因。
s.insert(node(pos, r, v)).first 返回的是插入元素的地址。
1 | void assign(int l, int r, int v) { |
作用是推平一段区间，也是\(ODT\)时间复杂度的保证。
注意如果先 split 左端点再 split 右端点就会 RE，原因是 l 和 r 在一个 node
上时，split(r) 会 erase 这个 node 再重新插入，导致 split(l)
的迭代器失效。
没被卡的习题比较少... - 「SHOI2015」脑洞治疗仪 - 「Luogu 2787」理理思维 - 「Luogu 4979」矿洞：坍塌
放一下正经的题
- LOJ 2005 「TJOI /
HEOI2016」排序 - LOJ 2958
「COCI 2009.10」ALADIN
鸽了好多天，今天终于开始写了233...
实际上分块并不能算一种数据结构？
分块的基本思想是，将原来的数据经过适当的划分(分成一个个块的样子)。
每次修改和询问时，都把一个块内元素当作整体处理，而边角直接暴力。
莫队就是基于分块思想实现的。
分块的复杂度主要取决于块长，根据均值不等式，块长为\(\mathjaxcal{O}(\sqrt n)\)时最优。当然不能一概而论。详细分析可以阅读\(2017\)年国家集训队论文中徐明宽的《非常规大小分块算法初探》。 所以分块的时间复杂度一般都是带根号的...
块大小：
1 | size = sqrt(n - 1) + 1 |
1 | for (int i = 1; i <= block; i++) { |
看大佬的博客学习了一下.
有一个很好懂的\(\mathjaxcal{O}(n^3)\)的\(dp\)方法.
设\(f-i\)表示大小为\(i\)的无标号树的组成方式.
儿子的子树大小为\(i-1\),假设有三个儿子大小为\(a,b,c\),\(0\leq
a\leq b\leq c\leq i-1\).
分类讨论一下转移就可以了.因为无标号,所以不能简单的乘法原理.
1. \(a=b=c\),\(f-i+=\binom{f-a+3-1}{3}\)
2. \(a=b\), \(f-i+=\binom{f-a+2-1}{2}\times f-c\),\(b=c\)时也是同理.
3. \(a < b < c\), \(f-i+=f-a\times f-b \times f-c\).
1 |
|
因为\(n\leq 5000\),所以朴素的\(dp\)是过不了的.
考虑一下怎么优化.
普通的\(dp\)要去枚举所有子树的大小,那么有没有办法把大小一样的子树一起考虑,像树形\(dp\)一样去计算贡献.
设\(f[s][i][j]\)表示大小为\(i\)的树,根节点度数为\(j\),儿子的子树大小不超过\(s\)时的方案数.
考虑怎么转移, 假设大小为\(s\)的子树有\(k\)个.(\(k\times
s<i\)且\(k\leq j\)).
这\(k\)个子树的形态的方案数是\(\binom{(\sum{f_{s-1,s,j}})+k-1}{k}\).
在乘上\(f_{s-1,i-s\times
k,j-k}\)就是答案了.
用背包的方式来\(dp\),可以省去第一维空间.
石锤我不会写背包
1 |
|
给定一张\(N\)个点\(M\)条边的无向图，每条边要染一个编号在\(1\)到\(K\)的颜色。
你可以对一张染色了的图进行若干次操作，每次操作形如，在图中选择一个简单环（即不经过相同点的环），并且将其颜色逆（顺）时针旋转一个单位。
两种染色方案被认为是本质相同的，当且仅当其中一种染色后的图经过若干次操作后可以变成另一种染色后的图。
问有多少本质不同的染色方案，输出对\(10^9+7\)取模。 
首先考虑\(n\)个点的简单环怎么做。
根据\(Burnside\)引理，染色方案有\(\frac{1}{n}\sum\limits_{i=0}^{n-1}k^{(n,i)}\)种。
那么可以将图的所有点双联通分量单独处理。
\(BCC\)缩点后，边分为三种情况。1. 单边
2. 单环 3. 复合环。
单边就直接算就可以了。
单环之前考虑过了，其实复合环也很类似。
可以发现复合环是可以不改变其他边换掉其中两条边的。
所以不同的染色方案不同颜色的数量是不同的。
若每种颜色有\(p\)个\(，p-1+p-2+...+p-k=m\)的划分方法就是所有的染色方案。
用插板法就可解决，方案数是\(\binom{n+k-1}{k-1}\)。
最后问题就解决了!时间复杂度是\(O(n+2*
m)\) 。
1 |
|
还没改啊,先鸽着吧...
# Problem B. Dispatch Money
假设区间\([l,r]\)的逆序对数是\(f_{l,r}\).
显然\(f_{l,r}=f_{l+1,r}+f_{l,r-1}-f_{l+1,r-1}+[P-l>P-r]\).
即\(f_{l,r} + f_{l+1,r-1} \geq
f_{l+1,r}+f_{l,r-1}\),所以决策具有单调性.
那么可以用想到CDQ分治来优化这个\(1D\)的\(DP\)方程.
主要是快速算出区间的逆序对,感觉像莫队一样啊.
还是比较套路,不过这个\(\mathjaxcal{O}(nlog^3n)\)真的能过?
1 |
|
\[2^{a-l}+2^{a_{l+1}}+...+2^{a-r}=2^x\]
可以发现,\(x\leq
max(a-l,a_{l+1}...a-r)+log-2^{r-l+1}\).
所以固定一个端点时,枚举\(x\)的值去验证有没有等于\(2^x\)的区间是可行的.
但是\(2^x\)可能很大,高精度很麻烦也会\(TLE\),那怎么办呢?
可以选一个大质数,然后把\(2^{a-l}+2^{a_{l+1}}+...+2^{a-r}=2^x\)分别模上它也是相等的.
可以分治来做比较简单,每次找到当前区间的最大的\(a-i\),然后枚举\(i\)左边的区间或者右边的区间(取决于区间长度).
端点固定后,就枚举\(x\),然后去哈希表验证一下有没有这样的另一个端点,如果存在这样的区间,那么就是合法的.
注意一下细节: 1. 在哈希表中要插入\((key=0,val=0)\),因为区间\([1,r]\)可能是合法的,而对应区间的值是\(sum_r-sum_0\).
2.
要选一个尽量大的质数,不然出错的概率很大.哈希表也要选择一个尽量大的,比如\(114514\).
3. 另外要用快速乘,因为模数是大于\(2^{31}-1\)的.龟速乘可能会超时吧.
时间复杂度\(\mathjaxcal{O}(nlog^2n)\)
1 |
|
还没改这道题啊,暂时鸽了.QωQ.
据说是最简单的一道...
题目不太好懂啊,翻译一下就是,给你\(N\)个元素的序列. 
这个序列每个排列的代价是\(n+1\)顶点的完美匹配边权和(顶点\(u,v\)之间的边权是\(max_{i=u}^{v-1}a-i\)),问你最大代价.
可以暴搜发现这样匹配是最优的.
怎么计算每个元素的贡献是多少呢?
\(n\)是顶点数,考虑每个长度为\(\frac{n}{2}\)的区间.
假设现在选出了最大值是第\(i\)个,那么另外\(\frac{n}{2}-1\)个顶点要选比它小的值,方案有\(\tbinom{i-1}{\frac{n}{2}-1}\)种.
而这个顶点在数组中有\(\frac{n}{2}\)种放法,区间里的顶点可以任意排列,答案乘上\(\frac{n}{2}!\).
而区间外的顶点也是,有\((\frac{n}{2}-1)!\)种排列方法.
最后再乘上权值.
答案是\(\sum\limits_{i=\frac{n}{2}}^{n}a-i\times
\tbinom{i-1}{\frac{n}{2}-1}\times \frac{n}{2}\times \frac{n}{2}! \times
(\frac{n}{2}-1)!\)
1 |
|
写完一次就 AC 了是我没想到的...
可以假设增加了\(c\)亮度.
即求\(\sum\limits_{i=1}^{n}(x-i-y-i+c)^2\)的最小值.
把式子展开, \(\sum\limits_{i=1}^{n}x-i^2+\sum\limits_{i=1}^{n}{y-i}^2+nc^2+2c(
\sum\limits_{i=1}^{n}(x-i-y-i))-2
\sum\limits_{i=1}^{n}x-iy-i\)
可以发现前面两项是固定的.
因为c比较小, \(|c|\leq m\),
中间两项可以直接枚举\(c\).
所以只需要求出\(\sum\limits_{i=1}^{n}x-iy-i\)的最大值.
因为可以旋转, 等价于\(\sum\limits_{i=1}^{n}x_{n-i+1}y-i\).
可以看出这就是卷积的形式.
断环成链, 即求\(\sum\limits_{i=1}^{n}x_{n-i+1+k}y-i\),
\(0 \leq k\leq n-1\).
所以把\(x\)翻转后,复制成两份做
fft.
第\(n+1\)到\(2n\)的系数就对应了旋转后的\(\sum\limits_{i=1}^{n}x-iy-i\).
取一个最大值就做完了.
注意数组要开大一些, 因为还要把\(x\)复制一份.
\(c\)要在\(-m\), \(m\)之间枚举, 因为展开后的式子可能是\(x-i-y-i\), 也可能是\(y-i-x-i\).
1 |
|