CSP_J 暑假清北學(xué)堂集訓(xùn) 第一天

數(shù)據(jù)結(jié)構(gòu) ：
數(shù)據(jù)結(jié)構(gòu)：1.怎么寫；2.怎么用
一、數(shù)組
1.負(fù)數(shù)下標(biāo)是可以定義的:
1.變量局部開在棧空間里
2.數(shù)組全局變量開在堆空間里
3.數(shù)組越界會(huì)出現(xiàn)一些奇奇怪怪到小問題

處理方法:

int a[1000010];
int *b = a + 500000;
結(jié)果:
b[-233] -> a[500000-233];
b[-500000 ~ 500000];

棧：stack(簡單一些)
queue<int> name

priority_queue<int> q;
priority_queue<int> heap_l;
priority_queue<int> heap_r;

map:
第一個(gè)int代表下標(biāo)類型 
第二個(gè)int代表元素類型 
實(shí)現(xiàn)：
map<int,int> name;
操作：
map<string,int> 強(qiáng)過結(jié)構(gòu)體呀

algorithm:

max(a,b); max(max(a,b),c)
min(a,b); min(min(a,b),c)
int c;
long long d;
min(c,d) 錯(cuò)誤！必須同樣類型 
swap(a,b)換

sort排序（好東西）:
typename (int) a[100];
cin >> n;
for(int i = 1; i <= n; i ++) cin >> a[i];
sort(z + 1, z + n + 1); //把a(bǔ)[1] 到 a[n] 從小到大排序 （nlogn)
從大到小： 
bool cmp(int a,int b)//返回ab后a是否應(yīng)該排在b前面 
｛
    return a > b; 
｝
sort(a + 1, a + n + 1,cmp);//從大到小 (相反數(shù)排序)
reverse(a + 1, a + n + 1);//翻轉(zhuǎn)數(shù)組

unique:
unique(a + 1, a + n + 1) ; 把a(bǔ)[1] ~ a[n] 去重 but必須把數(shù)組排完序才能使用 
int m = unique(a + 1, a + n + 1) - a - 1;去重完有幾個(gè)數(shù)

random_shuffle:
random_shuffle(a + 1, a + n + 1) 把a(bǔ)[1] ~ a[n] 隨機(jī)打亂

merge_sort: 
歸并排序根本思想： 分治，切幾刀，分別排序，直到只剩一個(gè)數(shù)字，停下 （分）  比較兩數(shù)列的最小值：min(a1,b1) min(a1,b2) ……（治）

merge_sort(int l, int r){
    long long ans = 0;
    if(r == l) return;啥也不用干 
    int m = (l + r) / 2;
    ans += merge_sort(l , m);左邊部分 
    ans += merge_sort(m + 1 , r);右邊部分
    int pl = l;左邊第一個(gè)數(shù)的下標(biāo) 
    int pr = m + 1;右邊第一個(gè)數(shù)的下標(biāo) 
    for(int i = l; i <= r; i++){
        if(pl > m) b[i] = a[pr],pr++;左邊沒數(shù)了 
        else if(pr > r) b[i] = a[pl],pl++;右邊沒數(shù)了 
        if(a[pl] < a[pr]) b[i] = a[pl],pl++;左邊少 
        else b[i] = a[pr],pr++,ans += m - p + 1;右邊少 
    }
    for(int i = l; i <= r; i++) a[i] = b[i];抄回來 
    return ans;
}
int main(){
    cin >> n;
    for(int i = 1; i <= n; i++){
        cin >> a[i];
    }
    merge_sort(1,n);
}

前綴和：
sum[i] = a1 + a2 + a3 + …… + ai
       = a1 + a2 + …… + ar - a …… - al-1

cin >> n;
for(int i = 1; i <= n; i++) cin >> a[i];
for(int i = 1; i <= n; i++) sum[i] = sum[i - 1] + a[i];
cin >> m;
for(int i = 1; i <= m; i++){
    int l , r;
    cin >> l >> r; 
    cout << sum[r] - sum[l - 1];
}

注意：
1.用“\n”不用endl 差距真的很大(4s多)
2.快讀代碼實(shí)現(xiàn)：

int read(){
    int x = 0;
    char c = '?';
    while(c < '0' || c > '9') c = getchar();
    while(c > '0' && c < '9'){
        x = x * 10 + c - '0';
        c = getchar();
    }
    return x;
}

3.不用快輸，用cout就行 
4.scanf用來 格式化： scanf("%d-%d-%d", &year, &month,&day);
5.速度排序：/ %  <   x   <  + -  <  & | ^ << >>   <  <= >= == != 
6.x << y == x * 2 ^ y
7.x >> y == x / 2 ^ y
map<string,string> b; 
map當(dāng)無限大數(shù)組用就行啦 /se
a[1] = 2; log級(jí)別速度 
a[-2333] = 9 log級(jí)別速度 （所有） 
b["hello"] = "world";
想怎么用就怎么用 
慢！ 
不同類型間的關(guān)系可以用

線性結(jié)構(gòu)：

struct shouxie_queue{//隊(duì)列 
    int z[1000000]; 
    int tail;
    int head;
    shouxie_queue(){//構(gòu)造函數(shù) 
        tail = 1;
        head = 0;
        memset(z,0,sizeof(z));
        //memset(z,-1,sizeof(z))
        //memset(z,0x3f,sizeof(z))
    }
    void pop(){
        head++;
    }
    void push(int x){
      /*while(head <= x && x < z[tail])    單調(diào)遞增 
            tail --;
        while(head <= x && x > z[tail])
            tail --;*/ 
        tail++;
        z[tail] = x;
    }
    int front(){
        return z[head];
    }
    int size(){
        return tail - head + 1;
    }
};
struct heap{//大根堆（二叉樹） 
    int a[100000];
    int n;
    int top(){
        return a[1];
    }
    int size(){
        return n;
    }
    void push(int x){
        n++;
        a[n] = x; 
        int p = n;
        while(p != 1){//根節(jié)點(diǎn)為一 不等于才需要換 
            int f = p / 2;
            if(a[f] < a[p]){
                swap(a[f], a[p]);
                p = f;
            }
            else break;
        }
    }
    void pop(){//彈出 每個(gè)節(jié)的值 都要大于子點(diǎn)的值  
        a[1] = a[n];
        n--;
        int p = 1;
        while(p * 2 <= n){
            int pp = 2 * p;//左兒子 
            if(pp + 1 <= n && a[pp + 1] > a[pp]) pp = pp + 1;
            if(a[p] < a[pp]){
                swap(a[p], a[pp]);
                p = pp;
            }
            else break;
        } 
    }
};//每個(gè)節(jié)的值 都要大于子點(diǎn)的值 
//題目：給出序列，求每個(gè)區(qū)間的中位數(shù) ll a[100000];
int main(){
    int n;
    cin >> n;
    for(int i = 1; i <= n; i++) cin >> a[i];
    for(int l = 1; l <= n; l++){
        heap_l.push(a[l]);
        cout << 中位數(shù) << endl;
        int median = a[l];//當(dāng)前中位數(shù) 
        for(int r = l + 1;r <= n; r++){
            if(a[r] > median) heap_r.push(-a[r]);
            else heap_l.push(a[r]);
            while(heap_l.size() > heap_r.size() + 1){
                int v = heap_l.top();
                heap_l.pop();
                heap_r.push(-v);
            }
            while(heap_r.size() > heap_l.size() + 1){
                int v = heap_r.top();
                heap_r.pop();
                heap_l.push(-v);
            }
            if(heap_l.size() > heap_r.size()) median= heap_l.top();
            else if(heap_l.size() < heap_r.size()) median= heap_r.top();
            else median = (heap_l.top() - heap_r.top) / 2;
            cout << median;
        }
    }

posted on 2023-07-11 18:42 Slz_konnyaku 閱讀(28) 評(píng)論(0) 收藏舉報(bào)

刷新頁面返回頂部

公告