C++：类的继承

析构函数释放规律

局部变量储存在栈区域
所以释放的时候采用“后创建 先释放”的模式
并且在函数内在创建一个栈，例如花括号，函数递归，会先释放内部栈元素，再释放外部栈元素

#include <iostream>
using namespace std;

class MyClass {
private:
    int id;
    static int count; // 静态成员变量

public:
    MyClass(int id){
        this->id=id;
        count++;
        cout << "Constructor: Object " << this->id << " created. Total objects: " << count << endl;
    }

    ~MyClass() {
        count--;
        cout << "Destructor: Object " << this->id << " destroyed. Total objects: " << count << endl;
    }

    void showId() const {
        cout << "Object ID: " << this->id << endl;
    }

    static int getCount() { // 静态成员函数
        return count;
    }
};

int MyClass::count = 0; // 初始化静态成员变量

int main() {
    MyClass obj1(1);
    {
        MyClass obj2(2);
        obj2.showId();
    }
    cout << "Total objects after block: " << MyClass::getCount() << endl;
    return 0;
}



输出：
Constructor: Object 1 created. Total objects: 1
Constructor: Object 2 created. Total objects: 2
Object ID: 2
Destructor: Object 2 destroyed. Total objects: 1
Total objects after block: 1
Destructor: Object 1 destroyed. Total objects: 0

malloc不调用构造函数

malloc不调用构造函数，free不调用析构函数
它们两个和new与delete比起来就只是分配了内存和释放了内存而已

    #include<iostream>
    #include<stdlib.h>
    using namespace std;
    class Test {
    public:
        Test() { cout << "Constructor\n"; }
        ~Test() { cout << "Destructor\n"; }
    };
    int main() {
        Test* obj1 = (Test*)malloc(sizeof(Test)); // 不会调用构造函数
        free(obj1); // 也不会调用析构函数
        cout<<"Test* obj2 = new Test();"<<endl;
        Test* obj2 = new Test(); // 调用构造函数
        delete obj2; // 调用析构函数
        cout<<"Test*mmm=new Test[3];"<<endl;
        Test*mmm=new Test[3];
        delete[] mmm;
        return 0;
    }


输出：

Test* obj2 = new Test();
Constructor
Destructor
Test*mmm=new Test[3];
Constructor
Constructor
Constructor
Destructor
Destructor
Destructor

思考：

new能否调用有参构造函数？

回复：

单个对象的new可以使用，数组无法使用

解决办法：

创建指针数组，对每个指针new

Test* arr[3]; 
for (int i = 0; i < 3; i++) {
    arr[i] = new Test(i + 1); // 传递不同的参数
}

// 释放内存
for (int i = 0; i < 3; i++) {
    delete arr[i];
}

注意，这样得到的就是一个指针数组,$arr[0]$是指针，而非Test对象

new分配内存失败

#include <iostream>
#include <new>  // std::bad_alloc

int main() {
    try {
        // 试图分配一个很大的数组，可能导致内存分配失败
        int* p = new int[100000000000];
    } catch (const std::bad_alloc& e) {
        std::cout << "内存分配失败: " << e.what() << std::endl;
    }

    return 0;
}

如果有new头文件（储存异常宏）
会直接终止程序，抛出std::bad_alloc异常
没有好像也没关系

但是如果把new加上修饰符，内存分配失败的时候就会返回空指针而不是抛出异常

int* p = new(std::nothrow) int[1000000];  // 若分配失败，p 为 nullptr，而不是抛出异常
if (!p) {
    std::cout << "内存分配失败" << std::endl;
}

default和delete使用限制

default可以在外部使用，也可以在内部使用
delete只能在第一次声明时写出，在类外部写出是非法的

delete报错与未定义

使用delete释放非指针变量时编译会报错
多次释放同一个指针地址会导致未定义行为（和数组越界，对new出的数组使用delete p差别不大）

拷贝构造函数/拷贝运算符/拷贝优化

#include <iostream>
using namespace std;

class FOO {
public: 
    FOO(int i)
    { 
        cout << "Constructing.\n"<<this<<endl;
        member = i;
    }

    FOO(const FOO& other)//拷贝构造
    { 
        cout << "Copy constructing.\n"<<this<<endl;
        member = other.member;
    }
    //拷贝赋值
    ~FOO()
    { 
        cout << "Destructing.\n"<<this<<endl; 
    }

    int get() { return member; }

private: 
    int member;
};

void display(FOO obj) { 
    cout << obj.get() << "\n"; 
}

FOO get_foo() { 
    int value;
    cout << "Input an integer:";
    cin >> value;
    FOO obj(value);
    return obj;
}

int main() {
    cout<<"--FOO obj1(15)--"<<endl;
    FOO obj1(15); // 调用一般的构造函数
    // cout<<"--FOO obj2 = get_foo()--"<<endl;
    // FOO obj2=get_foo();
    // cout<<"--obj2's 地址是--"<<&obj2<<endl;cout<<"--obj2's 地址是--"<<&obj2<<endl;
    cout<<"--obj2 = obj1--"<<endl;
    FOO obj2 = obj1; // 调用拷贝构造函数
    cout<<"--obj2's 地址是--"<<&obj2<<endl;

    cout<<"--display(obj2)--"<<endl;
    display(obj2); // 调用拷贝构造函数，传值给形参obj
    cout<<"--obj2 = get_foo()--"<<endl;
    obj2 = get_foo(); // 不会调用拷贝构造函数，返回时使用移动或复制消除
    cout<<"--display(obj2)--"<<endl;
    display(obj2); 
    cout<<"--obj2's 地址是--"<<&obj2<<endl;


    return 0; // 按声明的逆顺序释放对象
}

2680. 最大或值

问题：

观察到，要选找位数最高的数左移k位，才可能使或值最大

尝试通过两次循环而不是排序找出所有最高位元素。

时间复杂度从$O(nlogn)$到$O(n)$

随后，对取出的最高位元素各自尝试左移，找出最大答案。

时间复杂度约$O(nlogn)$

整体时间复杂度约为$O(nlogn)$

成功TLE

代码：

class Solution {
public:
    long long maximumOr(vector<int>& nums, int k) {
        auto maxIt=max_element(nums.begin(),nums.end());
        int maxIndex=maxIt-nums.begin();
        int len=nums.size(),big=0,temp=nums[maxIndex];
        while(temp){
            temp>>=1;
            big++;
        }
        big--;
        vector<int> maxIndexs;
        for(int i=0;i<len;i++){
            if(nums[i]>>big!=0)
                maxIndexs.push_back(i);
        }
        long long ans=0;
        for(auto&Index:maxIndexs){
            nums[Index]=nums[Index]<<k;
            ans=max(ans,cal(nums));
            nums[Index]=nums[Index]>>k;
        }
        return ans;
    }
    long long cal(vector<int>&nums){
        long long res=0;
        for(auto&a:nums){
            res=res|a;
        }
        return res;
    }
};

改进思路：

将逐个左移的操作压缩时间复杂度，先用O(n)时间复杂度处理前缀与后缀或数，以达到降低每次取或的时间复杂度

class Solution {
public:
    long long maximumOr(vector<int>& nums, int k) {
        auto maxIt=max_element(nums.begin(),nums.end());
        int maxIndex=maxIt-nums.begin();
        int len=nums.size(),big=0;
        long long temp=nums[maxIndex];
        while(temp){
            temp>>=1;
            big++;
        }
        big--;
        vector<int> maxIndexs;
        for(int i=0;i<len;i++){
            if(nums[i]>>big!=0)
                maxIndexs.push_back(i);
        }

        vector<long long> pre1(len,0),pre2(len,0);
        pre1[0]=nums[0];
        pre2[len-1]=nums[len-1];
        for(int i=1,j=len-2;i<len;i++,j--){
            pre1[i]=pre1[i-1]|nums[i];
            pre2[j]=pre2[j+1]|nums[j];
        }
        //pre1[i]表示从开头或到下标i

        long long ans=0;
        for(auto&Index:maxIndexs){
            // nums[Index]=nums[Index]<<k;
            long long temp=0;//此处计算最大或值
            if(len==1)
                temp=(long long)nums[Index]<<k;
            else if(Index==0)
                temp=pre2[1]|(long long)nums[Index]<<k;
            else if(Index==len-1)
                temp=pre1[len-2]|((long long)nums[len-1]<<k);
            else
                temp=pre1[Index-1]|((long long)nums[Index]<<k)|pre2[Index+1];
            ans=max(ans,temp);
        }
        return ans;
    }
};

P1075 [NOIP 2012 普及组] 质因数分解

简单水题

关键在于其搜索分界点是sqrt(n)

但是不能在分界点右边找

在右边查找的时间复杂度为$O(n - n^{\frac{1}{2}})$，而在分界点左边的时间复杂度是$O(n^{\frac{1}{2}})$，在n较大时差别尤其明显

#include<bits/stdc++.h>
using namespace std;

int n;

int main(){
    cin>>n;
    int l=sqrt(n);
    for(int i=2;i<=l;i++){
        if(n%i==0)
            cout<<n/i;
    }
    return 0;
}

关闭输入同步流黑魔法

std::ios::sync_with_stdio(0)

素数筛

P3383 【模板】线性筛素数

欧拉筛：CSDN欧拉筛与埃式筛参考博客
使用了bitset数组代替bool

#include<bits/stdc++.h>
using namespace std;

bitset<100000010> noP;
// bool noP[100000010];
vector<int> primer;
int main(){
    ios::sync_with_stdio(0);
    int n,q;
    cin>>n>>q;
    for(int i=2;i<=n;i++){
        if(noP[i]==0)
            primer.push_back(i);
        for(int len=primer.size(),j=0;j<len;j++){
            if(primer[j]*i>n)//若i是素数，则相当于从i开始乘倍，i之前的倍数没必要乘，因为i之前的数全部都被它们或它们的质因数筛过了
                break;
            noP[primer[j]*i]=1;
        }
    }
    for(int i=0;i<q;i++){
        int a;
        cin>>a;
        cout<<primer[a-1]<<"\n";
    }
    return 0;
}

P1012 [NOIP 1998 提高组] 拼数

解题思路：

按照字典序排序，可以选出左位数字高的字符串，然后按顺序拼接即可。

原代码：

#include<iostream>
#include <vector>
#include<algorithm>
using namespace std;
const int MAXN = 30;
int n;
string a[MAXN];
bool compare(const string& _a,const string& _b){
    return _a>_b;
}
int main(){
    cin>>n;
    for(int i=0;i<n;i++){
        int temp;
        cin>>temp;
        a[i] = to_string(temp);
    }
    sort(a,a+n,compare);
    string res = "";
    for(int i=0;i<n;i++){
        res+=a[i];
    }
    cout<<res<<endl;
    return 0;
}

得分：75分
原因：整数按字典序排序，虽然可以正确处理$64$排在$598$这种情况，但是并不能正确处理$32$与$321$的关系。
如果按字典序排序，那么$321$应该在$32$前面。但在本题之中，$321$与$32$之间的顺序关系应该是$32321$，因为$1$小于$3$
因此，不能比较字典序，因为那样会在前缀相同的情况下，把长的放到前面。
实际上，在前缀相同时，应该比较的是超出部分的第一位与另一个字符串的第一位，因此应该稍作修改比较函数

#include<iostream>
#include <vector>
#include<algorithm>
using namespace std;
const int MAXN = 30;
int n;
string a[MAXN];
bool compare(const string& _a,const string& _b){
    return _a+_b>_b+_a;
}
int main(){
    cin>>n;
    for(int i=0;i<n;i++){
        int temp;
        cin>>temp;
        a[i] = to_string(temp);
    }
    sort(a,a+n,compare);
    string res = "";
    for(int i=0;i<n;i++){
        res+=a[i];
    }
    cout<<res<<endl;
    return 0;
}

思维题：P1007 独木桥

本题关键：如何理解士兵的转向。

由于士兵相向之后必定转向，且转向无需耗费时间，因此可以认为，当他们开始行动时，就会不断转向转向转向，直到中间的相向对全部消除。

既然如此，最后的状态必然是： 左出口 < < < < < > > > > > > > > > 右出口 ，类似于这种结构，只需要针对士兵位置，特化出最长时间情况（全部同向）和最短时间情况（在中点左右分段）即可。

#include <iostream>
#include<algorithm>
using namespace std;
const int MAXN = 1e5+10;
int l,n,a[MAXN];
int main(){
    cin>>l>>n;
    int min_time=0;
    int max_time=0;
    for(int i=0;i<n;i++){
        int t;
        cin>>t;
        a[t]=1;
        min_time = max(min_time,min(t,l+1-t));
        max_time = max(max_time,max(t,l+1-t));
    }
    cout<<min_time<<" "<<max_time;
    return 0;
}

pair的max比较

在刷每日一题的时候，灵茶山艾府所写的一道简单题题解中，一个细节我认为十分有趣

• 链接
  数据结构pair<>是可以调用C++STL库的max()函数的，如何比较呢？按字典序和位比较，类似实数比较，仅在first位相等情况下比较second位

在此题中，这个性质恰好符合题目要求，用在此处浑然天成，令人惊叹。

class Solution {
public:
    int areaOfMaxDiagonal(vector<vector<int>>& dimensions) {
        pair<int, int> mx{};
        for (auto& d : dimensions) {
            int x = d[0], y = d[1];
            mx = max(mx, pair(x * x + y * y, x * y));
        }
        return mx.second;
    }
};