头像

洗个苹果




离线:7小时前


最近来访(18)
用户头像
Schwarzt
用户头像
夜寐
用户头像
incra
用户头像
qwq2
用户头像
zdkk
用户头像
一坨小橙橙
用户头像
梦魇影儀

活动打卡代码 AcWing 802. 区间和

洗个苹果
9小时前

如: 值域0 ~ 10^9 个数 : 10 ^ 5

1 a[]中可能重复元素 需要去重
2 如何算出 x 离散化后的值是多少 二分

vector<int> alls; // 存储所有待离散化的值
sort(alls.begin(), alls.end()); // 将所有值排序
alls.erase(unique(alls.begin(), alls.end()), alls.end());   // 去掉重复元素
//unique 将数组中所以元素去重,并且返回去重后数组的尾端点
// 二分求出x对应的离散化的值
int find(int x) // 找到第一个大于等于x的位置
{
    int l = 0, r = alls.size() - 1;
    while (l < r)
    {
        int mid = l + r >> 1;
        if (alls[mid] >= x) r = mid;
        else l = mid + 1;
    }
    return r + 1; // 映射到1, 2, ...n
}
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

typedef pair<int, int> PII;

const int N = 300010;

int n, m;
int a[N], s[N];

vector<int> alls;
vector<PII> add, query;

int find (int x)
{
    int l = 0, r = alls.size() - 1;
    while (l < r)
    {
        int mid = l + r >> 1;
        if (alls[mid] >= x) r = mid;
        else l = mid + 1;
    }
    return r + 1;   //映射到从1开始,因为前缀和从1开始做比较好做
}

int main ()
{
    cin >> n >> m;
    for (int i = 0; i < n; i ++)
    {
        int x, c;
        cin >> x >> c;
        add.push_back({x, c});

        alls.push_back(x);
    }

    for (int i = 0; i < m; i ++)
    {
        int l, r;
        cin >> l >> r;
        query.push_back({l, r});

        alls.push_back(l);
        alls.push_back(r);
    }

    //去重
    sort(alls.begin(), alls.end());
    alls.erase(unique(alls.begin(), alls.end()), alls.end());

    for (auto item : add)
    {
        int x = find(item.first);
        a[x] += item.second;
    }

    //预处理前缀和
    for (int i = 1; i <= alls.size(); i ++)   //all.size() 就是映射到的最大坐标
    s[i] = s[i - 1] + a[i];

    //处理询问
    for (auto item : query)
    {
        int l = find(item.first), r = find(item.second);
        cout << s[r] - s[l - 1] << endl;
    }

    return 0;
}



n的二进制表示中第k位是几

1 先把第k位移到最后一位 n >> k
2 看个位是几 如 : x & 1

1 和 2 合起来就行 n >> k & 1

位运算
求n的第k位数 :n >> k & 1
返回n的最后一位1: lowbit (n) = n & - n

#include <iostream>

using namespace std;

int lowbit (int x)
{
    return x & -x;
}

int main ()
{
    int n;
    cin >> n;
    while (n --)
    {
        int x;
        cin >> x;

        int res = 0;
        while (x) x -= lowbit (x), res ++;  //每次减去x的最后一位1

        cout << res << ' ';
    }

    return 0;
}



双指针

1归并排序算一个双指针 (指向一个序列)
2快排 (指向一个区间)

//基本代码
for (i = 0, j = 0; i < n; i ++)
{
    while (j < i && check (i, j)) j ++;
    //check i, j的性质
    //每道题目的具体逻辑
}

先写一个暴力算法, 再判断i和j有没有什么单调关系 将O(n^2)变成O(n)

核心性质

for (int i = 0; i < n; i ++)
    for (int j = 0; j < n; j ++)
        O(n^2)

//将上面的朴素算法优化到O(n)
#include <iostream>

using namespace std;

const int N = 100010;

int a[N], s[N];      //a[N]是原来的数
int n;               //s[N]是当前j到i的区间里,每一个数出现的次数

int main ()
{
    cin >> n;
    for (int i = 0; i < n; i ++)    cin >> a[i];

    int res = 0;    //答案
    for (int  i = 0, j = 0; i < n; i ++)
    {
        s[a[i]] ++;             //*****用来计a[i]这个数出现的次数,如:a[2] = 1, a[3] = 1, 则s[a[i] = 2;*****
        while (s[a[i]] > 1)     //区间中新加的数是a[i], 当a[i] > 1 时就表示有重复元素
        {
            s[a[j]] --;         
            j ++;               //j右移, 则a[j] 数就少1(i, j 区间里的)
        }
        res = max (res, i - j + 1);
    }

    cout << res << endl;

    return 0;
}


活动打卡代码 AcWing 798. 差分矩阵

二维差分

原 : aij
构造bij
使

#include <iostream>

using namespace std;

const int N = 1010;
int a[N][N], b[N][N];
int n, m, q;

void insert (int x1, int y1, int x2, int y2, int c)
{
    b[x1][y1] += c;
    b[x2 + 1][y1] -= c;
    b[x1][y2 + 1] -= c;
    b[x2 + 1][y2 + 1] += c;
}

int main ()
{
    scanf("%d%d%d", &n, &m, &q);

    for (int i = 1; i <= n; i ++)
        for (int j = 1; j <= m; j ++)
            scanf("%d", &a[i][j]);

    for (int i = 1; i <= n; i ++)
        for (int j = 1; j <= m; j ++)
            insert (i, j, i, j, a[i][j]);       //先把矩阵都看成0,然后进行插入操作,相当于构造了原矩阵

    while(q --)
    {
        int x1, y1, x2, y2, c;
        cin >> x1 >> y1 >> x2 >> y2>> c;
        insert (x1, y1, x2, y2, c);
    }

    for (int i = 1; i <= n; i ++)
        for (int j = 1; j <= m; j ++)
            b[i][j] += b[i - 1][j] + b[i][j - 1] - b[i - 1][j - 1];

    for (int i = 1; i <= n; i ++)
    {
        for (int j = 1; j <= m; j ++) printf("%d ", b[i][j]);
        puts("");
    }
    return 0;
}


活动打卡代码 AcWing 797. 差分

差分
a1, a2, a3, .... a称为b的前缀和
构造b1, b2, b3, ...... b称为a的差分
使得ai = b1 + b2 + b3 + b4 + …+ bi

b1 = a1 
b2 = a2 - a1
b3 = a3 - a2
.
.
.
bn = an - an- 1


想让a数组中 l ~ r 都加上c, 则我们可以通过bl + c ,br - c来实现
bl + c 则al 后面所以的数都 加了c, br - c则后面所以的数都 减了c
因为a是通过求前缀和得到的  
如 bi + c   ,则ai = b1 + b2 + b3 + b4.......+bi + c
                ai + 1 =  b1 + b2 +...+ bi +c + bi + 1
#include <iostream>

using namespace std;

const int N = 100010;

int n, m;
int a[N], b[N];

void insert (int l, int r, int c)
{
    b[l] += c;
    b[r + 1] -= c;
}

int main ()
{
    scanf("%d%d",&n, &m);
    for (int i = 1; i <= n; i ++) scanf("%d", &a[i]);

    for (int i = 1; i <= n; i ++) insert(i, i, a[i]);   //看成a数组初始的时候是0,则其差分数组也为0,可以看成进行了n次插入操作 
                                                        //如 1 ~ 1 的区间加上a1 ,2 ~ 2 的区间加上a2

    while (m --)
    {
        int l, r, c;
        scanf("%d%d%d", &l, &r, &c);
        insert (l, r, c);
    }

    for (int i = 1; i <= n; i ++) b[i] += b[i - 1];  //b变成自己的前缀和

    for (int i = 1; i <= n; i ++) printf("%d ", b[i]);

    return 0;

}


活动打卡代码 AcWing 796. 子矩阵的和

二维的前缀和

公式:s[x2][y2] - s[x1 - 1][y2] - s[x2][y1 - 1] + s[x1 - 1][y1 - 1]

#include <iostream>

using namespace std;

const int N = 1010;

int n, m, q;
int a[N][N], s[N][N];

int main ()
{
    scanf("%d%d%d", &n, &m, &q);
    for (int i = 1; i <= n; i ++)
        for (int j = 1; j <= m; j ++)       //前缀和都是从1开始的,方便写,
            scanf("%d", &a[i][j]);

    for (int i = 1; i <= n; i ++)
        for (int j = 1; j <= m; j ++)
            s[i][j] = s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1] + a[i][j];        //求前缀和


    while (q --)
    {
        int x1, y1, x2, y2;
        scanf("%d%d%d%d", &x1, &y1, &x2, &y2);
        printf("%d\n", s[x2][y2] - s[x1 - 1][y2] - s[x2][y1 - 1] + s[x1 - 1][y1 - 1]);      //求(子矩阵的和)部分和
    }

    return 0;
}


活动打卡代码 AcWing 795. 前缀和

原: a1, a2, a3, a4, ....
前缀和: Si = a1 + a2 + a3 + a4 + .... + ai S0 = 0
①如何求Si
②在l ~ r区间 Sr - Sl-1

#include <iostream>

using namespace std;

const int N = 100010;

int n, m;
int a[N], s[N];

int main ()
{
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i ++) scanf("%d", &a[i]);
    //从i=1开始读入因为让a[0] = 0, 即s[0] = 0 ,做到公式s[r] - s[l - 1] 的统一
    for (int i = 1; i <= n; i ++) s[i] = s[i - 1] + a[i];       //求前缀和

    while (m --)
    {
        int l, r;
        scanf("%d%d", &l, &r);

        printf("%d\n", s[r] - s[l - 1]);        //求(部分和)

    }
    return 0;
}


活动打卡代码 AcWing 827. 双链表

双链表:每一个结点会有两个指针

#include <iostream>

using namespace std;

const int N = 100010;

int m;
int e[N], l[N], r[N], idx;
//l[N]表示每个点左边的点, r[N]表示每个点右边的点

//初始化
void init()        //01的初始化一般在双链表重使用,具体讲解见双链表习题课3.30
{
    //0表示左端点,1表示右端点
    r[0] = 1, l[1] = 0;     //哨兵结点
    idx = 2; //0和1已经被占用了

    //初始化两个哨兵节点(0、1分别是首和尾),R[0]=1,L[1]=0,分别表示将首节点0向右连接到尾节点1、将尾节点1向左连接到首节点0。R[0]表示0的右,L[1]表示1的左
}

//在k的右边插入一个结点
void add (int k, int x)
{
    e[idx] = x; //把值赋给要加的结点

    r[idx] = r[k]; //把所加结点的右边指向k结点指向的右边的结点
    l[idx] = k;    //所加结点的左边指向k结点
    l[r[k]] = idx;  //先把k结点左边指向的结点指向所加结点   (原本指向k)
    r[k] = idx ++;     //k结点指向所加结点
    //注意最后两个式子不能写反,如果先r[k] = r[idx]的话,就不好引用原本的r[k]了,(即原来k所指的右边)

}
//如果在k的左边插入z,则调用add(l[k], x),
//注意: 这里不能用add(k - 1, x),k - 1 不一定是k的左边或者可能不存在,k - 1 和k不一定是连接在一起的


//删除第k个点
void remove (int k)
{
    r[l[k]] = r[k];     //让要删除的点k 所指的左边所指的右边直接 等于 k所指的右边 
    l[r[k]] = l[k];     //让要删除的点k 所指的右边所指的左边直接 等于 k所指的左边
}


int main ()
{
    int m;
    cin >> m;

    init ();

    while (m --)
    {
        string op;
        int k, x;
        cin >> op;

        if (op == "L") 
        {
            cin >> x;
            add (0, x);   //链表最左端就是0的右边的结点

        }
        else if (op == "R")
        {
            cin >> x;
            add(l[1], x);       //链表的最右端就是1的左边的结点
        }
        else if (op == "D")
        {
            cin >> k;
            remove (k + 1);  //第k个插入点的下标应该是k + 1, 因为idx是从2开始的
        }
        else if (op == "IL")
        {
            cin >> k >> x;
            add(l[k + 1], x);
        }
        else 
        {
            cin >> k >> x;
            add(k + 1, x);
        }
    }

    for (int i = r[0]; i != 1; i = r[i]) cout << e[i] << ' ';
    cout << endl;


    return 0;

}


活动打卡代码 AcWing 826. 单链表

单链表:邻链表 存储图 和 树

双链表:优化某些问题

//静态链表,用数组模拟链表

#include <iostream>

using namespace std;

const int N = 100010;

//head表示头结点的下标,可以看做指针
//e[i]表示节点i的值
//ne[i]表示节点i的next指针
//idx储存当前已经用到了哪个点, 相当于开辟一个空间给新结点,是新插入数据的坐标
int head, e[N], ne[N], idx;

void init ()
{
    head = -1;  //-1表示空
    idx = 0;
}

//将x插到头结点

//head里存的是头结点指向的结点的下标,不是头结点的下标

void add_to_head (int x)
{
    e[idx] = x; //x的值先存在要加的结点里
    ne[idx] = head;  //把要加的指针指向head所指的结点
    head = idx; //把head指向的要加的指针
    idx ++; //这时idx这个结点已经用过了,就移向下一个位置
}

void add (int k, int x)
{
    e[idx] = x; //同上
    ne[idx] = ne[k]; //把要加的结点指向k这个结点指向的下一个结点
    ne[k] = idx; //把k这个结点指向我们要加的结点
    idx ++; //同上
}

//将下标是k的点后面的点删掉
void remove (int k)
{
    ne[k] = ne[ne[k]]; //将k结点指向k所指向的下一个结点所指向的下一个结点
}


int main ()
{
    int m;
    cin >> m;

    init ();

    while (m --)
    {
        char op; 
        int k, x;

        cin >> op;
        if (op == 'H')
        {
            cin >> x;
            add_to_head (x);
        }
        else if (op == 'D')
        {
            cin >> k;
            if (!k) head = ne[head]; //如果k是0的话,就是删除头结点,就是把头指针指向 头结点所指的结点
            remove (k - 1);
        }
        else 
        {
            cin >> k >> x;
            add (k - 1, x);
        }
    }
    for (int i = head; i != -1; i = ne[i]) cout << e[i] <<' ';;
    cout << endl;

    return 0;
}


分享 重数问题

https://blog.csdn.net/qq_50737715/article/details/123694655?ops_request_misc=%257B%2522request%255Fid%2522%253A%2522166393100816782395336027%2522%252C%2522scm%2522%253A%252220140713.130102334..%2522%257D&request_id=166393100816782395336027&biz_id=0&utm_medium=distribute.pc_search_result.none-task-blog-2~all~top_positive~default-2-123694655-null-null.142^v50^control,201^v3^control&utm_term=%E4%BC%97%E6%95%B0%E9%97%AE%E9%A2%98&spm=1018.2226.3001.4187

#include <iostream>

using namespace std;

const int N = 100010;
int q[N], zz, count;

void quick_sort (int q[], int l, int r)
{
    if (l >= r) return ;

    int i = l - 1, j = r + 1, x = q[r + l >> 1];

    while (i < j)
    {
        do i ++; while (q[i] < x);
        do j --; while (q[j] > x);
        if (i < j) swap (q[i], q[j]);
    }

    quick_sort (q, l, j);
    quick_sort (q, j + 1, r);

}

void search (int q[], int l, int r, int &n)
{
    if (l >= r) return ;    //左边界等于右边界时return 

    int  mid = l + r >> 1, xmid = q[mid], i = mid - 1, j = mid + 1;

    do i --; while (q[i] == xmid && i); //向左查找 
    do j ++; while (q[j] == xmid && j <= n); //向右查找 

    int length = j - i - 1;     //length就是先假定的相同的数的数量 
    if (length > count || (length == count && xmid < zz))
    {
        count = length;
        zz = xmid;
    }

    if (i - l + 1 >= count) search (q, l, i, n); //当左段小于count时运行,count是先假定的重数的数量 
    if (r - j + 1 >= count) search (q, j + 1, r, n);


//  if (j - i > m) m = j - i; 
//  for (int i = l - 1; q[i] < x; i ++) ;
//  for (int j = i + 1; q[j] > x; j ++) ;
}
int main ()
{
    int n;
    scanf("%d", &n);

    for (int i = 0; i < n; i ++) scanf("%d", &q[i]);

    quick_sort(q, 0, n - 1);

    search (q, 0, n - 1, n);    //先排序后查找 

    printf("%d \n %d", zz, count);


}