题库目录：

DP

#include<cstring>`
#include<iostream>`
`using namespace std;`

`const int N = 105;`
`int a[2][N], f[2][N], q, n, m;`

`int main()
`{`
    `cin >> q;
    `while(q--){
        `cin >> n >> m;

    `for(int i = 1; i <= n; i++){
        `for(int j = 1; j <= m; j++){
         `cin >> a[i&1][j];
            `f[i&1][j] = max(f[i&1][j-1], f[(i-1)&1][j]) + a[i&1][j];
        }
    }
    cout << f[n&1][m] << endl;

    memset(f, 0, sizeof f);
}
}

这一段代码用了流动数组，因为只需比较这一行与上一行的数据，所以可以节省空间复杂度。acwing1015

Dp关键是把所要求的数据作为数组值，根据题意可以使用多重数组进行处理，比如acwing1212

int的大小是2147483648——214748364，为十位数，小心爆int，比如如下代码这样处理。

      f[i][j][cnt][k] = (f[i][j][cnt][k] + f[i - 1][j][cnt][k]) % MOD;
      f[i][j][cnt][k] = (f[i][j][cnt][k] + f[i][j - 1][cnt][k]) % MOD;

排序与搜索：

sort（）的复杂度为nlogn

搜索

一般会用前缀和进行搜索，减少复杂度。

搜索时可以通过改变判断顺序使题目更加简单，比如判断回文日期可以前判断回文，再判断日期。（判断当月天数这样的操作可以通过数组存储进行读取判断！）

读数直接用scanf区分就能起到split的效果。

getline用法：

string i;

getline(cin,i);

忽略回车写法：

int n;

scanf("%d",&n);

string line;

getline(cnt,line);

线段树和树状数组

树状数组

代码短，数据短。

o(logn)的复杂度

单点修改，区间查询

x的二进制表示最后有k个零 lowbit(x)=x&-x=2的k次方

c(x)=(x-lowbit(x),x)的和

int lowbit(int x)//公式定义

{

	return x&-x;

}
void add(int x,int v)//单点操作
{
    for(int i=x;i<=n;i+=lowbit(x)) tr[i]+=v;
}
int query(int x)//1到x区间求和
{
    int res=0;
    for(int i=x;i;i-=lowbit(i)) res+=tri[i];
    return res;
}

对一个数组初始成树状数组可以如下

for(int i=0;i<=n;i++) add(i,a[i]);

线段树

贪心

没有固定套路，但是你要想出最大算法背后的原理。

acwin112 —-区间问题

只计算右端点即可算出最小个数

struct segment
{
    double l,r;//左右端点计算
    bool operator <(const segment&t)const//对小于号进行重载
    {
        return r<t.r;
    }
}segment[N];//结构体数列
segment[i].r=xxxx;//这个是用法

关于运算符重载

• 成员函数重载，本质是person p3 = p2.operator+(p1),p1.p2的先后顺序是有很大影响

• 全局函数重载也是一样，本质上是p3 = operator+(p1,p2)，p1.p2的先后顺序是有很大影响

  实例代码复习：

  class Person
  {
  public:
      Person(){};
      Person(int a, int b)
      {
          this->m_A = a;
          this->m_B = b;
      }
      //成员函数实现 + 号运算符重载
      Person operator+(const Person &p)
      {
          Person temp;
          temp.m_A = this->m_A + p.m_A;
          temp.m_B = this->m_B + p.m_B;
          return temp;
      }
  
  public:
      int m_A;
      int m_B;
  };
  
  // 全局函数实现 + 号运算符重载
  Person operator+(const Person &p1, const Person &p2)
  {
      Person temp(0, 0);
      temp.m_A = p1.m_A + p2.m_A;
      temp.m_B = p1.m_B + p2.m_B;
      return temp;
  }
  
  // 运算符重载 可以发生函数重载
  Person operator+(const Person &p2, int val)
  {
      Person temp;
      temp.m_A = p2.m_A + val;
      temp.m_B = p2.m_B + val;
      return temp;
  }
  

1235 1239 1247 1248

数论

辗转相除法

int gcd(int a,int b)//返回最大公约数
{
    return b?gcd(b,a%b):a;
}

算数基本定理

所有数都可以分为p1（pi为质数）的x次方加以此规律类推。

双指针，BFS，图论

双指针就是一个思想，一个头，一个尾。

学习pair的用法:

typedef pair<int,int >PII;
 
PII p1(,);//初始化
make_pair(v1,v2);//以v1 v2的值创建一个新的对象
p1.first;
p1.second;//第一个值与第二个值，可以同变量一样进行赋值等操作
p1={,};

#define x first;
#define y second;//方便操作

在某些情况，函数会以pair对象作为返回值时，可以直接通过std::tie进行接收。比如：

std::pair<std::string, int> getPreson() {
    return std::make_pair("Sven", 25);
}

int main(int argc, char **argv) {
    std::string name;
    int ages;

std::tie(name, ages) = getPreson();

std::cout << "name: " << name << ", ages: " << ages << std::endl;

return 0;

队列

#include<queue>//导入

queue<T>s1;//创建T类型的s1变量
s1.push();//入队操作
s1.front();//获取队首元素
s1.back();//获取队尾元素
s1.pop();//另队首元素出队，时间复杂度为O（1）；
s1.empty();//检测queue是否为空，返回true,false;
s1.size();//返回queue中元素的个数。

关于auto:

auto 关键字基本的使用语法如下：

auto name = value;

name 是变量的名字，value 是变量的初始值。

注意：auto 仅仅是一个占位符，在编译器期间它会被真正的类型所替代。或者说，C++ 中的变量必须是有明确类型的，只是这个类型是由编译器自己推导出来的。

while的小错误！

while（循环控制表达式）//每次循环判断一次，返回true则执行循环。
{
  语句序列
}

数组边界与横纵坐标的意义

数组由于输入是从0开始，所以最后一个没有值，在进行类似acwing1101迷宫判断时要注意边界范围：

scanf("%d%d",&r,&c);

for(int i=0;i<4;i++)
{
    int x=t.x+dx[i],y=t.y+dy[i];
    if(x<0||x>=r||y<0||y>=c) continue;//这个等号要注意加上，按输入的顺序来，不要用xy坐标轴的想法去想，会反的
    if(m[x][y]=='#') continue;
    if(state[x][y]!=-1) continue;

    state[x][y]=state[t.x][t.y]+1;
    if(end==make_pair(x,y)) return state[x][y];
    q.push({x,y});
}

图论

acwing1224题解很详细，大概就是用连线图对路径进行模拟，最后规划出每个数各一个环。

差分

acwing797是差分解决的主要问题。（写

周赛4862也是（写

复杂dp

acwing1050题可以分为有0和无0，有0则f[i][j]=f[i][j-1]因为新增的一个方案为0，所以和原来的方案数一样，没有0的话则最短数是1，那么可以所有数减去1，及i-j个数，则为f[i-j][j]。

f[N][N]={0};
f[0][0]=1;
for(int i=0;i<=n;i++)
	for(int j=1;j<=m;j++)
	{
		f[i][j]=f[i][j-1];
		if(i>j) f[i][j]+=f[i-j][j];
	}