P8398 [CCC 2022 S4] Good Triplets
题目描述
Andrew\rm AndrewAndrew是十分好奇的学生，一天他在纸上画了一个圆，圆心在(0,0)(0,0)(0,0)。设周长为CCC，圆上每一个点的坐标为：
现在Andrew\rm AndrewAndrew在圆上画了nnn个点，第iii的点画在pip_ipi上，Andrew\rm AndrewAndrew可能在一个位置上画多个点。
现在一个好的三角形（a,b,c)（a,b,c)（a,b,c)的定义为：
- 1≤a<b<c≤n1\le a<b<c\le n1≤a<b<c≤n
- 原点（0，0）（0，0）（0，0）严格位于顶点在pap_apa，PbP_bPb和pcp_cpc的三角形内。特别注意的是，原点不在三角形的周长上。
Andrew\rm AndrewAndrew问你有多少个好的三角形。
输入格式
第一行两个整数n,cn,cn,c，表示点的个数和圆的周长。
接下来一行，有nnn个整数，具体意义见题目描述。
输出格式
输出一个整数xxx，表示有xxx个好的三角形。
输入输出样例 #1
输入 #1
8 10 0 2 5 5 6 9 0 0输出 #1
6说明/提示
样例111解释：
Andrew\rm AndrewAndrew画了下面的图：
原点严格地位于顶点为p1p_1p1、p2p_2p2和p5p_5p5的三角形内，所以（1，2，5）（1，2，5）（1，2，5）是一个好的三角形。其他五个好三联体是（2，3，6），（2，4，6），（2，5，6），（2，5，7）（2，3，6），（2，4，6），（2，5，6），（2，5，7）（2，3，6），（2，4，6），（2，5，6），（2，5，7）和（2，5，8）（2，5，8）（2，5，8）。
对于20%20\%20%的数据：3≤n≤200,3≤c≤1063\le n\le 200,3\le c\le10^63≤n≤200,3≤c≤106
对于另外20%20\%20%的数据：3≤n≤106,3≤c≤60003\le n\le 10^6,3\le c\le60003≤n≤106,3≤c≤6000
对于40%40\%40%的数据：3≤n≤106,3≤c≤1063\le n\le 10^6,3\le c\le10^63≤n≤106,3≤c≤106且所有点的位置互不相同。
对于100%100\%100%的数据：3≤n≤106,3≤c≤1063\le n\le 10^6,3\le c\le10^63≤n≤106,3≤c≤106
C++实现
#include<iostream>#include<cstdio>#include<algorithm>usingnamespacestd;constintN=1e6+5;intn,c;inta[N];intcnt[N];intsum[N];longlongc2(intx){if(x<=1){return0;}return(longlong)x*(x-1)/2;}longlongc3(intx){if(x<=2){return0;}return(longlong)x*(x-1)*(x-2)/6;}intmain(){scanf("%d%d",&n,&c);for(inti=1;i<=n;i++){scanf("%d",&a[i]);cnt[a[i]]++;}intli=c/2;longlongans=0;intnow=0;for(inti=1;i<=li;i++){now+=cnt[i];}if(c%2==0){for(inti=0;i<c;i++){ans+=(longlong)cnt[i]*c2(now);ans+=(longlong)c2(cnt[i])*(now-cnt[(i+li)%c]);now-=cnt[(i+1)%c];now+=cnt[(i+li+1)%c];}}else{for(inti=0;i<c;i++){ans+=(longlong)cnt[i]*c2(now);ans+=(longlong)c2(cnt[i])*now;now-=cnt[(i+1)%c];now+=cnt[(i+li+1)%c];}}for(inti=0;i<c;i++){ans+=c3(cnt[i]);}longlongsum=c3(n);printf("%lld\n",sum-ans);return0;}后续
接下来我会不断用C++来实现信奥比赛中的算法题、GESP考级编程题实现、白名单赛事考题实现，记录日常的编程生活、比赛心得，感兴趣的请关注，我后续将继续分享相关内容
