SOJ 2785_Binary Partitions
1791 단어 ACM_동적 기획
【분석】 사고방식 1: 완전 가방
【코드】
#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>
#include <set>
#include <map>
#include <algorithm>
#include <stack>
#include <queue>
#include <cmath>
#include<ctime>
using namespace std;
const int INF=0x3fffffff,maxn=1e5+40;
const int mod=1000000;
const int total=2000050;
int f[total];
int main (void)
{
int T,temp;
f[0]=1;
scanf("%d",&T);
for(int i=0;i<=20;i++)//2^20<total<2^21
for(int j=(1<<i);j<total;j++)
f[j]+=f[j-(1<<i)]%mod;
while(T--)
{
scanf("%d",&temp);
printf("%d
",f[temp]%mod);
}
}코드는 zoj에서 AC를 하는데 soj에서 계속 TLE를 해요. 오랫동안 고쳐서 겨우 AC를...슬그머니 울다
사고방식2: 다른 사람의 블로그를 보면 점차적인 사상을 사용할 수 있다. 이진수의 측면에서 어떤 수든 그의 앞의 수+1으로 표시할 수 있다. 그러나 이 수n이 짝수라면 그는 그의 절반 n/2로 표시할 수 있다. 곧 n/2가 한 자리를 왼쪽으로 옮길 것이다.
【코드】
#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>
#include <set>
#include <map>
#include <algorithm>
#include <stack>
#include <queue>
#include <cmath>
#include<ctime>
using namespace std;
const int INF=0x3fffffff,maxn=1e5+40;
const int mod=1000000;
const int total=2000050;
int f[total];
int main (void)
{
int T,num;
f[0]=1;
for(int i=0;i<total;i++)
{
if(i%2==0)
f[i]=(f[i/2]+f[i-1])%mod;
else
f[i]=f[i-1]%mod;
}
scanf("%d",&T);
while(T--)
{
scanf("%d",&num);
printf("%d
",f[num]);
}
}이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
UVA 1025_A Spy in the Metro[제의] (소자서) 한 사람이 플랫폼 1에서 출발하면 차를 타려면 시간 T에 플랫폼 n에 도착해야 한다. 플랫폼에서 차를 기다리는 시간이 가장 짧기 때문에 그녀는 두 방향의 열차를 타고 버스가 정차할 때 갈아타야 한...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
