CF981D/E补题

世界上有10种人,一种懂二进制,一种不懂(我)。

981D

感谢蔡队抬一手。

题意:长度为$n$的数组,分成连续的$k$段,段内加法,段间按位与,最后求最大值。
首先二进制按位贪心,即从高位开始贪心当前位$1$是否可行;
判断可行性就需要dp,这里需要满足在前面贪心出来的答案也可行;
状态定义:$dp[i][k]$ 表示第k段以i结尾时可行。
转移方程:$dp[j][k+1] = ((sum[j]-sum[i-1]) \& mask)==mask$,枚举第$k+1$段右端点$j$时,条件是$dp[i-1][k]=true$(第$k$段右端点是$i-1$时可行)
复杂度是$O(log(S) \times n \times n \times k)$

Mehr lesen

树分治

qzc大神的那篇论文很早就看了,当时没有理解,这个坑就一直在那了。
最近又想起来去看看,突然好像有点懂了,然而现在只会裸题。

如果我们有一个和路径相关的问题,那么可以想想是不是能用点分治处理。

递归分治

1
2
3
4
5
6
7
8
9
10
11
12
void dfs(int x) {
ans += solve(x, 0);
vis[x] = 1;
for (int i = head[x]; ~i; i = e[i].next) {
int v = e[i].to, w = e[i].val;
if (vis[v]) continue;
ans -= solve(v, w);
sum = sz[v]; root = 0;
get_root(v, 0);
dfs(root);
}
}

Mehr lesen

Codeforces935E

蔡队给的题还是非常的有水平。

题意:给一个字符串,是由(), ?, 数字组成的表达式;
?可以变成+/-,问这个表达的最大值;
字符串长$1e4$,+/-中少的那个不超过$100$;

Mehr lesen

Dancing Links

舞蹈链,一个非常优雅的名字,实质上是搜索。
问题:给定一个n*m的矩阵,有些位置为1,有些位置为0。

  1. 选定最少的行,使得每列有且仅有一个1.(精确覆盖)
  2. 选定最少的行,使得每列至少一个1.(重复覆盖)
    实现是用了一个十字链表的数据结构,可以快速的删除和恢复矩阵的行列。

Mehr lesen

网络流的一些套路

最基础的増广路、残流网的算法思想一定要非常清楚,Dinic,SAP基于増广路的思路去优化的。

记录一下网络流的建模常见基本套路。

最大流最小割定理

结论:对于任一个网络流图来说,其最大流一定是小于等于最小割的。

Mehr lesen

domjudge配置

春季赛总算是没有崩的太惨,万幸,体验上来说要比PC^2好用一些吧。
上午热身赛的时候,判题机一下子炸了一半,顿时感觉心凉。
后来发现terminal里信息显示需要输入密码,想到可能是没有复制文档里说的权限文件,拷过去后发现没有问题了。
下午正式比赛的时候,9台机器每台同时可以跑4个提交,完全没有判题的压力。

Mehr lesen

C++ Primer chap5&6

异常处理机制:

  • throw表达式。
  • try语句块,抛出的异常被某个catch子句处理。

Mehr lesen

最短路判负环

一般的做法是bfsSPFA判断一下入队次数是否大于n次。
一个更好的想法是,用dfs版本的SPFA,判断存在一点在一条路径上出现多次。
把距离数组初始化为0,这样初始化后第一次只会加负边权松弛,枚举每个点为起点,找到一个负环就停止。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
void dfs(int x) {
vis[x] = true;
for (auto pii : g[x]) {
int v = pii.first;
int d = pii.second;
if (dist[v] > dist[x] + d) {
dist[v] = dist[x] + d;
if (vis[v]) {
flag = true;
return;
}
dfs(v);
}
}
vis[x] = false;
}

Mehr lesen

Codeforces Round 456

Solved only: A, B

A

x需要2个A
y需要1个A,1个B
z需要3个B

问还缺少多少A,B

B

从1~n中拿k个数xor起来,要求最大值。

Mehr lesen

从头开始之基础思维训练

51nod 1007 正整数分组

想到两组数都接近所有数和的一半的话差是最小的,那么01背包一下就好了。

Mehr lesen