Hexo
0%

ACM学习笔记

发表于 更新于 分类于
接触map类，其他关于STL的知识，BFS，DFS和一些乱七八糟的笔记。

给出一串数以及一个数字C，要求计算出所有A - B = C 的数对的个数（不同位置的数字一样的数对算不同的数对）。原题

借鉴的思路

这个思路的核心就是将A - B = C转换位A - C = B。
1、在输入的时候使用map来统计每个数出现的次数。
2、通过将每一个数都减去C来将A转换成B，如此，只需要统计符合要求的B的次数就可以得到这个题目的答案。
3、对map进行一次遍历，得到所有符合要求的B的出现次数的累加和，即为正确答案。原因：1中统计的是一长串数中每个数字出现的频率，如果没有在这里出现的数字其频率自然为0，在2中将每个A所要求的B求出来，并将它的值直接赋给A，于是就可以拿着这个想要查找到的目标数组去map表里查，最终就很容易得到了符合要求的B的个数。

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
#include<iostream>
#include<map>
using namespace std;
//typedef long long LL;下面的声名与此相同，不过更为直观
using LL = long long;
LL database[200005] = { 0 };
int main()
{
 map<LL, LL>m;
 int number;
 LL aim, ans = 0;//这里一定要是LL型，不然的的话数据范围不够大会挂在一个测试点上
 cin >> number >> aim;
 for (int i = 1; i <= number; i++)
 {
  cin >> database[i];
  m[database[i]]++;
  database[i] = database[i] - aim;
 }
 for (int i = 1; i <= number; i++)
 {
  ans = ans + m[database[i]];
 }
 cout << ans << endl;
 return 0;
}

经验教训

map真的好好用

又一个可以使用map的题

原题太长了，就不贴了，思路很简单，就是对于每一次存放操作，建立一次二维映射；对于每一次查询操作，直接输出其映射的值。

解法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include<iostream>
#include<map>
using namespace std;
map<int, map<int, int> >m;
int main()
{
 int numberofbox, asknumber,mode,x,y,z;
 cin >> numberofbox >> asknumber;
 for (int i = 1; i <= asknumber; i++)
 {
  cin >> mode >> x >> y;
  if (mode == 1)
  {
   cin >> z;
   m[x][y] = z;
  }
  else
  {
   cout << m[x][y] << endl;
  }
 }
 return 0;
}

unique

1、作用：去重
2、用法：unique（数组名，数组名+大小），与sort一模一样
3、注意：
在unique之前必须保证去重数组有序，也就是得sort一下。
unique并不会生成一个新的数组，而是将原数组多余的部分”移“到了数组之后，同时unique本身还会返回一个指针，指向去重之后的最后一位。
利用C++可以指针相加减的特点，我们可以通过unique-数组指针来知道去重之后数组的”大小“。

1
int size  = unique(x,x+k)-x;

真的很好用，在用set超时的情况下可以考虑一下噢。

二维变长数组

下列语句申请了100个vector，实现了二维变长数组

1
vector<int>vec[100]

在map中使用两个索引对应一个value

方法一：

1
2
map<pair<int,int>,int>ma;
ma[make_pair(x,y)] = 12312;

方法二：(摘自又一个可以使用map的题)

1
2
map<int,map<int,int> > m;
m[x][y] = z;

通过value确定数组的index

lower_bound(起始地址，结束地址，要查找的数值)-起始地址;
上述的结果就是index

使用sort

方法一：重写sort的比较函数
方法二：重载结构体的大于号

BFS和DFS

DFS

1、使用DFS搜索方案时要记得回退（就是把标记已经走过的点取消标记）—回溯法。
2、DFS的特点是搜索到下一个可访问节点立即就去访问下一个节点（只修改当前访问点的标记，不修改下一个节点的标记）
3、求最短距离要在DFS函数中多加一个参数记录步数，最后在递归终点取最小值就可以。
4、DFS有可能会被卡，沿着一条路走到TLE。

BFS

1、BFS的特点是搜索到下一个可访问节点就将它加入到队列中，而不是立即去访问它，首先要遍历当前节点所有可以访问的节点。（会修改下一个可访问节点的标记，为的是避免在以后的搜索中不再重复将这个待访问点加入到队列中）
2、BFS可以天然的求出最小路径。因为BFS是一层一层地向外扩展，每一个点最先被加入到队列时，一定是通过拓展层数最小地方法扩展到的。（也就是第一个求出来的结果一定是最短的）
3、BFS更占空间，更难写。

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
void bfs()
{
 Node st;
 st.n = 3;
 st.nown = 1;
 q.push(st);
 while(!q.empty())
 {
  Node zt = q.front();
  q.pop();
  printf("%d:",zt.nown);
  for(int i = 1;i < zt.nown;i++)
    printf("%d ",zt.A[i]);
  printf("\n");
  if(zt.nown == zt.n+1)
  {
   for(int i = 1;i <= zt.n;i++)
    printf("%d ",zt.A[i]);
   printf("\n");
  }else{
   for(int i = 1;i <= zt.n;i++)
   {
    int ok = 1;
    for(int j = 1;j < zt.nown;j++)
    {
     if(zt.A[j] == i) ok = 0;
    }
    if(ok)
    {
     zt.A[zt.nown] = i;
     Node nextn;
     memcpy(nextn.A,zt.A,(zt.nown+1) * sizeof(int));
     nextn.n = zt.n;
     nextn.nown = zt.nown+1;
     q.push(nextn);
    }
   }
  }
 }
}

相同点

1、无论BFS还是DFS，我们都有一个提供这些信息的东西。
2、这些信息定义了一个子问题，提供了定位一个子问题所需的所有条件，定义了解决一个问题过程中的状态。
3、都要对结果进行判重，防止重复搜索甚至陷入死循环。

取模

1、同余符号=（就那个恒等于符号）
就是等号两边取模结果相同
2、模意义下的 +-/
%8的域里面
(6/3)%8 = 2;
(63)%8 = 2;
1 2
1 -
2在模八意义下的逆元不存在：2x%8 = 1无解

筛素数

1、欧拉筛：去掉当前数的所有质数。
2、优化：只用质素去筛，在筛之前判断是不是质数。
3、因为每个数可能会有不止一个的质因子，因此理想的状态是使用最小质因子来筛。
4、也就是需要多一个break条件
当前数%质数数组[index] == 0 满足这个条件就break；
二重循环，外层是当前数，内层是质数数组的index循环。

　最小公约数

1、核心代码
if(a>b)
gcd(a,b) = gcd(a%b,b);
2、在alg这个头文件里有个自带的_gcd函数
3、最大公约数*最小公倍数 = 两个数的乘积
4、丢番图方程
ax + by = c;

丢番图方程(扩展欧几里得)

1、判断什么方程有解
当且仅当gcd(a,b)|c时有解(|表示整除)
如果ax+by = 5,那么ax+by = 10也一定有解
2、ax+by = gcd(a,b)一定有解 即必须c%gcd（a，b） = 0
如果gcd = 1那么这个方程一定有解
3、
5在11域中的逆元
5x + 11y = gcd(5,11);

phi

比如求phi 10
1、筛去质因子(2,5)
2、筛去质因子的倍数
3、减去筛去的数（奇数加，偶数减）
4、加上多减的，减去多加的

梦比乌斯函数mub

mub就是容斥时的系数
id*mub = phi（这是个卷积）

Sparse Table Algorithm

1、f[i][j]表示的是从i开始，区间长度为2^j的最小值，也就是[i,i+2^j-1]的最小值。
2、求[2,8]的最小值分成[2,5][5,8]两个区间的最小值。其中，k = floor(log(b-a+1)/log(2)),即2^k = b-a+1。
3、f[i][0] 区间长度为1，结果是它本身。

树状数组

1、高效的获取连续k个数的和。
2、给定序列（数列）A，我们设一个数组C满足C[i] = 。k是二进制末尾0的个数，i从1开始。
3、lowbit = i&（-i）；
4、A[1]+A[2]+…+A[6] = C[6]+C[4];
前驱的编号即为比自己小的，最近的，最末连续0比自己多的数。
t = x-lowbit（x）；//前驱的编号，相当于x减去了最右边的1
5、求区间[x,y]之和getsum(y)-getsum(x-1)；
6、修改某个A[i],就需改动所有包含A[i]的C[j];就是要修改从叶子节点到根节点路径上的所有C[j]。
父结点：比自己大的，最近的，末位连续0比自己多的
T = x+lowbit（x）；//x父结点的编号相当于让x最右边的1变为0，增加1个0
7、如果整数范围是1e9，显然不能开那么大的数组，于是我们对它们进行排序，然后按照1~numberofdata这样子赋给它们下标，只需要知道它们大相对大小关系即可，不需要知道它们具体是多少。

树上倍增

1、fa[v][k] = fa[fa[v][k-1]][k-1];
2、从低位到高位枚举，将向上查找的层数分成一个1后面好多个0这种形式。
101&001 = 1；
101&010 = 0；
101&100 = 100 = 1；
3、求公共祖先
-先让层数较多的那个节点向上跳到另一个节点的同层。
-然后逐个去试，从根节点（最高层）向下跳，知道此时两个节点的祖先不相同结束，则表示上一步就是所求的最近公共祖先。

时间复杂度

O ：
对任意的N，存在n>N,使得f(n)<=Cg(n),则我们得到f(n) = O(g(n))。O是时间增长的上界。
Ω：
对任意的N，存在n>N,使得f(n)>=Cg(n),则我们得到f(n) = Ω(g(n))。O是时间增长的下界。
θ：
对任意的N，存在n>N,使得C1g(n)<=f(n)<=C2g(n),则f(n) = θ(g(n))。
若f(n) = O(g(n))，f(n) = Ω(g(n))，则(n) = θ(g(n))。

一个有用的STL函数

prev_permutation函数可以制造前一个排列，如果已经为第一个，则返回false

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
#include<bits/stdc++.h>
using namespace std;
int n,a[10000];
int main()
{
    cin>>n;
    for(int i=0;i<n;i++)   //读入数据
        cin>>a[i];
    if(prev_permutation(a,a+n))  //如果为真就输出数组
        for(int i=0;i<n;i++)
            cout<<a[i]<<" ";
    else cout<<"ERROR";   //否则输出ERROR
    cout<<endl;
    return 0;
}

高精

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
void jiafa(int k)//高精加法
{
 for(int i=1; i<=len; i++)//两数相加
     f[k][i]=f[k-1][i]+f[k-2][i];
 for(int i=1; i<=len; i++)//进位
  if(f[k][i]>=10)
  {
   f[k][i+1]+=f[k][i]/10;
   f[k][i]%=10;
   if(f[k][len+1]>0)len++;
  }
}
//注意输出的时候是要倒着输出的
for(int i=len; i>=1; i--)//输出，len一定是要定义成全局变量
     cout<<f[n][i];