Jesus

411

im0use
torus

ふぇありぃあい
wuli.遇

csr
11111151

Jesus
20小时前

#include <iostream>
#include <algorithm>

using namespace std;

typedef unsigned long long ULL;

const int N = 100010, P = 131;

int n, m;
char str[N];
ULL h[N], p[N];
ULL Q = (ULL)1 << 63 ; //  2的64次方

ULL get(int l, int r)
{
return (h[r] - h[l - 1] * p[r - l + 1]) % Q; // 可以不取余Q，返回值类型是ULL就行
}

int main()
{
scanf("%d%d", &n, &m);
scanf("%s", str + 1);
p[0] = 1;
for (int i = 1; i <= n; i ++ )
{
h[i] = h[i - 1] * P + str[i]; //看图片公式
p[i] = p[i - 1] * P;  //保存下P对应所有次方的数，方便下标直接使用
}

while (m -- )
{
int l1, r1, l2, r2;
scanf("%d%d%d%d", &l1, &r1, &l2, &r2);

if (get(l1, r1) == get(l2, r2)) puts("Yes");
else puts("No");
}

return 0;
}



Jesus
1天前
#include <iostream>
#include <algorithm>
#include <string.h>

using namespace std;

const int N = 100010;

int h[N], ph[N], hp[N], cnt;

void heap_swap(int a, int b)
{
swap(ph[hp[a]],ph[hp[b]]);
swap(hp[a], hp[b]);
swap(h[a], h[b]);
}

void down(int u)
{
int t = u;
if (u * 2 <= cnt && h[u * 2] < h[t]) t = u * 2;
if (u * 2 + 1 <= cnt && h[u * 2 + 1] < h[t]) t = u * 2 + 1;
if (u != t)
{
heap_swap(u, t);
down(t);
}
}

void up(int u)
{
while (u / 2 && h[u] < h[u / 2])
{
heap_swap(u, u / 2);
u >>= 1;
}
}

int main()
{
int n, m = 0;
scanf("%d", &n);
while (n -- )
{
char op[5];
int k, x;
scanf("%s", op);
if (!strcmp(op, "I"))
{
scanf("%d", &x);
cnt ++ ;
m ++ ;
ph[m] = cnt, hp[cnt] = m;
h[cnt] = x;
up(cnt);
}
else if (!strcmp(op, "PM")) printf("%d\n", h[1]);
else if (!strcmp(op, "DM"))
{
heap_swap(1, cnt);
cnt -- ;
down(1);
}
else if (!strcmp(op, "D"))
{
scanf("%d", &k);
k = ph[k];
heap_swap(k, cnt);
cnt -- ;
up(k);
down(k);
}
else
{
scanf("%d%d", &k, &x);
k = ph[k];
h[k] = x;
up(k);
down(k);
}
}

return 0;
}



Jesus
2天前

题目描述

blablabla

样例

blablabla


算法1

blablabla

C++ 代码

blablabla


算法2

blablabla

C++ 代码

blablabla


Jesus
3天前
#include <iostream>
#include <algorithm>

using namespace std;
const int N = 100010, M = 31 * N + 10;

int n;
int a[N], son[M][2], idx;

void insert(int x) {
int p = 0;
for (int i = 30; i >= 0; i--) {
int u = x >> i & 1;
if (!son[p][u])  son[p][u] = ++idx;
p = son[p][u];
}
}

int query(int x) {
int p = 0, res = 0;
for (int i = 30; i >= 0; i--) {
int u = x >> i & 1;

if (son[p][!u]) {
p = son[p][!u];
res = res * 2 + !u;
} else {
p = son[p][u];
res = res * 2 + u;
}
}

return res;
}

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

int res = 0;
for (int i = 0; i < n; i++) {
insert(a[i]);
int t = query(a[i]);
res = max(res, a[i] ^ t);
}

cout << res;
return 0;
}


Jesus
3天前

/*
(d[x] - d[y]) % 3  （由于有负数的可能直接d[x]和d[y]分别取余结果是不正确的，这里需要使用取模）

C/C++和java %是取余   python是取模

①进行求模运算c = [a/b] = -7 / 4 = -2（向负无穷方向舍入），
②进行求余运算c = [a/b] = -7 / 4 = -1（向0方向舍入）；

①求模时：r = a - c*b =-7 - (-2)*4 = 1，
②求余时：r = a - c*b = -7 - (-1)*4 =-3。
*/

#include <iostream>

using namespace std;

const int N = 50010;

int n, m;
int p[N], d[N];

int find(int x)
{
if (p[x] != x)
{
int t = find(p[x]);
d[x] += d[p[x]];
p[x] = t;

}
return p[x];
}

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

for (int i = 1; i <= n; i ++ ) p[i] = i;

int res = 0;
while (m -- )
{
int t, x, y;
scanf("%d%d%d", &t, &x, &y);

if (x > n || y > n) res ++ ;
else
{
int px = find(x), py = find(y);
if (t == 1)
{
if (px == py && (d[x] - d[y]) % 3) res ++ ;
else if (px != py)
{
p[px] = py;
d[px] = d[y] - d[x];
}
}
else
{
if (px == py && (d[x] - d[y] - 1) % 3) res ++ ;
else if (px != py)
{
p[px] = py;
d[px] = d[y] + 1 - d[x];
}
}
}
}

printf("%d\n", res);

return 0;
}



Jesus
4天前
#include <iostream>
#include <cstdio>

using namespace std;
const int N = 1e5 + 10;
int p[N], cnt[N]; //size变量名会冲突

int find(int x) {
if (p[x] != x) return p[x] = find(p[x]);
return p[x];
}

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

for (int i = 0; i < n; i++) {
p[i] = i;
cnt[i] = 1;
}

while (m--) {
string op;
int a, b;
cin >> op;

if (op == "C")
{
cin >> a >> b;
a = find(a), b = find(b);
if (a != b)
{
p[a] = b;
cnt[b] += cnt[a];
}
}
else if (op == "Q1")
{
cin >> a >> b;
if (find(a) == find(b)) puts("Yes");
else puts("No");
}
else
{
cin >> a;
cout << cnt[find(a)] << endl;
}

}

return 0;
}


Jesus
2个月前

https://mp.weixin.qq.com/s?__biz=MjM5NTY1MjY0MQ==&mid=2650853887&idx=4&sn=8bc8a0ae10131ed7ba8c9b6d71a83ed4&chksm=bd0144b18a76cda77f904b23a05818ea3db6ac58910eca05e8d844bef7e9b44e119281cbb8b9&mpshare=1&scene=23&srcid=06111rCJYTgEAZJQjMjqX0TY&sharer_sharetime=1654940817042&sharer_shareid=21b047d30a12b4dea3199d43fe677347#rd

#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

const int N = 100010, M = 200010, INF = 0x3f3f3f3f;

int n, m;
int p[N];

struct Edge
{
int a, b, w;

bool operator< (const Edge &W)const
{
return w < W.w;
}
}edges[M];

int find(int x)
{
if (p[x] != x) p[x] = find(p[x]);
return p[x];
}

int kruskal()
{
sort(edges, edges + m);

for (int i = 1; i <= n; i ++ ) p[i] = i;    // 初始化并查集

int res = 0, cnt = 0;
for (int i = 0; i < m; i ++ )
{
int a = edges[i].a, b = edges[i].b, w = edges[i].w;

a = find(a), b = find(b);
if (a != b)
{
p[a] = b;
res += w;
cnt ++ ;
}
}

if (cnt < n - 1) return INF;
return res;
}

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

for (int i = 0; i < m; i ++ )
{
int a, b, w;
scanf("%d%d%d", &a, &b, &w);
edges[i] = {a, b, w};
}

int t = kruskal();

if (t == INF) puts("impossible");
else printf("%d\n", t);

return 0;
}



Jesus
2个月前
#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

const int N = 510, INF = 0x3f3f3f3f;

int n, m;
int g[N][N];
int dist[N];
bool st[N];

int prim()
{
memset(dist, 0x3f, sizeof dist);

int res = 0;
for (int i = 0; i < n; i ++ )
{
int t = -1;
for (int j = 1; j <= n; j ++ )
if (!st[j] && (t == -1 || dist[t] > dist[j]))
t = j;

if (i && dist[t] == INF) return INF;

if (i) res += dist[t];
st[t] = true;

for (int j = 1; j <= n; j ++ ) dist[j] = min(dist[j], g[t][j]);
}

return res;
}

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

memset(g, 0x3f, sizeof g);

while (m -- )
{
int a, b, c;
scanf("%d%d%d", &a, &b, &c);
g[a][b] = g[b][a] = min(g[a][b], c);
}

int t = prim();

if (t == INF) puts("impossible");
else printf("%d\n", t);

return 0;
}



Jesus
2个月前
#include <iostream>
#include <cstdio>

using namespace std;
const int N = 210;

int INF = 1E9, n, m, q;
int dis[N][N];

int Floyd() {
for (int i = 1; i <= n; i++)
for (int j = 1; j <= n; j++)
for (int k = 1; k <= n; k++) {
dis[j][k] = min(dis[j][k], dis[j][i] + dis[i][k]);
}
}

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

for (int i = 1; i <= n; i++)
for (int j = 1; j <= n; j++)
if (i == j) dis[i][j] = 0;
else dis[i][j] = INF;

while (m--) {
int a, b, c;
scanf("%d %d %d", &a, &b, &c);
dis[a][b] = min(dis[a][b], c);
}

Floyd();

while (q--) {
int a, b;
scanf("%d %d", &a, &b);
if (dis[a][b] > INF / 2) cout << "impossible" << endl;
else cout << dis[a][b] << endl;
}

return 0;
}


Jesus
2个月前
#include <iostream>
#include <cstdio>
#include <cstring>
#include <queue>
using namespace std;

const int N = 1e5 + 10;
int h[N], e[N], ne[N], w[N], idx;
int n, m;
int dis[N], st[N], cnt[N];

void add(int a, int b, int c) {
e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx++;
}

int spfa() {
memset(dis, 0x3f, sizeof(dis));
dis[1] = 0;
queue<int> q;
for (int i = 1; i <= n; i++) q.push(i);

while (q.size()) {
int t = q.front();
q.pop();
st[t] = false;

for (int i = h[t]; i != -1; i = ne[i]) {
int j = e[i];
if (dis[j] > dis[t] + w[i]) {
dis[j] = dis[t] + w[i];
cnt[j] = cnt[t] + 1;
if (cnt[j] >= n) return true;
if (!st[j]) {
q.push(j);
st[j] = true;
}
}
}
}
return false;
}

int main() {
cin >> n >> m;
memset(h, -1, sizeof(h));

for (int i = 0; i < m; i++) {
int a, b, c;
scanf("%d %d %d", &a, &b, &c);