HDU - Tricks in Bits YY 문제

5737 단어 HDU
이 문 제 는 처음부터 DP 구 해 를 생각 했 지만 곰 곰 이 생각해 보 는 것 은 옳지 않다. 왜냐하면 이런 비트 조작 은 마지막 계산 이 없 을 때 가장 좋 은 해 를 얻 을 수 없고 가장 좋 은 서브 구조 도 존재 하지 않 기 때문이다.
먼저 a 와 b 가 연산 을 할 때 우 리 는 64 비트 의 모든 사람 을 분석 합 니 다. 우 리 는 & 와 ^ 작업 이 항상 0 을 만 들 수 있다 는 것 을 알 고 있 습 니 다. 그러면 두 64 의 숫자 에 있어 우 리 는 적어도 32 비트 를 0 과 같 게 할 수 있 습 니 다. 그리고 이 숫자 x 와 c 를 연산 하면 우 리 는 x & c 를 직접 합 니 다. 0 이 된 자 리 는 반드시 0 이 고 나머지 자 리 는 0 이 아니면 1 입 니 다.만약 결과 에서 1 대 0 이 많 으 면 우 리 는 c 에 대해 반 대 를 취한 다. 어차피 절반 은 0 이 되 고 6 개 를 넘 으 면 이 수 는 0 이 될 것 이다.0 이하 의 상황 에 대해 우 리 는 직접 폭력 을 행사 할 것 이다.
코드 는 다음 과 같 습 니 다:
#include <cstdlib>

#include <cstring>

#include <cstdio>

#include <algorithm>

using namespace std;



typedef unsigned long long int Int64;



int N;



Int64 seq[10], ret;



void dfs(Int64 statu, int deep)

{

    if (deep == N) {

        ret = min(statu, ret);

        return;

    }

    if (deep == 0) {

        dfs(seq[deep+1], deep+1);

        dfs(~seq[deep+1], deep+1);

    }

    else {

        dfs(statu & seq[deep+1], deep+1);

        dfs(statu | seq[deep+1], deep+1);

        dfs(statu ^ seq[deep+1], deep+1);

        dfs(statu & (~seq[deep+1]), deep+1);

        dfs(statu | (~seq[deep+1]), deep+1);

        dfs(statu ^ (~seq[deep+1]), deep+1);

    }

}



int main()

{

    int T, ca = 0;

    Int64 x;

    scanf("%d", &T);

    while (T--) {

        scanf("%d", &N);

        if (N > 6) {

            for (int i = 0; i < N; ++i) {

                scanf("%I64u", &x);    

            }

            printf("Case #%d: %I64u
", ++ca, 0LLU); continue; } ret = 1LLU<<63; for (int i = 1; i <= N; ++i) { scanf("%I64u", &seq[i]); } dfs(0, 0); printf("Case #%d: %I64u
", ++ca, ret); } return 0; }

좋은 웹페이지 즐겨찾기