24暑期算法竞赛集训

Day 1 小专题

多个输入

读入大量数据的范式
比如，求未知个整数的和

1
2
3
4
5
6
7
8
9
10
11
12
13
int main()
{
    int c=0;
    int x;
    while(true)
    {
        cin>>x;
        if(!cin) break;
        c+=x;
    }
    cout<<c<<endl;
    return 0;
}

自己调试的时候要加ctrl z模拟文件流结束的EOF

串与整数转换

eg：把字符串转成整数数字 

1
2
3
4
5
6
7
8
const char* s="12053";
int n=0;
while(*s)
{
    n=n*10+(*s-'0');
    s++;
}
cout<<n;

把数字转化为字符串

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
int main()
{
    char s[100];
    int n=12503;
    char* p=s;
    do{
        *p=n%10+'0';
        p++;
        n/=10;   //update n
    }while(n>0);   //后判断
    //此时p指向最后一个数字的后一位
    *p='\0';
    //反转这个串
    p--；
    char* q=s;
    while(p>q)
    {
        chat t=*p;
        *p=*q;
        *q=t;
        p--;
        q++;
    }
    cout<<s;
    return 0;
}




进制转换

串->值 高位算起 值->串 低位算起，结果反转

eg:16进制转换 

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
const char* s="FF";
int n=0;
while(*s)
{
    n=n*16+((*s>='0'&&*s<='9')? *s-'0' : *s-'A'+10);
    s++;
}
cout<< n<< endl;


n=255;
int a[]={'0','1','2','3','4','5','6','7','8','9',
         'A'.'B','C'.'D','E','F'};
char buf[100];
char *p=buf;
do{
    *p=a[n%16];
    p++;
    n/=16;
}while(n>0);

*p='\0';
p--;
char* q=buf;
//双指针交换
while(q<p){
    char t=*p;
    *p=*q;
    *q=t;
    p--;
    q++;
}
cout<<n<<endl;

事实上16进制可以直接调用API

1
2
3
4
5
6
7
8
9
10
11
12
13
14
int main()
{
    int n=1000;
    char buf[100];
    //printf("%X",n); //16进制
    
    sprintf(buf,"%X",n);  //写入buf中
    const char* a[] ={}
    char* p=buf;
    while(*p){
        cout<< ((*p>='0'&&*p<='9')? a[*p-'0'] : a[*p-'A'+10])
        p++;
    }
}

伪进制问题/Excel列地址

A B C D…Z AA AB… ZZ

  • Q1
  • 字符转序号？ AA=> 27 1到26的进位而非0到25的进位 
    1
    2
    3
    4
    5
    6
    7
    8
    const char* s="XYZA";
    int n=0;
    while(*s){
        n=n*26+(*S-'A'+1);
        s++;
    }
    cout<< n<< endl;

  • Q2
  • 序号转字符？ n 可以表示为
    n=262626a + 2626b + 26c + d 发现 n%26=d
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include <iostream>
#include<string>
int main()
{
    int n=434901;
    string s;

    do{
        int a=n%26;
        int b=n/26;
        if(a==0){
            a=26;
            b--;
        }   //因为0 无对应字母
        s = (a-1+'A') + s;   //不用自己翻转了
        n=b;
    }while(n>0);

    cout<< s << endl;
}

基本排序

  • 交换排序

不断交换逆序的元素，达到最终的有序，冒泡排序就是一种交换排序算法，它比较并交换相邻的元素，当然我们也可以不局限于相邻的元素。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
int main()
{
    int n;
    cin>>n;
    int* buf =new int[n];
    // scanf buf
    for(int i=0;i<n;i++) 
    {
        for(int j=0;j<n-1-i;j++)
        {
            if(a[j]>a[j+1])
            swap(a[j],a[j+1]);
        }
    }



    delete [] buf;
}
  • 选择排序

从一堆元素中找出最小元素放入有序列，再从剩下的元素中选最小，重复上述操作直到最后一个元素。

1721894019395.png

稳定性指的是：排序结束之后，相等的元素是否还是排序之前的顺序？
你别说，分开多个函数写还挺舒服。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
void f(int *p, int n)
{
    int t=0; //最小元素位置
    for(int i=1;i<n;i++){
        if(p[i]<p[t]) t=i;
    }
    if(t>0){
        int x=p[0];
        p[0]=p[t];
        p[t]=x;
    }
}
void sort(int *buf,int n)
{
    for(int i=0;i<n-1;i++)  //从第一个开始找，从第二个开始找****从第n-1个开始找
    {
        f(buf+i,n-i);
    }
}
  • 插入排序 基本思想是：把一个元素插入到有序队列的适当位置 1721897363146.png 
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    void f(int* p,int k)   //k待插入
    {
        int*q=p;
        int t=p[k];
        //查找应该插入的位置
        while(*q<t) q++;

        int *r=p+k-1;    //右边界
        while(r>=q){
            r[1]=r[0];   //做交换
            r--;
        }
        *q=t;
    }
    void sort(int* buf,int n)
    {
        for(int i=1;i<n;i++){
            f(buf,i)  //i就是准备加入进来的元素
        }
    }

数据结构

vector

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include <iostream>
#include <vector>
using namespace std
int main()
{
    vector<int> arr[100];
    vector<int> list;
    for(int i=0;i<100;i++)
    {
        scanf("%d",&arr[i]);
        cout<<arr[i]<<endl;
    }
    for (int i=0;i<100;i++)
    {
        int a=0;
        cin>> a;
        list.push_back(a);
        printf("%d",list[i]);
    }
}

我们一般把vector当做链表看待使用，也就是第二种方式，这可以方便的处理不定长数组。 STL中的指针被称为迭代器 

1
2
3
4
5
vector<int> arr1(100);
int arr2[100];
vector<int>::iterator p1;
int *p2;

常见操作 
1
2
3
4
5
6
7
8
list.size();//数组元素个数   O(1)
list.clear();//一键清空数组 O(n)
list.empty();// 数组是否为空 O(1)
list.begin()； //首元素迭代器
list.end()；//最后一个元素的下一个元素的迭代器（此元素在数组中不存在）
list.erase(p1) //删除某个迭代器所在位置的元素 O(n) 这和实际的链表有区别，链表应该是O(1)
list.push_back(1)  //在数组最后添加元素  O(1);
list.pop_back(1) //删除数组最后一个元素  O(1);

利用stl实现stack和queue

  • 括号匹配问题/stack 策略：碰到左括号，压栈，碰到右括号，弹栈，判断是否相等。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
bool ok(char* p)
{
    stack<char> a;
    while(*p){
        if(*p=='(') a.push(')');
        if(*p=='[') a.push('[');
        if(*p=='{') a.push('{');
        if(*p==')'||*p==']'||*p=='}'){
            if(a.empty()) return false;
            if(a.top()!=*p) return false;
            a.pop();
        }
        p++
    }
    return a.empty();
}

  • queue 不多用，略

逆波兰表达式

逆波兰表达式又叫后缀表达式，就是把运算符放在运算数的右边。 例子：我们常用的中缀表达式：（2+3）5-（42）
逆波兰： 2 3 + 5 * 4 2 * -
不需要括号极大的方便了机器的求值

求值过程？遇到操作数就入栈
遇到操作符，则从栈弹出两个操作数，计算后再入栈。

  • stringstream类
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#include <iostream>  
#include <sstream>  
#include <string>  
  
int main() {  
    std::stringstream data("123 456 hello");  
    int a, b;  
    std::string s;  
  
    data >> a >> b >> s; // 使用重载的 >> 操作符从 data 中提取数据  
  
    std::cout << a << " " << b << " " << s << std::endl; // 输出提取的数据  
  
    return 0;  

    //结果 123 456 hello
}
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

#include<iostream?
#include<sstream>
#include<string>
#include<stack>
#include<cstdlib>
using namespace std;
int main()
{
    stack<int> w;
    stringstream data("2 3 + 5 * 4 2 * -  ");   
    string s;   
    //忽略了空白字符
    /*
    data >> s; 是一个输入操作，它从 stringstream 对象 data 中读取数据，并将读取的数据存储在字符串变量 s 中。这里的 >> 是 C++ 中的提取操作符，用于从输入流中提取数据。在这个上下文中，它从 data 中提取下一个非空白字符序列，并将其作为字符串存储在 s 中。
    */
    while(data>> s){
        if(s=="+" || s=="-" || s=="*"){
            int b=w.top();w.pop();
            int a=w.top();w.pop();
            //罗列if语句
            if(s=="+") w.push(a+b);
            else if(s=="-") w.push(a-b);
            else w.push(a*b);
        }
        else {
            w.push(atoi(s.c_str()));
        }
    }
    cout<<w.top()<<endl;
}

链表

之前敲过了，现在简单复习一下，然后用链表解决约瑟夫环问题

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
#include<iostream>
using namespace std;
struct Node{
    int data;
    Node* next;
    Node(int x){
        data=x;
        next=NULL;
    }
};

int len(Node* p)    //链表长度？
{
    int n=0;
    while(p){
        p=p->next;
        n++
    }
    return n;
}

void show(Node* p){
    Node* t=head;
    while(t){
        cout<<head->data<<endl;
        t=t->next;
    }
    cout<<endl;
}

Node* del(Node* head,int x){
    if(head==NULL) return NULL;
    Node* p=head;
    while(p->next){
        if(p->next->data==x){
            Node* q=p->next;
            p->next=(p->next)->next;
            delete q;
            return head;
        }
    }
}


二叉树

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
#include<iostream>
#include<sstream>
using namespace std;
struct bitree{
    int data;
    bitree* left;
    bitree* right;
    bitree(int x){
        data=x;
        left=NULL;
        right=NULL;
    }

    int height(){                   //树的深度
        int a =left? left->height() : 0;
        int b =right? right->height() : 0;
        return max(a,b)+1;
    }
}
void pre_order(){
    cout<<data<<" ";
    if(left) left->pre_order();
    if(right) right->pre_order();
}
bitree* create_tree(stringstream* ss)
{
    int x; *ss>>x;
    if(x==-1) return NULL;

    bitree* r = new bitree(x);

    r-left=create_tree(ss);
    r->right =create_tree(ss);

    return r;

}
int main()
{
    /*bitree a(1);
    a.left = new bitree(2);
    a.right = new bitree(3);
    
    cout<< a.height()<<endl;*/
    stringstream ss("1 2 4 -1 -1 5 9 -1 -1 -1 3 -1 6 7 -1 -1 8 -1 -1");
    bitree* p=create_tree(&ss);
    cout<< p->height();
}



树

多个分支考虑动态数组

1
2
3
4
5
6
7
8
struct Tree{
    string data;
    vector<Tree*> child;

    Tree(string x){
        data = x;
    }
};

模拟一个菜单

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
#include<iostream>
#include<vector>
#include<string>
using namespace std;

struct Tree{
    string data;
    vector<Tree*> child;

    Tree(string x){
        data=x;
    }

    void add(Tree* t){
        child.push_back(t);
    }

    string run(){
        if(child.size()==0) return data;
        while(1){
            for(int i=0; i<child.size();i++){
                cout<<i<<" "<<child[i]->data<<endl;
            }
            cout<< "-1 return to the pre"<<endl;

            int  a; cin>>a;

            if(a==-1) return " ";
            if(a>=0&& a<child.size()){
                string r= child[a]->run;
                if(r==" ") continue;
                return r;
            }
        }

    }

};

int main()
{
    Tree* a=new Tree("fruit")；
    a->add(new Tree("apple"));
    a->add(new Tree("banana"));
    a->add(new Tree("purple"));

    string r=a.run();
    cout<<"you select "<<r<<endl;
}

dfs与bfs

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include<queue>
void dfs(Tree* p){      //先根序
    cout<<p->data <<" ";
    for(int i=0;i<p->child.size();i++)
        dfs(p->child[i]);
}

void bfs(Tree* p){     //使用队列
    queue<Tree*> Q;
    Q.push(p);
    while(!Q.empty()){
        Tree* q= Q.front();
        Q.pop();
        cout<<q->data<<" ";           //打印次层
        for(int i=0;i<q->child.size();i++)
            Q.push(q->child[i];)    //所有孩子入队
    }
}

树的二叉树表示

在存储上使用二叉树，仍然能表示出一般树，甚至森林，也就是说二叉树和树存在一一对应关系 用二叉树表示的规则是： - 左孩子： 表示该节点的第一个孩子 - 右孩子： 表示该节点的下一个兄弟

定理
- 树的先根遍历等于二叉树的先根序遍历
- 树的后根遍历等于二叉树的中根序遍历

1721915798292.png 
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

struct Tree{
    int data;
    Tree* child;
    Tree* brother;

    Tree(int x){
        data=x;
        child=brother=NULL
    }

    void add(Tree* t){
        if(child=NULL) child=t;   //该节点没孩子就是该节点的孩子
        else child->add_brother(t);   //该节点有孩子，但是该节点只能有一个孩子，所以作为该节点孩子的兄弟
    }

    void add_brother(){
        if(brother==NULL)  
            brother=t;
        else 
            brother->add_brother(t);
    }

    void pre_order(){
        cout<<data<<" ";
        if(child) child->pre_order();
        if(brother) brother->pre_order();
    }

    void in_order(){
        
        if(child) child->pre_order();
        cout<<data<<" ";
        if(brother) brother->pre_order();
    }
    
};
int main()
{
    Tree a(1);
    a.add(new Tree(2));
    a.add(new Tree(3));
    a.add(new Tree(4));
    a.child->brother->add(new Tree(5));
    a.child->brother->add(new Tree(6));
}

排序二叉树

二叉树可以用于方便的搜索，动态查找

  • 插入数据时候，小的在左，大的在右
  • 按照中根序遍历就可以得到排序结果
  • 折半查找速度很快
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
struct bitree{
    int data;
    bitree* left;
    bitree* right;
    bitree(int x){
        data=x;
        left=NULL;
        right=NULL;
    }

    void add(bitree* t){
        if(t->data<data){
            if(left)
                left->add(t);
            else 
                left=t;
        }
        else {
            if(right)
                right->add(t);
            else 
                right=t;
        }
    }
}
void show(){
    
    if(left) left->pre_order();
    cout<<data<<" ";
    if(right) right->pre_order();
}
算法
#算法竞赛
24暑期算法竞赛集训
http://example.com/2024/07/25/算法/240725信息学竞赛集训营/
作者
bradin
发布于
2024年7月25日
许可协议