发表于 | 更新于 | 阅读次数：

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)$

代码