题目
看起来好像不是很难啊，为什么我做不出来呢；
1. 暴力枚举
枚举x,y,z的值，再判断是否符合条件 ;
时间复杂度： \(\mathcal{O}(n ^ 3)\)
期望得分：\(20pts\)
\(Code\):
#include <bits/stdc++.h>
using namespace std;
const int N=100010;
long long n,m,ans;
long long color[N],number[N];
int main()
{
scanf("%lld %lld",&n , &m);
for(int i=1 ; i<=n ; i++) scanf("%lld",&number[i]);
for(int i=1 ; i<=n ; i++) scanf("%lld",&color[i]);
for(int x=1 ; x<=n ; x++)
{
for(int y=x+1 ; y<=n ; y++)
{
for(int z=y+1 ; z<=n ; z++)
{
if( color[x] == color[z] && y-x == z-y )
ans += (x+z) * (number[x] + number[z]);
}
}
}
printf("%lld",ans%10007);
}
2.优化暴力枚举
整理条件(\(y-z=z-y\))我们可以发现
$$y = (z+x)\div2$$
也就是说，我们可以通过枚举x,z的值来确定y的值
时间复杂度： \(\mathcal{O}(n ^ 2)\)
期望得分：\(40pts\)
\(Code：\)
#include <bits/stdc++.h>
using namespace std;
const int N=100010;
long long n,m,ans;
long long color[N],number[N];
int main()
{
scanf("%lld %lld",&n , &m);
for(int i=1 ; i<=n ; i++) scanf("%lld",&number[i]);
for(int i=1 ; i<=n ; i++) scanf("%lld",&color[i]);
for(int x=1 ; x<=n ; x++)
{
for(int z=x+2 ; z<=n ; z+=2)
{
int y=(x+z)/2;
if(color[x] == color[z])
ans += (x+z) * (number[x] + number[z]);
}
}
printf("%lld",ans%10007);
}
3.正解
仔细观察这个式子 $$y = (x+z)\div2$$
因为\(y\)是整数
所以\(x+z\)必定是偶数
也就是说 \(x\)和\(z\)同奇偶
再想想题目(\(color[z]=color[z]……\)
◝(⑅•ᴗ•⑅)◜..°♡ 欸！！瞧瞧我们发现了什么!
\(x\)和\(z\)具有两项相同的性质
整理一下
- \(x与z同奇偶\)
- \(color[x] = color[z]\)
这个时候我们就要运用分组思想
————那么 什么是分组思想?
分组思想，就是把具有相同性质的两个集合放在一起，方便计算。
————沃兹·基朔德
放在这题里就是
先将所有数字按颜色分组，再按奇偶分组（其实先按什么分都一样的啦
显然，每一组中，任意一对x,z都可以构造出一个符合条件的三元组（\(y=(x+z)\div2\)）
推式子时间到！
我们不知道从哪搞来了两个数组a,number;
- a[i]表示某一组内第i个格子的编号
- number[i]表示某一组内第i个格子表上写的数字
- k表示组内共有k个格子
那么这个组内的分数应该为
\[(a[1]+a[2])\times(number[1]+number[2])+(a[1]+a[3])\times(number[1]+number[3])+……+(a[2]+a[3])\times(numebr[2]+number[3])+(a[2]+a[4])\times(number[2]+number[4])+……+(a[k-1]+a[k])\times(number[k-1]+number[k]) \]化简一下可得
\[a[1]\times(number[1]+number[2]+number[1]+number[3]……+number[1]+number[k])+……+a[k]\times(number[1]+number[k]+number[2]+number[k]+……+number[k-1]+number[k]) \]\[=a[1]\times(number[1]\times(k-2)+number[1]+number[2]+……+number[k])+………+a[k]\times(number[k]\times(k-2)+number[1]+number[2]+……+number[k]) \]至于计算\(number[1]+number[2]+……+number[k]\)只需要加一个前缀和优化就可以力
那么整张纸条的分数就是将所有分出来的组的分数的总和！！！
有了思路，写代码清晰无比；
时间复杂度：\(\mathcal{O}(n ^ )\)
期望得分：\(100pts\)
\(Code\)
#include <bits/stdc++.h>
using namespace std;
const int NN=100010;
const int MOD = 10007;
long long number[NN] ,color[NN];
long long sum[NN][2] , k[NN][2];//sum是前缀和数组，k是每组的个数
long long n,m,ans;
int main()
{
scanf("%d %d" , &n , &m);
for(int i=1 ; i<=n ; i++) scanf("%d",&number[i]);
for(int i=1 ; i<=n ; i++) scanf("%d",&color[i]);
for(int i=1 ; i<=n ; i++)
{
k[color[i]][i%2] ++;
sum[color[i]][i%2] = (sum[color[i]][i%2] + number[i]) % MOD;
}
for(int i=1 ; i<=n ; i++)
{
ans += i * (number[i] * (k[color[i]][i%2]-2) + sum[color[i]][i%2] );
ans %= MOD;
}
printf("%d",ans);
return 0;
}
By Hu_taooo
标签：NOIP2015,number,NN,int,题解,T3,long,times,color From： https://www.cnblogs.com/Hutaooo/p/16757354.html