noip 아날로그 문제 소기 2 by hzwer [DP] [경로 압축] [분류 토론] [비트 연산]
이 문제는 2h밖에 안 봤는데 괜찮은 것 같아요. T2가 비슷한 걸 해봤기 때문에 A를 했어요. T1과 T3도 기본적으로 큰 문제가 없어요. 관건은 문제의 특징을 깊이 파헤치는 거예요.분류 토론(많은 문제에서 많은 가지를 잘라낼 수 있다. 예를 들어 T1, 샤오치1의 T3, noip2015 day1 T3는 이런 분류 의식이 필요하다. T1: 제목: 좌표축에 약간의 수익이 있다. 0부터 물어보면 매번 4(0+4=4)보 또는 7(0+7=7)보만 앞으로 뛸 수 있다. 최대 수익은.데이터 범위: 20%의 데이터 n=1, m<=10^5는 40%의 데이터 n<=15, m<=10^5는 60%의 데이터 m<=10^5는 100%의 데이터 n<=10^5, m<=10^9, 1<=ai<=10^4, 1<=bi<=m 분석: 이 문제가 데이터 배분(또는 무엇, 뭐라고 하는지 모르겠다)의 전형적인 예인 것 같아서 황 학장은 이 두 문제를 잘 냈다.20%n=1, 갈 수 있는지 없는지만 보면 돼요.60%의 데이터는 m가 비교적 작아서 f[i]로 i의 이 위치의 최대치를 나타낼 수 있다. 그러면 -4, -7의 최대치를 찾아가면 된다.100%, 분석 결과, >=18의 상황은 반드시 갈 수 있습니다!그러면 18 이내에 수조로 저장해서 갈 수 있는지, 18 이외에 모두 갈 수 있으며, 갈 때 18 이내의 최대치를 갱신하면 됩니다!다음은 잔소리입니다. 보지 않아도 됩니다. 관건은 >=18의 그 성질을 발견하는 것입니다. 이것은 우리가 여러 손으로 규칙을 찾아야 한다는 요구입니다.이치대로 말하면 발견>=18 이후 100점 알고리즘은 순조롭게 이루어져야 하는데 나는 뜻밖에도 발견하지 못했고 이런 의식을 기르지 못했다.그리고 이 문제를 시험할 때 너무 zz했어요. 왜냐하면 제 알고리즘은 40점일 거예요. 뒤에 20점을 어떻게 받을지 고민을 많이 했는데 그 결과 문제풀이 보고서를 받아서 생각이 났어요. m을 매거하면 시간 복잡도 선형...
60분 프로그램:
#includeint read()
{
int x=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
return x*f;
}
void init()
{
n=read();m=read();
each(i,n){
a[i].b=read();
a[i].a=read();
}
sort(a+1,a+n+1,cmp);
}
int boo[20]={1,0,0,0,1,0,0,1,1,0,0,1,1,0,1,1,1,0,1,1};
int check(int cur,int pre)
{
if(cur-pre>=18)return 1;
return boo[cur-pre];
}
void work()
{
for(int i=1;i<=n;i++){
int j=i-1;int flg=1;
for(;j>=0;j--)if(check(a[i].a,a[j].a))
f[i]=max(f[j]+a[i].b,f[i]);
ans=max(ans,f[i]);
}
printf("%d",ans);
}
void debug()
{
//
}
int main()
{
freopen("hop.in","r",stdin);
freopen("hop.out","w",stdout);
init();
work();
//debug();
return 0;
} 100점:
#includeint read()
{
int x=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
return x*f;
}
void init()
{
n=read();m=read();
each(i,n){
a[i].b=read();
a[i].a=read();
}
sort(a+1,a+n+1,cmp);
}
int boo[20]={1,0,0,0,1,0,0,1,1,0,0,1,1,0,1,1,1,0,1,1};
int check(int cur,int pre)
{
if(cur-pre>=18)return 1;
return boo[cur-pre];
}
void work()
{
for(int i=1;i<=n;i++){
int j=i-1;
for(;j>=max(0,i-17);j--)if(check(a[i].a,a[j].a))f[i]=max(f[j]+a[i].b,f[i]);
if(i>18)maxn=max(maxn,f[i-18]);
if(check(a[i].a,0))f[i]=max(f[i],maxn+a[i].b);
ans=max(ans,f[i]);
}
printf("%d",ans);
}
void debug()
{
//
}
int main()
{
freopen("hop.in","r",stdin);
freopen("hop.out","w",stdout);
init();
work();
//debug();
return 0;
} T2: 제목: 권한 행렬의 왼쪽 상단에서 오른쪽 하단(아래로 또는 오른쪽으로만 갈 수 있음)으로 가세요.Σn+m -3. 1i=1(Ai -3. Aavg) 2의 최소값.분석: 우선, 우리는 하나의 서열에 대해 평균치가 틀리면 V값이 반드시 더 작다는 것을 증명할 수 있다. (구체적으로 어떻게 증명합니까? 길이가 2인 서열을 고려하여 그것을 뜯어 보세요. 이것은 균일치 부등식이 아닙니까?)그리고 이 권한 범위 <=30을 보세요. 한눈에 이상한 짓을 할 수 있어요.최소 정밀도에 따라 평균치를 매거하면 된다.
#include
",ans/lim);
}
void debug()
{
//
}
int main()
{
freopen("matrix.in","r",stdin);
freopen("matrix.out","w",stdout);
t=read();
for(int i=1;i<=t;i++){
init();
work();
}
//debug();
return 0;
}T3: 제목: 한 그루의 나무에 대해 각 점에 대해 다른 점에서 이 점까지의 거리가 각각 다르거나 1치의 합을 구한다.분석: 사실은 다법도에서 발견할 수 있듯이 이 물건은 사실 마지막 몇 위의 01을 통계하여 해결할 수 있다.구체적인 실현은 0의 상황(즉 두 번의 dfs로 두 개의 그룹을 기록하는 것)을 처리하는 방법으로 01을 동시에 처리하면 된다는 것이다. 그러나 나는 당초에 너무 순진해서 폭력을 썼다.잔소리: 다fa도.폭력:(m!=0처리 잘못한 것 같아WA팀, 신에게 가르침을 구함)
#includevoid work()
{
if(m)
{
for(int i=1;i<=n;i++){
ans=0;dfs(i,0,0LL);
printf("%d
",ans);
}
}
else{
dfs2(1,0);
f[0]=f[1];dfs3(1,0);
for(int i=1;i<=n;i++)
printf("%d
",f[i]+g[i]);
}
}
void debug()
{
//
}
int main()
{
freopen("tree1.in","r",stdin);
freopen("tree1.out","w",stdout);
init();
work();
//debug();
return 0;
} 이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
백준 10844번 쉬운 계단 수 - node.js문제 설명 계단수: 인접한 모든 자리의 차이가 1인 수 (EX. 로직 설명 N = 2일 때 가능한 계단수를 생각해보자. 해당 숫자들을 보면 십의자리 숫자들은 일의자리 숫자가 무엇이 오는지에 따라 올 수 있는 단어들이...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
