全源最短路径的一种错误解法
错误代码
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
int main() {
while (~scanf("%d", &N)) {
// assume that if no edge i->j, then input w[i][j] will be INF
// and assume that w[i][i] == 0
FWD(i, 0, N) {
FWD(j, 0, N) {
scanf("%d", &w[i][j]);
}
}
memset(dp, 0xff, sizeof(dp));
FWD(i, 0, N) {
FWD(j, 0, N) {
// if i == j, dfs can still return true answer
dfs(i, j);
}
}
FWD(i, 0, N) {
FWD(j, 0, N) {
printf("%15d", dp[i][j]);
}
printf("\n");
}
}
}
bool visit[MAXV];
int __dfs(int now, int target);
int dfs(int from, int target) {
memset(visit, 0, sizeof(visit));
visit[from] = true;
return __dfs(from, target);
}
int __dfs(int now, int target) {
if (dp[now][target] > -1) {
return dp[now][target];
}
if (now == target) {
dp[now][target] = 0;
return 0; // visit[now] will never be true;
}
int ans = INF;
FWD(i, 0, N) {
if (visit[i] || w[now][i] == INF || i==now) { // avoid rings and not edge
continue;
}
visit[i] = true;
int p = __dfs(i, target) + w[now][i];
visit[i] = false;
if (p < ans) {
NEXT[now][target] = i; // record the NEXT vertex of i in the shortest path now->target
ans = p;
}
}
dp[now][target] = ans;
return ans;
}不可以使用这种dp
对于每对点执行dfs，然后执行过程中，记忆化搜索。当然，为了避免执行过程出现不断的走环路的情况，需要使用visit，避免dfs过程中走环路。
虽然复杂度是$O(V^3)$ ，但是算法是错的
记忆化搜索计算$(begin,target)$ 时，假设dfs过程中经过了点
i，为了避免环，i不可以经过begin，但是，可能$(i,target)$ 的最优路径就是i经过点begin到达的。但是，记忆化过程中，却把在dfs$(begin,target)$过程中 计算出来的$(i,target)$ 作为
i到target的结果。
NYOJ7
题目描述:
一个街区有很多住户，街区的街道只能为东西、南北两种方向。
住户只可以沿着街道行走。
各个街道之间的间隔相等。
用(x,y)来表示住户坐在的街区。
例如（4,20），表示用户在东西方向第4个街道，南北方向第20个街道。
现在要建一个邮局，使得各个住户到邮局的距离之和最少。
求现在这个邮局应该建在那个地方使得所有住户距离之和最小；输入描述:
2
3
4
> 每组第一行一个整数m<20,表示本组有m个住户，下面的m行每行有两个整数0<x,y<100，表示某个用户所在街区的坐标。
> m行后是新一组的数据；
>
输出描述:
2
>
样例输入:
2
3
4
5
6
7
8
9
10
11
12
> 3
> 1 1
> 2 1
> 1 2
> 5
> 2 9
> 5 20
> 11 9
> 1 1
> 1 20
>
样例输出:
2
3
> 44
>
- 考虑横坐标的情况，取那个横坐标可以使得大家的在横坐标上需要走的距离最短？显然是中位数——反证法，加入有N个点，如果N是奇数，那么中位数就是d[N/2]，然后，尝试采用第N/2-1个点计算，显然，总量的变化是（设 t = d[N/2]-d[N/2-1] ），$+t(N/2+1)-tN/2$ ，也就是缩短的对于前N/2的用户来说，是缩短了，但是对于后面N/2+1个用户来说延长了
- 所以，无论y坐标取值多少，x坐标都要取中位数。同理，y也要取中位数
01背包
- 动态规划算法是伪多项式复杂度$O(NW)$，如果W很大，那么可能，直接枚举N元素的集合的所有子集会更快一些
找出一个序列中任意长度的逆序对
- 首先定义什么是逆序对：比如一个序列是从小到大排列的，那么如果$x_i>x_{i+1}>x_{i+2}>…$那么就是逆序对
- 主要思路是，对于n元逆序对，flag数组中的index表示某个序列中的某个等于index的数，而flag[index]的值表示以这个index结尾的n-1元的逆序对的数量
- 假设序列有n个数，数的范围是[0, MAX], 首先搞一个int flag[MAX+1], 该数组的所有值初始化为0，还有一个int result[n]
- 首先看看如何求二元逆序对
- 从左到右扫描序列，对于值位置为
i的值x，flag[x]+=1 - 然后此时，以该x结尾的逆序对的数量就是$\sum_{j=x+1}^{MAX}flag[j]$，将这个数量记录在result[i]
- 那么result的数组的和就是逆序对的数量
- 同样的，在刚才flag[x]+=1的步骤，可以输出后面的数与x组成的序对来输出具体的逆序对
- 从左到右扫描序列，对于值位置为
- 三元组的，我们已经用上面的方法求出二元的result数组(此处将其记为result_2数组)，此时设另外的两个数组int flag_3[MAX+1], int result_3[n];
- 同样扫描序列，对于位置为
i的数x，取出result_2[i]的值，也就是以该x结尾的二元组逆序对的数量m，然后flag_3[x]+=m。此时flag_3[x]记录了截止目前，以x结尾的二元组逆序对的数量 - 求$\sum_{j=x+1}^{MAX}flag_3[j]$，得到以x结尾的三元组逆序对的数量，记录在result_3[i]中
- 到最后，result_3就是结果
- 同样扫描序列，对于位置为
- 更多元组的也如此思路
- 这是利用数组记录了当前已经有的数，然后新加入的数如果不是该数组中当前index最大的，那么意味着其比之前加入的一些数小，这就形成了逆序对
- 对于n元逆序对，同理，数组记录了当前已有的数
x作为最后一个元素是x的n-1元逆序对的逆序对的数量，然后如果我们往该数组加入一个数，然后这个数不是index最大的，那么其比之前已经加入的一些数小，从而与比他大的数代表的n-1元逆序对形成了更长的逆序对 - 然后，既然这其中，对数组求和很重要，我们就可以利用树状数组优化这个往flag[x]中增加数值然后求和计算出对应result[i]的过程（原始序对中第
i位的值是x）
3p另一种思路：针对三元逆序对，还有一种简单的解法，先把数据按顺序插入，用树形数组记录此时比这个数大的数的数目x，再把数据倒着插入，用另一个树形数组记录此时比这个数小的数的数目y，x*y=以这个数为中心的三元逆数对数目，把各个数计算累计起来即可（来自17级大佬Potatso）
关于使用优先队列的bfs
- 其实就是dijstra单源最短路径算法
- 关于O((V+E)lgV)：对每个点都需要从堆中pop出来（除了源点），对于每条边，都需要把该边对应的一个点压进堆里或者decrease key，consider that，如果一个点被pop出来，那么该点就在result set里，所以不会再被压到堆里。所以是O((V+E)lgV)，如果使用斐波那契堆，因为压到堆里以及decrease key的代价是O(1)，所以是O(VlgV+E)
DP
- DP要找到什么因素影响了当前你要求的东西，有影响的我们就处理，没影响的我们不用管
浮点数输入
- 由于是二进制，所以有些十进制有限小数成了无限的，所以读取时会截断，所以要加上一个偏移量（比如读入到小数点后6位，可以加一个$2*10^{-7}$，这样，截断部分如果比较大，就可以反映出来，如果比较小，不会对产生进位，则没影响）
枚举所有素数
- $O(N)$ 的做法
1
2
3
4
5
6
7
8
9
10
11
12const int CNT = (int)1e9+10;
bool a[CNT];
int main() {
a[0] = a[1] = true;
FWD(i, 2, CNT) {
if (a[i]) {
continue;
}
for (int j = 2 * i; j < CNT; j += i) {
a[j] = true;
}
}
树状数组
注意，a[0]是没有放东西的，因为$i-lowbit(i)+1 > 0$
插线问点中，每一点 i 的值都是 sum(a[1] to a[i])。
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//NYOJ 123
int c[1000010],N;
int lowbit(int x) //求最低位1的位置所表示的数
{
return x&(-x);
}
void update(int p,int q)//常规数组中的a[p]更新，在树状数组中需要这样更新
{
while(p<=N)
{
c[p]+=q;
p+=lowbit(p);
}
}
int S(int x) //S(i)表示的是的前i个数的和
{
int sum=0;
while(x>0)
{
sum+=c[x];
cout<<"sum: "<<sum<<" ";
x-=lowbit(x);
}
cout<<endl;
return sum;
}
int main()
{
int T;
char s[10];
scanf("%d%d",&T,&N);
while(T--){
scanf("%s",s);
if(s[0]=='A'){
int l,r,num;
scanf("%d%d%d",&l,&r,&num);
update(l,num);
update(r+1,-num);
//每个士兵 i 的军功都是前 i 个元素的和，所以，[l, m]区间每个人加 num 的军功只需要给
//l 位置加上num，这样，[l, N]区间的每个人都加上了 num ，但是，我们只要[l, m]，所以要
//给 m+1 位置减去num,
}
else {
int x;
scanf("%d",&x);
printf("%d\n",S(x));
for(int i=0;i<=x;i++) {
cout<<c[i]<<" ";
}
cout<<endl;
for(int i=0;i<=x;i++) {
cout<<S(i)<<" ";
}
cout<<endl;
}
}
return 0;
}
离散化
-
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
using namespace std;
double x[201],y[201],s[101][4];
int xy[201][201];
int n,cas=0;
double sum;
int main()
{
int i,j,k;
while(cin>>n)
{
if(n==0) break;
cas++;
k=0;
sum=0.0;
memset(xy,0,sizeof(xy));
for(i=1;i<=n;i++)
{
cin>>s[i][0]>>s[i][1]>>s[i][2]>>s[i][3];
x[k]=s[i][0];
y[k]=s[i][1];
k++;
x[k]=s[i][2];
y[k]=s[i][3];
k++;
}
sort(x,x+2*n);
sort(y,y+2*n);
for (int i=1;i<=n;i++)
{
int i1=lower_bound(x,x+2*n,s[i][0])-x;//二分查找，跟普通的FOR语句一样
int j1=lower_bound(y,y+2*n,s[i][1])-y;
int i2=lower_bound(x,x+2*n,s[i][2])-x;
int j2=lower_bound(y,y+2*n,s[i][3])-y;
for (int p1=i1;p1<i2;p1++)
//标记状态，记住我们是以一个方块的角标记状态所以p1<i2，不是<=
for (int p=j1;p<j2;p++)
xy[p1][p]=1;
}
for (int i=0;i<2*n;i++)//统计
for (int j=0;j<2*n;j++)
if (xy[i][j]) {
sum+=(x[i+1]-x[i])*(y[j+1]-y[j]);
}
printf("Test case #%d\n",cas);
printf("Total explored area: %.2f\n",sum);
printf("\n");
}
return 0;
}其实就是，把坐标间的距离都忽略掉，把坐标的集中在一起，一个挨着一个，然后遍历整个标记区域，某个单元格有标记说明该位置两边都对应地存在两个坐标（原始数据中的），则只需要知道这两个原始数据中的坐标相差多远，就可以知道这个标记代表着多大的面积。
POJ3278
- N是人的位置，K是牛的位置
- 一种lgN的做法
- 如果N的二进制大于等于K的二进制，则直接走x-1法
- 否则，想办法修改N的二进制使得其与K的二进制的最高几位重合，然后接下来的二进制就直接用x2和+1来实现（二进制位为0则x2，为1则+1）
- 假设K与N重合的二进制部分为W
- 如果W<N，可以消减N使得N==W，也可以N乘以多次2然后减去一些1使得N与新的W相同（因为随着N×2，其与K重合的最高二进制位变多，所以说是新的W）
- 如果W>N，可以先进行多次加一使得重合，或者是多次×2后多次-1使得重合
- 即使W小于N，也有可能先乘以几次2后在进行几次-1比较高效（因为可能后面很多个1，导致如果直接消减W）
- 总结起来就是，构造W与N相同的过程中，可以对N乘以一次2、两次2…P次2，对于每种乘2，减去或加上一些1使得重合，然后再计算在此基础上需要的时间
- 也就是不断试错的过程
子集和问题的动态规划解法
- 如果只是要求出是否有一个解法，或者是要求出有多少个解法，那么动态规划可行
子集和问题变形
- 问题：给定一个正整数M和另一个K，要求求出M切分成K份，每份都是正整数的解法有多少。同样可以动态规划
floyd求最小环
- 最小环的定义：在有向或是无向的简单图中在找到一条路径，其从点x到点x，总的权重最小。（不可以直接x到x，在无向图中也不可以利用x到y，y到x，因为如果可以这样，意味着多重边或是使用同一条边）
- 如果可以确定w[x][x] = INF，那么floyd然后找到最小的w[x][x]既可。
- 否则，不可以通过使得所有的w[x][x]变为INF来实现，因为floyd过程中，会使用到
查询第K大
- 如果是静态数组，多次查询，直接一个sort
- 如果是静态数组，一次查询，算导中那个快排变体，$O(N)$
- 如果是动态数组，字典树——每个数以二进制表示，构造字典树，字典树的node需要维护当前node为root的子树的叶子数目，从而在任意一个非叶子节点，可以选择要走那条路下去——可以算出，二进制比x进制更快
Nim游戏（博弈论）
定义P-position和N-position，其中P代表Previous，N代表Next。直观的说，上一次move的人有必胜策略的局面是P-position，也就是“后手可保证必胜”或者“先手必败”，现在轮到move的人有必胜策略的局面是N-position，也就是“先手可保证必胜”。更严谨的定义是：1.无法进行任何移动的局面（也就是terminal position）是P-position；2.可以移动到P-position的局面是N-position；3.所有移动都导致N-position的局面是P-position。
- P-position需要保证所有子格局都是N-position，N-position只要找到第一个子格局是P-position即可。
- 通过数学归纳法，两堆石子的情况下，两堆相等是P-position
如果局面不可能重现，或者说positions的集合可以进行拓扑排序，那么每个position或者是P-position或者是N-position，而且可以通过定义计算出来。
HDU3483
[题意]
输入n, x, m ，求$(1^x)(x^1)+(2^x)(x^2)+(3^x)(x^3)+…+(n^x)(x^n)$
[解题方法]
设$f[n] = [x^n, n(x^n), (n^2)(x^n),…, (n^x)(x^n)]$，则$f[n][k] = (n^k)(x^n)$，问题转化为求：$(g[n] = f[1][x]+f[2][x]+…+f[n][x])$，设C(i,j)为组合数，即i种元素取j种的方法数，所以有：$$f[n+1][k] = ((n+1)^k)(x^(n+1)) \text{（二次多项式展开）}\ = x( C(k,0)(x^n)+C(k,1)n(x^n)+…+C(k,k)(n^k)(x^n))\= x(C(k,0)f[n][0]+C(k,1)f[n][1]+…+C(k,k)*f[n][k])$$
所以得：
1 | |x*1 0................................0| |f[n][0]| |f[n+1][0]| |
KMP算法理解
预处理算法
- 预处理出来的第 $i$ 位结果 $p[i]$ 是原字符串截止到第 $i$ 那个字符的最小周期，也就是只需要移动最少量的字符 $p[i]$ 既可以使得原先匹配部分再次匹配起来。
为什么偶数长度的回文数字串不是primer
- ref
Because even length prime digit numbers are divisible by 11 therefore are not prime.
It’s a trick that has to do powers of 10 and mod 11.
Ex: 10 = 10^1 mod 11 = -1 mod 11
$100 = 10^2 = 1 \mod 11$
$1000 = 10^3 = -1 \mod 11$
$10000 = 10^4 = 1 \mod 11$
See the pattern?
Even exponent powers of 10 are 1 mod 11
Odd exponent powers of 10 are -1 mod 11.We also know decimal numbers are just base 10 expansion of the digits.
So $1225 = (10^3)1 + 2(10^2) + 2(10^1) + 5(10^0).$
using modular arithmetic we can say,1225 MOD 11 = (-1)*1 + 2*(1) + 2*(-1) + 5*(1) = -1 + 2 + 2 + 5 = 8. In other words, in MOD 11 we calculate what a decimal number is by just alternating the addition and subtraction across the digits.Another example.
$1323412 \mod 11 = 1 -3 +2 -3 +4 -1 +2\mod 11 = 0.$
Then it becomes why it is quite obvious why the above logic works for even palindromes.
Example:
$321123 = -3 + 2 - 1 + 1 -2 + 3 = 0$. All the numbers cancel out with each other.
贪心算法总结
- 在每个贪心算法后面几乎总有一个DP解法
- 如何证明是否可以用贪心算法求解一个问题？并没有通用方法，但是贪心选择性质和最优子结构是两个关键要素
- 如果贪心选择时需要考虑众多选择，通常意味着可以改进贪心选择来获得更高效的解法
贪心选择性质
- 可以通过做出局部最优的选择来构造全局最优
- 证明方法：首先考察某个子问题的最优解，然后用贪心选择替换某个其他选择来修改此解，从而得到一个相似但是更小的子问题
一组有效的步骤
- 确定问题的最优子结构（如果一个问题的最优解包含其子问题的最优解，则称此问题具有最优子结构性质）
- 设计一个递归解法（该递归解法加上记忆就可以变成自顶向下的DP）
- 证明如果做出一个贪心选择，就只剩下一个子问题（或许可能是几个子问题？不过子问题的数量确实要比自顶向下的DP解法少）
- 证明贪心选择总是安全的
- 什么是安全的？
- 做出贪心选择后，原问题总存在最优解，即贪心选择总是安全的
- 做出贪心选择后，剩余的子问题满足性质：其最优解与贪心选择组合即可得到原问题的最优解，这样就得到了最优子结构
- 设计一个递归算法实现贪心策略
- 把递归算法转为迭代算法
一组简化的步骤
- 将最优化问题转为这样的形式：做出一次选择后，只剩下一个子问题需要求解
- 证明做出贪心选择后，原问题总存在最优解，即贪心选择总是安全的
- 证明做出贪心选择后，剩余的子问题满足性质：其最优解与贪心选择组合即可得到原问题的最优解，这样就得到了最优子结构