概述
NEUQ-ACM预备队第一次双周赛
学习priority_queue
priority_queue 又称为优先队列，其底层是用堆来进行实现的。在优先队列中，队首元素一定是当前队列中优先级最高的那一个。
可以在任何时候往优先队列里面加入元素，而优先队列底层的数据结构堆（heap）会随时调整结构，使得每次的队首元素都是优先级最高的
priority_queue的常见用途：
priority_queue 可以解决一些贪心问题，也可以对 Dijkstra 算法进行优化。
需要要注意使用 top() 函数之前，必须用 empty() 判断优先队列是否为空。
1.1 基本用法
**和队列不同的是优先队列没有 front()函数与back()函数，而*只能通过 top() 函数来访问队首*元素（也称堆顶元素），也就是优先级最高的元素
基本用法:push(), top() ,pop(), empty(), q.size()
priority_queue<int> q;
q.push(3); //入队
q.push(5);
q.push(1);
cout<<q.top()<<endl; //获取队首元素
q.pop(); //令队首元素出队
cout<<q.top()<<endl;
if(q.empty())
{
cout<<"Empty"<<endl;
}
else
{
cout<<"Not empty"<<endl;
}
cout<<q.size()<<endl;
1.2 优先级设置
1）基本数据类型的优先级设置：（即可以直接使用的数据类型），优先队列对他们的优先级设置一般是数字越大的优先级越高，因此队首是优先级最大的那个（如果是 char 类型，则是字典序最大的）。以 int 型为例下面两种是等价的：
priority_queueq;
priority_queue<int,vector,less >q;
可以发现第二种定义方式的尖括号内多出了两个参数：其中 vector填写的是承载底层数据结构堆 （heap）的容器，如果是其他类型 可写为 vector或vector;
第三个参数 less 则是对第一个参数的比较类，！！less 表示数字大的优先级越大，而 greater 表示数字小的优先级越大。
1. Lily
签到题(也是唯一做出来的题555)
比较简单,模拟,遍历判断即可
#include<bits/stdc++.h>
using namespace std;
const int N =1005;
int a[N];
int main()
{
int len;cin>>len;
string s;cin>>s;
for(int i=0;i<=s.size();i++)
{
if(s[i]=='L') a[i]=1;
}
for(int i=0;i<=s.size();i++)
{
if(a[i-1]!=1&&a[i]!=1&&a[i+1]!=1) s[i]='C';
}
cout<<s;
return 0;
}
2. a*b
转进制加高精乘
还是不太熟练,考试时没做出来
后来看还是挺简单的
#include<bits/stdc++.h>
using namespace std;
const int N=2005;
int a[N],b[N],c[N];//分别存a,b和结果
int main(){
//学到了hhhh确实不太难,但没想到
string x,y;cin>>x>>y;
//1. 转进制
for(int i=x.size()-1,j=1;i>=0;i--,j++)
{
if(x[i]>='0'&&x[i]<='9') a[j]+=x[i]-'0';
else {
switch(x[i]){
case'A':a[j]+=10;break;
case'B':a[j]+=11;break;
case'C':a[j]+=12;break;
case'D':a[j]+=13;break;
case'E':a[j]+=14;break;
case'F':a[j]+=15;break;
}
}
}
for(int i=y.size()-1,j=1;i>=0;i--,j++)
{
if(y[i]>='0'&&y[i]<='9') b[j]+=y[i]-'0';
else {
switch(y[i]){
case'A':b[j]+=10;break;
case'B':b[j]+=11;break;
case'C':b[j]+=12;break;
case'D':b[j]+=13;break;
case'E':b[j]+=14;break;
case'F':b[j]+=15;break;
}
}
}
//2. 先乘再进位再换进制
int len=x.size()+y.size();
for(int i=1;i<=x.size();i++)
{
for(int j=1;j<=y.size();j++){
c[i+j-1]+=a[i]*b[j];
}
}//乘
for(int i=1;i<=len;i++)
{
c[i+1]+=c[i]/16;
c[i]%=16;
} //每16进1
for(;!c[len];) len--;//去0
for(int i=max(len,1);i>=1;i--){
if(c[i]>=0&&c[i]<=9) cout<<c[i];
else
{
switch(c[i])
{
case 10:cout<<'A';break;
case 11:cout<<'B';break;
case 12:cout<<'C';break;
case 13:cout<<'D';break;
case 14:cout<<'E';break;
case 15:cout<<'F';break;//再转回16进制
}
}
}
return 0;
}
3. 山头攻防战
模拟题:二分算法,优先队列(解决了最近的敌人的问题)
学到了一种极妙的解法…(思路真的不错)
#include<bits/stdc++.h>
int n,m,ans,a[2005];
using namespace std;
priority_queue<int,vector<int>,greater<int> >q;
void remake(){
while(!q.empty()) q.pop(); //清空
for(int i=0;i<n;i++) q.push(a[i]); //重新进入
}
bool ok(int t){
int time_sum=0; //时间积累变量
while(1)
{
if(q.empty()) return 1;
int tmp=q.top();//取出离小明最近的敌人
q.pop();
tmp=tmp-time_sum;//初始距离减去经过的时间即当前距离
if(tmp>m) time_sum+=tmp-m;
if(tmp<0) return 0;
time_sum+=t;
}
}
int main(){
cin>>n>>m;
for(int i=0;i<n;i++) cin>>a[i];
remake();
int L=1,R=1e5;
while(R>L) //二分查找答案,降低复杂度
{
int mid=(R+L)/2;
if(ok(mid)) L=mid+1,ans=mid;
else R=mid-1;
remake();//每次测试完,用remake优先排列
}
cout<<ans;
return 0;
}
5.一元二次方程(加强版)
数据较强,引入求导,用极限划分三个区间,再二分.
注意事项写在了注释里
#include<bits/stdc++.h>
using namespace std;
#define lim 1e-6
double a,b,c,d,p,q,T,x1,x2,middle;
double f(double x) {
return a*x*x*x+b*x*x+c*x+d;//简便写法,避免重复写公式
}
double func(double x,double y){
double L=x,R=y;
while(fabs(f(L)-f(R))>=lim)
{
middle=(R+L)/2.0;
if(f(middle)*f(L)<0) R=middle;//零点存在定理
else L=middle;
}
return R;
}
int main(){
cin>>T;
while(T--)//T组数据
{
cin>>a>>b>>c>>d>>p>>q;
x1=(-2.0*b-sqrt(4*b*b-12*a*c))/(6*a);//求导找两个极值点,划分三个区间
x2=(-2.0*b+sqrt(4*b*b-12*a*c))/(6*a);
if(x1>x2) swap(x1,x2);//确保区间顺序
cout<<fixed<<setprecision(6)<<func(p,x1)<<" "<<func(x1,x2)<<" "<<func(x2,q)<<endl;
}
return 0;
}
malloc学习
void * malloc (size_t size); //size 为开辟的空间的字节大小 为保证可移植性使用sizeof
这个函数向内存申请一块连续可用的空间，并返回指向这块空间的指针。
1.申请空间时，强转返回值类型
2.申请空间后，判空操作
3.不要对指针指向位置进行操作，预防释放空间错误
4.使用完成后回收空间
使用示例:
#include<stdio.h>
#include<stdlib.h>
int main()
{
int n=10;
int *ar=(int*)malloc(sizeof(int)*n); //在堆区开辟十个int型空间
if(ar==NULL) //判空操作
{
printf("空间申请失败！");
return ;
}
for(int i=0;i<n;i++)
{
ar[i]=i; //*(ar+i)=i ,前者可读性高
}
for(int i=0;i<n;i++)
{
printf("%d ",ar[i]);
}
printf("n");
free(ar); //释放空间
ar=NULL;
return 0;
}
最后
以上就是醉熏蚂蚁为你收集整理的NEUQ-ACM预备队第一次双周赛的全部内容，希望文章能够帮你解决NEUQ-ACM预备队第一次双周赛所遇到的程序开发问题。
如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。
发表评论 取消回复