【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 Security基于数据库验证流程详解

Spring Security基于数据库验证流程详解

Spring Security 校验流程图 相关解释说明（认真看哦） AbstractAuthenticationProcessingFilter 抽象类 /*** 调用 #requiresAuthentication(HttpServletRequest, HttpServletResponse) 决定是否需要进行验证操作。* 如果需要验证，则会调用 #attemptAuthentica
阅读更多...
认识、理解、分类——acm之搜索

认识、理解、分类——acm之搜索

普通搜索方法有两种：1、广度优先搜索；2、深度优先搜索； 更多搜索方法： 3、双向广度优先搜索； 4、启发式搜索（包括A*算法等）； 搜索通常会用到的知识点：状态压缩（位压缩，利用hash思想压缩）。
阅读更多...
OpenHarmony鸿蒙开发（ Beta5.0）无感配网详解

OpenHarmony鸿蒙开发（ Beta5.0）无感配网详解

1、简介 无感配网是指在设备联网过程中无需输入热点相关账号信息，即可快速实现设备配网，是一种兼顾高效性、可靠性和安全性的配网方式。 2、配网原理 2.1 通信原理 手机和智能设备之间的信息传递，利用特有的NAN协议实现。利用手机和智能设备之间的WiFi 感知订阅、发布能力，实现了数字管家应用和设备之间的发现。在完成设备间的认证和响应后，即可发送相关配网数据。同时还支持与常规Sof
阅读更多...
【数据结构】——原来排序算法搞懂这些就行，轻松拿捏

【数据结构】——原来排序算法搞懂这些就行，轻松拿捏

前言：快速排序的实现最重要的是找基准值，下面让我们来了解如何实现找基准值 基准值的注释：在快排的过程中，每一次我们要取一个元素作为枢纽值，以这个数字来将序列划分为两部分。 在此我们采用三数取中法，也就是取左端、中间、右端三个数，然后进行排序，将中间数作为枢纽值。 快速排序实现主框架： //快速排序 void QuickSort(int* arr, int left, int rig
阅读更多...
6.1.数据结构-c/c++堆详解下篇（堆排序，TopK问题）

6.1.数据结构-c/c++堆详解下篇（堆排序，TopK问题）

上篇：6.1.数据结构-c/c++模拟实现堆上篇（向下，上调整算法，建堆，增删数据）-CSDN博客 本章重点 1.使用堆来完成堆排序 2.使用堆解决TopK问题 目录 一.堆排序 1.1 思路 1.2 代码 1.3 简单测试 二.TopK问题 2.1 思路(求最小)： 2.2 C语言代码（手写堆） 2.3 C++代码（使用优先级队列 priority_queue）
阅读更多...
K8S（Kubernetes）开源的容器编排平台安装步骤详解

K8S（Kubernetes）开源的容器编排平台安装步骤详解

K8S（Kubernetes）是一个开源的容器编排平台，用于自动化部署、扩展和管理容器化应用程序。以下是K8S容器编排平台的安装步骤、使用方式及特点的概述： 安装步骤： 安装Docker：K8S需要基于Docker来运行容器化应用程序。首先要在所有节点上安装Docker引擎。 安装Kubernetes Master：在集群中选择一台主机作为Master节点，安装K8S的控制平面组件，如AP
阅读更多...
Node.js学习记录（二）

Node.js学习记录（二）

目录 一、express 1、初识express 2、安装express 3、创建并启动web服务器 4、监听 GET&POST 请求、响应内容给客户端 5、获取URL中携带的查询参数 6、获取URL中动态参数 7、静态资源托管 二、工具nodemon 三、express路由 1、express中路由 2、路由的匹配 3、路由模块化 4、路由模块添加前缀 四、中间件
阅读更多...
RabbitMQ练习（AMQP 0-9-1 Overview）

RabbitMQ练习（AMQP 0-9-1 Overview）

1、What is AMQP 0-9-1 AMQP 0-9-1（高级消息队列协议）是一种网络协议，它允许遵从该协议的客户端（Publisher或者Consumer）应用程序与遵从该协议的消息中间件代理（Broker，如RabbitMQ）进行通信。 AMQP 0-9-1模型的核心概念包括消息发布者（producers/publisher）、消息（messages）、交换机（exchanges）、
阅读更多...
《数据结构（C语言版）第二版》第八章-排序（8.3-交换排序、8.4-选择排序）

《数据结构（C语言版）第二版》第八章-排序（8.3-交换排序、8.4-选择排序）

8.3 交换排序 8.3.1 冒泡排序 【算法特点】 (1) 稳定排序。 (2) 可用于链式存储结构。 (3) 移动记录次数较多，算法平均时间性能比直接插入排序差。当初始记录无序，n较大时， 此算法不宜采用。 #include <stdio.h>#include <stdlib.h>#define MAXSIZE 26typedef int KeyType;typedef char In
阅读更多...
嵌入式Openharmony系统构建与启动详解

嵌入式Openharmony系统构建与启动详解

大家好，今天主要给大家分享一下，如何构建Openharmony子系统以及系统的启动过程分解。 第一：OpenHarmony系统构建      首先熟悉一下，构建系统是一种自动化处理工具的集合，通过将源代码文件进行一系列处理，最终生成和用户可以使用的目标文件。这里的目标文件包括静态链接库文件、动态链接库文件、可执行文件、脚本文件、配置文件等。      我们在编写hellowor
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2