HDU 1729 Stone Game
사고: 먼저 조금 큰 숫자 를 골 라 서 각 점 의 SG 상 태 를 인쇄 한 다음 에 규칙 을 찾 습 니 다. 이 문 제 는 i * i + i > = s 를 만족 시 키 는 첫 번 째 점 에 도착 하면 SG 값 은 (s - i) 입 니 다. 그러면 c > = k (k 는 첫 번 째 로 i * i > = s 를 만족 시 킬 때 SG 값 을 빨리 판단 할 수 있 습 니 다.c < k 시, 나 는 앞으로 c 의 SG 값 으로 밀어 넣 는 것 을 사용 합 니 다. k 가 최대 1000 을 얻 을 수 있 기 때문에 이렇게 하면 시간 을 초과 하지 않 습 니 다.제 가 쓴 특별한 점 이 있 습 니 다. 바로 c < k 시 SG 값 을 찾 을 때 i + j > = k 시 에 바로 break 를 하 는 것 입 니 다. 왜냐하면 > = k 시의 SG 값 은 모두 크 고 점점 줄 어 들 기 때 문 입 니 다. 마지막 으로 SG [s] 가 0 이라는 것 을 알 고 규칙 을 찾 을 때 도 쉽게 알 수 있 습 니 다. 첫 번 째 로 i * i + i > = s 의 SG 값 이 0 이 라 고 생각 하면 제 가 왜 그 랬 는 지 알 수 있 습 니 다. 코드 를 보 세 요.참, 두 개의 특 판 점 이 있 습 니 다. s = = c | c = = 0 시 에 바로 contine 하면 됩 니 다. 이 상 태 는 이 상자 가 없 는 것 과 같 기 때 문 입 니 다.
#include
#include
#include
#include
#include
using namespace std;
int SG[10005], mex[10005];
int c, s, k;
void getSG(){
int i, j;
for(i = k-1; i >= c; --i){
memset(mex, 0, sizeof mex);
for(j = 1; j <= i*i; ++j){
if(i+j >= k) break;
mex[SG[i+j]] = 1;
}
for(j = 0;; ++j) if(!mex[j]) break;
SG[i] = j;
}
}
int main(){
int n, ans, count = 0;
while(cin >> n && n){
ans = 0;
while(n--){
cin >> s >> c;
if(c == s || c == 0) continue;
k = sqrt(s);
for(; k <= s; ++k) if(k*k+k >= s) break;
if(k <= c) {
ans ^= (s-c);
continue;
}
getSG();
ans ^= SG[c];
}
printf("Case %d:
", ++count);
if(ans) cout << "Yes" << endl;
else cout << "No" << endl;
}
return 0;
} 계속 파 이 팅 ~
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
[오라 함수] HDOJ 2824 The Euler function텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
