【ACM练习记录】数据结构题型详解——2021JNU寒假训练营D1

2023-11-05 06:38
文章标签 详解 数据结构 记录 练习 训练营 acm 寒假 题型 d1 2021jnu

本文主要是介绍【ACM练习记录】数据结构题型详解——2021JNU寒假训练营D1，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

title : 2021JNU寒假训练营Day1
tags : ACM,练习记录
date : 2021-9-18
author : Linno

放个logo

题目链接：https://vjudge.net/contest/417319#overview

考察内容：基本数据结构

榜有点歪，像第二题这么简单居然没人做。

题目不难均可做，需要熟悉STL的用法。

A-queue

思路

对于先进的队伍是优先输出的，并且每次插入要先查看元素所属的队伍是否存在队列中。我们开一个map记录每个元素所属的队伍，然后再开两个队列。其中qq表示当前排在队列中的队伍，q[i]表示i队伍中的队伍。（可能有点绕，因为题目给的是一个大队伍中有很多小队伍）。

注意不要从1~n枚举q[i]，这样不但会超时，还会使得编号小的队伍排在整支队的前面！

代码

#include<iostream>
#include<stdio.h>
#include<map>
#include<queue>
#define int long long
using namespace std;
const int maxn=1e5+7;
const int mod=1e9+7;
typedef long long ll;inline void read(int &data){int x=0,f=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-') f=f*-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}data=x*f;
}int t,n,x,idx=0;
map<int,int>mp;
string str;
queue<int>q[1005],qq;signed main(){read(t);while(t){printf("Scenario #%d\n",++idx);mp.clear();while(!qq.empty()){int fro=qq.front(); while(!q[fro].empty()) q[fro].pop();qq.pop();}for(int T=1;T<=t;T++){ read(n);for(int i=1;i<=n;i++){read(x);mp[x]=T;}}cin>>str;while(1){if(str=="STOP") break;if(str=="ENQUEUE"){read(x);if(q[mp[x]].empty()) qq.push(mp[x]);q[mp[x]].push(x);}if(str=="DEQUEUE"){int i=qq.front();if(!q[i].empty()){printf("%lld\n",q[i].front());q[i].pop();}if(q[i].empty()) qq.pop();}cin>>str;}puts("");read(t);}return 0;
}

B-stack1

思路

如果要让所有子串不合法，那么最终字符串的形式必然会是")))((“这种，左边全是失配的”)"，右边全是"("。我们容易想到每当找到一个"()“匹配，都可以用一次操作使得他不合法。那么我们只需要忽略失配的”(“和”)"，然后记录所有合法的"()"的数量，就是答案。

代码

#include<bits/stdc++.h>
#define debug(x) cout<<"x="<<x<<endl
#define int long long
using namespace std;
const int maxn=1e5+7;
const int mod=1e9+7;
typedef long long ll;inline void read(int &data){int x=0,f=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-') f=f*-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}data=x*f;
}int n;
string str[1005];signed main(){read(n);for(int i=1;i<=n;i++){cin>>str[i];int ans=0,num1=0,num2=0;for(int j=0;j<str[i].length();j++){if(str[i][j]==')'){if(num1){ //前面有左括号 ans++; //需要抵消num1--; }else num2++; //未匹配的右括号 }else{num1++; //未匹配的左括号 }}cout<<ans<<endl;}return 0;
}

C-stack2

思路

容易想到这道题的答案和化简操作次数的奇偶性有关，如何确定化简操作次数？如果读入字符的时候遇到了和前面一样的，那么我们可以直接压缩成一个字符；那么我们只要模拟一个栈，实时处理当前读入的字符，如果读入字符与栈顶相同，那么就直接弹出，并且更新操作次数就可以了。

代码

#include<bits/stdc++.h>
#define debug(x) cout<<"x="<<x<<endl
#define int long long
using namespace std;
const int mod=1e9+7;
typedef long long ll;inline void read(int &data){int x=0,f=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-') f=f*-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}data=x*f;
}char str[1000005];signed main(){int i=1,ans=0;while(cin>>str[i]&&str[i]>='a'&&str[i]<='z'){if(str[i]==str[i-1]){i-=2;ans++;}i++;}if(ans&1) cout<<"Yes\n";else cout<<"No\n";return 0;
}

D-set1

思路

数据范围很小，我们只需要熟悉set的操作，然后A删除B的元素就可以了。

代码

#include<iostream>
#include<cstring>
#include<set>
#include<algorithm>
#include<stdio.h>
#include<queue>
#include<cstdio>
#include<vector>
#include<map>
using namespace std;int main(){int n,m,x;scanf("%d%d",&n,&m);while(n!=0||m!=0){set<int>a,b;for(int i=1;i<=n;i++){scanf("%d",&x);a.insert(x);}for(int i=1;i<=m;i++){scanf("%d",&x);b.insert(x);}for(std::set<int>::iterator it=b.begin();it!=b.end();it++){a.erase(*it);}if(a.empty()) printf("NULL\n");else{for(std::set<int>::iterator it=a.begin();it!=a.end();it++){cout<<*it<<" ";}printf("\n");} scanf("%d%d",&n,&m);} return 0;
}

E-set2

思路

看题目是一道单点修改+区间查询，可以考虑用线段树来维护。

查询的时候对每一个字母都遍历这棵树就可以了。

复杂度O(nlogn)，较坏情况下应该近似两个logn

代码

#include<bits/stdc++.h>
#define int long long
#define MID int mid=(l+r)>>1
#define ls node<<1
#define rs node<<1|1
using namespace std;
typedef long long ll;
const int maxn=1e5+7;
int tr[maxn<<2][30];
string str;void build(int node,int l,int r){if(l==r){tr[node][str[l-1]-'a']++;return;}MID;build(ls,l,mid);build(rs,mid+1,r);for(int i=0;i<26;i++) tr[node][i]=tr[ls][i]+tr[rs][i];
}char update(int node,int l,int r,int pos,char c){char rg=' ';if(l==r){rg=str[l-1];tr[node][rg-'a']--;str[l-1]=c;tr[node][str[l-1]-'a']++;return rg;}MID;if(pos<=mid) rg=update(ls,l,mid,pos,c);else rg=update(rs,mid+1,r,pos,c);if(rg!=' '){tr[node][rg-'a']--;tr[node][c-'a']++;}return rg;
}bool query(int node,int l,int r,int ql,int qr,char c){if(ql<=l&&r<=qr) return tr[node][c-'a'];MID;bool r1=0,r2=0,res=0;if(ql<=mid) r1=query(ls,l,mid,ql,qr,c);if(qr>mid) r2=query(rs,mid+1,r,ql,qr,c);res=r1|r2;return res;
}signed main(){ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);cin>>str;int n=str.length(),m,op,l,r;char ch;build(1,1,n);cin>>m;for(int i=1;i<=m;i++){cin>>op;if(op==1){cin>>l>>ch;update(1,1,n,l,ch);}else{cin>>l>>r;int ans=0;for(int j=0;j<26;j++){ans+=query(1,1,n,l,r,char(j+'a'));}cout<<ans<<"\n";} } return 0;
}

F-map1

思路

熟悉map数据结构，并且开一个map<string,int>就可以过了。

代码

#include<iostream>
#include<cstring>
#include<map>
using namespace std;int n,inx=0;
string str;
map<string,int>mp;
int main(){scanf("%d",&n);for(int i=1;i<=n;i++){cin>>str;if(mp[str]){cout<<str<<mp[str]<<endl; }else{printf("OK\n");}mp[str]++; }return 0;
}

G-map2

思路

非常好玩的一道题，在map里面套map，然后两层迭代就能搞定。

代码

#include<bits/stdc++.h>
#define int long long
using namespace std;
typedef long long ll;map<string,map<string,int>>mp;int t,n,num;
string str1,str2;signed main(){ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);cin>>t;while(t--){cin>>n;mp.clear();for(int i=1;i<=n;i++){cin>>str1>>str2>>num;mp[str2][str1]+=num;}for(auto it=mp.begin();it!=mp.end();it++){cout<<(it->first)<<"\n";for(auto iter=(it->second).begin();iter!=(it->second).end();iter++){cout<<"   |----"<<(iter->first)<<"("<<(iter->second)<<")\n";}}if(t) cout<<"\n"; }return 0;
}

H-next_permutation

思路

题目告诉我们用全排列去做了，数据范围很小，只需要对每个排列都生成左右两个数字，然后找出差值最小的那一组就行了。虽然跑得慢，但注意每次排列直接将数字对半分并且避免前导零就能过。

复杂度O(n*2^n)反正不会爆。

贪心可做而且快，但是思维量大。

代码

#include<stdio.h>
#include<algorithm>
#include<vector>
#include<cmath>
#include<iostream>
//#define int long long
using namespace std;
const int inf=0x3f3f3f3f;
int t,a,b,n;
char ch;
vector<int>vt;inline void read(int &data){int x=0;char c=getchar();while(c<'0'||c>'9') c=getchar();while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}data=x;
} signed main(){read(t);while(t--){int ans=inf,idx=0;vt.clear();while(ch<'0'||ch>'9') ch=getchar();while(ch!='\n'){if(ch>='0'&&ch<='9')vt.push_back(ch-'0');ch=getchar();}n=vt.size();do{a=0,b=0;if(n==2){a=vt[0];b=vt[1];}else{ if(vt[0]==0||vt[n/2]==0) continue;// 避免前导零 for(int k=0;k<n/2;k++) a=a*10+vt[k]; for(int k=n/2;k<vt.size();k++) b=b*10+vt[k];}if(abs(a-b)<ans) ans=abs(a-b);//	}}while(next_permutation(vt.begin(),vt.end()));printf("%d\n",ans);}return 0;
}

I-sort

思路

开个结构体，排序就能过的签到题，注意输出格式。

代码

#include<iostream> 
#include<cstring> 
#include<algorithm> 
using namespace std; struct X{ string x; int num;
}bl[11];bool cmp(X a,X b){return a.num>b.num;
}int main(){int n,t;scanf("%d",&t);while(t--){scanf("%d",&n);for(int i=1;i<=n;i++)cin>>bl[i].x>>bl[i].num;sort(bl+1,bl+n+1,cmp);for(int i=1;i<=n;i++){cout<<bl[i].x;if(i!=n) printf(" ");else printf("\n");}}return 0;
}

J-problem1

思路

坑比较多，首先有一个结论就算这个函数是收敛于 π 2 6 \frac{\pi^2}{6} 6π2​的，证明方法很多，感兴趣可以自行了解。所以我们要预处理1000000以内的数据；其次这个n可能整数型装不下，直接开字符串去存，如果大于7位数就直接输出收敛值就好了。

代码

#include<bits/stdc++.h>
#define rep(i,x,y) for(int i=x; i<=y; ++i)using namespace std;
const double pi=acos(-1);
double ans,f[1000007];
int n;
char s[1000005]; signed main(){memset(f,0,sizeof(f));for(int i=1;i<=1000000;i++){f[i]=f[i-1]+1.0/i/i;		}while(scanf("%s",s+1)!=EOF){n=strlen(s+1);int x=0;rep(i,1,n) x=min(1000000,x*10+s[i]-48);printf("%.5lf\n",f[x]);} return 0;
}

这篇关于【ACM练习记录】数据结构题型详解——2021JNU寒假训练营D1的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！


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

相关文章

Spring IOC的三种实现方式详解

Spring IOC的三种实现方式详解

《SpringIOC的三种实现方式详解》：本文主要介绍SpringIOC的三种实现方式,在Spring框架中,IOC通过依赖注入来实现,而依赖注入主要有三种实现方式,构造器注入、Setter注入... 目录1. 构造器注入（Cons编程tructor Injection）2. Setter注入（Setter
阅读更多...
Java中注解与元数据示例详解

Java中注解与元数据示例详解

《Java中注解与元数据示例详解》Java注解和元数据是编程中重要的概念,用于描述程序元素的属性和用途,：本文主要介绍Java中注解与元数据的相关资料,文中通过代码介绍的非常详细,需要的朋友可以参... 目录一、引言二、元数据的概念2.1 定义2.2 作用三、Java 注解的基础3.1 注解的定义3.2 内
阅读更多...
将sqlserver数据迁移到mysql的详细步骤记录

将sqlserver数据迁移到mysql的详细步骤记录

《将sqlserver数据迁移到mysql的详细步骤记录》：本文主要介绍将SQLServer数据迁移到MySQL的步骤,包括导出数据、转换数据格式和导入数据,通过示例和工具说明,帮助大家顺利完成... 目录前言一、导出SQL Server 数据二、转换数据格式为mysql兼容格式三、导入数据到MySQL数据
阅读更多...
JavaScript中的isTrusted属性及其应用场景详解

JavaScript中的isTrusted属性及其应用场景详解

《JavaScript中的isTrusted属性及其应用场景详解》在现代Web开发中,JavaScript是构建交互式应用的核心语言,随着前端技术的不断发展,开发者需要处理越来越多的复杂场景,例如事件... 目录引言一、问题背景二、isTrusted 属性的来源与作用1. isTrusted 的定义2. 为
阅读更多...
使用Python实现操作mongodb详解

使用Python实现操作mongodb详解

《使用Python实现操作mongodb详解》这篇文章主要为大家详细介绍了使用Python实现操作mongodb的相关知识,文中的示例代码讲解详细,感兴趣的小伙伴可以跟随小编一起学习一下... 目录一、示例二、常用指令三、遇到的问题一、示例from pymongo import MongoClientf
阅读更多...
关于rpc长连接与短连接的思考记录

关于rpc长连接与短连接的思考记录

《关于rpc长连接与短连接的思考记录》文章总结了RPC项目中长连接和短连接的处理方式,包括RPC和HTTP的长连接与短连接的区别、TCP的保活机制、客户端与服务器的连接模式及其利弊分析,文章强调了在实... 目录rpc项目中的长连接与短连接的思考什么是rpc项目中的长连接和短连接与tcp和http的长连接短
阅读更多...
一文详解Python中数据清洗与处理的常用方法

一文详解Python中数据清洗与处理的常用方法

《一文详解Python中数据清洗与处理的常用方法》在数据处理与分析过程中,缺失值、重复值、异常值等问题是常见的挑战,本文总结了多种数据清洗与处理方法,文中的示例代码简洁易懂,有需要的小伙伴可以参考下... 目录缺失值处理重复值处理异常值处理数据类型转换文本清洗数据分组统计数据分箱数据标准化在数据处理与分析过
阅读更多...
详解如何在React中执行条件渲染

详解如何在React中执行条件渲染

《详解如何在React中执行条件渲染》在现代Web开发中,React作为一种流行的JavaScript库,为开发者提供了一种高效构建用户界面的方式,条件渲染是React中的一个关键概念,本文将深入探讨... 目录引言什么是条件渲染？基础示例使用逻辑与运算符（&&）使用条件语句列表中的条件渲染总结引言在现代
阅读更多...
详解Vue如何使用xlsx库导出Excel文件

详解Vue如何使用xlsx库导出Excel文件

《详解Vue如何使用xlsx库导出Excel文件》第三方库xlsx提供了强大的功能来处理Excel文件,它可以简化导出Excel文件这个过程,本文将为大家详细介绍一下它的具体使用,需要的小伙伴可以了解... 目录1. 安装依赖2. 创建vue组件3. 解释代码在Vue.js项目中导出Excel文件，使用第三
阅读更多...
SQL注入漏洞扫描之sqlmap详解

SQL注入漏洞扫描之sqlmap详解

《SQL注入漏洞扫描之sqlmap详解》SQLMap是一款自动执行SQL注入的审计工具,支持多种SQL注入技术,包括布尔型盲注、时间型盲注、报错型注入、联合查询注入和堆叠查询注入... 目录what支持类型how---less-1为例1.检测网站是否存在sql注入漏洞的注入点2.列举可用数据库3.列举数据库
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2