wjundong

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;
}


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天前

### 问题

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


### 解答

a = 023是八进制，即十进制19。printf(“%d\n”,–a,a–)的控制符却是要求用十进制输出的

printf(“%d\n”,–a,a–)的格式控制符只有一个%d，就是说后面的输出变量表中的两个变量只道输出1个值；

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天前

#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;
}


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;
}


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;
}


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;
}


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;
}