题解 P2671 【求和】

学无止境

2018-07-30 23:13:16

Solution

(不与其他题解重复) 既然没有人用指针申请动态数组做,我就来一发吧QwQ 经过本蒟蒻的试验,用动态数组分类讨论的话,即使没有数学优化,也能骗到90分!!!如果开O2优化的话可以直接AC (也许是数据太弱了) 首先教大家了解一下怎么用指针申请动态数组(会的可以直接看后面) //创建↓ ``` int *a;// 需要一个指针来执行 new 操作 a=new int[100];//申请了一个长为100的int数组 //以此为例,调用此动态数组的元素的做法如下↓ cin>>a[5],a[5]+=1;//赋值之类的操作(是不是很简单) ``` 当然,作为一名合格的OIer,我们还是要学会数学优化方法(其实只是很简单的推导) 毕竟,OI比赛中不允许使用O2优化 [ 滑稽 ] 我们可以发现,三元组本身和 y 没有任何关系,y的存在只是告诉我们:(x+z)/2 是个整数 容易发现当x、z两者均为奇数或均为偶数时满足 (x+z)/2是个整数 所以,我们既然有动态数组这种利器,就可以毫不顾忌的对奇偶性不同、颜色不同的部分进行分组,如果有 m 种颜色,我们可以将其分为*2m**组 如果不能理解,让我举个例子: ``` //栗子: 假如n=10,纸带有编号1~10的10个部分,有1、2两种颜色,m=2 编号: 1 2 3 4 5 6 7 8 9 10 颜色:1 1 0 1 0 1 1 1 0 0 那么,我们可以将纸带分成2*m=4个部分 一、颜色为0且编号为偶数:10号 二、颜色为1且编号为偶数:2、4、6、8号 三、颜色为0且编号为奇数:3、5、9号 四、颜色为1且编号为奇数:1、7号 //是否理解了分类方法呢 ``` 依据上述分类方法,对于同一组的n个数据:A1,A2,A3……An(编号单调递增) A1可以与A2、A3……An组成三元组(中间的y不用管了) A2可以与A3、A4……An组成三元组(中间的y不用管了) 同理,每一组中的任意一个元素均能与同组并排在它后面的元素组成三元组 那么就好求了,简单运用数学归纳法可以证明(其实举例子都可以猜出来): ``` //数学优化的主体部分 若一组数中有A1,A2,A3……An 共n个元素(编号单调递增) 其编号分别为R1,R2,R3……Rn 其上的值分别为S1,S2,S3……Sn 那么这一组数中所有三元组对答案的贡献: (R1+R2+R3……Rn)*(S1+S2+S3……Sn)+(n-2)*(R1*S1+R2*S2+R3*S3+Rn*Sn) 实例可以证明: n=3 时 总贡献: (R1+R2)*(S1+S2)+(R1+R3)*(S1+S3)+(R2+R3)*(S2+S3) =R1S1+R1S2+R2S1+R2S2+R1S1+R1S3+R3S1+R3S3+R2S2+R2S3+R3S2+R3S3 =(R1+R2+R3)*(S1+S2+S3)+1*(R1S1+R2S2+R3S3) //在上面的实例中 n-2=3-2=1 其实随便手算一下就能猜出规律,至于上面的系数为什么是n-2的问题 也很容易想到,对于任意一个元素,与其有关的R、S总的乘了n-1组 而有一组被放到前面去用于合并,剩下n-2组 ``` 最后一个重点,该开long long 的地方不要舍不得,具体见我的代码QaQ 感觉自己已经讲的很详细了,还不懂私信问我 再安利一波动态数组,代码效率挺高的 ``` Code: #include<iostream> #include<cstdio> using namespace std; struct color { long long rank,points; }*a[200001]; int num[200001],n,m; int mem[100001],col[100001],flag[200001],top[200001],mm,tmp1; long long tmp,sum,tsum1,tsum2,tsum3; int main() { scanf("%d%d",&n,&m);//偶数记录在后面 mm=m*2; for(register int i=1;i<=n;i++) scanf("%d",&mem[i]); for(register int i=1;i<=n;i++) scanf("%d",&col[i]),(i&1)==1?num[col[i]]++:num[col[i]+m]++; for(register int i=1;i<=mm;i++) if(num[i]>0) { flag[i]=true; a[i]=new color[num[i]+1]; } for(register int i=1;i<=n;i++) { tmp1=((i&1)==1)?col[i]:(col[i]+m); a[tmp1][++top[tmp1]].points=mem[i]; a[tmp1][top[tmp1]].rank=i; } for(register int i=1;i<=mm;i++) { if(flag[i]) { tsum1=tsum2=tsum3=0; for(register int j=1;j<=num[i];j++) { tsum1+=a[i][j].points; tsum2+=a[i][j].rank; tsum3+=(a[i][j].rank*a[i][j].points); } sum+=tsum1*tsum2+tsum3*(num[i]-2); sum%=10007; } } cout<<sum<<endl; } ```