Data_structure

2024-04-22 06:08
文章标签 data structure

本文主要是介绍Data_structure，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

没想到这次写博客的时候就已经决定离开他们了。
我是真的很喜欢这么做题，无奈自己选择强加个竞赛的东西在，做题都做不开心。想想还是算了。
多路归并的问题，即把k个有序表合成一个有序表的题。
用优先队列维护每个表的“当前元素”，如果有n个元素，则时间复杂度为O（nlogk）
uva 11997
题目意思是有k个整数数组，各包含k个元素。在每个数组中取一个元素加起来，可以得到k^k个和。求这些和中最小的k个值。
分析：（非常漂亮的解法）
在解决这个问题前，我们先解决它的简化版：给出两个长度为n的有序表A和有序表B，分别在A和B中任取一个数并相加，可以得到n^2个和。求这些和中最小的n个和。
这个问题可以转换成多路归并的问题。这需要我们把这n^2个和组织成如下n个有序表：
1: A1 + B1 <= A1 + B2 <= A1 + B3 <= A1 + B4 …. <= A1 + Bn
2: A2 + B1 <= A2 + B2 <= A2 + B3 <= A2 + B3 …. <= A2 + Bn
.
.
.
n: An + B1 <= …. An + Bn
这样的话我们就可以用二元组(s, idx)来表示一个元素，其中s = A[x] + B[idx]， idx为B的下标。之所以不需要A的下标是因为下一个元素的和s1 = A[x] + B[idx + 1] = s - B[idx] + B[idx + 1]。这样通过一个结构体和一个函数就能完成二路归并的问题：

struct Item {int s, idx;Item(int s_ = 0, int idx_ = 0): s(s_), idx(idx_){}friend bool operator < (const Item & it1, const Item & it2) {return it1.s > it2.s;}
};void merge(int *a, int *b, int *c, int cnt) {priority_queue<Item> pq;rep(i, 0, cnt) {pq.push(Item(a[i] + b[0], 0));}rep(i, 0, cnt) {Item tmp = pq.top(); pq.pop();c[i] = tmp.s;int idx = tmp.idx++;tmp.s = tmp.s - b[idx] + b[idx + 1];if(tmp.idx < n) pq.push(tmp);}
}

那么把这题拓展到n路的话，那就只需两两归并了。代码如下：

/*************************************************************************> File Name: test.cpp> Author: Triose> Mail: Triose@163.com> Created Time: 2016年09月25日 星期日 13时38分14秒************************************************************************/#include<bits/stdc++.h>
using namespace std;
//#define ONLINE_JUDGE#define eps 1e-8
#define inf 0x3f3f3f3f
#define INF 0x7fffffff
#define INFL 0x3f3f3f3f3f3f3f3fLL
#define enter putchar(10)#define rep(i,a,b) for(int i = (a); i < (b); ++i)
#define per(i,a,b) for(int i = (a); i >= (b); --i)
#define repe(i,a,b) for(int i = (a); i <= (b); ++i)
#define ECH(it, A) for (typeof(A.begin()) it=A.begin(); it != A.end(); ++it)#define PR(a,b) pair<a,b>
#define slen(str) strlen(str)
#define ds(t) int t; sf(t)
#define Down(t) while(t--)
#define dc(t) int t; cin >> t;
#define dsD(t) ds(t); Down(t)
#define dcD(t) dc(t); Down(t)
#define ALL(A) A.begin(), A.end()
#define sf(a) scanf("%d",&a)
#define sfI(a) scanf("%I64d",&a)
#define sfd(a,b) scanf("%d%d",&a,&b)
#define sft(a,b,c) scanf("%d%d%d",&a,&b,&c)
#define pft(a,b,c) printf("%d %d %d\n",a,b,c)
#define scpy(str1, str2) strcpy(str1, str2)
#define sfs(a) scanf("%s",a)
#define pf(a) printf("%d\n",a)
#define pfd(a,b) printf("%d %d\n",a,b)
#define pfP(a) printf("%d %d\n",a.fi,a.se)
#define pfs(a) printf("%s\n",a)
#define pfI(a) printf("%I64d\n",a)
#define mem(a,b) memset((a),b,sizeof(a))#define fi first
#define se second
#define LL long long
#define DB double
#define isws ios::sync_with_stdio(false)
const double PI = acos(-1.0);
const double E = exp(1.0);template<class T> T gcd(T a, T b) { return b ? gcd(b, a % b) : a; }
template<class T> T lcm(T a, T b) { return a / gcd(a, b) * b; }
template<class T> inline T Min(T a, T b) { return a < b ? a : b; }
template<class T> inline T Max(T a, T b) { return a > b ? a : b; }int n, m;
const int maxn = 760;
int A[maxn][maxn];struct Item {int s, idx;Item(int s_ = 0, int idx_ = 0): s(s_), idx(idx_){}friend bool operator < (const Item & it1, const Item & it2) {return it1.s > it2.s;}
};void merge(int *a, int *b, int *c, int cnt) {priority_queue<Item> pq;rep(i, 0, cnt) {pq.push(Item(a[i] + b[0], 0));}rep(i, 0, cnt) {Item tmp = pq.top(); pq.pop();c[i] = tmp.s;int idx = tmp.idx++;tmp.s = tmp.s - b[idx] + b[idx + 1];if(tmp.idx < n) pq.push(tmp);}
}void Init() {rep(i, 0, n) {rep(j, 0, n) sf(A[i][j]);sort(A[i], A[i] + n);}rep(i, 1, n) merge(A[0], A[i], A[0], n);
}void print() {rep(i, 0, n) printf("%d%c", A[0][i], i == n - 1 ? '\n' : ' ');
}int main() {
#ifndef ONLINE_JUDGEfreopen("in.txt","r",stdin);
//  freopen("Out.txt", "w", stdout);
#endifwhile(~sf(n)) {Init();print();}return 0;
}

uvalive 3644
有一些简单的化合物，每个都由两种元素组成，你需要按照顺序把这些化合物装到箱子里，如果箱子里存在k个化合物并且含有k个不同的元素，就会爆炸。为了安全起见，每拿到一个化合物装箱时，你需要检查放入后是否会爆炸，如果会，则必须拒绝装这个化合物。输出拒绝的次数。
k个化合物每个化合物含两种元素，含有k个不同元素时爆炸。这个条件很直白的说了，你可以把每种元素当成点，每个化合物当成边，如果放进来的边能成环，就拒绝。那么并查集就可以做了。

/*************************************************************************> File Name: test.cpp> Author: Triose> Mail: Triose@163.com> Created Time: 2016年09月25日 星期日 13时38分14秒************************************************************************/#include<bits/stdc++.h>
using namespace std;
//#define ONLINE_JUDGE#define eps 1e-8
#define inf 0x3f3f3f3f
#define INF 0x7fffffff
#define INFL 0x3f3f3f3f3f3f3f3fLL
#define enter putchar(10)#define rep(i,a,b) for(int i = (a); i < (b); ++i)
#define per(i,a,b) for(int i = (a); i >= (b); --i)
#define repe(i,a,b) for(int i = (a); i <= (b); ++i)
#define ECH(it, A) for (typeof(A.begin()) it=A.begin(); it != A.end(); ++it)#define PR(a,b) pair<a,b>
#define slen(str) strlen(str)
#define ds(t) int t; sf(t)
#define Down(t) while(t--)
#define dc(t) int t; cin >> t;
#define dsD(t) ds(t); Down(t)
#define dcD(t) dc(t); Down(t)
#define ALL(A) A.begin(), A.end()
#define sf(a) scanf("%d",&a)
#define sfI(a) scanf("%I64d",&a)
#define sfd(a,b) scanf("%d%d",&a,&b)
#define sft(a,b,c) scanf("%d%d%d",&a,&b,&c)
#define pft(a,b,c) printf("%d %d %d\n",a,b,c)
#define scpy(str1, str2) strcpy(str1, str2)
#define sfs(a) scanf("%s",a)
#define pf(a) printf("%d\n",a)
#define pfd(a,b) printf("%d %d\n",a,b)
#define pfP(a) printf("%d %d\n",a.fi,a.se)
#define pfs(a) printf("%s\n",a)
#define pfI(a) printf("%I64d\n",a)
#define mem(a,b) memset((a),b,sizeof(a))#define fi first
#define se second
#define LL long long
#define DB double
#define isws ios::sync_with_stdio(false)
const double PI = acos(-1.0);
const double E = exp(1.0);template<class T> T gcd(T a, T b) { return b ? gcd(b, a % b) : a; }
template<class T> T lcm(T a, T b) { return a / gcd(a, b) * b; }
template<class T> inline T Min(T a, T b) { return a < b ? a : b; }
template<class T> inline T Max(T a, T b) { return a > b ? a : b; }int n, m;
const int maxn = 100010;
int fat[maxn];
int ans;int get_fat(int u) {return u == fat[u] ? u : (fat[u] = get_fat(fat[u]));
}void merge(int u, int v) {int fu = get_fat(u);int fv = get_fat(v);
//  fat[u] = fat[v] = Min(fu, fv);  wrong !!!fat[Max(fu, fv)] = Min(fu, fv); //习惯这么写，大的数的父亲是小的
}bool circle(int u, int v) {return get_fat(u) == get_fat(v);
}bool Init() {rep(i, 0, maxn) fat[i] = i;ans = 0;int u, v;while(~sf(u)) {if(u == -1) return true;sf(v);if(circle(u, v)) ans++;else {merge(u, v);}}return false;
}int main() {
#ifndef ONLINE_JUDGEfreopen("in.txt","r",stdin);
//  freopen("Out.txt", "w", stdout);
#endifwhile(Init()) {pf(ans);}return 0;
}

并查集的两题：
uvalive 3027
有n个结点，初始每个结点的根都是本身。两种操作：
I u v ：把u的父结点设置成v，距离为|u - v| % 1000
E u : 询问u到根结点的距离
比普通并查集多维护了一个dis数组用于直接求得到根结点的距离。
注意：某结点u + DIS[father]时不需要再对1000取余

/*************************************************************************> File Name: test.cpp> Author: Triose> Mail: Triose@163.com> Created Time: 2016?09?25? ??? 13?38?14?************************************************************************/#include<bits/stdc++.h>
using namespace std;
//#define ONLINE_JUDGE#define eps 1e-8
#define inf 0x3f3f3f3f
#define INF 0x7fffffff
#define INFL 0x3f3f3f3f3f3f3f3fLL
#define enter putchar(10)#define rep(i,a,b) for(int i = (a); i < (b); ++i)
#define per(i,a,b) for(int i = (a); i >= (b); --i)
#define repe(i,a,b) for(int i = (a); i <= (b); ++i)
#define ECH(it, A) for (typeof(A.begin()) it=A.begin(); it != A.end(); ++it)#define PR(a,b) pair<a,b>
#define slen(str) strlen(str)
#define ds(t) int t; sf(t)
#define Down(t) while(t--)
#define dc(t) int t; cin >> t;
#define dsD(t) ds(t); Down(t)
#define dcD(t) dc(t); Down(t)
#define ALL(A) A.begin(), A.end()
#define sf(a) scanf("%d",&a)
#define sfI(a) scanf("%I64d",&a)
#define sfd(a,b) scanf("%d%d",&a,&b)
#define sft(a,b,c) scanf("%d%d%d",&a,&b,&c)
#define pft(a,b,c) printf("%d %d %d\n",a,b,c)
#define scpy(str1, str2) strcpy(str1, str2)
#define sfs(a) scanf("%s",a)
#define pf(a) printf("%d\n",a)
#define pfd(a,b) printf("%d %d\n",a,b)
#define pfP(a) printf("%d %d\n",a.fi,a.se)
#define pfs(a) printf("%s\n",a)
#define pfI(a) printf("%I64d\n",a)
#define mem(a,b) memset((a),b,sizeof(a))#define fi first
#define se second
#define LL long long
#define DB double
#define isws ios::sync_with_stdio(false)
const double PI = acos(-1.0);
const double E = exp(1.0);template<class T> T gcd(T a, T b) { return b ? gcd(b, a % b) : a; }
template<class T> T lcm(T a, T b) { return a / gcd(a, b) * b; }
template<class T> inline T Min(T a, T b) { return a < b ? a : b; }
template<class T> inline T Max(T a, T b) { return a > b ? a : b; }int n, m;
const int maxn = 200010;
char od[5];
int root[maxn], dis[maxn];int mbs(int x) {return x > 0 ? x : -x;
}void Init() {sf(n);repe(i, 1, n) root[i] = i, dis[i] = 0;
}int get_root(int u) {if(root[u] != u) {int rt = get_root(root[u]);dis[u] += dis[root[u]];return root[u] = rt;}return u;
}void merge(int u, int v) {root[u] = v;dis[u] = mbs(u - v) % 1000;
}int main() {
#ifndef ONLINE_JUDGEfreopen("in.txt","r",stdin);
//  freopen("Out.txt", "w", stdout);
#endifdsD(t) {Init();int u, v;while(sfs(od) && *od != 'O') {if(*od == 'I') {sfd(u, v);merge(u, v);}else {sf(u);get_root(u);pf(dis[u]);}}}return 0;
}

第二题， cf上的一个好题目
722C：
给你一个数组a，下标为1～n。另外一个数组b，b[i]表示把下标为b[i]的数置0。问你，从1～n， 每次置零一个b[i]后，最大连续和是多少？
这题可以很巧秒的逆向思维：
a数组一开始是空的，因为是按照1 ～ n的顺序把b[i]位置的数置零，那么就可以等价成从n->1依次把b[i]位置上的数放到数组上去，那么并查集+sum数组轻松搞定。
sum数组中：sum[i]表示以i为根的总和。
那么放上一个数(pos位置)就可能有这么几种情况：
1：右边有数（此时右边的数肯定是某一段的终点），这时把右边的数的终点指向放上去的数即可
2：左边有数（这时候左边的数的终点要不是它本身要不保存在了root[pos - 1]里），这时让sum[root[pos - 1]] += sum[pos]就行。
输出的时候用一个栈倒一下就行了。
非常巧妙的题目：

/*************************************************************************> File Name: test.cpp> Author: Triose> Mail: Triose@163.com> Created Time: 2016年09月25日 星期日 13时38分14秒************************************************************************/#include<bits/stdc++.h>
using namespace std;
//#define ONLINE_JUDGE#define eps 1e-8
#define inf 0x3f3f3f3f
#define INF 0x7fffffff
#define INFL 0x3f3f3f3f3f3f3f3fLL
#define enter putchar(10)#define rep(i,a,b) for(int i = (a); i < (b); ++i)
#define per(i,a,b) for(int i = (a); i >= (b); --i)
#define repe(i,a,b) for(int i = (a); i <= (b); ++i)
#define ECH(it, A) for (typeof(A.begin()) it=A.begin(); it != A.end(); ++it)#define PR(a,b) pair<a,b>
#define slen(str) strlen(str)
#define ds(t) int t; sf(t)
#define Down(t) while(t--)
#define dc(t) int t; cin >> t;
#define dsD(t) ds(t); Down(t)
#define dcD(t) dc(t); Down(t)
#define ALL(A) A.begin(), A.end()
#define sf(a) scanf("%d",&a)
#define sfI(a) scanf("%I64d",&a)
#define sfd(a,b) scanf("%d%d",&a,&b)
#define sft(a,b,c) scanf("%d%d%d",&a,&b,&c)
#define pft(a,b,c) printf("%d %d %d\n",a,b,c)
#define scpy(str1, str2) strcpy(str1, str2)
#define sfs(a) scanf("%s",a)
#define pf(a) printf("%d\n",a)
#define pfd(a,b) printf("%d %d\n",a,b)
#define pfP(a) printf("%d %d\n",a.fi,a.se)
#define pfs(a) printf("%s\n",a)
#define pfI(a) printf("%I64d\n",a)
#define mem(a,b) memset((a),b,sizeof(a))#define fi first
#define se second
#define LL long long
#define DB double
#define isws ios::sync_with_stdio(false)
const double PI = acos(-1.0);
const double E = exp(1.0);template<class T> T gcd(T a, T b) { return b ? gcd(b, a % b) : a; }
template<class T> T lcm(T a, T b) { return a / gcd(a, b) * b; }
template<class T> inline T Min(T a, T b) { return a < b ? a : b; }
template<class T> inline T Max(T a, T b) { return a > b ? a : b; }int n, m;
const int maxn = 100010;
LL a[maxn];
bool has[maxn];
int dir[maxn], root[maxn];
LL sum[maxn];int find_root(int u) {return (u == root[u] ? u : root[u] = find_root(root[u]));
}void Init() {mem(has, false);repe(i, 1, n) sfI(a[i]);repe(i, 1, n) sf(dir[i]);repe(i, 1, n) root[i] = i;
}void solve() {stack<LL> s; s.push(0);LL maxv = -1;per(i, n, 2) {has[dir[i]] = true;sum[dir[i]] = a[dir[i]];if(has[dir[i] + 1]) {sum[dir[i]] += sum[dir[i] + 1];root[dir[i] + 1] = dir[i];}if(has[dir[i] - 1]) {int rt = find_root(dir[i] - 1);root[dir[i]] = rt;sum[rt] += sum[dir[i]];}maxv = Max(sum[root[dir[i]]], maxv);s.push(maxv);}while(!s.empty()) pfI(s.top()), s.pop();
}int main() {
#ifndef ONLINE_JUDGEfreopen("in.txt","r",stdin);
//  freopen("Out.txt", "w", stdout);
#endifwhile(~sf(n)) {Init();solve();}return 0;
}

这篇关于Data_structure的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！


http://www.chinasem.cn/article/924981。

相关文章

论文翻译：arxiv-2024 Benchmark Data Contamination of Large Language Models: A Survey

论文翻译：arxiv-2024 Benchmark Data Contamination of Large Language Models: A Survey

Benchmark Data Contamination of Large Language Models: A Survey https://arxiv.org/abs/2406.04244 大规模语言模型的基准数据污染：一项综述 文章目录 大规模语言模型的基准数据污染：一项综述摘要1 引言 摘要 大规模语言模型（LLMs），如GPT-4、Claude-3和Gemini的快
阅读更多...
CentOS下mysql数据库data目录迁移

CentOS下mysql数据库data目录迁移

https://my.oschina.net/u/873762/blog/180388        公司新上线一个资讯网站，独立主机，raid5，lamp架构。由于资讯网是面向小行业，初步估计一两年内访问量压力不大，故，在做服务器系统搭建的时候，只是简单分出一个独立的data区作为数据库和网站程序的专区，其他按照linux的默认分区。apache，mysql，php均使用yum安装（也尝试
阅读更多...
使用Spring Boot集成Spring Data JPA和单例模式构建库存管理系统

使用Spring Boot集成Spring Data JPA和单例模式构建库存管理系统

引言 在企业级应用开发中，数据库操作是非常重要的一环。Spring Data JPA提供了一种简化的方式来进行数据库交互，它使得开发者无需编写复杂的JPA代码就可以完成常见的CRUD操作。此外，设计模式如单例模式可以帮助我们更好地管理和控制对象的创建过程，从而提高系统的性能和可维护性。本文将展示如何结合Spring Boot、Spring Data JPA以及单例模式来构建一个基本的库存管理系统
阅读更多...
15 组件的切换和对组件的data的使用

15 组件的切换和对组件的data的使用

划重点 a 标签的使用事件修饰符组件的定义组件的切换：登录 / 注册 泡椒鱼头 ：微辣 <!DOCTYPE html><html lang="en"><head><meta charset="UTF-8"><meta name="viewport" content="width=device-width, initial-scale=1.0"><meta http-equiv="X-UA-
阅读更多...
12C 新特性，MOVE DATAFILE 在线移动 包括system， 附带改名 NID ，cdb_data_files视图坏了

12C 新特性，MOVE DATAFILE 在线移动 包括system， 附带改名 NID ，cdb_data_files视图坏了

ALTER DATABASE MOVE DATAFILE  可以改名 可以move file，全部一个命令。 resue 可以重用，keep好像不生效！！！ system照移动不误-------- SQL> select file_name, status, online_status from dba_data_files where tablespace_name='SYSTEM'
阅读更多...
SIGMOD-24概览Part7: Industry Session (Graph Data Management)

SIGMOD-24概览Part7: Industry Session (Graph Data Management)

👇BG3: A Cost Effective and I/O Efficient Graph Database in ByteDance 🏛机构：字节 ➡️领域： Information systems → Data management systemsStorage management 📚摘要：介绍了字节新提出的ByteGraph 3.0(BG3)模型，用来处理大规模图结构数据 背景
阅读更多...
java.sql.SQLException: No data found

java.sql.SQLException: No data found

Java代码如下： package com.accord.utils;import java.sql.Connection;import java.sql.DriverManager;import java.sql.PreparedStatement;import java.sql.ResultSet;import java.sql.ResultSetMetaData;import
阅读更多...
FORM的ENCTYPE=multipart/form-data 时request.getParameter()值为null问题的解决

FORM的ENCTYPE=multipart/form-data 时request.getParameter()值为null问题的解决

此情况发生于前台表单传送至后台java servlet处理： 问题：当Form需要FileUpload上传文件同时上传表单其他控件数据时，由于设置了ENCTYPE=”multipart/form-data” 属性，后台request.getParameter()获取的值为null 上传文件的参考代码：http://www.runoob.com/jsp/jsp-file-uploading.ht
阅读更多...
Oracle Data Guard：Oracle数据库的高可用性和灾难恢复解决方案

Oracle Data Guard：Oracle数据库的高可用性和灾难恢复解决方案

在企业级数据库管理中，确保数据的高可用性和在灾难情况下的快速恢复是至关重要的。Oracle Data Guard是Oracle公司提供的一种强大的数据库高可用性解决方案，它通过在主数据库和至少一个备用数据库之间提供实时或近实时的数据保护来实现这一目标。本文将详细介绍如何在Oracle数据库中部署和使用Oracle Data Guard，包括其基本概念、配置步骤、管理技巧和实际应用示例。 1. O
阅读更多...
Creating OpenAI Gym Environment from Map Data

Creating OpenAI Gym Environment from Map Data

题意：从地图数据创建 OpenAI Gym 环境 问题背景： I am just starting out with reinforcement learning and trying to create a custom environment with OpenAI gym. However, I am stumped with trying to create an enviro
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2