2019.9.9 P4462 [CQOI2018]异或序列

口胡一下。

开个桶记录异或值,然后就可做了。

代码先坑着,还没写完。

upd on 2019.9.10 22:09

代码写完了,cmp写错了调了好久

代码

2019.9.10 校内训练20190910 T1 旅馆

大原题+sb题

将$1$到$v$之间的房号分给两批客人,要求给第一批客人分的房间房号不是$p1$的倍数,第二批客人分的房间房号不为$p2$的倍数,求最小的$v$。

直接上二分啊。

但是要注意,$n1+n2<=Mid-Mid/(p1 * p2)$,保证有足够的数,以至于不会被数重复使用。

代码

upd on 2019.10.13

咕了好久,赶紧补一下

[FJSC2019D5T3]魔术帽游戏(magic)

首先依旧先将所有询问读入一遍,开两个链表$l$,$r$,指向操作序列数组,表明该询问在哪一个操作序列开始,在哪一个结束;

我们可知,将球移动到其他位置,相当于将球所在的魔术帽与另一个魔术帽交换;

于是将操作序列按照顺序模拟一遍;

如果有一个 $l_i$
指针指向当前位置,记录下位置为 $x_i$的魔术帽的编号;

如果有一个 $r_i$
指针指向当前位置,输出 $l_i$

指针所记下的魔术帽目前所在的位置;

复杂度: $O(m+q)$

代码

[HNOI2012]永无乡

平衡树启发式合并或者线段树合并

平衡树:每合并两个点,就将这两个点进行启发式合并。

然后看到求k大,就能用平衡树做。

线段树:看到查询k大,就能想到权值线段树。

然后怎么合并呢?

容易想到线段树合并

连通性用并查集维护一下就行了.

显然线段树合并更好写吧。虽然我做这道题是来练习Splay的…

代码

bzoj3798 特殊的质数

分块打表,块外的有表,块内的暴力。

代码

[FJSC2019D5T2]行商(trade)

三分求单峰函数最大值

代码

三国杀1v1大赛

$dp$

设$f_{i,j}$表示前$i$场比赛前$j$个人(重新排序后)的最小值。显然$f_{i,j} = min(f_{i,j-1}, f_{i-1,j-2})$, 其中,$j >= i * 3$, 这样一来我们就可以确保,一定每组都有裁判。

代码

codevs 特种部队

我们可以分成两条路

$f_{i,j}$代表一条路走到$i$,一条路走到$j$的最小值

那么转移方程就是$f_{i,k}=min(f_{i,j}+dis_{j,k})$

$f_{k,j}=min(f_{k,j}+dis_{i,k}) (k=max(i,j))(dis_{i,j}=a_j-a_i)$

代码

数学题

一道双搜好题

把6个数前三个分一组,后三个分一组,把前三个数和后三个数所有可能的情况都搞出来,如果前三个数的某个和与后三个数的某个和的和为0,就会贡献答案。

于是开个哈希表,记录前三个数加起来和为x的方案数,这一步来一个dfs,然后下一步再用一个dfs找后三个数加起来的和为-x

代码

upd on 2019.10.14

P5160 WD与循环

计数题

首先要把题面中的代码的意思搞清楚

1
2
3
4
5
6
7
8
9
10
int cnt = 0;
for (int a_1 = 0; a_1 <= m; a_1++) {
for (int a_2 = 0; a_1 + a_2 <= m; a_2++) {
...
for (int a_n = 0; a_1 + a_2 + ... + a_n <= m; a_n++) {
cnt = (cnt + 1) % 19491001;
}
}
}
printf("%d\n", cnt);

我们感性理解一下,这个就是求有多少个数列${a_1,a_2,…a_n}$

满足$a_1+a_2+…+a_n<=m$

$a_i$可以取$0$,比较难搞,那么我们就把$a_i+1$,变成

$a_1+a_2+…+a_n<=n+m$

然后就变成一个简单的数学题了

代码

upd on 2019.10.16

P2327 [SCOI2005]扫雷

我们设$f_{i,0/1,0/1}$表示第$i$个格子是否是雷,下一个格子是否是雷。

那么转移就很好写了…

代码

P1725 琪露诺

经典的单调队列优化$dp$

代码

P3173 – [FJSC2017D5T1]邮局选址

设$f_{i,j}$表示前$i$个小屋,建立$j$个加油站的最小距离。

然后预处理出$g_{i,j}$,表示第$i$个小屋到第$j$个小屋只建立一个加油站的最小距离和。

然后转移方程就是$f_{i,j}=\min(f_{i,j},f_{k,j-1}+g_{k+1,j})$ $(k<i)$

代码