xuanxuan0604的博客

博客

标签

暂无

新博客

2026-03-21 11:25:41 By xuanxuan0604

我发现在数据统计中前缀和和后缀和标反了

阅读全文

新博客

2025-12-20 11:10:38 By xuanxuan0604

class long_int{

private:

size_t m_length;
int m_num[10005];

public:

long_int(){
    memset(m_num,0,sizeof(m_num));
    m_length=1;
}

long_int(size_t x,bool flag){
    if(flag){
        memset(m_num,0,sizeof(m_num));
        m_length=x;
    }
    else{
        string str;
        while(x){
            str+=(x%10)+'0';
            x/=10;
        }
        for(int i=0;i<str.length();i++){
            m_num[i]=str[i]-'0';
        }
        m_length=str.length();
    }
}

void Measure_size(){
    for(int i=0;i<10005;i++){
        if(m_num[i]){
            m_length=i;
        }
    }
    m_length++;
}

void print_sys(){
    for(int i=0;i<m_length;i++){
        cout<<m_num[i];
    }
    cout<<endl;
}

size_t size(){
    return m_length;
}

size_t length(){
    return m_length;
}

bool operator<(long_int b){
    for(int i=max(m_length,b.length());i>-1;i--){
        if(m_num[i]>b[i]){
            return false;
        }
        if(m_num[i]<b[i]){
            return true;
        }
    }
    return false;
}

int operator[](int __index__){
    return m_num[__index__];
}

long_int operator*(long_int b){
    long_int res(m_length+b.length(),1);
    for(int i=0;i<m_length+b.length()-1;i++){
        for(int j=0;j<=i;j++){
            res.m_num[i]+=m_num[j]*b[i-j];
        }
        res.m_num[i+1]+=res.m_num[i]/10;
        res.m_num[i]%=10;
    }
    res.Measure_size();
    return res;
}

void operator=(int x){
    string str;
    while(x){
        str+=(x%10)+'0';
        x/=10;
    }
    for(int i=0;i<str.length();i++){
        m_num[i]=str[i]-'0';
    }
    m_length=str.length();
}

void operator=(string str){
    for(int i=0;i<str.length();i++){
        m_num[i]=str[str.length()-i-1]-'0';
    }
    m_length=str.length();
}

friend ostream& operator<<(ostream& out_put__,long_int& out_num){
    for(int i=out_num.length()-1;i>-1;i--){
        out_put__<<out_num[i];
    }
    return out_put__;
}

};

long_int max_(long_int a,long_int b){ return a<b?b:a; }

阅读全文

730题庆！

2025-11-22 11:20:57 By xuanxuan0604

好久没发过题庆了

阅读全文

新博客

2024-07-22 16:55:02 By xuanxuan0604

deque 是 double-ended queue 的缩写，又称双端队列容器。

deque 容器和 vecotr 容器有很多相似之处，比如：

deque 容器也擅长在序列尾部添加或删除元素（时间复杂度为O(1)），而不擅长在序列中间添加或删除元素。

deque 容器也可以根据需要修改自身的容量和大小。

和 vector 不同的是，deque 还擅长在序列头部添加或删除元素，所耗费的时间复杂度也为常数阶O(1)。当需要向序列两端频繁的添加或删除元素时，应首选 deque

容器。

deque 容器以模板类 deque（T 为存储元素的类型）的形式在头文件中，并位于 std 命名空间中。因此，在使用该容器之前，代码中需要包含下面两行代码：

    #include <deque>
    using namespace std;

创建 deque 容器，根据不同的实际场景，可选择使用如下几种方式

创建一个没有任何元素的空 deque 容器：

    deque<int> d;

和空 array 容器不同，空的 deque 容器在创建之后可以做添加或删除元素的操作，因此这种简单创建 deque 容器的方式比较常见。

创建一个具有 n 个元素的 deque 容器，其中每个元素都采用对应类型的默认值：

    deque<int> d(10);

此行代码创建一个具有 10 个元素（默认都为 0）的 deque 容器。

创建一个具有 n 个元素的 deque 容器，并为每个元素都指定初始值，例如：

    deque<int> d(10, 5);

如此就创建了一个包含 10 个元素（值都为 5）的 deque 容器。

在已有 deque 容器的情况下，可以通过拷贝该容器创建一个新的 deque 容器，例如：

    deque<int> d1(5);
    deque<int> d2(d1);

注意，采用此方式，必须保证新旧容器存储的元素类型一致。

通过拷贝其他类型容器中指定区域内的元素（也可以是普通数组），可以创建一个新容器，例如：

//拷贝普通数组，创建deque容器
int a[] = { 1,2,3,4,5 };
deque<int>d(a, a + 5);
//适用于所有类型的容器
array<int, 5>arr{ 11,12,13,14,15 };
deque<int>d(arr.begin()+2, arr.end());//拷贝arr容器中的{13,14,15}

deque 容器中，无论是添加元素还是删除元素，都只能借助 deque 模板类提供的成员函数: 成员函数 | 功能

push_back( ) | 队尾插入元素

push_front( ) | 队首插入元素

pop_back( ) | 队尾删除元素

pop_front( ) | 队首删除元素

emplace_back( ) | 队尾生成元素(C++11添加)

emplace_front( ) | 队首生成元素(C++11添加)

insert( ) | 在指定位置生成元素

emplace( ) | 在指定位置生成元素(C++11添加),比insert( )省时

erase( ) | 删除指定位置或区域的元素

clear( ) | 删除元素中所有元素

重点讲一下 insert( ) 函数的用法。insert( ) 函数的功能是在 deque 容器的指定位置插入一个或多个元素。该函数的语法格式有多种，如下所示:

insert(pos,elem) 在pos前插入elem
insert(pos,n,elem) 在pos前插入n个elem
insert(pos,first,last) 在pos前插入其他容器[first,last)间的所有元素
insert(pos,initlist) 在pos之前插入initlist的元素，initlist是大括号括起的多个元素，中间用逗号相连

容器适配器，其就是将不适用的序列式容器（包括 vector、deque 和 list）变得适用。容器适配器本质上还是容器，只不过此容器模板类的实现，利用了大量其它基础容器模板类中已经写好的成员函数。当然，如果必要的话，容器适配器中也可以自创新的成员函数。 STL 提供了 3 种容器适配器，分别为 stack 栈适配器、queue 队列适配器以及 priority_queue 优先权队列适配器。

由于 stack 适配器以模板类

stack<T,Container=deque<T> >

其中 T 为存储元素的类型，Container 表示底层容器的类型）的形式位于头文件中，并定义在 std 命名空间里。因此，在创建该容器之前，程序中应包含以下 2 行代码：

#include <stack>
using namespace std;

创建 stack 适配器，大致分为如下几种方式。

创建一个不包含任何元素的 stack 适配器，并采用默认的 deque 基础容器：

    stack<int> values;

上面这行代码，就成功创建了一个可存储 int 类型元素，底层采用 deque 基础容器的 stack 适配器。

上面提到，

    stack<T,Container=deque<T> >

模板类提供了 2 个参数，通过指定第二个模板类型参数，我们可以使用出 deque 容器外的其它序列式容器，只要该容器支持 empty( )、size( )、back( )、push_back( )、pop_back( ) 这 5 个成员函数即可。在介绍适配器时提到，序列式容器中同时包含这 5 个成员函数的，有 vector、deque 和 list 这 3 个容器。因此，stack 适配器的基础容器可以是它们 3 个中任何一个。例如，下面展示了如何定义一个使用 list 基础容器的 stack 适配器：

    stack<int, list<int> > values;

可以用一个基础容器来初始化 stack 适配器，只要该容器的类型和 stack 底层使用的基础容器类型相同即可。例如：

    list<int> values {1, 2, 3};
    stack<int,list<int> > my_stack (values);

注意，初始化后的 my_stack 适配器中，栈顶元素为 3，而不是 1。另外在第 2 行代码中，stack 第 2 个模板参数必须显式指定为 list（必须为 int 类型，和存储类型保持一致），否则 stack 底层将默认使用 deque 容器，也就无法用 lsit 容器的内容来初始化 stack 适配器。

还可以用一个 stack 适配器来初始化另一个 stack 适配器，只要它们存储的元素类型以及底层采用的基础容器类型相同即可。例如：

    list<int > values{ 1, 2, 3 };
    stack<int, list<int> > my_stack1(values);
    stack<int, list<int> > my_stack=my_stack1;
    //stack<int, list<int> > my_stack(my_stack1);

下表列出了 stack 容器支持的全部成员函数：

成员函数 | 功能

empty( ) | 为空返回true，否则返回false

size( ) | 返回存储元素个数（栈的大小）

top( ) | 返回栈顶的引用形式

push(const T&obj) | 将 obj的副本放到栈顶，调用内部的push_back( )

push(T&& obj) | 将obj以移动元素的方式压到栈顶，调用内部的有右值引用参数的push_back( )

emplace(Args&&… args) | 根据既定的排序规则，在栈顶生成元素

pop( ) | 移除栈顶元素

swap(priority_queue& other) | 互换两个元素类型及基础容器类型相同的栈

queue 容器适配器以模板类

    queue<T,Container=deque<T> >

    #include <queue>
    using namespace std;

创建 queue 容器适配器的方式大致可分为以下几种。

创建一个空的 queue 容器适配器，其底层使用的基础容器选择默认的 deque 容器：

    queue<int> values;

通过此行代码，就可以成功创建一个可存储 int 类型元素，底层采用 deque 容器的 queue 容器适配器。

当然，也可以手动指定 queue 容器适配器底层采用的基础容器类型。作为 queue 容器适配器的基础容器，其必须提供 front( )、back( )、push_back( )、pop_front( )、empty( ) 和 size( ) 这几个成员函数，符合条件的序列式容器仅有 deque 和 list。

例如，下面创建了一个使用 list 容器作为基础容器的空 queue 容器适配器：

    queue<int, list<int>  > values;

注意，在手动指定基础容器的类型时，其存储的数据类型必须和 queue 容器适配器存储的元素类型保持一致。

可以用基础容器来初始化 queue 容器适配器，只要该容器类型和 queue 底层使用的基础容器类型相同即可。例如：
```
deque<int> values{1,2,3};
queue<int> my_queue(values);
```
由于 my_queue 底层采用的是 deque 容器，和 values 类型一致，且存储的也都是 int 类型元素，因此可以用 values 对 my_queue 进行初始化。
还可以直接通过 queue 容器适配器来初始化另一个 queue 容器适配器，只要它们存储的元素类型以及底层采用的基础容器类型相同即可。例如：
```
deque<int> values{1,2,3};
queue<int> my_queue1(values);
queue<int> my_queue(my_queue1);
//或者使用queue<int> my_queue = my_queue1;
```
注意，和使用基础容器不同，使用 queue 适配器给另一个 queue 进行初始化时，有 2 种方式，使用哪一种都可以。

值得一提的是，第 3、4 种初始化方法中 my_queue 容器适配器的数据是经过拷贝得来的，也就是说，操作 my_queue 容器适配器中的数据，并不会对 values 容器以及my_queue1 容器适配器有任何影响；反过来也是如此。

下表罗列了 queue 容器支持的全部成员函数：

成员函数 | 功能

empty( ) | 为空返回true，否则返回false

size( ) | 返回存储元素个数（队列大小）

front( ) | 返回第一个元素（队首）的引用形式

back( ) | 返回最后一个元素（队尾）的引用形式

push(const T& obj) | 将obj的副本放到队尾，调用内部的push_back( )

emplace(Args&&… args) | 在尾部直接生成元素

pop( ) | 移除队首元素，调用内部的pop_back( )

swap(priority_queue& other) | 互换两个元素类型及基础容器类型相同的队列

和 stack 一样，queue 也没有迭代器，因此访问元素的唯一方式是遍历容器，通过不断移除访问过的元素，去访问下一个元素。

priority_queue 容器适配器模拟的也是队列这种存储结构，即使用此容器适配器存储元素只能“从一端进（称为队尾），从另一端出（称为队头）”，且每次只能访问 priority_queue 中位于队头的元素。

但是，priority_queue 容器适配器中元素的存和取，遵循的并不是 “First in,First out”（先入先出）原则，而是“First in，Largest out”原则。直白的翻译，指的就是先进队列的元素并不一定先出队列，而是优先级最大的元素最先出队列。

由于 priority_queue 容器适配器模板位于头文件中，并定义在 std 命名空间里，因此在试图创建该类型容器之前，程序中需包含以下 2 行代码：

    #include <queue>
    using namespace std;

创建 priority_queue 容器适配器的方法，大致有以下几种。 1. 创建一个空的 priority_queue 容器适配器，第底层采用默认的 vector 容器，排序方式也采用默认的 less 方法：

    priority_queue<int> values;

可以使用普通数组或其它容器中指定范围内的数据，对 priority_queue 容器适配器进行初始化：
```
//使用普通数组
int values[]{4,1,3,2};
priority_queue<int>copy_values(values,values+4);//{4,2,3,1}
//使用序列式容器
array<int,4>values{ 4,1,3,2 };
priority_queue<int>copy_values(values.begin(),values.end());
//{4,2,3,1}
```
注意，以上 2 种方式必须保证数组或容器中存储的元素类型和 priority_queue 指定的存储类型相同。另外，用来初始化的数组或容器中的数据不需要有序，

priority_queue 会自动对它们进行排序。

还可以手动指定 priority_queue 使用的底层容器以及排序规则，比如：
```
int values[]{ 4,1,2,3 };
priority_queue<int, deque<int>, greater<int> >copy_values(values, values+4);//{1,3,2,4}
```
事实上，less 和 greater 适用的场景是有限的，更多场景中我们会使用自定义的排序规则。

priority_queue 容器适配器提供了下表所示的这些成员函数：

成员函数 | 功能

empty( ) | 为空返回true，否则返回false

size( ) | 返回存储元素个数（队列大小）

top( ) | 返回第一个元素（队首）的引用形式

push(const T&obj) | 根据既定的排序规则，obj的副本放到对应的位置

push(T&& obj) | 根据既定的排序规则，obj放到对应的位置

emplace(Args&&… args) | 根据既定的排序规则，在适当位置生成元素

pop( ) | 移除队首元素

swap(priority_queue& other) | 互换两个元素类型及基础容器类型相同的优先队列

和 queue 一样，priority_queue 也没有迭代器，因此访问元素的唯一方式是遍历容器，通过不断移除访问过的元素，去访问下一个元素。

阅读全文

链表（不循环！！！）

2024-07-16 21:31:45 By xuanxuan0604

一.单向链表

1.插入

a[i]________________________a[i+1]

___________________________^

|___________________________|

|----------> (a[j])-----------| （方括号[]内的是下标，a[j]表示插入进去的元素）

插入分两步

第一步把插入进的 a[j]的next赋值成a[i+1];

第二步把a[i]的next赋值成a[j]

    a[j]->next=a[i]->next;
    a[i]->next=a[j];

2.删除 （逻辑意义上的，实际只是按链表访问不到这个元素了）

a[i-1]______a[i]_______a[i+1]

|________________________^

|________________________|

删除只需要一步

把a[i-1]的next指向a[i-1]的next的next就行了（为了防止a[i+1]被删掉了）

    a[i-1]->next=a[i-1]->next->next;

二.双向链表

1.双向链表与单向链表的区别

单向链表一项有一个数据和一个指针，叫next，代表它的后一项。

双向链表一项有一个数据和两个指针，一个指针叫pre，代表它前一项，另一个指针叫next，代表它的后一项。

双向链表因为多一个指针，就多空间，少访问时间，但较复杂，慎用，一般用单项就够了。

2.插入

比单向链表的插入多了两步，一步将a[i+1]的pre指针指向a[j]，一步将a[j]的pre指针指向a[i] （图太难画了）

前两步（单、双向都有的步骤）的顺序固定，后两步顺序任意

    a[j]->next=a[i]->next;
    a[i]->next=a[j];
    a[i+1]->pre=a[j];
    a[j]->pre=a[i];

3.删除

比单向链表的插入多了一步，将a[i+1]的pre指针指向a[i-1]

    a[i-1]->next=a[i-1]->next->next;
    a[i-1]->next->pre=a[i-1];

阅读全文

顺序表

2024-07-16 11:35:56 By xuanxuan0604

1.顺序表的优缺

优点：随机存取，知道首地址和下标就能直接算出地址，存取方便

缺点：插入和删除需要移动大量元素，复杂度高

2.插入和删除操作

插入：（x是插入位置，y是插入数值，arr的下标从0开始）（网站题号：#7352）

    for(int i=n-1;i>=x;i--){
        arr[i+1]=arr[i];
    }
    arr[x]=y;

删除：（x是删除位置，arr的下标从0开始）（网站题号：#7048）

    for(int i=x;i<n;i++){
        arr[i]=arr[i+1];
    }

阅读全文

论#1163 积分游戏

2024-07-14 14:07:06 By xuanxuan0604

#1163中的 TEST#5 是这样的：

3 3 3

9 2 9 3 4 7 3 9 7

8 1 4 7 8 8 6 1 6

4 7 3 4 4 1 2 6 10

题目中说了，有m行，每行n个数字，这里n和m都是3，可是他一行有9个数字，为啥？？？

阅读全文

你们信息与未来考了多少

2024-06-04 19:19:48 By xuanxuan0604

如题

阅读全文

共 12 篇博客

xuanxuan0604的博客

博客

新博客

Complex（复数类）(半成品)

新博客

730题庆！

欧拉筛

新博客

链表（不循环！！！）

顺序表

论#1163 积分游戏

你们信息与未来考了多少