【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。

相关文章

Python中的魔术方法__new__详解

Python中的魔术方法__new__详解

《Python中的魔术方法__new__详解》：本文主要介绍Python中的魔术方法__new__的使用,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录一、核心意义与机制1.1 构造过程原理1.2 与 __init__ 对比二、核心功能解析2.1 核心能力2.2
阅读更多...
在PyCharm中安装PyTorch、torchvision和OpenCV详解

在PyCharm中安装PyTorch、torchvision和OpenCV详解

《在PyCharm中安装PyTorch、torchvision和OpenCV详解》：本文主要介绍在PyCharm中安装PyTorch、torchvision和OpenCV方式,具有很好的参考价值,... 目录PyCharm安装PyTorch、torchvision和OpenCV安装python安装PyTor
阅读更多...
SpringBoot条件注解核心作用与使用场景详解

SpringBoot条件注解核心作用与使用场景详解

《SpringBoot条件注解核心作用与使用场景详解》SpringBoot的条件注解为开发者提供了强大的动态配置能力,理解其原理和适用场景是构建灵活、可扩展应用的关键,本文将系统梳理所有常用的条件注... 目录引言一、条件注解的核心机制二、SpringBoot内置条件注解详解1、@ConditionalOn
阅读更多...
MySQL 中查询 VARCHAR 类型 JSON 数据的问题记录

MySQL 中查询 VARCHAR 类型 JSON 数据的问题记录

《MySQL中查询VARCHAR类型JSON数据的问题记录》在数据库设计中,有时我们会将JSON数据存储在VARCHAR或TEXT类型字段中,本文将详细介绍如何在MySQL中有效查询存储为V... 目录一、问题背景二、mysql jsON 函数2.1 常用 JSON 函数三、查询示例3.1 基本查询3.2
阅读更多...
Qt spdlog日志模块的使用详解

Qt spdlog日志模块的使用详解

《Qtspdlog日志模块的使用详解》在Qt应用程序开发中,良好的日志系统至关重要,本文将介绍如何使用spdlog1.5.0创建满足以下要求的日志系统,感兴趣的朋友一起看看吧... 目录版本摘要例子logmanager.cpp文件main.cpp文件版本spdlog版本：1.5.0采用1.5.0版本主要
阅读更多...
Linux ls命令操作详解

Linux ls命令操作详解

《Linuxls命令操作详解》通过ls命令,我们可以查看指定目录下的文件和子目录,并结合不同的选项获取详细的文件信息,如权限、大小、修改时间等,：本文主要介绍Linuxls命令详解,需要的朋友可... 目录1. 命令简介2. 命令的基本语法和用法2.1 语法格式2.2 使用示例2.2.1 列出当前目录下的文
阅读更多...
MySQL中的交叉连接、自然连接和内连接查询详解

MySQL中的交叉连接、自然连接和内连接查询详解

《MySQL中的交叉连接、自然连接和内连接查询详解》：本文主要介绍MySQL中的交叉连接、自然连接和内连接查询,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录一、引入二、交php叉连接（cross join）三、自然连接（naturalandroid join）四
阅读更多...
Go 语言中的select语句详解及工作原理

Go 语言中的select语句详解及工作原理

《Go语言中的select语句详解及工作原理》在Go语言中,select语句是用于处理多个通道（channel）操作的一种控制结构,它类似于switch语句,本文给大家介绍Go语言中的select语... 目录Go 语言中的 select 是做什么的基本功能语法工作原理示例示例 1：监听多个通道示例 2：带
阅读更多...
mysql的基础语句和外键查询及其语句详解(推荐)

mysql的基础语句和外键查询及其语句详解(推荐)

《mysql的基础语句和外键查询及其语句详解(推荐)》：本文主要介绍mysql的基础语句和外键查询及其语句详解(推荐),本文给大家介绍的非常详细,对大家的学习或工作具有一定的参考借鉴价值,需要的朋... 目录一、mysql 基础语句1. 数据库操作 创建数据库2. 表操作 创建表3. CRUD 操作二、外键
阅读更多...
Spring Boot项目部署命令java -jar的各种参数及作用详解

Spring Boot项目部署命令java -jar的各种参数及作用详解

《SpringBoot项目部署命令java-jar的各种参数及作用详解》：本文主要介绍SpringBoot项目部署命令java-jar的各种参数及作用的相关资料,包括设置内存大小、垃圾回收... 目录前言一、基础命令结构二、常见的 Java 命令参数1. 设置内存大小2. 配置垃圾回收器3. 配置线程栈大小
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2