21050148

UID: 47494, 注册于 2024-4-8 21:56:59, 最后登录于 2024-10-13 16:44:35, 目前离线.

解决了 2 道题目，RP: 4.2 (No. 4793)

个人简介

Dijkstra

#include<bits/stdc++.h>
using namespace std;
priority_queue<pair<int,int> >q;
int head[1000010],ver[1000010],edge[1000010],_next[1000010],dist[1000010],n,m,tot;
bool b[1000010];
void add(int x,int y,int z){
    ver[++tot]=z,edge[tot]=y,_next[tot]=head[x],head[x]=tot;
}void dijkstra(){
    for(int i=1;i<=n;++i)
        dist[i]=0x7fffffff;
    dist[1]=0;
    q.push(pair<int,int>(0,1));
    while(!q.empty()){
        int x=q.top().second;
        q.pop();
        if(b[x])continue;
        b[x]=true;
        for(int i=head[x];i;i=_next[i]){
            int y=edge[i];
            if(dist[y]>dist[x]+ver[i]){
                dist[y]=dist[x]+ver[i];
                if(!b[y])
                    q.push(pair<int,int>(-dist[y],y));
            }
        }
    }
}signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    cin>>n>>m;
    for(int i=1,x,y,z;i<=m;++i){
        cin>>x>>y>>z;
        add(x,y,z);
    }dijkstra();
    for(int i=1;i<=n;++i)
        cout<<dist[i]<<' ';
    cout<<'\n';
    return(0);
}

C++中map详解

map简介

map是STL的一个关联容器，以键值对存储的数据，其类型可以自己定义，每个关键字在map中只能出现一次，关键字不能修改，值可以修改；map同set、multiset、multimap（与map的差别仅在于multimap允许一个键对应多个值）内部数据结构都是红黑树，而java中的hashmap是以hash table实现的。所以map内部有序（自动排序，单词时按照字母序排序），查找时间复杂度为O(logn)。

map用法

1、头文件

#include<map>

2、定义

map<string,int> my_map;
也可以使用
typedef map<string,int> My_Map;
My_Map my_map;

3、基本方法

函数名	功能
my_map.insert()或按照数组直接赋值	插入
my_map.find()	擦查找一个元素
my_map.clear()	清空
my_map.erase()	删除一个元素
my_map.size()	map的长度大小
my_map.begin()	返回指向map头部的迭代器
my_map.end()	返回指向map末尾的迭代器
my_map.rbegin()	返回一个指向map尾部的逆向迭代器
my_map.rend()	返回一个指向map头部的逆向迭代器
my_map.empty()	map为空时返回true
swap()	交换两个map,两个map中所有元素都交换

显示详细信息

4、map插入数据的几种方法

第一种：用insert函数插入pair数据：
map<int,string> my_map;
my_map.insert(pair<int,string>(1,"first"));
my_map.insert(pair<int,string>(2,"second"));

第二种：用insert函数插入value_type数据：
map<int,string> my_map;
my_map.insert(map<int,string>::value_type(1,"first"));
my_map.insert(map<int,string>::value_type(2,"second"));

map<int,string>::iterator it;           //迭代器遍历
for(it=my_map.begin();it!=my_map.end();it++)
    cout<<it->first<<it->second<<endl;

第三种：用数组的方式直接赋值：
map<int,string> my_map;
my_map[1]="first";
my_map[2]="second";

map<int,string>::iterator it;
for(it=my_map.begin();it!=my_map.end();it++)
    cout<<it->first<<it->second<<endl;

5、查找元素（判定这个关键字是否在map中出现）

第一种：用count函数来判断关键字是否出现，其缺点是无法定位元素出现的位置。由于map一对一的映射关系，count函数的返回值要么是0，要么是1。

map<string,int> my_map;
my_map["first"]=1;
cout<<my_map.count("first")<<endl;    //输出1；

第二种：用find函数来定位元素出现的位置，它返回一个迭代器，当数据出现时，返回的是数据所在位置的迭代器；若map中没有要查找的数据，返回的迭代器等于end函数返回的迭代器。

#include <map>  
#include <string>  
#include <iostream>  

using namespace std;  

int main()  
{  
    map<int, string> my_map;  
    my_map.insert(pair<int, string>(1, "student_one"));  
    my_map.insert(pair<int, string>(2, "student_two"));  
    my_map.insert(pair<int, string>(3, "student_three"));  
    map<int, string>::iterator it;  
    it = my_map.find(1);  
    if(it != my_map.end())  
       cout<<"Find, the value is "<<it->second<<endl;      
    else  
       cout<<"Do not Find"<<endl;  
    return 0;  
}
//通过map对象的方法获取的iterator数据类型是一个std::pair对象，包括两个数据iterator->first和iterator->second，分别代表关键字和value值。

6、删除元素

#include <map>  
#include <string>  
#include <iostream>  

using namespace std;  

int main()  
{  
    map<int, string> my_map;  
    my_map.insert(pair<int, string>(1, "one"));  
    my_map.insert(pair<int, string>(2, "two"));  
    my_map.insert(pair<int, string>(3, "three"));  
    //如果你要演示输出效果，请选择以下的一种，你看到的效果会比较好
    //如果要删除1,用迭代器删除
    map<int, string>::iterator it;  
    it = my_map.find(1);  
    my_map.erase(it);                   //如果要删除1，用关键字删除
    int n = my_map.erase(1);            //如果删除了会返回1，否则返回0
    //用迭代器，成片的删除
    //一下代码把整个map清空
    my_map.erase( my_map.begin(), my_map.end() );  
    //成片删除要注意的是，也是STL的特性，删除区间是一个前闭后开的集合
    //自个加上遍历代码，打印输出吧
    return 0;
}

7、排序，按value排序

map中元素是自动按key升序排序（从小到大）的；按照value排序时，想直接使用sort函数是做不到的，sort函数只支持数组、vector、list、queue等的排序，无法对map排序，那么就需要把map放在vector中，再对vector进行排序。

#include <iostream>
#include <string>
#include <map>
#include <algorithm>
#include <vector>
using namespace std;

bool cmp(pair<string,int> a, pair<string,int> b) {
	return a.second < b.second;
}

int main()
{
    map<string, int> ma;
    ma["Alice"] = 86;
    ma["Bob"] = 78;
    ma["Zip"] = 92;
    ma["Stdevn"] = 88;
    vector< pair<string,int> > vec(ma.begin(),ma.end());
    //或者：
    //vector< pair<string,int> > vec;
    //for(map<string,int>::iterator it = ma.begin(); it != ma.end(); it++)
    //    vec.push_back( pair<string,int>(it->first,it->second) );

    sort(vec.begin(),vec.end(),cmp);
    for (vector< pair<string,int> >::iterator it = vec.begin(); it != vec.end(); ++it)
    {
        cout << it->first << " " << it->second << endl;
    }
    return 0;
}

from c++中map详解 (csdn.net)

SET用法

1、set的作用 set就是集合的意思，集合的特点就是不会出现重复的内容。一般用来作查重或去重操作，举个场景，给出一个表：

姓名	爱好
小明	打篮球
小刚	画画
小明	听音乐

问该表中出现了多少个人，学会了set，就可以很轻松地解决这个问题

2、set的定义 set<储存的类型> 容器名如：储存int型的值 set s; 储存double型的值 set s; 储存string型的值 set s; 储存结构体或者类的值的值 set<结构体名> s;

(1)set的一些基本的成员函数

//常用函数（必学）
insert()//插入元素
count()//判断容器中是否存在某个元素
size()//返回容器的尺寸，也可以元素的个数
erase()//删除集合中某个元素
clear()//清空集合
empty()//判断是否为空
begin()//返回第一个节点的迭代器
end()//返回最后一个节点加1的迭代器
rbegin()//反向迭代器
rend()//反向迭代器

//功能函数（进阶）
find()//查找某个指定元素的迭代器
lower_bound()//二分查找第一个不小于某个值的元素的迭代器
get_allocator()//返回集合的分配器
swap()//交换两个集合的变量
max_size()//返回集合能容纳元素的最大限值

代码：

#include<iostream>//c++标准头文件，可以使用cout,cin等标准编译用法
#include<set>//使用set需要带上这个文件
using namespace std;//命名空间，防止重名给程序带来各种隐患，使用cin,cout,map,set,vector,queue时都要使用
int main(){
	set<int> s;//定义 
	s.insert(1);//插入元素1 
	s.insert(3);//插入元素3
	s.insert(2);//插入元素2
	cout<<"现有的元素有"<<endl; 
	for(int c:s){//遍历set，注意set会将元素自动排序，插入的顺序是1、3、2，遍历的顺序是1、2、3 
		cout<<c<<' ';
	} 
	cout<<endl;
	cout<<endl;
	s.erase(3);//删除元素3
	
	cout<<"删除元素3后，现有的元素有"<<endl; 
	for(int c:s){//遍历set，注意set会将元素自动排序，插入的顺序是1、3、2，遍历的顺序是1、2、3 
		cout<<c<<' ';
	} 
	cout<<endl;
	cout<<endl;
	
	cout<<"现在s.size()=="; 
	cout<<s.size();
	cout<<",即有两个元素" ;
	cout<<endl;
	cout<<endl;
	
	cout<<"是否包含元素2:"<<endl;
	cout<<"s.count(2)=="<<s.count(2)<<"即包含元素2"; 
	cout<<endl;
	cout<<endl;
	cout<<"是否包含元素3:"<<endl;
	cout<<"s.count(3)=="<<s.count(3)<<"即不包含元素3"; 
	cout<<endl;
	cout<<endl;
	
	cout<<"s是否是空的:"<<endl;
	cout<<"s.empty()=="<<s.empty()<<"即s不为空"; 
	cout<<endl;
	cout<<endl;
	
	s.clear();//清空集合 
	
	cout<<"s是否是空的:"<<endl;
	cout<<"s.empty()=="<<s.empty()<<"即s是空的"; 
	cout<<endl;
	cout<<endl;
	
	
	cout<<"s是否是空的:"<<endl;
	cout<<"s.size()=="<<s.size()<<"即s是空的"; //s.size()==0也可以判断集合是否为空，为了考虑代码可读性，一般不用size()代替empty() 
	cout<<endl;
	cout<<endl;
}

运行结果：

现有的元素有
1 2 3

删除元素3后，现有的元素有
1 2

现在s.size()==2,即有两个元素

是否包含元素2:
s.count(2)==1即包含元素2

是否包含元素3:
s.count(3)==0即不包含元素3

s是否是空的:
s.empty()==0即s不为空

s是否是空的:
s.empty()==1即s是空的

s是否是空的:
s.size()==0即s是空的

3、set的两种遍历方法

(1)迭代器iterator 代码：

#include<iostream>
#include<set>
using namespace std;
int main(){
	set<int> s;//定义 
	s.insert(1);//插入元素1 
	s.insert(3);//插入元素3
	s.insert(2);//插入元素2
	set<int>::iterator it;//使用迭代器
	for(it=s.begin();it!=s.end();it++){
		cout<<*it<<' ';
	} 
}

运行结果：

1 2 3

set有一个很重要的特性，那就是自动升序排序，在很多场景可以方便使用，那么当需要降序排序的时候需要怎样呢？ 1、逆向思维从end()-1到begin()遍历就是降序的了

#include<iostream>
#include<set>
using namespace std;
int main(){
	set<int> s;//定义 
	s.insert(1);//插入元素1 
	s.insert(3);//插入元素3
	s.insert(2);//插入元素2
	set<int>::iterator it;//使用迭代器
	for(it=--s.end();it!=--s.begin();it--){
		cout<<*it<<' ';
	} 
}

运行结果：

3 2 1

2、rbegin()和rend() 逆向迭代器本来就是实现逆向迭代的功能的，下面看用法

#include<iostream>
#include<set>
using namespace std;
int main(){
	set<int> s;//定义 
	s.insert(1);//插入元素1 
	s.insert(3);//插入元素3
	s.insert(2);//插入元素2
	set<int>::reverse_iterator it;//使用反向迭代器
	for(it=s.rbegin();it!=s.rend();it++){
		cout<<*it<<' ';
	} 
}

运行结果：

3 2 1

(2)foreach遍历

#include<iostream>
#include<set>
using namespace std;
int main(){
	set<int> s;//定义 
	s.insert(1);//插入元素1 
	s.insert(3);//插入元素3
	s.insert(2);//插入元素2
	for(auto it:s){
		cout<<it<<' ';
	} 
}

运行结果：

1 2 3

这种写法简单易记，但是不能实现降序遍历

(#)用迭代器iterator来foreach遍历：

#include<iostream>
#include<set>
using namespace std;
int main(){
	set<int> s;//定义 
	s.insert(1);//插入元素1 
	s.insert(3);//插入元素3
	s.insert(2);//插入元素2
	for(auto it=s.begin();it!=s.end();it++){
		cout<<*it<<' ';
	} 
}

运行结果：

1 2 3

from c++ set用法入门必看超详细 (csdn.net)

火车头

#pragma GCC optimize(3)
#pragma GCC target("avx")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("inline")
#pragma GCC optimize("-fgcse")
#pragma GCC optimize("-fgcse-lm")
#pragma GCC optimize("-fipa-sra")
#pragma GCC optimize("-ftree-pre")
#pragma GCC optimize("-ftree-vrp")
#pragma GCC optimize("-fpeephole2")
#pragma GCC optimize("-ffast-math")
#pragma GCC optimize("-fsched-spec")
#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("-falign-jumps")
#pragma GCC optimize("-falign-loops")
#pragma GCC optimize("-falign-labels")
#pragma GCC optimize("-fdevirtualize")
#pragma GCC optimize("-fcaller-saves")
#pragma GCC optimize("-fcrossjumping")
#pragma GCC optimize("-fthread-jumps")
#pragma GCC optimize("-funroll-loops")
#pragma GCC optimize("-fwhole-program")
#pragma GCC optimize("-freorder-blocks")
#pragma GCC optimize("-fschedule-insns")
#pragma GCC optimize("inline-functions")
#pragma GCC optimize("-ftree-tail-merge")
#pragma GCC optimize("-fschedule-insns2")
#pragma GCC optimize("-fstrict-aliasing")
#pragma GCC optimize("-fstrict-overflow")
#pragma GCC optimize("-falign-functions")
#pragma GCC optimize("-fcse-skip-blocks")
#pragma GCC optimize("-fcse-follow-jumps")
#pragma GCC optimize("-fsched-interblock")
#pragma GCC optimize("-fpartial-inlining")
#pragma GCC optimize("no-stack-protector")
#pragma GCC optimize("-freorder-functions")
#pragma GCC optimize("-findirect-inlining")
#pragma GCC optimize("-fhoist-adjacent-loads")
#pragma GCC optimize("-frerun-cse-after-loop")
#pragma GCC optimize("inline-small-functions")
#pragma GCC optimize("-finline-small-functions")
#pragma GCC optimize("-ftree-switch-conversion")
#pragma GCC optimize("-foptimize-sibling-calls")
#pragma GCC optimize("-fexpensive-optimizations")
#pragma GCC optimize("-funsafe-loop-optimizations")
#pragma GCC optimize("inline-functions-called-once")
#pragma GCC optimize("-fdelete-null-pointer-checks")

ios::sync_with_stdio(0);
cin.tie(0);cout.tie(0);

Super GCD

#include<bits/stdc++.h>
#define maxn 10050
using namespace std;
const int mm=1e6;
char s[maxn];
struct num{
    int e[maxn];
    num(int x=0):e(){
        for(int i=x;i;i/=mm)
            e[++e[0]]=i%mm;
        if(!e[0])++e[0];
    }void read(){
        scanf("%s",&s);
        e[0]=1;
        for(int r=strlen(s)-1,l=0;r>=0;r=l-1){
            l=r-6+1;
            if(l<0)l=0;
            for(int i=l;i<=r;++i)
                e[e[0]]=e[e[0]]*10+s[i]-48;
            ++e[0];
        }--e[0];
    }void print(){
        while(e[0]&&!e[e[0]])--e[0];
        printf("%d",e[e[0]]);
        for(int i=e[0]-1;i>=1;--i)
            printf("%06d",e[i]);
        printf("\n");
    }
};num operator +(const num &a,const num &b){
    num c;
    c.e[0]=max(a.e[0],b.e[0]);
    for(int i=1;i<=c.e[0];++i)
        c.e[i]+=a.e[i]+b.e[i],
        c.e[i+1]+=c.e[i]/mm,
        c.e[i]%=mm;
    if(c.e[c.e[0]+1])++c.e[0];
    return(c);
}num operator -(const num &a,const num &b){
    num c;
    c.e[0]=max(a.e[0],b.e[0]);
    int jw=0;
    for(int i=1;i<=c.e[0];++i){
        c.e[i]=a.e[i]-b.e[i]-jw;
        if(c.e[0]<0)
            c.e[i]+=mm,jw=1;
        else jw=0;
    }while(c.e[0]>1&&!c.e[c.e[0]])
        --c.e[0];
    return(c);
}num operator *(const num &a,const num &b){
    num c;
    c.e[0]=a.e[0]+b.e[0];
    for(int i=1;i<=a.e[0];++i)
        for(int j=1;j<=b.e[0];++j)
            c.e[i+j-1]+=a.e[i]*b.e[j],
            c.e[i+j]+=c.e[i+j-1]/mm,
            c.e[i+j-1]%=mm;
    while(c.e[0]>1&&!c.e[c.e[0]])
        --c.e[0];
    return(c);
}num operator /(const num &a,int k){
    num c;
    c.e[0]=a.e[0];
    int x=0;
    for(int i=a.e[0];i>=1;--i){
        x=x*mm+a.e[i];
        c.e[i]=x/k;
        x%=k;
    }while(c.e[0]>1&&!c.e[c.e[0]])
        --c.e[0];
    return(c);
}bool operator < (const num &a,const num &b){
    if(a.e[0]!=b.e[0])
        return(a.e[0]<b.e[0]);
    for(int i=a.e[0];i>=1;--i)
        if(a.e[i]!=b.e[i])
            return(a.e[i]<b.e[i]);
    return 0;   
}bool operator > (const num &a,const num &b){
        return(b<a);
}num GCD(num a,num b){
    if(a<b)swap(a,b);
    int tt=0;
    while(b>0){
        if(a.e[1]%2==0&&b.e[1]%2==0)
            a=a/2,b=b/2,++tt;
        else if(a.e[1]%2==0&&b.e[1]%2!=0)
            a=a/2;
        else if(a.e[1]%2!=0&&b.e[1]%2==0)
            b=b/2;
        else a=(a-b)/2;
        if(a<b)swap(a,b);
    }
    for(int i=1;i<=tt;++i)
        a=a*2;
    return(a);
}num a,b;
int main(){
    // ios::sync_with_stdio(0);
    // cin.tie(0);cout.tie(0);
    a.read(),b.read();
    GCD(a,b).print();
    // num n;
    // n.read();
    // num l=1,r=n,mid,mid1;
    // while (l<r)
    // {
    //     mid=(l+r)/2;
    //     mid1=mid+1;
    //     if (mid1*mid1>n) r=mid;else l=mid1;
    // }
    // l.print();
    return(0);
}

通过的题目
H1000
H1032
最近活动

This person is lazy and didn't join any contests or homework.
最近编写的题解

This person is lazy and didn't write any solutions.
Stat
Rating

系统测试: 1
数学: 1
快速幂: 1

21050148

个人简介

Dijkstra

C++中map详解

map简介

map用法

SET用法

火车头

Super GCD

通过的题目

最近活动

最近编写的题解

Stat

Rating

题目标签

状态

开发

支持

21050148

个人简介

Dijkstra

C++中map详解

map简介

map用法

SET用法

火车头

Super GCD

通过的题目

最近活动

最近编写的题解

Stat

Rating

题目标签

状态

开发

支持

还没有账户？

登录