poj1840 - Eqs

2151 단어
문제 의 대의: 5 개의 매개 변 수 를 a1 에서 a5 까지 제시 한 다음 에 하나의 방정식 a1x 1 ^ 3 + a2x 2 ^ 3 + a3x 3 ^ 3 + a4x 4 ^ 3 + a5x 5 ^ 3 = 0 을 풀 어 5 개의 풀이 (x1, x2, x3, x4, x5) 를 풀 게 한 다음 에 몇 개의 풀이 가 있 는 지 물 어 본 다음 에 xi 와 ai 의 범 위 는 모두 '[- 50, 50] 이 고 0 문제 풀이 방향 과 같 지 않다. 먼저 폭력 알고리즘 을 사용 하면 각 x 를 - 50 에서 50 으로 순환 한 다음 에 0 과 같 는 지 판단 한다.그리고 100 ^ 5, 1000 W 회 연산, 시간 초과.
그리고 연산 의 복잡 도 를 낮 추 려 고 노력 하면 차방 을 줄 일 수 있 지 않 을 까?방정식 을 - (a1x1 ^ 3 + a2x2 ^ 3) = a3x 3 ^ 3 + a4x 4 ^ 3 + a5x 5 ^ 3 이렇게 최대 연산 은 100 ^ 3 이 고 10W 회 연산 은 좌우 방정식 의 일치 여 부 를 비교 하면 됩 니 다.
물론 판단 이 같 더 라 도 하나의 배열 을 열 어 보존 해 야 한다. 예 를 들 어 1 * 3 + 2 * 1 과 1 * 1 + 2 * 2 는 같 지만 2 이다.
종 해그래서 결과 가 5 인 횟수 가 얼마 인지 기록 하고 배열 hash [] 를 엽 니 다. 이 럴 때 hash [5] = 2 배열 의 최대 열 림 (50 * 50 ^ 3 + 50 * 50 ^ 3) * 2 = 25000000 을 기록 합 니 다. 음 수 를 고려 하여 12500000 을 0 으로 하면 몇 개의 해 를 구 할 수 있 습 니 다. 마지막 으로 hash 배열 을 열 때 short 를 사용 하지 않 아 도 메모리 가 초 과 됩 니 다.
#include <iostream>
using namespace std;
#define MAXV 25000000
int x1,x2,x3,x4,x5;

short int hash[MAXV + 1];			//hash  

int main(){
	int a,b,c,d,e;
	int sum ,ans;

	while(cin>>a>>b>>c>>d>>e){
		memset(hash,0,sizeof(hash));		//   

		for(x1 = -50;x1 <= 50;x1++){			//         
			if(x1 == 0) continue;
			for(x2 = -50;x2 <= 50;x2++){
				if(x2 == 0) continue;
				
				sum = -(x1*x1*x1*a + x2*x2*x2*b);
				sum += MAXV/2;			//        
				hash[sum]++;			//    
			}
		}

		ans = 0;

		for(x3 = -50;x3 <= 50;x3++){
			if(x3 == 0) continue;
			for(x4 = -50;x4 <= 50;x4++){
				if(x4 == 0) continue;
				
				for(x5 = -50;x5 <= 50;x5++){
					if(x5 == 0) continue;

					sum = x3*x3*x3*c + x4*x4*x4*d + x5*x5*x5*e;
					sum += MAXV/2;			//        
					if(sum < 0 || sum >= MAXV) continue;		//                

					if(hash[sum]){
						ans+=hash[sum];		//    
					}
				}
			}
		}

		cout<<ans<<endl;
	}
	return 0;
}
검지 Offer 43. 1 ~ n 정수 중 1 이 나타 나 는 횟수 (수학)
Codeforces Round #308(Div.2)--D(사비테마)

좋은 웹페이지 즐겨찾기

개발자 우수 사이트 수집

개발자가 알아야 할 필수 사이트 100선 추천 우리는 당신을 위해 100개의 자주 사용하는 개발자 학습 사이트를 정리했습니다
best100-homepage