ACM笔记 | Mox的笔记库

干ACM了，emmm(持续更新中)

2021年2月28日：由于个人时间紧迫，外加阅读书目改变，本笔记不再更新

#include<bits/stdc++.h>
C++通用库，使c++支持所有库，vj要选c++5.1.0/g++才行

按照《算法竞赛:入门到进阶》编排内容

ACM (Advanced Computer Maker)

想要编写又快又好的程序，构造测试数据和写出优良代码一样重要

环境配置

谁叫这是官配IDE，不然怎么会用这种东西

CodeBlocks17.12版本无法进行单步调试的相关原因及可能的解决办法

CodeBlock无法断点调试的解决方案

在codeblocks中使用C++11标准，安装及配置方法_autocyz-CSDN博客

codeblocks 字体光标颜色设置_lydcsdn-CSDN博客

codeblocks 背景设置和光标的设置！！！_谈笑风声，雨下成林-CSDN博客

2020年11月23日，我的codeblock出现编译完的程序死锁，使用完居然不自动释放，垃圾东西

格式规范

1.不能用float，要用double

2.输出的时候不能多输空格

解决long long的定义

typedef long long ll;

交换宏的定义

#define swap(a,b) {int temp=a;a=b;b=temp}

识别2002/11/22

scanf("%d/%d/%d", &y, &m, &d) != EOF

不间断输入

while(scanf("%lf",&r) != EOF)

不间断输入之输入0时程序停止

while(scanf(“%d”, &n) && n)

while(cin>>n && n)

好像scanf本身就能整行输入，不间断输入

while(scanf("%lf",&r))

取整数位

#include<stdio.h>
int main(){
int n = 123456;
int unitPlace = n / 1 % 10;
int tenPlace = n / 10 % 10;
int hundredPlace = n / 100 % 10;
int thousandPlace = n / 1000 % 10;
printf("个位bai:%d\n十位:%d\n百位:%d\n千位:%d\n", unitPlace, tenPlace, hundredPlace, thousandPlace);

数组定义不能用变量！

输入两行

只要第一个循环EOF，后面的输入在循环里就可以了

\b不是退格

以一定排序规则排序指定范围内的元素，但是算法不具有稳定性，如果元素的值是相同的话不保证它们的相对顺序保持不变

？？？

第二重循环时j

第三重循环时k

答案用ans命名

实际用不到do……while

给定次数以后就不要用

while(t--)

使用这种方法代替sqrt()

for(int i=2;i*i<=x;i++)

等号不能少

数组初始化

memset(N,0,sizeof(N));

复杂度计算

时间复杂度

1.常数量级，用常熟1

2.保留时间函数的最高项

循环N次，O（n）

3.如果最高项存在，省去最高结项前面的系数

两次N循环，就是O(n)

二次内

j*=j

o(n*sqrt())

3 STL和基本数据结构

3.1 容器

迭代器

http://c.biancheng.net/view/338.html

使用前先进行声明

vector<int>::iterator i;

迭代器提供对一个容器中的对象的访问方法，并且定义了容器中对象的范围

设计人员无需关心容器对象的内存分配的实现细节

但是，迭代器不仅仅是指针，因此你不能认为他们一定具有地址值。例如，一个数组索引，也可以认为是一种迭代器

案例:遍历vector

#include <iostream>
#include <vector>
//i是指针！！！
using namespace std;
int main()
{
    vector<int> v;  //v是存放int类型变量的可变长数组，开始时没有元素
    for (int n = 0; n<5; ++n)
        v.push_back(n);  //push_back成员函数在vector容器尾部添加一个元素
    vector<int>::iterator i;  //定义正向迭代器
    for (i = v.begin(); i != v.end(); ++i) {  //用迭代器遍历容器
        cout << *i << " ";  //*i 就是迭代器i指向的元素
        *i *= 2;  //每个元素变为原来的2倍
    }
    cout << endl;
    //用反向迭代器遍历容器
    for (vector<int>::reverse_iterator j = v.rbegin(); j != v.rend(); ++j)
        cout << *j << " ";
    return 0;
}

for(it=shop.begin();it!=shop.end();it++)

常用迭代查找

algorithm

sort()

一般是两个参数

cmp是比较函数

int a[]={5,4,3,2,1};
sort(a,a+5,cmp);

sort(toy,toy+1,cmp)

这样做，是自己和自己比较，易犯错误

结构提比较

#include<iostream>
#include<algorithm>
#include<string>
using namespace std;
struct x
{
    int a,b,c;
}toy[50];
bool cmp(x aa,x bb)
{
    return aa.b>bb.b;
}
int main()
{
  sort(toy,toy+50,cmp)
    return 0;
}

reverse()

reverse(a.begin(),a.end());

可用于回文数

vector

向量（Vector）是一个封装了动态大小数组的顺序容器（Sequence Container）。跟任意其它类型容器一样，它能够存放各种类型的对象。可以简单的认为，向量是一个能够存放任意类型的动态数组。

其实原来根本就没这个必要，但是编译器不认

1.顺序序列

顺序容器中的元素按照严格的线性顺序排序。可以通过元素在序列中的位置访问对应的元素。

2.动态数组

支持对序列中的任意元素进行快速直接访问，甚至可以通过指针算述进行该操作。操供了在序列末尾相对快速地添加/删除元素的操作。

3.能够感知内存分配器的（Allocator-aware）

容器使用一个内存分配器对象来动态地处理它的存储需求。

#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
int main()
{
    vector<int>a;
    for(int i=0;i<10;i++)
    {
        a.push_back(i);
    }
    cout<<a.size()<<endl;
    for(int i=0;i<10;i++)
    {
        cout<<a[i];
    }
    return 0;
}

queue

a.pop() 是void

**总结：**先进先出；push到队尾；pop队首元素。

注意，不是双向队列

#include<iostream>
#include<queue>
using namespace std;
int main()
{
    queue<int>a;
    a.push(1000);
    a.push(200);
    cout<<a.front()<<endl;
    cout<<a.back()<<endl;
    a.pop();
    cout<<a.size()<<endl;
    return 0;
}

这东西不是双向的

swap需要开 c11

#include <iostream>       // std::cout
#include <queue>          // std::queue
using namespace std;
int main ()
{
  queue<int> foo,bar;
  foo.push (10); foo.push(20); foo.push(30);
  bar.push (111); bar.push(222);
  foo.swap(bar);
  std::cout << "size of foo: " << foo.size() << '\n';
  std::cout << "size of bar: " << bar.size() << '\n';
  return 0;
}

list

list就是数据结构中的双向链表

deque

double-ended queue

这好像才是双向队列

ush_back,push_front,pop_back,pop_front等，并且在两端操作上与list的效率也差不多

#include<iostream>
#include<algorithm>
#include<string>
using namespace std;
struct x
{
    int a,b,c;
};
bool cmp(x aa,x bb)
{
    return aa.b>bb.b;
}
int main()
{
  string a;
  a="Hello World";
  cout << a << endl;
  cout << a.size() << endl;
  cout << a[3] << endl;
  reverse(a.begin(),a.end());
  cout << a << endl;
}

string

3.1.1 vector

vector是STL的动态数组

可以以数组的方式遍历

#include <iostream>
#include<bits/stdc++.h>
using namespace std;
int main()
{
    int n;
    cin>>n;
    while(n--)
    {
        int n1,l;
        cin>>n1;
        vector<int>p;
        cin>>l;
        p.push_back(l);
        cin>>l;
        p.push_back(l);
        for(int i=0;i<n1;i++)
            cout << p[i];
    }
    return 0;
}

3.1.2 栈和stack

栈是经典的先进后出FILO

HDU1062（这道题还可以用string和reverse实现）

The underlying container may be any of the standard container class templates or some other specifically designed container class. The container shall support the following operations:

empty
size
back
push_back
pop_back

3.1.3 队列和queue

队列是经典的先进先出FIFO

HDU1702

The underlying container may be one of the standard container class template or some other specifically designed container class. This underlying container shall support at least the following operations:

empty
size
front
back
push_back
pop_front

The standard container classes deque and list fulfill these requirements. By default, if no container class is specified for a particular queue class instantiation, the standard container deque is used.

3.1.4 优先队列和priority_queue

3.1.5 链表和list

链表的插入和删除都是常数时间，主要应对插入删除频繁的问题

HDU1276

初始化方案

for(int i=1;i<=n;i++)
        {
            mylist.push_back(i);
        }

遍历方案为迭代器

迭代器本质是指针

 for(it = mylist.begin();it != mylist.end();it++)

STL已经完善了很多操作，比如清空，删除节点，反转，排序，访问第一个和最后一个元素，删除相邻重复元素

有点像队列，但本质完全不同

没说结构体？应该差不多？

3.1.6 set

hdu2094

#include <iostream>
using namespace std;
int main()
{
    set<string>A,B;
    string s1,s2;
    int n;
    while(cin>>n && n)
    {
        for(int i=0;i<n;i++)
        {
            cin>>s1>>s2;
            A.insert(s1);
            A.insert(s2);
            B.insert(s2);
        }
        if(A.size()-B.size()==1)
            cout<<"Yes"<<endl;
        else
            cout<<"NO"<<endl;
        A.clear();
        B.clear();
    }
    return 0;
}

A.size()

这个最好用

set用法+unique用法，unique，去重，但不是真正去重，而是把重复的放在后面返回重复第一个下标，如果没记错的话，还不知道unique去重原理问度娘

#include<bits/stdc++.h>
using namespace std;
set<string>se;
int main()
{
    int n;
    string s;
    cin>>n;
    while(n--)
    {
        cin>>s;
        sort(s.begin(),s.end());
        s.erase(unique(s.begin(),s.end()),s.end());
        se.insert(s);
    }
    cout<<se.size();
    return 0;
}

数组全部遍历

for (it=A.begin(); it!=A.end(); ++it)
    {
        cout << ' ' << *it;
        cout << '\n';
    }

我觉得A.find有问题，这个留待后续研究

查找元素是否存在

 A.insert(5);
    A.insert(4);
    A.insert(5);
    if( *A.find(4) ==4 ) cout<<"True"<<endl;
    A.erase(4);
    if( *A.find(4) ==4 ) cout<<"True"<<endl;
    else cout<<"False"<<endl;

想要插入元素需要借助中间变量

集合的内部是可以比较输出的

for (auto it = ++A.cbegin(); it != A.cend(); it++)
        {
            cout << " " << *it;
        }
        cout<<endl;

3.1.7 map

map使用平衡二叉搜索树实现高速查找

3.1.8 next_permutation

按照字典序进行排列，cba的字典序大于abc

只能针对字符使用

实现一串字符的全排列的当前排列的下一个排列

字典序大小比较：从第一个字符开始一个一个比较，然后找到到一个不相等的，哪个大，哪个字典序就大，如果找不到不相等的，那就相等

HDU1027

从后往前找一个Si<Si+1，然后从i+1到n之间找一个比Si大的最小字符，交换位置，然后把i+1到n升序排序

该函数，在下一个排列存在的情况下返回while，不存在的情况返回false

排序算法

冒泡算法

通过n-1趟排序，将大的数一步一步往上冒

O（n^2）

Flag思想

观察函数swap是否被调用

如果没有发生排序，则false

如果flag为false，说明已排完

这个优化方案好像不错

qsort()

https://www.cnblogs.com/tsingke/p/5347672.html

见C语言笔记

不打乱顺序的情况下，找出最小

遍历

    for(int i=1;i<n;i++)
    {
        if(temp1 > d[i])
        {
            temp1=d[i];
            temp2=i;
        }
    }

就没更好的方案？

上课时提到了一种方案

直接摆擂台，大数和小数各一个，通过遍历实现，最大最小的序号用变量记住，

（如果是两个相关联的量）正确做法是构建结构体，选择结构题内容经行结构体排序（排序才需要这么做）

4 搜索技术

二分查找

二分查找真的很简单吗？并不简单。看看 Knuth 大佬（发明 KMP 算法的那位）怎么说的：

Although the basic idea of binary search is comparatively straightforward, the details can be surprisingly tricky…

https://www.zhihu.com/question/36132386/answer/712269942

首先先排序

核心是查找！！！！

然后每次缩小一半范围

O(log2n)

二分查找也称折半查找（Binary Search），它是一种效率较高的查找方法。但是，折半查找要求线性表必须采用顺序存储结构，而且表中元素按关键字有序排列

4.1 递归和排列

排列与组合

用next_permutation轻易实现全排列

使用递推方程讲解递归概念

计算机中，递归是用嵌套实现的，涉及指针，地址，栈的使用

4.2 子集生成和组合问题

一个包含N个元素的集合，它的子集有2的n次方个

4.3 BFS（广度优先）

题目，概念太多，未完待续

4.4 DFS（深度优先）

4.4.2 回溯和剪枝

4.5 小结

DFS一般用递归实现，代码比BFS更短

1、如果是求最短路径，树的直径（两次bfs），一般用bfs 2、如果只是左转或者右转（像上一篇博客一样的话）就用dfs 3、如果是翻转系列的（flip game，行列变换）一定是dfs

5 高级数据结构

数据结构的作用是分析数据，组织数据，存储数据

（1）存储的空间效率

地图与棋盘就是典型的图，前者更加复杂，用1表示相邻，用0表示不相邻

(2)访问的效率

存储无序数字，很明显在排序过后再二分查找效率最高

数据结构有三要素

（1）逻辑结构：线性结构，非线性结构，集合，图

（2）存储结构：顺序存储，链式存储，索引存储，散列存储

（3）数据的运算：初始化，判空，统计，查找，插入，删除，更新（？）

5.1 并查集

HUD1213

代码附上

#include <bits/stdc++.h>
using namespace std;
const int maxn=1050;
int s[maxn];
void init_set()
{
    for(int i=1;i<maxn;i++)
    {
        s[i]=i;
    }
}
int find_set_old(int x)
{
    return x==s[x]?x:find_set(s[x]);
}
int find_set(int x)
{
    return x==s[x]?x:find_set(s[x]);
}
void union_set(int x,int y)
{
    x = find_set(x);
    y = find_set(y);
    if(x!=y) s[x]=s[y];
}
int main()
{
    int t,n,m,x,y;
    cin >> t;
    while(t--)
    {
        cin>>n>>m;
        init_set();
        for(int i=1;i<=m;i++)
        {
            cin>>x>>y;
            union_set(x,y);
        }
        int ans=0;
        for(int i=1;i<=n;i++)
        {
            if(s[i]==i) ans++;//只要数组下标与元素相同，就属于一个集合
        }
        cout<<ans<<endl;
    }
    return 0;
}

其中，查找和合并还可以继续优化，复杂度从O(n)降到O(log2n)

5.1.2 合并的优化

合并时先搜根结点,依据数的高度决定合并方向，即小树向大树靠拢

（所以这是一种单项关系）

#include <bits/stdc++.h>
using namespace std;
const int maxn=1050;
int s[maxn];
int height[maxn];
void init_set()//初始化，学到了
{
    for(int i=1;i<maxn;i++)
    {
        s[i]=i;
        height[i]=i;
    }
}
int find_set(int x)
{
    return x==s[x]?x:find_set(s[x]);
}
void union_set(int x,int y)
{
    x = find_set(x);
    y = find_set(y);
    if(height[x]==height[y])
    {
        height[x]+=1;
        s[y]=x;
    }
    else
    {
        if(height[x]<height[y]) s[x]=y;
        else s[y]=x;
    }
}
int main()
{
    int t,n,m,x,y;
    //cin >> t;
    t=1;
    while(t--)
    {
        cin>>n>>m;
        init_set();
        for(int i=1;i<=m;i++)
        {
            cin>>x>>y;
            union_set(x,y);
        }
        int ans=0;
        for(int i=1;i<=n;i++)
        {
            if(s[i]==i) ans++;//只要数组下标与元素相同，就属于一个集合
        }
        cout<<ans<<endl;
    }
    return 0;
}

5.1.3 查询的优化——路径压缩

好家伙，直接把树长变为1

int find_set(int x)
{
    if(x!=s[x]) s[x]=find_set(s[x]);
    return s[x];//递归写法
}

如果怕爆栈，多设几个变量走循环

int find_set(int x)
{
    int r=x;
    while(s[r]!=r)r=s[r];
    int i=x,j;
    while(i!=r)
    {
        j=s[i];
        s[i]=r;
        i=j;
    }
    return r;
}

这两种优化产生的优势在HDU1312均没有体现

5.2 二叉树

书是非线性结构，书本的目录就是典型的树形结构

A binary tree is a finite set of vertices that is either empty or consists of a root r and two disjoint binary trees called the left and right subtrees. There are three most important ways in which the vertices of a binary tree can be systematically traversed or ordered. They are preorder, inorder and postorder.

5.2.1 二叉树的存储

1 二叉树的性质

二叉树的每个节点最多有两个子节点

如果每一层节点数都是满的，称之为满二叉树

如果满二叉树只在最后一层缺失，且缺失编号都在后边，称之为完全二叉树

2 二叉树的存储结构

一般用指针实现

结构体里有一个节点的值，有两个指针指向左右节点

5.2.2 二叉树的遍历

1 宽度优先遍历

2 深度优先遍历

默认左儿子在右儿子前面

分为先序遍历，中序遍历，后序遍历三种遍历情况

只要中序遍历加上任何一序，就能确定一棵树

前序遍历：父节点->左儿子->右儿子

中序遍历(inorder)：左儿子->父节点->右儿子

在二叉搜索树中，中序遍历实现了排序功能

后序遍历: 左儿子->右儿子>父节点

HDU1710为案例讲述

#include <iostream>
#include<bits/stdc++.h>
using namespace std;
const int N=1010;
int pre[N],in[N],post[N];
int k;
struct node{
    int value;
    node *l,*r;
    node(int value =0,node *l = NULL,node *r = NULL):value(value),l(l),r(r){} //？？？
};
void buildtree(int l,int r,int &t,node* &root)
{
    int flag=-1;
    for(int i=l;i<=r;i++)
        if(in[i]==pre[t])
        {
        flag=i;break;
        }
    if(flag==-1)return;
    root=new node(in[flag]);
    t++;
    if(flag>1) buildtree(l,flag-1,t,root->l);
    if(flag<r) buildtree(flag+1,r,t,root->r);
}
void preorder(node *root)
{
    if(root != NULL)
    {
        post[k++] = root->value;
        preorder(root->l);
        preorder(root->r);
    }
}
void inorder(node *root)
{
    if(root!=NULL)
    {
        inorder(root->l);
        post[k++] = root->value;
        inorder(root->r);
    }
}
void postorder(node *root)
{
    if(root!=NULL)
    {
        postorder(root->l);
        postorder(root->r);
        post[k++]=root->value;
    }
}
void remove_tree(node *root)
{
    if(root==NULL)return;
    remove_tree(root->l);
    remove_tree(root->r);
    delete root;
}
int main()
{
    int n;
    while(scanf("%d",&n)!=EOF)
    {
        for(int i=1;i<=n;i++) scanf("%d",&pre[i]);
        for(int j=1;j<=n;j++) scanf("%d",&in[j]);
        node *root;
        int t=1;
        buildtree(1,n,t,root);
        k=0;
        postorder(root);
        for(int i=0;i<k;i++)printf("%d%c",post[i],i==k-1?'\n':' ');
        remove_tree(root);
    }
}

（尚未理解）

5.2.3 二叉搜索树

结构精巧，访问高效

二叉查找树（Binary Search Tree），（又：二叉搜索树，二叉排序树）它或者是一棵空树，或者是具有下列性质的二叉树： 若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值； 若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值；它的左、右子树也分别为二叉排序树。二叉搜索树作为一种经典的数据结构，它既有链表的快速插入与删除操作的特点，又有数组快速查找的优势；所以应用十分广泛，例如在文件系统和数据库系统一般会采用这种数据结构进行高效率的排序与检索操作。

（1）建树和插入

（2）删除

（4）遍历

BST的优劣在于它是否为一个平衡的二叉树

5.2.4 treap树

一种比较简单的平衡二叉搜索树，可翻译成树堆

Treap（树堆）的大部分功能STL的set都可以实现，但因为set的过度封装使得某些特定的功能不能实现，比如求第k大的值

（这时候的代码量已经到80行以上，上课摸不了了）

6 基础算法

6.1 贪心法

例题有HDU 2570

把整个问题分成多个步骤，每个步骤都选取当前步骤的最优方案

（就是当赌狗，赌其中一个方面最大）

8 数学

错排

错排的递推算法

错排的递推公式：f(n) = ( f(n-1) + f(n-2) ) * (n-1)

8.2 数论

8.2.1 模运算

将大数变小

8.2.2 快速幂

https://blog.csdn.net/qq_19782019/article/details/85621386

杭电OJ中序号为2035

机器运算10的9次方，而这个数10的12次方

我们程序设计语言中最大的long lnog类型也无法承载这么大的数值

题目才不会要求你输出结果，因为结果可能会非常的大

(a * b) % p = (a % p * b % p) % p

根据上面这条运算法则，可以经行初步优化，OJ结果可通过

快速幂就是快速算底数的n次幂。其时间复杂度为 O(log₂N)，与朴素的O(N)相比效率有了极大的提高

指数分成两半，而相应的底数做平方运算。这样不仅能把非常大的指数给不断变小，所需要执行的循环次数也变小，而最后表示的结果却一直不会变

8.2.3 GCD,LCM

GCD 最小公约数

#include <iostream>
using namespace std;
int gcd(int a,int b)
{
    return b==0?a:gcd(b,a%b);
}
int lcm(int a,int b)
{
    return a*b/gcd(a,b);
}
int main ()
{
    cout<<gcd(120,9)<<" "<<lcm(120,9)<<endl;
    return 0;
}

辗转相除，简单又方便

基础算法思想

贪婪法

B独木舟

线上小的，与大的匹配

简单博弈

F - 石子博弈
    雄雄学长和正曦学长今天都很无聊。两个人相约一起玩游戏。
    雄雄学长取出了一堆奇形怪状的石子，并且把它分成了三堆。他和正曦学长轮流从里面取石子，取出最后一颗石子的人胜利。正曦学长觉得这样没意思，于是他要求加入一个限制条件：每个人每次只能取出 1 , 3 , 7 或 9 颗石子。石子数目不够的时候不能多取，如还剩 2 颗石子的情况下，只能拿走 1 颗，而不能选择 3 , 7 , 9 。雄雄学长答应了，但是他要让正曦学长先拿。
    已知雄雄学长和正曦学长都足够聪明，总是会做出最好的拿石子办法。现在你能知道，正曦学长究竟能不能赢吗？
    输入格式
    共一行，包括三个整数 n , m 和 k ( 1 ≤ n , m , k ≤ 1000 )，代表三堆石子的数目。
    输出格式
    如果花椰妹能赢，则输出"win"；否则则输出"lose"。

奇偶偶 win

奇奇偶 win

前缀和差分

一维前缀和：

是一个数组的某项下标之前(包括此项元素)的所有数组元素的和

sum[i] = a[i] + a[i-1] + …………+ a [2] + a[1]

差分：

差分是一个数组相邻两元素的差

a[i] = sum[i] - sum[i+1]

二维前缀和：

（二维数组）

 b[x][y] = b[x-1][y] + b[x][y-1] – b[x-1][y-1]+a[x][y]