Codeforces Round #697(Div. 3)(Unrated for Div. 3) 전체 문제 해결
60040 단어 Codeforces
문서 목록
A.Odd Divisor
수론 제목은 n에 기수인자가 있는지 없는지를 판단하는 것이다.유일한 분해 정리를 고려하면 n의 모든 질인자 중 2만 짝수이고 n의 질인자가 2만 포함하는 정정수 차멱을 제외하고 나머지 n은 모두 판정 조건에 부합된다.
#include
");
else{
while(n>1&&n%2==0) n>>=1;
if(n>1) printf("YES
");
else printf("NO
");
}
}
return 0;
}
B.New Year’s Number
수학 문제풀이는 n이 2020과 2021의 몇 개의 합으로 분해될 수 있는지를 판단해야 한다.2021은 2020+1으로 n/2020과 n%2020의 결과를 계산한 결과 n/2020은 n이 분해할 수 있는 2020의 개수이고 n%2020은 n이 분해된 후 남은 수이며 n%2020이 n/2020보다 작으면 더 많은 n%2020을 평균적으로 2020에 분배하여 2021을 구성하고 조건을 만족시킬 수 있으며 n%2020이 n/2020보다 크면 조건에 부합되지 않는다.
#include
");
else printf("NO
");
}
return 0;
}
C.Ball in Berland
수학 문제는 두 쌍의 조합을 선택해야 하며, 한 사람이 두 조에 동시에 있을 수 없으며, 실행 가능한 방안의 수를 구해야 한다는 뜻이다.두 개의 그룹을 이용하여 남녀가 그룹에 나타난 횟수를 기록하고 모든 그룹을 다시 한 번 훑어보며 전체 인원수로 현재 그룹의 인물 번호가 모두 나타난 횟수, 즉 충돌하는 그룹 수를 빼고 마지막에 자신을 추가해야 한다.결과는 롱 롱 메모리를 켜야 한다.
#include
",ans/2);
}
return 0;
}
D.Cleaning the Phone
욕심, 정렬 제목은 조건에 맞는 응용을 선택하여 최소한 m의 공간을 방출하는 동시에 편의치를 최소화하는 것을 의미한다.이 문제는 배낭 같지만 배낭을 이용해 해답을 구하는 시간과 공간의 복잡도는 만족할 수 없다.정해는 다음과 같다. 우선 모든 응용 프로그램이 차지하는 메모리의 총계가 m보다 작으면 해가 없다.응용 프로그램을 편의값이 1 또는 2에 따라 각각 내림차순으로 정렬하고 편의값이 1인 응용 프로그램을 우선적으로 제거한다. 제거 과정에서 방출 메모리가 m보다 크면 현재 결과를 직접 출력한다.만약 편의값이 1인 응용 프로그램이 요구를 충족시키지 못하면 정렬된 순서대로 2를 선택하고 선택 과정에서 1보다 많은 응용 프로그램을 제거할 응용 프로그램에서 계속 차내고 그 과정에서 최소값을 기록하며 출력하면 된다.
#include
");
else{
sort(a+1,a+1+n,cmp);
pos1=1;pos2=n+1;
for(ll i=1;i<=n;i++){
if(a[i].b==2){
pos2=i;
break;
}
}
ll i;
for(i=1;i<pos2;i++){
tot+=a[i].a;
ans+=a[i].b;
if(tot>=m) break;
}
if(i==pos2) i--;
sum=ans;
if(tot<m) ans=1e15;
for(ll j=pos2;j<=n;j++){
tot+=a[j].a;
sum+=a[j].b;
while(tot-a[i].a>=m&&i>=1){
tot-=a[i].a;
sum-=a[i].b;
i--;
}
if(tot>=m) ans=min(ans,sum);
}
printf("%lld
",ans);
}
}
return 0;
}
E.Advertising Agency
조합수학, 정렬 문제는 n개 수에서 k개를 선택하고 k개 수의 최대 방안수를 구하는 것을 의미한다.먼저 모든 수의 출현 횟수를 기록하고 그 다음에 입력 데이터를 정렬하여 가장 큰 k개수를 선택하고 이 k개수 중 각 수가 선택한 횟수를 기록한다. 그 다음에 1-n에서 모든 수를 훑어보고 조합수 공식을 이용하여 화합을 구하면 된다.
#include
",ans);
}
return 0;
}
F.Unusual Matrix
욕심은 행렬 A가 행렬을 통과하는 이변 또는 연산이 행렬 B를 얻을 수 있는지 판단하라는 뜻이다.먼저 가장 왼쪽 열의 숫자를 훑어본다. 만약에 A와 B의 숫자가 다르면 전체 줄의 원소를 이차 또는 연산한다. 훑어본 후에 더 많은 줄이나 다른 조작이 없을 것이다. 따라서 두 번째 열부터 훑어본다. 이때 행렬 A와 행렬 B가 같은 열에 있는 원소는 모두 같거나 모두 반대해야 한다. 만약에 모순이 생기면 행렬 A는 변환을 통해 행렬 B에 도달할 수 없다.
#include
");
else printf("NO
");
}
return 0;
}
G.Strange Beauty
DP, 수론은 최소한 몇 개의 수를 삭제해서 수열의 모든 수와 양 사이를 한쪽에서 제거할 수 있도록 하는 것을 의미한다.처음에 나는 DP가 자열을 내리지 않도록 하는 방법을 본떠서 했지만, 그렇게 하는 시간의 복잡도는 O (n2) 이고 분명히 시간을 초과할 것이다.우리가 데이터를 입력할 때 각 숫자가 나타나는 횟수num[i]를 통계하고 수조 f[i]로 숫자 i를 최대치로 하는 수열의 숫자 개수를 표시하면 대응 전이 방정식은 f[i]=num[i]+max(f[a1], f[a2], f[a3],..., f[ak])이고 그 중에서 i%aj==0(1<=j<=k)이다.숫자 1부터 200000까지 열거하고 i의 모든 배수 j의 f[j]값을 f[i]와 최대치로 합니다.
#include
",n-ans);
}
return 0;
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
Codeforces 1287C Garland제목 링크:Codeforces 1287C Garland 사고방식: 우리기dp[i][j][0]와 dp[i][j][1]는 각각 i개가 홀수/짝수이고 앞의 i개 안에 j개의 짝수가 있는 상황에서 i개의 최소 복잡도.첫 번...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
