단순 산 목록 예제 와 간단 한 DFS 예제

낙 곡: 간단 한 시 뮬 레이 션
P1056 시트
클릭 하여 제목 설명 보기
이 문 제 는 산 목록 의 사상 을 활용 하여 데 이 터 를 저장 하 였 다.
무엇이 산 목록 입 니까?
산 목록 (Hash table, 해시 표 라 고도 함) 은 키 (Key) 에 따라 메모리 저장 위치 에 직접 접근 하 는 데이터 구조 입 니 다.즉, 키 값 에 관 한 함 수 를 계산 하여 필요 한 조회 데 이 터 를 표 의 한 위치 에 비 추어 기록 에 접근 하 는 것 은 검색 속 도 를 가속 화 시킨다.이 맵 함 수 는 해시 함수 라 고 하고 기록 을 저장 하 는 배열 을 산 목록 이 라 고 합 니 다. -위 키 백과

키워드 가 k 이면 그 값 은 f (k) 의 저장 위치 에 저 장 됩 니 다.따라서 비교 하지 않 아 도 조사 한 기록 을 직접 얻 을 수 있다.이 대응 관계 f 를 해시 함수 라 고 부 르 고 이 사상 에 따라 만들어 진 표 는 산 목록 입 니 다.

#include
using namespace std;
struct  node{
	int guodao;
	int count;
};
node a[2500]={},b[2500]={};//   ，    0
inline int cmp2(node n1,node n2){
	return n1.guodao<n2.guodao; 
}
bool cmp(node x,node y)
{
	return x.count>y.count;
}
int main()
{
	int M,N,K,L,D;//       M N 
	cin>>M>>N>>K>>L>>D;//K     ，L     ；D      
	int cntl,cntk;
	int e=0,f=0;
	for(int i=0;i<D;i++)
	{
		int x1,x2,y1,y2;
		cin>>x1>>y1>>x2>>y2;	
		if(x1==x2)	//       ，            
		{
			cntl=(y1<y2)?y1:y2;
			b[cntl].guodao=cntl;//   cntl 
			b[cntl].count++;	
		}
		else if(y1==y2)	//       ，            
		{
			cntk=(x1<x2)?x1:x2;
			a[cntk].guodao=cntk; //   cntk 
			a[cntk].count++;
		}
	}
    //            
	sort(a,a+M,cmp);
	sort(b,b+N,cmp);
    //            
	sort(a,a+K,cmp2);
	sort(b,b+L,cmp2);
	for(int i=0;i<K;i++)
		cout<<a[i].guodao<<" ";	
	cout<<endl;
	for(int i=0;i<L;i++)
		cout<<b[i].guodao<<" ";	
	return 0;
}

P1540 기계 번역
클릭 하여 제목 상세 보기
문 제 를 보고 나 는 대열 이 생각 났 지만, 나 는 직접 배열 로 대열 을 모 의 했 고, STL 선수 들 이 직접 queue 를 사용 한 다 는 것 을 알 았 다.
다음은 이 두 가지 사상의 서로 다른 코드 입 니 다. STL 만세!
수 동 시 뮬 레이 션:

#include
using namespace std;

bool searchin(int num,int M,int m[])
{
	bool k=false;
	for(int i=0;i<M;i++)
	{
		if(num==m[i])
		{
			k=true;
			break;	
		}
	}
	return k;
}
int main()
{
	int cnt;//   
	int M,N;
	cin>>M>>N;
	int m[M],n[N];	
	memset(m,-1,sizeof(m));
	for(int i=0;i<N;i++)
	{
		cin>>n[i];
		if(!searchin(n[i],M,m))
		{
			cnt++;
			for(int j=1;j<M;j++)
				m[j-1]=m[j];
			m[M-1]=n[i];
		}
	}
	cout<<cnt;
	return 0;
}

STL：queque

#include
#include
#include
using namespace std;
queue<int>s;
int main()
{
	int m,word,count=0,f[1010]={0};
	cin >> m >> word;
	for(int i = 0; i<word; i++)
	{
		int x;
		cin>>x;
		if(f[x]==1)continue;	    
		else 
		{
			if(s.size()>=m)
			{
				f[s.front()]=0;
				s.pop();//    
	     	}
			s.push(x);//    
			f[x]=1;
			count++;	
		}
	}
	cout<<count; 
}

소 객 소 백월 경기 16
그 중에서 G 문 제 는 매우 간단 하지만 정밀도 에 대한 요구 가 매우 높다. 이에 PI 의 높 은 정밀도 표현 방식 을 적어 둔다.

double PI=4.0*atan(1.0)

또한 출력 형식 에서 흔히 볼 수 있 는 세 가지 방법

printf(“%.3lf”, a); //a 의 세 번 째 소 수 를 보류 하고 네 번 째 사사사오입

(int)a;//a 를 0 에 가 깝 게 정렬

ceil(a);floor(a);//위로 올 리 기;아래로 정렬 하기;이 두 함 수 는 모두 double

로 되 돌아 갑 니 다.
E. 소우 의 행렬
제목 설명:
가랑비×n 의 행렬, 출발점 은 (1, 1) 이 고 종점 은 (n, n) 이 며 아래로 또는 오른쪽으로 만 갈 수 있 으 며 매번 한 걸음 만 갈 수 있 습 니 다.행렬 에 점 마다 점 권 a i, j a 가 있 습 니 다.{i,j} ai,j​。 종점 까지 가 는 경로 가 얼마나 다른 점 권 과
입력 설명:
첫 번 째 줄 에 정수 n 을 입력 하 십시오.다음 n + 1 줄, 줄 당 n 개 수 는 a i, j a 를 나타 낸다.{i,j} ai,j​。
비고: 1 < = n < = 8, 0 < = a i, j a{i,j} ai,j​<=50
출력 설명:
모두 한 줄 로 수출 은 몇 가지 서로 다른 점 권 과.
예시 1:

  ：
2
1 5
2 4
  ：
2

설명:
(1, 1) → (2, 1) → (2, 2): 합 은 7 이다.(1, 1) → (1, 2) → (2, 2): 합 은 10 이다.
이것 은 전형 적 인 DFS 단순 문제 로 템 플 릿 을 직접 끼 워 넣 으 면 된다.
그 중 하 나 는 STL 의 set 용기 에 사용 되 었 다.
set (집합): 길 어 지 는 요소 서열 을 제어 하 는 대상 을 설명 합 니 다.정렬 된 데 이 터 를 포함 하고 있 습 니 다. 이 데이터 의 값 (value) 은 유일 해 야 합 니 다.
그래서 문제 에서 서로 다른 점 권 과 set 로 저장 하 는 것 이 편리 하고 유일한 지 판단 할 필요 가 없다.

#include
using namespace std;
long long a[MAXN][MAXN];
int n;
set<int> s;

void dfs(int x,int y,int sum){
    if(x==n && y==n){
        s.insert(sum);	//  （n,n）  sum    s
        return;
    }
    if(x+1<=n){
        dfs(x+1,y,sum+a[x+1][y]);//   
    }
    if(y+1<=n){
        dfs(x,y+1,sum+a[x][y+1]);//   
    }
}
 
int main() {
    cin>>n;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            cin>>a[i][j];	//    
        }
    }
    dfs(1,1,a[1][1]);	//    
    cout<<s.size()<<endl;//    s   
    return 0;
}

보충:
용기 (Container) 의 개념 은 템 플 릿 (template) 보다 일찍 나 타 났 다. 컴퓨터 과학 분야 의 중요 한 개념 이 었 으 나 여기 서 는 STL 과 혼합 되 었 다.
다음은 STL 에 나 오 는 7 가지 용기 입 니 다.

vector (벡터) - STL 의 표준 적 이 고 안전 한 배열.vector 의 "앞" 에 만 데 이 터 를 추가 할 수 있 습 니 다.

deque (양 끝 대기 열 double - ended quue) - 기능 적 으로 vector 와 비슷 하지만 앞 뒤 양쪽 에 데 이 터 를 추가 할 수 있 습 니 다.

list (목록) - 커서 는 한 번 에 한 걸음 만 이동 할 수 있 습 니 다.만약 에 링크 에 대해 잘 알 고 있다 면 STL 의 list 는 양 방향 링크 입 니 다.

set (집합) - 정렬 된 데 이 터 를 포함 합 니 다. 이 데이터 의 값 (value) 은 유일 해 야 합 니 다.

map (맵) - 정렬 된 이원 그룹의 집합 을 거 쳐 map 의 모든 요 소 는 두 개의 값 으로 구성 되 어 있 습 니 다. 그 중의 key (키 값, 하나의 map 의 키 값 은 유일한 것 이 어야 합 니 다) 는 정렬 이나 검색 할 때 사용 되 며, 그 값 은 용기 에서 다시 가 져 올 수 있 습 니 다.다른 값 은 이 요소 와 연 결 된 값 입 니 다.예 를 들 어 AR [43] = 'overripe' 처럼 데 이 터 를 찾 을 수 있 는 것 을 제외 하고 map 는 AR [banana] = 'overripe' 와 같은 방법 으로 데 이 터 를 찾 을 수 있다.그 중의 요소 정 보 를 얻 으 려 면 요소 의 전체 이름 을 입력 하면 쉽게 이 루어 질 수 있다.

multiset (다 중 집합) - 집합 (set) 과 비슷 하지만 그 중의 값 은 유일한 것 이 어야 합 니 다 (즉 중복 이 가능 합 니 다).

multimap (다 중 맵) - 맵 (map) 과 비슷 하지만 키 값 은 유일 해 야 합 니 다 (즉 중복 이 가능 합 니 다).