头像

wjundong


访客:845

离线:1天前


活动打卡代码 AcWing 841. 字符串哈希

wjundong
16天前
//字符串hash
//1.首先把字符串写成p进制,p的经验值是质数131、13331
//写成p进制时,要取模,这里把数据类型unsigned long long
//溢出时会自动取模
//2.对于要查询的子串的hash值h[l-r] = h[r] - h[l-1]*p^(r -l + 1)
#include<bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
#define ull unsigned long long
ull f[N],p[N];
const ull mod = 131;

int main()
{
    ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    int n,q;
    string s;
    cin >> n >> q;
    cin >> s;
    p[0] = 1;
    for(int i = 0;i < n;i++)
    {
        f[i+1] = f[i]*131 + (s[i] - 'a' + 1);
        p[i+1] = p[i]*131;
    }
    while(q--)
    {
        int l1,l2,r1,r2;
        cin >> l1 >> r1 >> l2 >> r2;
        ull a = f[r1] - f[l1-1]*p[r1 - l1 + 1];
        ull b = f[r2] - f[l2 -1]*p[r2 - l2 + 1];
        if(a == b) cout << "Yes" << endl;
        else cout << "No" << endl;
    }
    return 0;
}


活动打卡代码 AcWing 840. 模拟散列表

wjundong
16天前
拉链法
#include<bits/stdc++.h>
using namespace std;

const int N = 1e5 + 3; 
int h[N],ver[N],ne[N],id = 0;

void insert(int x)
{
    int k = (x%N + N) % N;
    ver[id] = x;
    ne[id] = h[k];
    h[k] = id++;
}

bool find(int x)
{
    int k = (x % N + N) % N;
    for(int i = h[k]; i!= -1; i = ne[i])
    if(ver[i] == x) return 1;
    return 0;
}

int main()
{
    ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    memset(h,-1,sizeof h);
    int n,x;
    string s;
    cin >> n;
    while(n--)
    {
        cin >> s >> x;
        if(s == "I")
        insert(x);
        else {
            if(find(x)) cout << "Yes" << endl;
            else cout << "No" << endl;
        }
    }
    return 0;
}
开放地址法
#include<bits/stdc++.h>
using namespace std;
const int N = 2e5 + 3,inf = 0x3f3f3f3f;//N经验值是两倍 

int h[N];

int find(int x)
{
    int k = (x % N + N) % N;
    while(h[k] != inf && h[k] != x)
    {
        k++;
        if(k == N) k = 0;
    }
    return k;
}

int main()
{
    ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    memset(h,0x3f,sizeof h);
    int n,x;
    string s;
    cin >> n;
    while(n--)
    {
        cin >> s >> x;
        int k = find(x);
        //cout << k << endl;
        if(s == "I") h[k] = x;
        else{
            if(h[k] == inf) cout << "No" << endl;
            else cout << "Yes" << endl;
        }
    }
    return 0;
}



wjundong
16天前

分享一个c语言知识

问题

int a=023;
printf(“%d\n”,--a,a--);

解答

这个也是百度的,主要是记录一下这个冷门知识
a = 023是八进制,即十进制19。printf(“%d\n”,–a,a–)的控制符却是要求用十进制输出的
即要把023换算成十进制再经–运算最后输出。printf(“%d\n”,–a,a–)是从右向左来计度算要输出的变量列表的,本题中先计算a–,再计算–a:
printf(“%d\n”,–a,a–)的格式控制符只有一个%d,就是说后面的输出变量表中的两个变量只道输出1个值;
那么,输出哪一个呢?是–a还是a–呢?答案是–a,输出17.因为虽然printf函数的变量表是从右至左计算的,但输内出时却是从最左端对应输出的,就是说一个%d对应–a而不是a–。本题若把printf(“%d\n”,–a,a–)改为printf(“%d%d\n”,–a,a–),那就会输出17 19,或许还与编译器有关,因为C/C++的编译器太多。



活动打卡代码 AcWing 839. 模拟堆

wjundong
16天前
#include<bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
int h[N],in[N],id[N];//堆中节点的值:第i个插入的数,在堆中对应的节点编号:堆中节点为i的是第几个插入的 
int sz = 0;

void sp(int a,int b)
{
    swap(in[id[a]],in[id[b]]);
    swap(id[a],id[b]);
    swap(h[a],h[b]);
}

void down(int x)
{
    int t = x;
    if(x*2 <= sz && h[t] > h[x*2]) t = x*2;
    if(x*2 + 1 <= sz && h[t] > h[x*2 + 1]) t = x*2 + 1;
    if(t != x)
    {
        sp(x,t);
        down(t);
    }
}

void up(int x)
{
    while(x/2 && h[x] < h[x/2])
    {
        sp(x,x/2);
        x /= 2;
    }
}

int main()
{
    ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    int n, cur = 0;
    cin >> n;
    while(n--)
    {
        string op;
        int k, x;
        cin >> op;
        //cout << op << endl;
        if(op[0] == 'I'){
            cin >> x; 
            sz++;
            cur++;
            h[sz] = x;
            id[sz] = cur;
            in[cur] = sz;
            up(sz);
        }
        else if (op == "PM") cout << h[1] << endl;
        else if(op == "DM")
        {
            sp(1,sz);
            sz--;
            down(1);
        }
        else if(op[0] == 'D')
        {
            cin >> k;
            int t = in[k];
            sp(t,sz);
            sz--;
            up(t);
            down(t);
        }
        else{
            cin >> k >> x;
            int t = in[k];
            h[t] = x;
            up(t);
            down(t);
        }
    }
    return 0;
 } 



wjundong
17天前

题目链接 Acwing

我遇到了本地编译器有输出acwing没有输出问题,被气哭了,woc。

错误的代码:

#include<bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
int h[N],in[N],id[N];//堆中节点的值:第i个插入的数,在堆中对应的节点编号:堆中节点为i的是第几个插入的 
int sz = 0;

void sp(int a,int b)
{
    swap(in[id[a]],in[id[b]]);
    swap(id[a],id[b]);
    swap(h[a],h[b]);
}

void down(int x)
{
    int t = x;
    if(x*2 <= sz && h[t] > h[x*2]) t = x*2;
    if(x*2 + 1 <= sz && h[t] > h[x*2 + 1]) t = x*2 + 1;
    if(t != x)
    {
        sp(x,t);
        down(t);
    }
}

void up(int x)
{
    while(x/2 && h[x] < h[x/2])
    {
        sp(x,x/2);
        x /= 2;
    }
}

int main()
{
    //ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    int n, cur = 0;
    scanf("%d",&n);
    while(n--)
    {
        char op[2];
        int k, x;
        scanf("%s", op);
        if(op[0] == 'I'){
            scanf("%d",&x); 
            sz++;
            cur++;
            h[sz] = x;
            id[sz] = cur;
            in[cur] = sz;
            up(sz);
        }
        else if (!strcmp(op, "PM")) printf("%d\n", h[1]);
        else if(op == "DM")
        {
            sp(1,sz);
            sz--;
            down(1);
        }
        else if(op[0] == 'D')
        {
            scanf("%d",&k);
            int t = in[k];
            sp(t,sz);
            sz--;
            up(t);
            down(t);
        }
        else{
            scanf("%d%d",&k,&x);
            int t = in[k];
            h[t] = x;
            up(t);
            down(t);
        }
    }
    return 0;
 } 

编译器报了什么错误?没有输出




wjundong
17天前
#include<bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
int a[N],b[N];
int n,m,x;

int main()
{
    ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    cin >> n >> m >> x;
    for(int i = 1;i <= n;i++)
    cin >> a[i];

    for(int i = 1;i <= m;i++)
    cin >> b[i];
    int l = 1,r = m;
    while(true)
    {
        if(a[l] + b[r] == x)
        {
            cout << l-1 << " " << r-1 << endl;
            break;
        }
        else if(a[l] + b[r] < x) l++;
        else r--;
    }
    return 0;
}


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

wjundong
17天前
#include<bits/stdc++.h>
using namespace std;
const int N = 1e3 + 10;
int n,m,q;
int a[N][N],b[N][N];

int main()
{
    ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    cin >> n >> m >> q;
    int r1,c1,r2,c2,d;
    for(int i = 1;i <= n;i++)
    for(int j = 1;j <= m;j++)
    cin >> a[i][j];

    while(q--)
    {
        cin >> r1 >> c1 >> r2 >> c2 >> d;
        b[r1][c1] += d;
        b[r1][c2 + 1] -= d;
        b[r2+1][c1] -= d;
        b[r2+1][c2 + 1] += d;
    }

    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];
        cout << a[i][j] + b[i][j] << " \n"[j == m];
    }
    return 0;
}


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

wjundong
17天前
#include<bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
int a[N];
int n,m;

int main()
{
    ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); 
    cin >> n >> m;
    for(int i = 1;i <= n;i++)
    {
        cin >> a[i];
        a[i] += a[i-1];
    }
    while(m--)
    {
        int l,r,c;
        cin >> l >> r;
        cout << a[r] - a[l-1] << endl;
    }

    return 0;
 } 


活动打卡代码 AcWing 797. 差分

wjundong
17天前
#include<bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
int a[N],b[N];
int n,m;

int main()
{
    ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); 
    cin >> n >> m;
    for(int i = 1;i <= n;i++)
    cin >> a[i];
    while(m--)
    {
        int l,r,c;
        cin >> l >> r >> c;
        b[l] += c,b[r+1] -= c;
    }

    for(int i = 1;i <= n;i++)
    {
        b[i] += b[i-1];
        cout << a[i] + b[i] << " ";
    }
    cout << endl;
    return 0;
 } 


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

wjundong
17天前
#include<bits/stdc++.h>
using namespace std;
const int N = 1010;
int a[N][N];

int n,m,q,x1,y_1,x2,y2;
int main()
{
    ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    cin >> n >> m >> q;
    for(int i = 1;i <= n;i++)
    for(int j = 1;j <= m;j++)
    {
        int x;
        cin >> x;
        a[i][j] = a[i-1][j] + a[i][j-1] - a[i-1][j-1] + x;
    }

    while(q--)
    {
        cin >> x1 >> y_1 >> x2 >> y2;
        int res = a[x2][y2] - a[x1-1][y2] - a[x2][y_1-1] + a[x1-1][y_1-1];
        cout << res << endl;
    }
    return 0;
 }