프로그래머 상호작용 연맹 코딩 대회 첫 번째 문제

1에서 N까지의 연속 정수로 구성된 집합을 두 개의 서브 집합으로 나누고 각 집합의 숫자와 같음을 보증한다.예를 들어 N=3에 대응하는 집합 {1,2,3}은 {3}과 {1,2} 두 개의 서브집합으로 나눌 수 있다.이 두 자 집합 중의 원소는 각각 과 같다.N=3에 대해 우리는 단지 하나의 구분 방법만 있을 뿐, N=7에 대해서는 4가지 구분 방안이 있을 것이다.입력은 N의 값(1≤ N ≤ 39)을 나타내는 정수로 한 줄을 포함합니다.출력은 한 줄을 포함하고, 단지 하나의 정수만 포함하며, 샤오맹은 N에 대응하는 집합의 방안의 개수를 구분할 수 있다.구분이 없을 때 0을 출력합니다.
입력: 7 출력: 4 프로그래머 상호작용 연맹은 위챗 신호로 괜찮고 제목도 어렵지 않다.분석: 이 문제는 폭력적으로 해결된 것이 분명하지만 이전에 문제를 잘못 봤어. 한참을 고민했는데 어이가 없어!사고방식도 간단하다. 바로 무작위로 평화를 구하는 것이다. 중복되지 않도록 순서대로 검색하면 된다!

#include<iostream>
#include<string>
#include<cstring>
#include<algorithm>
using namespace std;
int n,as=0;
int mark[300];
void dfs(int ans,int sm,int k)//sum   ，sm        k        
{
    if(sm>ans)
    return;
    if(ans==sm) 
    {
        as++;
        return ;
    }
    for(int i=k+1;i<=n;i++)
    {
        if(!mark[i])
        {
        mark[i]=i;
        dfs(ans,sm+i,i);
        mark[i]=0;
        }
    }
}

int main()
{
    memset(mark,0,sizeof(mark));
    while(cin>>n)
    {
        int sum=(1+n)*n/2;//n    
        sum/=2;
    dfs(sum,0,0);
    cout<<as/2<<endl;//    ，         
    }
    return 0;
 }

이 내용에 흥미가 있습니까?

현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:

정렬이 원본 비교를 지원하지 않는 대상

너는 같은 유형의 대상을 정렬하고 싶지만, 그들은 원생의 비교 조작을 지원하지 않는다. 내장된sorted () 함수에는 키워드 매개 변수 키가 있습니다.callable 대상을 전송할 수 있습니다. 이callable ...

텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.

CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.

프로그래머 상호작용 연맹 코딩 대회 첫 번째 문제

좋은 웹페이지 즐겨찾기