2018.12.08 [NOIP 향상팀] 시뮬레이션 B팀 5123.diyiti
2262 단어 dp
Description은 n개의 곧은 나무 막대기를 정하고 그 중에서 6개의 나무 막대기를 골라야 한다. 만족: 이 6개의 나무 막대기로 정사각형을 만들 수 있다.나무 막대기가 구부러지지 않도록 주의해라.방안 수를 묻다.정사각형: 네 변은 모두 같고 네 각은 모두 직각의 사각형이다.
Input의 첫 번째 행은 정수 n입니다.두 번째 줄은 n개의 정수ai를 포함하고 각 나무 막대기의 길이를 대표한다.
Output은 스키마 수를 나타내는 정수 행입니다.
Sample Input 8 4 5 1 5 1 9 4 5
Sample Output 3
데이터 콘straint는 20%의 데이터에 만족: n≤30은 40%의 데이터에 만족: n≤200은 60%의 데이터에 만족: n≤1000은 100%의 데이터에 만족: n≤5000;1 ≤ ai ≤ 10^7
사고방식: 1.두 가지 상황을 분류하여 토론하다
먼저 a수조를 b로 다시 바꾸고 b가 이 수치에 대응하는 횟수num는 i를 매거한다. 가장 긴 두 개(1,1)는 1~i-1 구간에서 합법적인 두 쌍을 찾는다. 이 두 쌍의 합은 모두 b[i]ans+=C(num[i], 2)*C(합법적인 대수, 2)이다.두 개의 바늘로 l, r를 끊임없이 가운데로 가리키며 합법적인 대수(조를 기록할 수 있다
n^3 매거가 안 되는데 어떡하지?i:1->n은 세 개의 짧은 변 중 가장 긴 것을 매거하고, j:i+1->n은 가장 긴 세 개(1,1,1)를 매거한다. 그러면 중복되는 것을 두려워하지 않는다. 만약에 우리가 f[x]가 현재 원소의 두 쌍과 x의 방안 수가 있다면ans+=C(num[j],3)*s[b[j]-a[i]];(변의 길이는 b[j]로 이미 변의 i를 확정했고 b[j]-a[i]가 남았습니다)
#include
#define ll long long
#define N 5010
#define MAX (ll)(1e7)
#define open(x) freopen(x".in","r",stdin);freopen(x".out","w",stdout);
using namespace std;
ll n,m,l,r,i,j,ans,cnt,sum;
ll a[N],b[N],num[N],id[N],s[MAX];
int main()
{
open("yist");
scanf("%lld",&n);
for(i=1;i<=n;i++)scanf("%lld",&a[i]);
sort(a+1,a+1+n);
for(i=1;i<=n;i++)
{
if(a[i]!=a[i-1])b[++m]=a[i];
++num[m];
id[i]=m;
}
for(i=1;i<=m;i++)
{
if(num[i]>=2)
{ sum=cnt=0;
for(l=1,r=i-1;l<=r;l++)
{
while(l<=r && b[l]+b[r]>b[i])--r;
if(l>r|| b[l]+b[r]!=b[i])continue;
if(l=2 && num[r]>=2)cnt+=(num[l])*(num[l]-1)/2*(num[r])*(num[r]-1)/2;
cnt+=num[l]*num[r]*sum;
sum+=num[l]*num[r];
}
else
{
if(num[l]>=4)cnt+=num[l]*(num[l]-1)*(num[l]-2)*(num[l]-3)/24;
cnt+=num[l]*(num[l]-1)/2*sum;
}
}
ans+=num[i]*(num[i]-1)/2*cnt;
}
}
memset(s,0,sizeof s);
for(i=1;i<=n;i++)
{
for(j=id[i]+1;j<=m;j++)if(num[j]>=3)ans+=num[j]*(num[j]-1)*(num[j]-2)/6*s[b[j]-a[i]];
for(j=1;j 이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
【경쟁 프로 전형적인 90문】008의 해설(python)의 해설 기사입니다. 해설의 이미지를 봐도 모르는 (이해력이 부족한) 것이 많이 있었으므로, 나중에 다시 풀었을 때에 확인할 수 있도록 정리했습니다. ※순차적으로, 모든 문제의 해설 기사를 들어갈 예정입니다. 문자열...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
