STL (본 기교 와 용법 총화)

8585 단어
STL(Standard Template Library)
프로 그래 밍 경기 에서 가끔 은 특수 구조 로 해결 해 야 할 문제 에 부 딪 힐 수 있다. 이때 STL 라 이브 러 리 의 일부 데이터 구 조 를 유연 하 게 활용 하면 문제 의 해결 을 가속 화 할 수 있다. 여기 서 나 는 내 가 만난 응용 사례 를 써 서 STL 의 강 함 을 이해 하도록 도와 주 었 다.
이런 특수 한 구 조 는 많은 문 제 를 해결 할 수 있 지만 성능 이 떨 어 지고 일부 시간, 공간 성능 에 대한 요구 가 높 은 문제 에 적용 되 지 않 는 다.
목차
STL(Standard Template Library)
set
단어 수 HDOJ - 2072
map
Shopping HDOJ - 2648
Intelligent IME HDOJ - 4287
과일 HDOJ - 1263
우선 순위 대기 열  priority_queue
Windows Message Queue HDOJ - 1509
The kth great number HDOJ - 4006
set
간단 한 소개: 말하자면 하나의 요소 가 중복 되 지 않 는 용기 입 니 다. 예 를 들 어 용기 에 집합 {1, 1, 2} 을 넣 으 면 용기 에 {1, 2} 만 있 습 니 다. 즉, 이 안의 모든 요소 값 이 유일한 것 이 고 시스템 은 요소 의 값 에 따라 요 소 를 정렬 하지만 용기 안의 요소 값 은 직접 바 꿀 수 없습니다.
구체 적 으로 어떻게 사용 하 는 지: 관련 함수 와 그 사용 세부 사항 은 스스로 검색 하 세 요 ~ 이것들 은 여기 서 군말 하지 않 고 문제 와 해결 방법 만 넣 습 니 다.
 
단어 수 HDOJ - 2072
제목 링크
제목: 글 한 편 을 입력 하고 글 안의 단어 간 을 빈 칸 으로 구분 하 며 글 은 기호 '\ #' 로 끝나 고 글 안에 중복 되 지 않 는 단어 수 를 계산 하여 결 과 를 출력 합 니 다.
분석: set 용기 의 특징 을 이용 하여 글 의 모든 단 어 를 set 용기 에 저장 하고 끝 기 호 를 만 났 을 때 max 를 출력 합 니 다.size。
AC 코드:
//HDOJ - 2072
#include
#include
#include
#include
#include
using namespace std;
char s[1000000];
int main()
{
    while(gets(s))
    {
        setp;//set     ,         
        if(!strcmp(s,"#"))
            break;
        stringstream ss(s);
        string di;//
        while(ss>>di)//      , ss       di 
            p.insert(di);//    
        cout<

map
간단 한 소개: 하나의 맵 용기, 키 쌍 (key - value) 단위 로 요 소 를 저장 합 니 다. key 값 은 유일 해 야 합 니 다. value 값 은 중복 할 수 있 고 용기 가 자동 으로 정렬 되 는 특징 이 있 습 니 다.배열 로 이 해 를 돕 습 니 다. 배열 은 a [0] 로 배열 의 위치 0 요 소 를 얻 을 수 있 습 니 다. 이때 0 은 key 입 니 다. a [0] 는 value 입 니 다. 배열 과 map 가 다른 것 은 map 안의 key 는 다른 데이터 형식 으로 정의 할 수 있 습 니 다. 예 를 들 어 string 등 은 map 로 한 무리의 이름과 대응 하 는 나 이 를 저장 할 수 있 고 그들의 이름 을 통 해 연령 치 를 얻 을 수 있 습 니 다.
구체 적 으로 어떻게 사용 하 는 지: 관련 함수 와 그 사용 세부 사항 은 스스로 검색 하 세 요 ~ 이것들 은 여기 서 군말 하지 않 고 문제 와 해결 방법 만 넣 습 니 다.
 
Shopping HDOJ - 2648
제목 링크
제목: 처음에 n 개의 가게 이름 을 입력 한 다음 에 일 수 를 입력 하여 매일 memory 의 순 위 를 출력 하 라 고 요구 합 니 다 (큰 것 에서 작은 것 까지).
분석: 매일 집합 에 있 는 요소 () 를 옮 겨 다 니 며 memory 의 초기 rank 은 1 이다. memory 보다 가격 이 비 싼 가 게 를 만 났 을 때 rank + 1 은 모든 가 게 를 옮 겨 다 닌 후에 이때 rank 은 바로 이날 memory 의 순위 이다.
AC 코드:
//HDOJ - 2648
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
using namespace std;

mapmp;///     key,         
string name[10009];
int main()
{
    int n,m,num;
    while(cin>>n)
    {
        for(int i=0;i>name[i];
            mp[name[i]]=0;
            if(name[i]=="memory")
                num=i;///     ,       
        }
        cin>>m;
        while(m--)
        {
            string ss;
            int rank=1;
            int rise;
            for(int i=0;i>rise>>ss;
                mp[ss]+=rise;
            }
            for(int i=0;imp[name[num]]) /// memory  ,memory    +1
                   rank++;
            cout<

Intelligent IME HDOJ - 4287
제목 링크
제목: 입력 순서 와 사전 을 제시 하고 사전 에서 찾 은 일치 하 는 단어의 개 수 를 출력 해 야 합 니 다.
분석: 각 자모의 키보드 위 치 를 배열 ch 로 기록 한 다음 단 어 를 입력 할 때마다 해당 문자열 에 비 친 값 +, 최종 출력.
AC 코드:
//HDOJ - 4287
#include 
#include 
#include 
#include 
#define mod 10007
using namespace std;

char ch[30]={'2','2','2','3','3','3','4','4','4','5','5','5'
,'6','6','6','7','7','7','7','8','8','8','9','9','9','9'};
map ma;
string a[5050];

int main()
{
    int t,n,m;
    string s1,s2;
    cin>>t;
    while(t--)
    {
        cin>>n>>m;
        for(int i=0;i>s1;
            a[i]=s1;
            ma[s1]=0;
        }
        for(int i=0;i>s1;
            s2="";
            for(unsigned j=0;j

과일 HDOJ - 1263
제목 링크
제목: 한 조 의 데 이 터 를 제시 하고 각 줄 의 데 이 터 는 과일 이름, 과일 산지, 과일 판 매 량 을 포함 하 며 각 산지 의 각종 과일 판 매 량 을 수출 하도록 요구한다.
분석: 매 핑 관 계 는 지명 - > 과일 - > 판매 수량 입 니 다. 두 개의 맵 을 끼 워 서 이 루어 져 야 합 니 다. 한 줄 의 데 이 터 를 입력 할 때마다 맵 을 업데이트 하고 코드 를 구체 적 으로 볼 수 있 습 니 다.
AC 코드:
//HDOJ - 1263
#include
#include
#include
using namespace std;

struct MyStruct
{
	map MyStructma;  //              
};
int main()
{
	map ma;    //  
	map ::iterator it;
	map ::iterator MyStructmait;
	string fruit,place;
	int count;
    	int n,t;
	cin>>t;
	while(t--)
	{
		ma.clear();
		cin>>n;
		while(n--)
		{
			cin>>fruit>>place>>count;
			ma[place].MyStructma[fruit] += count;
		}
		for (it = ma.begin(); it != ma.end(); it++)
		{
			cout<first<second.MyStructma.begin(); MyStructmait != it->second.MyStructma.end(); MyStructmait++)
			{
				cout<first<second<

 
우선 순위 대기 열  priority_queue
간단 한 소개: 대열 의 가장 큰 요 소 는 항상 팀 의 첫 번 째 (기본 상황) 에 있 는 것 이 특징 입 니 다. 하나의 요 소 를 삽입 할 때마다 대열 이 조 정 됩 니 다.대기 열 안의 정렬 규칙 을 스스로 설정 할 수 있 습 니 다.
구체 적 으로 어떻게 사용 하 는 지: 관련 함수 와 그 사용 세부 사항 은 스스로 검색 하 세 요 ~ 이것들 은 여기 서 군말 하지 않 고 문제 와 해결 방법 만 넣 습 니 다.
 
Windows Message Queue HDOJ - 1509
제목: 일련의 GET 와 PUT 명령 을 입력 하여 출력 결 과 를 표시 해 야 합 니 다.명령 이 PUT 일 때 출력 이 없고 명령 이 GET 일 때 대기 열 이 비어 있 지 않 으 면 우선 순위 가 가장 높 은 메 시 지 를 가 져 와 출력 합 니 다. 대기 열 이 비어 있 으 면 'EMPTY QUEUE!' 를 표시 합 니 다.
분석: 입력 한 PUT 메시지 의 내용 을 우선 순위 로 정렬 하고, 순 위 는 우선 순위 와 시간 순서에 따라 우선 순위 가 일치 할 때, 시간 순 위 는 상위 순위 가 높 습 니 다.구체 적 으로 코드 참조.
AC 코드:
//HDOJ - 1509
#include 
#include 
#include 
#include 
#include 
#include 
#define mod 10007
using namespace std;

struct message
{
    string name;
    int val;
    int ran;
    int t;
    friend bool operator < (message m1,message m2)//          
    {
        if(m1.ran!=m2.ran)
            return m1.ran > m2.ran;
        else
            return m1.t>m2.t;
    }
};
int main()
{
    priority_queuem;
    string ope;
    int time=0;
    message mm;
    while(cin>>ope)
    {
        if(ope=="GET")
        {
            if(m.empty())
                printf("EMPTY QUEUE!
"); else { cout<>mm.name>>mm.val>>mm.ran; mm.t=++time; m.push(mm); } } return 0; }//MIC_H

The kth great number HDOJ - 4006
제목: n 과 k 를 입력 하면 다음 n 개의 동작 이 있 음 을 의미 합 니 다. I 작업 이 라면 대기 열 에 요 소 를 삽입 하 는 것 입 니 다. Q 작업 이 라면 k 번 째 큰 요 소 를 출력 하 는 것 입 니 다.
분석: 대기 열 에 최대 k 개의 요소 만 있 고 개 수 는 k 보다 적 으 면 대기 열 에 삽입 합 니 다. 만약 에 대기 열 요소 의 개수 가 k 라면 이때 삽입 하고 자 하 는 요소 가 대기 열 에 있 는 최소 값 (팀 꼬리 요소) 보다 큰 지 판단 합 니 다. 만약 에 크 면 팀 꼬리 요 소 를 삭제 하고 이 yuan 's 에 삽입 하면 팀 꼬리 는 k 번 째 큰 값 입 니 다.
AC 코드:
//HDOJ - 4006
#include 
#include 
#include 
#include 
#include 
#include 
#include 
using namespace std;

int main()
{
    int i,n,wro;
    unsigned k;
    char ope;
    while(cin>>n>>k)
    {
        priority_queue,greater >nn;
        for(i=0;i>ope;
            if(ope=='I')
            {
                cin>>wro;
                if(nn.size()

= = = = = = = 마지막 업데이트 시간: 2019.07.26 = = = = = = = = = =
= = = = = = =
= = = = 여러분, 번 번 이 지나 가 는데 문제 가 발견 되면 반 영 됩 니 다.  (「・ω・)「헤 이 = =

좋은 웹페이지 즐겨찾기