题解 - Vijos

3

Leachim (wmxwmx) LV 8 @ 2015-11-08 22:36:01

测试数据 #0: Accepted, time = 0 ms, mem = 5132 KiB, score = 10
测试数据 #1: Accepted, time = 0 ms, mem = 5132 KiB, score = 10
测试数据 #2: Accepted, time = 0 ms, mem = 5132 KiB, score = 10
测试数据 #3: Accepted, time = 0 ms, mem = 5136 KiB, score = 10
测试数据 #4: Accepted, time = 46 ms, mem = 5132 KiB, score = 10
测试数据 #5: Accepted, time = 46 ms, mem = 5132 KiB, score = 10
测试数据 #6: Accepted, time = 31 ms, mem = 5132 KiB, score = 10
测试数据 #7: Accepted, time = 31 ms, mem = 5132 KiB, score = 10
测试数据 #8: Accepted, time = 31 ms, mem = 5132 KiB, score = 10
测试数据 #9: Accepted, time = 15 ms, mem = 5132 KiB, score = 10
Accepted, time = 200 ms, mem = 5136 KiB, score = 100
楼上的数据是100%考试时的代码做来的（还有点需要优化一下下）
这道题害得我写了一个多小时，但是现在看来民间数据能满分，我想想来心中还是比较满足的。

现在说下算法，比赛时为了保底，我先写了个暴力算法。大家应该都会，就不说了。（暴力算法中m都用不到）

讲下优化后的算法。
首先观察(x-y=y-z)...判断出奇偶分开（不用说的事儿）
然后我们开始看如果同奇偶有x个相同颜色的格子的话，我们设第i个的编号是ai,数字是ni
然后我们可以写出来这个颜色带个sum的数量是(a1+a2)(n1+n2)+(a1+a3)(n1+n3)+..+(a2+a3)(n2+n3)+...+(ax-1/*x-1下标*/+ax)(nx-1+nx)
楼上有点类似选择排序的思想，那么暴力就这么解了
但是我们现在把括号拆开。
发现是这样子的。
(x-1)(n1*a1+n2*a2+...nx*ax)+a1*n2+a1*n3+...+ax*nx-1
我们向前面x-1个那坨东西中提取一份出来，放入后面。
变成(x-2)(前面那坨)+a1(n1+n2+..+nx)+a2(n1+n2+..+nx)+..+ax(n1+..+nx);
就是(x-2)(n1*a1+..+nx*ax)+(a1+a2+..+ax)(n1+n2+..+nx)
这么一看就非常简单了。你可以带几个x进去试试，是对的。
然后我们就只用分奇偶用循环过一遍N个格子，然后用桶排的思想，创建4个大小为M的数组，一个记录x,一个记录sum(ni*ai),一个记录sum(ni),一个记录sum(ai)。然后最后再循环一遍from 1 to m 把桶里的东西按照上面的公式加起来一遍（记住要mod/*%*/ 10007）
下面是我考试的代码，有点不雅观请不要在意。//其中的Int64（long long）应该是不必要的。
###Block code
var n,m,i,sum:longint;
num,color,t,tc,tn,tm:array[1..100000]of Int64;

begin
read(n,m);
for i:=1 to n do
read(num[i]);
for i:=1 to n do
read(color[i]);
fillchar(t,sizeof(t),0);
fillchar(tc,sizeof(tc),0);
fillchar(tn,sizeof(tn),0);
fillchar(tm,sizeof(tm),0);
sum:=0;
i:=1;
while i<=n do
begin
inc(t[color[i]]);
inc(tc[color[i]],i*num[i]);
inc(tn[color[i]],num[i]);
inc(tm[color[i]],i);
inc(i,2);
end;
for i:=1 to m do
if t[i]>1 then
sum:=(sum+(t[i]-2)*tc[i]+tn[i]*tm[i])mod 10007;
fillchar(t,sizeof(t),0);
fillchar(tc,sizeof(tc),0);
fillchar(tn,sizeof(tn),0);
fillchar(tm,sizeof(tm),0);
i:=2;
while i<=n do
begin
inc(t[color[i]]);
inc(tc[color[i]],i*num[i]);
inc(tn[color[i]],num[i]);
inc(tm[color[i]],i);
inc(i,2);
end;
for i:=1 to m do
if t[i]>1 then
sum:=(sum+(t[i]-2)*tc[i]+tn[i]*tm[i])mod 10007;
writeln(sum);
end.

刘天弘 @ 2016-08-22 17:21:31

膜
lrj124 @ 2016-08-22 21:18:51

orz大神
loddian @ 2016-11-17 19:23:12

Int64是需要的，用longint会溢出WA

1

niujinyu LV 10 @ 2022-07-20 13:47:14

记得使用万能头文件 #include <bits/stdc++.h>
```cpp
#include <bits/stdc++.h>
using namespace std;

int s[100005][2],sum[100005][2],c[100005],x[100005];
int n,m,ans;
int main(){
cin>>n>>m;
for(int i=1; i<=n; i++)
cin>>x[i];
for(int i=1; i<=n; i++){
cin>>c[i];
s[c[i]][i%2]++;
sum[c[i]][i%2]=(sum[c[i]][i%2]+x[i])%10007;
}
for(int i=1; i<=n; i++)
ans=(ans+i*((s[c[i]][i%2]-2)*x[i]%10007+sum[c[i]][i%2]))%10007;
cout<<ans;
return 0;
}

1

aph。 (chenqianrong) LV 10 @ 2021-08-30 08:38:12

#include <bits/stdc++.h>
using namespace std;

int s[100005][2],sum[100005][2],c[100005],x[100005];
int n,m,ans;
int main(){
    cin>>n>>m;
    for(int i=1; i<=n; i++)
        cin>>x[i];
    for(int i=1; i<=n; i++){
        cin>>c[i];
        s[c[i]][i%2]++;
        sum[c[i]][i%2]=(sum[c[i]][i%2]+x[i])%10007;
    }
    for(int i=1; i<=n; i++)
        ans=(ans+i*((s[c[i]][i%2]-2)*x[i]%10007+sum[c[i]][i%2]))%10007;
    cout<<ans;
    return 0;
}

1

PowderHan LV 10 @ 2018-08-20 09:23:17

/*
一道有趣的题目Orz
说说我做这道题的思路经历吧
一看到这道题
我就直接想到了其实就是求颜色相同且距离差值为偶数的点对
然后想直接枚举一下O(n^2)
看一下数据范围n到了10万
肯定超时
怎么做呢Orz
然后我就看到了数据范围中那一句
"且不存在出现次数超过 20 的颜色"
然后瞬间就想到
这题的突破口在颜色数量少？
看一下颜色也不少呀百分之百的范围
然后就先去看第四题了
果然第四题直接写了个暴力
然后就直接回来看到这道题
想了半天
诶不对突破口应该就是这个颜色数量！
我们可不可以记录下每个颜色出现的奇数位置或者偶数位置
诶不对 (～￣▽￣)→))*￣▽￣*)o
傻了
我们可以记录下每种颜色的出现位置啊
那这样就不大了对吧
然后我就直接赤裸裸地写了个vector保存下这个颜色出现位置
然后对于每一个点都进入它的颜色中的vector[]来找满足条件的数
匆匆打完
完美23333333
然后四题都检查完了
就提交了    90分一个点过不去
Orz难道这不是标程？QAQ
忍住不看题解
继续想吧
盯着屏幕发呆啊
然后突然就想到了
我擦我傻了
为啥要遍历所有的点然后找是否成立呢？
我们可以直接进入所有的颜色集合中去
然后在这里面找一下所有可能的配对
这样的时间瞬间就缩小了很多
QAQ
好有道理的样子
然后就瞬间改了过来
AC了
长见识了QAQ
嗯有了这个思路应该能听懂了吧QWQ
注意因为数据很大啊
加的时候和乘的时候都取一下模
才不会溢出
QAQ反正碰到取模的就有可能溢出的地方都保险加上个取模
毕竟这东西又不要你钱又不要你命的
QAQ考试一定要小心
长知识了
挺锻炼逻辑思维的
*/
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <vector>
using namespace std;

const int MAXN=100006;
const int mod=10007;
struct node
{
    int num,color;
}a[MAXN];
vector<int> c[MAXN];
int n,m;
int ans;

void init()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)
        scanf("%d",&a[i].num);
    for(int i=1;i<=n;i++)
        scanf("%d",&a[i].color);
}

int main()
{
    init();
    for(int i=1;i<=n;i++)
        c[a[i].color].push_back(i);
    for(int k=1;k<=m;k++)
    {
        int d=c[k].size();
        for(int i=0;i<d;i++)
            for(int j=i+1;j<d;j++)
                if((c[k][j]-c[k][i])%2==0)
                    ans=(ans+(c[k][j]+c[k][i])%mod*(a[c[k][j]].num+a[c[k][i]].num)%mod)%mod;
    }
    printf("%d\n",ans%mod);
    return 0;
}

1

sslz-grh LV 7 @ 2017-09-08 01:45:37

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<map>
using namespace std;
long long n,m,ans=0;
struct locin{
long long color=0,num,id;
}jyx1[100010],jyx2[100010];
void jyxin(long long &x)
{
char c=getchar();
x=0;
while(c>'9'||c<'0')c=getchar();
while(c<='9'&&c>='0')x=x*10+c-48,c=getchar();
}
int comp(const locin &a,const locin &b)
{
return a.color<b.color;
}
int main()
{
long long codif1[100010],codif2[100010];
jyxin(n);
jyxin(m);
long long d1=0,d2=0;
for(int i=1;i<=n;++i)
{
if(i%2==0)jyxin(jyx1[i/2].num);
if(i%2==1)jyxin(jyx2[i/2+1].num);
}
for(int i=1;i<=n;++i)
{
if(i%2==0)jyxin(jyx1[i/2].color),jyx1[i/2].id=i;
if(i%2==1)jyxin(jyx2[i/2+1].color),jyx2[i/2+1].id=i;
}
sort(jyx1+1,jyx1+n/2+1,comp);
sort(jyx2+1,jyx2+n-n/2+1,comp);
for(int i=1;i<=n/2+1;++i)
if(jyx1[i].color!=jyx1[i-1].color)d1++,codif1[d1]=i;
for(int i=1;i<=n-n/2+1;++i)
if(jyx2[i].color!=jyx2[i-1].color)d2++,codif2[d2]=i;
for(int i=1;i<=d1-1;++i)
{
int hg=codif1[i+1]-codif1[i];
if(hg>=2)
{
unsigned long long r=0,t=0;
for(int j=codif1[i];j<=codif1[i+1]-1;++j)
ans=(ans+(hg-2)*jyx1[j].id*jyx1[j].num)%10007,r+=jyx1[j].id,t+=jyx1[j].num;
ans=(ans+(r%10007)*(t%10007))%10007;
}
}
for(int i=1;i<=d2-1;++i)
{
int hg=codif2[i+1]-codif2[i];
if(hg>=2)
{
unsigned long long r=0,t=0;
for(int j=codif2[i];j<=codif2[i+1]-1;++j)
ans=(ans+(hg-2)*jyx2[j].id*jyx2[j].num)%10007,r+=jyx2[j].id,t+=jyx2[j].num;
ans=(ans+(r%10007)*(t%10007))%10007;
}
}
cout<<ans%10007;
return 0;
}

1

sslz-grh LV 7 @ 2017-09-08 01:45:33

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<map>
using namespace std;
long long n,m,ans=0;
struct locin{
long long color=0,num,id;
}jyx1[100010],jyx2[100010];
void jyxin(long long &x)
{
char c=getchar();
x=0;
while(c>'9'||c<'0')c=getchar();
while(c<='9'&&c>='0')x=x*10+c-48,c=getchar();
}
int comp(const locin &a,const locin &b)
{
return a.color<b.color;
}
int main()
{
long long codif1[100010],codif2[100010];
jyxin(n);
jyxin(m);
long long d1=0,d2=0;
for(int i=1;i<=n;++i)
{
if(i%2==0)jyxin(jyx1[i/2].num);
if(i%2==1)jyxin(jyx2[i/2+1].num);
}
for(int i=1;i<=n;++i)
{
if(i%2==0)jyxin(jyx1[i/2].color),jyx1[i/2].id=i;
if(i%2==1)jyxin(jyx2[i/2+1].color),jyx2[i/2+1].id=i;
}
sort(jyx1+1,jyx1+n/2+1,comp);
sort(jyx2+1,jyx2+n-n/2+1,comp);
for(int i=1;i<=n/2+1;++i)
if(jyx1[i].color!=jyx1[i-1].color)d1++,codif1[d1]=i;
for(int i=1;i<=n-n/2+1;++i)
if(jyx2[i].color!=jyx2[i-1].color)d2++,codif2[d2]=i;
for(int i=1;i<=d1-1;++i)
{
int hg=codif1[i+1]-codif1[i];
if(hg>=2)
{
unsigned long long r=0,t=0;
for(int j=codif1[i];j<=codif1[i+1]-1;++j)
ans=(ans+(hg-2)*jyx1[j].id*jyx1[j].num)%10007,r+=jyx1[j].id,t+=jyx1[j].num;
ans=(ans+(r%10007)*(t%10007))%10007;
}
}
for(int i=1;i<=d2-1;++i)
{
int hg=codif2[i+1]-codif2[i];
if(hg>=2)
{
unsigned long long r=0,t=0;
for(int j=codif2[i];j<=codif2[i+1]-1;++j)
ans=(ans+(hg-2)*jyx2[j].id*jyx2[j].num)%10007,r+=jyx2[j].id,t+=jyx2[j].num;
ans=(ans+(r%10007)*(t%10007))%10007;
}
}
cout<<ans%10007;
return 0;
}

1

sslz-grh LV 7 @ 2017-09-08 01:45:29

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<map>
using namespace std;
long long n,m,ans=0;
struct locin{
long long color=0,num,id;
}jyx1[100010],jyx2[100010];
void jyxin(long long &x)
{
char c=getchar();
x=0;
while(c>'9'||c<'0')c=getchar();
while(c<='9'&&c>='0')x=x*10+c-48,c=getchar();
}
int comp(const locin &a,const locin &b)
{
return a.color<b.color;
}
int main()
{
long long codif1[100010],codif2[100010];
jyxin(n);
jyxin(m);
long long d1=0,d2=0;
for(int i=1;i<=n;++i)
{
if(i%2==0)jyxin(jyx1[i/2].num);
if(i%2==1)jyxin(jyx2[i/2+1].num);
}
for(int i=1;i<=n;++i)
{
if(i%2==0)jyxin(jyx1[i/2].color),jyx1[i/2].id=i;
if(i%2==1)jyxin(jyx2[i/2+1].color),jyx2[i/2+1].id=i;
}
sort(jyx1+1,jyx1+n/2+1,comp);
sort(jyx2+1,jyx2+n-n/2+1,comp);
for(int i=1;i<=n/2+1;++i)
if(jyx1[i].color!=jyx1[i-1].color)d1++,codif1[d1]=i;
for(int i=1;i<=n-n/2+1;++i)
if(jyx2[i].color!=jyx2[i-1].color)d2++,codif2[d2]=i;
for(int i=1;i<=d1-1;++i)
{
int hg=codif1[i+1]-codif1[i];
if(hg>=2)
{
unsigned long long r=0,t=0;
for(int j=codif1[i];j<=codif1[i+1]-1;++j)
ans=(ans+(hg-2)*jyx1[j].id*jyx1[j].num)%10007,r+=jyx1[j].id,t+=jyx1[j].num;
ans=(ans+(r%10007)*(t%10007))%10007;
}
}
for(int i=1;i<=d2-1;++i)
{
int hg=codif2[i+1]-codif2[i];
if(hg>=2)
{
unsigned long long r=0,t=0;
for(int j=codif2[i];j<=codif2[i+1]-1;++j)
ans=(ans+(hg-2)*jyx2[j].id*jyx2[j].num)%10007,r+=jyx2[j].id,t+=jyx2[j].num;
ans=(ans+(r%10007)*(t%10007))%10007;
}
}
cout<<ans%10007;
return 0;
}

1

sslz-grh LV 7 @ 2017-09-08 01:45:24

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<map>
using namespace std;
long long n,m,ans=0;
struct locin{
long long color=0,num,id;
}jyx1[100010],jyx2[100010];
void jyxin(long long &x)
{
char c=getchar();
x=0;
while(c>'9'||c<'0')c=getchar();
while(c<='9'&&c>='0')x=x*10+c-48,c=getchar();
}
int comp(const locin &a,const locin &b)
{
return a.color<b.color;
}
int main()
{
long long codif1[100010],codif2[100010];
jyxin(n);
jyxin(m);
long long d1=0,d2=0;
for(int i=1;i<=n;++i)
{
if(i%2==0)jyxin(jyx1[i/2].num);
if(i%2==1)jyxin(jyx2[i/2+1].num);
}
for(int i=1;i<=n;++i)
{
if(i%2==0)jyxin(jyx1[i/2].color),jyx1[i/2].id=i;
if(i%2==1)jyxin(jyx2[i/2+1].color),jyx2[i/2+1].id=i;
}
sort(jyx1+1,jyx1+n/2+1,comp);
sort(jyx2+1,jyx2+n-n/2+1,comp);
for(int i=1;i<=n/2+1;++i)
if(jyx1[i].color!=jyx1[i-1].color)d1++,codif1[d1]=i;
for(int i=1;i<=n-n/2+1;++i)
if(jyx2[i].color!=jyx2[i-1].color)d2++,codif2[d2]=i;
for(int i=1;i<=d1-1;++i)
{
int hg=codif1[i+1]-codif1[i];
if(hg>=2)
{
unsigned long long r=0,t=0;
for(int j=codif1[i];j<=codif1[i+1]-1;++j)
ans=(ans+(hg-2)*jyx1[j].id*jyx1[j].num)%10007,r+=jyx1[j].id,t+=jyx1[j].num;
ans=(ans+(r%10007)*(t%10007))%10007;
}
}
for(int i=1;i<=d2-1;++i)
{
int hg=codif2[i+1]-codif2[i];
if(hg>=2)
{
unsigned long long r=0,t=0;
for(int j=codif2[i];j<=codif2[i+1]-1;++j)
ans=(ans+(hg-2)*jyx2[j].id*jyx2[j].num)%10007,r+=jyx2[j].id,t+=jyx2[j].num;
ans=(ans+(r%10007)*(t%10007))%10007;
}
}
cout<<ans%10007;
return 0;
}

1

sslz-grh LV 7 @ 2017-09-08 01:45:20

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<map>
using namespace std;
long long n,m,ans=0;
struct locin{
long long color=0,num,id;
}jyx1[100010],jyx2[100010];
void jyxin(long long &x)
{
char c=getchar();
x=0;
while(c>'9'||c<'0')c=getchar();
while(c<='9'&&c>='0')x=x*10+c-48,c=getchar();
}
int comp(const locin &a,const locin &b)
{
return a.color<b.color;
}
int main()
{
long long codif1[100010],codif2[100010];
jyxin(n);
jyxin(m);
long long d1=0,d2=0;
for(int i=1;i<=n;++i)
{
if(i%2==0)jyxin(jyx1[i/2].num);
if(i%2==1)jyxin(jyx2[i/2+1].num);
}
for(int i=1;i<=n;++i)
{
if(i%2==0)jyxin(jyx1[i/2].color),jyx1[i/2].id=i;
if(i%2==1)jyxin(jyx2[i/2+1].color),jyx2[i/2+1].id=i;
}
sort(jyx1+1,jyx1+n/2+1,comp);
sort(jyx2+1,jyx2+n-n/2+1,comp);
for(int i=1;i<=n/2+1;++i)
if(jyx1[i].color!=jyx1[i-1].color)d1++,codif1[d1]=i;
for(int i=1;i<=n-n/2+1;++i)
if(jyx2[i].color!=jyx2[i-1].color)d2++,codif2[d2]=i;
for(int i=1;i<=d1-1;++i)
{
int hg=codif1[i+1]-codif1[i];
if(hg>=2)
{
unsigned long long r=0,t=0;
for(int j=codif1[i];j<=codif1[i+1]-1;++j)
ans=(ans+(hg-2)*jyx1[j].id*jyx1[j].num)%10007,r+=jyx1[j].id,t+=jyx1[j].num;
ans=(ans+(r%10007)*(t%10007))%10007;
}
}
for(int i=1;i<=d2-1;++i)
{
int hg=codif2[i+1]-codif2[i];
if(hg>=2)
{
unsigned long long r=0,t=0;
for(int j=codif2[i];j<=codif2[i+1]-1;++j)
ans=(ans+(hg-2)*jyx2[j].id*jyx2[j].num)%10007,r+=jyx2[j].id,t+=jyx2[j].num;
ans=(ans+(r%10007)*(t%10007))%10007;
}
}
cout<<ans%10007;
return 0;
}

1

sslz-grh LV 7 @ 2017-09-08 01:45:17

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<map>
using namespace std;
long long n,m,ans=0;
struct locin{
long long color=0,num,id;
}jyx1[100010],jyx2[100010];
void jyxin(long long &x)
{
char c=getchar();
x=0;
while(c>'9'||c<'0')c=getchar();
while(c<='9'&&c>='0')x=x*10+c-48,c=getchar();
}
int comp(const locin &a,const locin &b)
{
return a.color<b.color;
}
int main()
{
long long codif1[100010],codif2[100010];
jyxin(n);
jyxin(m);
long long d1=0,d2=0;
for(int i=1;i<=n;++i)
{
if(i%2==0)jyxin(jyx1[i/2].num);
if(i%2==1)jyxin(jyx2[i/2+1].num);
}
for(int i=1;i<=n;++i)
{
if(i%2==0)jyxin(jyx1[i/2].color),jyx1[i/2].id=i;
if(i%2==1)jyxin(jyx2[i/2+1].color),jyx2[i/2+1].id=i;
}
sort(jyx1+1,jyx1+n/2+1,comp);
sort(jyx2+1,jyx2+n-n/2+1,comp);
for(int i=1;i<=n/2+1;++i)
if(jyx1[i].color!=jyx1[i-1].color)d1++,codif1[d1]=i;
for(int i=1;i<=n-n/2+1;++i)
if(jyx2[i].color!=jyx2[i-1].color)d2++,codif2[d2]=i;
for(int i=1;i<=d1-1;++i)
{
int hg=codif1[i+1]-codif1[i];
if(hg>=2)
{
unsigned long long r=0,t=0;
for(int j=codif1[i];j<=codif1[i+1]-1;++j)
ans=(ans+(hg-2)*jyx1[j].id*jyx1[j].num)%10007,r+=jyx1[j].id,t+=jyx1[j].num;
ans=(ans+(r%10007)*(t%10007))%10007;
}
}
for(int i=1;i<=d2-1;++i)
{
int hg=codif2[i+1]-codif2[i];
if(hg>=2)
{
unsigned long long r=0,t=0;
for(int j=codif2[i];j<=codif2[i+1]-1;++j)
ans=(ans+(hg-2)*jyx2[j].id*jyx2[j].num)%10007,r+=jyx2[j].id,t+=jyx2[j].num;
ans=(ans+(r%10007)*(t%10007))%10007;
}
}
cout<<ans%10007;
return 0;
}

1

sslz-grh LV 7 @ 2017-09-08 01:45:13

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<map>
using namespace std;
long long n,m,ans=0;
struct locin{
long long color=0,num,id;
}jyx1[100010],jyx2[100010];
void jyxin(long long &x)
{
char c=getchar();
x=0;
while(c>'9'||c<'0')c=getchar();
while(c<='9'&&c>='0')x=x*10+c-48,c=getchar();
}
int comp(const locin &a,const locin &b)
{
return a.color<b.color;
}
int main()
{
long long codif1[100010],codif2[100010];
jyxin(n);
jyxin(m);
long long d1=0,d2=0;
for(int i=1;i<=n;++i)
{
if(i%2==0)jyxin(jyx1[i/2].num);
if(i%2==1)jyxin(jyx2[i/2+1].num);
}
for(int i=1;i<=n;++i)
{
if(i%2==0)jyxin(jyx1[i/2].color),jyx1[i/2].id=i;
if(i%2==1)jyxin(jyx2[i/2+1].color),jyx2[i/2+1].id=i;
}
sort(jyx1+1,jyx1+n/2+1,comp);
sort(jyx2+1,jyx2+n-n/2+1,comp);
for(int i=1;i<=n/2+1;++i)
if(jyx1[i].color!=jyx1[i-1].color)d1++,codif1[d1]=i;
for(int i=1;i<=n-n/2+1;++i)
if(jyx2[i].color!=jyx2[i-1].color)d2++,codif2[d2]=i;
for(int i=1;i<=d1-1;++i)
{
int hg=codif1[i+1]-codif1[i];
if(hg>=2)
{
unsigned long long r=0,t=0;
for(int j=codif1[i];j<=codif1[i+1]-1;++j)
ans=(ans+(hg-2)*jyx1[j].id*jyx1[j].num)%10007,r+=jyx1[j].id,t+=jyx1[j].num;
ans=(ans+(r%10007)*(t%10007))%10007;
}
}
for(int i=1;i<=d2-1;++i)
{
int hg=codif2[i+1]-codif2[i];
if(hg>=2)
{
unsigned long long r=0,t=0;
for(int j=codif2[i];j<=codif2[i+1]-1;++j)
ans=(ans+(hg-2)*jyx2[j].id*jyx2[j].num)%10007,r+=jyx2[j].id,t+=jyx2[j].num;
ans=(ans+(r%10007)*(t%10007))%10007;
}
}
cout<<ans%10007;
return 0;
}

1

sslz-grh LV 7 @ 2017-09-08 01:45:06

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<map>
using namespace std;
long long n,m,ans=0;
struct locin{
long long color=0,num,id;
}jyx1[100010],jyx2[100010];
void jyxin(long long &x)
{
char c=getchar();
x=0;
while(c>'9'||c<'0')c=getchar();
while(c<='9'&&c>='0')x=x*10+c-48,c=getchar();
}
int comp(const locin &a,const locin &b)
{
return a.color<b.color;
}
int main()
{
long long codif1[100010],codif2[100010];
jyxin(n);
jyxin(m);
long long d1=0,d2=0;
for(int i=1;i<=n;++i)
{
if(i%2==0)jyxin(jyx1[i/2].num);
if(i%2==1)jyxin(jyx2[i/2+1].num);
}
for(int i=1;i<=n;++i)
{
if(i%2==0)jyxin(jyx1[i/2].color),jyx1[i/2].id=i;
if(i%2==1)jyxin(jyx2[i/2+1].color),jyx2[i/2+1].id=i;
}
sort(jyx1+1,jyx1+n/2+1,comp);
sort(jyx2+1,jyx2+n-n/2+1,comp);
for(int i=1;i<=n/2+1;++i)
if(jyx1[i].color!=jyx1[i-1].color)d1++,codif1[d1]=i;
for(int i=1;i<=n-n/2+1;++i)
if(jyx2[i].color!=jyx2[i-1].color)d2++,codif2[d2]=i;
for(int i=1;i<=d1-1;++i)
{
int hg=codif1[i+1]-codif1[i];
if(hg>=2)
{
unsigned long long r=0,t=0;
for(int j=codif1[i];j<=codif1[i+1]-1;++j)
ans=(ans+(hg-2)*jyx1[j].id*jyx1[j].num)%10007,r+=jyx1[j].id,t+=jyx1[j].num;
ans=(ans+(r%10007)*(t%10007))%10007;
}
}
for(int i=1;i<=d2-1;++i)
{
int hg=codif2[i+1]-codif2[i];
if(hg>=2)
{
unsigned long long r=0,t=0;
for(int j=codif2[i];j<=codif2[i+1]-1;++j)
ans=(ans+(hg-2)*jyx2[j].id*jyx2[j].num)%10007,r+=jyx2[j].id,t+=jyx2[j].num;
ans=(ans+(r%10007)*(t%10007))%10007;
}
}
cout<<ans%10007;
return 0;
}

1

sslz-grh LV 7 @ 2017-09-08 01:45:00

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<map>
using namespace std;
long long n,m,ans=0;
struct locin{
long long color=0,num,id;
}jyx1[100010],jyx2[100010];
void jyxin(long long &x)
{
char c=getchar();
x=0;
while(c>'9'||c<'0')c=getchar();
while(c<='9'&&c>='0')x=x*10+c-48,c=getchar();
}
int comp(const locin &a,const locin &b)
{
return a.color<b.color;
}
int main()
{
long long codif1[100010],codif2[100010];
jyxin(n);
jyxin(m);
long long d1=0,d2=0;
for(int i=1;i<=n;++i)
{
if(i%2==0)jyxin(jyx1[i/2].num);
if(i%2==1)jyxin(jyx2[i/2+1].num);
}
for(int i=1;i<=n;++i)
{
if(i%2==0)jyxin(jyx1[i/2].color),jyx1[i/2].id=i;
if(i%2==1)jyxin(jyx2[i/2+1].color),jyx2[i/2+1].id=i;
}
sort(jyx1+1,jyx1+n/2+1,comp);
sort(jyx2+1,jyx2+n-n/2+1,comp);
for(int i=1;i<=n/2+1;++i)
if(jyx1[i].color!=jyx1[i-1].color)d1++,codif1[d1]=i;
for(int i=1;i<=n-n/2+1;++i)
if(jyx2[i].color!=jyx2[i-1].color)d2++,codif2[d2]=i;
for(int i=1;i<=d1-1;++i)
{
int hg=codif1[i+1]-codif1[i];
if(hg>=2)
{
unsigned long long r=0,t=0;
for(int j=codif1[i];j<=codif1[i+1]-1;++j)
ans=(ans+(hg-2)*jyx1[j].id*jyx1[j].num)%10007,r+=jyx1[j].id,t+=jyx1[j].num;
ans=(ans+(r%10007)*(t%10007))%10007;
}
}
for(int i=1;i<=d2-1;++i)
{
int hg=codif2[i+1]-codif2[i];
if(hg>=2)
{
unsigned long long r=0,t=0;
for(int j=codif2[i];j<=codif2[i+1]-1;++j)
ans=(ans+(hg-2)*jyx2[j].id*jyx2[j].num)%10007,r+=jyx2[j].id,t+=jyx2[j].num;
ans=(ans+(r%10007)*(t%10007))%10007;
}
}
cout<<ans%10007;
return 0;
}

1

205610760 LV 8 @ 2016-11-12 20:47:21

register开不开吧。。反正没有优化hhhhhhhh一定要记得不要多开变量hhhhh尤其是unsigned long long。。（不然会被卡一个点。。。所以我开了#define）。。
思路没什么可说的。。y-x=z-y这个式子化简一下得到y=(x+z)/2。。然后我们发现x，y，z都是整数（废话，题目已知），然后发现跟y的大小没关系。。只要是x+z是偶数就行了。。然后我们发现奇数＋奇数＝偶数、偶数＋偶数＝奇数。。然后我们需要维护一下每一组color的位置顺序。。分成两拨来维护：位置处于奇数上的、位置处于偶数上的。然后就暴力就ok。。
然而这道题考查的方面就两个：1.审题（当初看错题了。。搞成了O（m*20*20*logn）的复杂度。。。）2.优化常数（比如说color的奇数偶数分拨处理。。如果你要是弄成了一个数组那么就是O(2n)，如果按照这么搞的话貌似是O（n）。。等等貌似这不是重点！）
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <vector>

using namespace std;

int n,m;
unsigned long long ans;
#define x (unsigned long long)colors[i][t][j]
#define z colors[i][t][k]
int color,num[200000];
vector<int>colors[200000][2];

int main(){
scanf("%d%d",&n,&m);
for(register int i=1;i<=n;i++)
scanf("%d",&num[i]);
for(register int i=1;i<=n;i++)
colors[scanf("%d",&color),color][i&1].push_back(i);
for(register int i=1;i<=m;i++)
for(register char t=0;t<2;t++)
for(register int j=0;j<colors[i][t].size();j++)
for(register int k=j+1;k<colors[i][t].size();k++)
if(x<z)(ans=(ans+((x+z)*(num[x]+num[z])))%10007);
printf("%lld\n",ans);
}

1

caesar_199 LV 9 @ 2016-08-14 20:44:27

#include<iostream>
#include<cstdio>
#include<vector>
using namespace std;

const int MOD = 10007;
const int maxn = 100000 + 10;
const int maxm = 100000 + 10;
typedef long long LL;

struct Block {
    int id, number;
    Block (int a, int b) : id(a), number(b) {}
};

int plus_mod (int a, int b) {
    return (a+b) % MOD;
}

int n, m;
int numbers[maxn];
vector<Block> blocks[maxm];

int main ()
{
    cin >> n >> m;
    
    for (int i = 0; i < n; i++) scanf("%d", &numbers[i]);
    for (int i = 0; i < n; i++) {
        int color; scanf("%d", &color); color--;
        blocks[color].push_back(Block(i+1, numbers[i]));
    }
    
    int ans = 0;
    for (int color = 0; color < m; color++) {
        int odd_cnt = 0, odd_tot_x = 0, odd_tot_xnx = 0, odd_tot_nx = 0;
        int even_cnt = 0, even_tot_x = 0, even_tot_xnx = 0, even_tot_nx = 0;
        for (int i = 0; i < blocks[color].size(); i++) 
            if (blocks[color][i].id & 1) {
                odd_cnt++; 
                odd_tot_nx = plus_mod(odd_tot_nx, blocks[color][i].number);
                odd_tot_x = plus_mod(odd_tot_x, blocks[color][i].id);
                odd_tot_xnx = plus_mod(odd_tot_xnx, (LL)blocks[color][i].number*blocks[color][i].id%MOD);
            }
            else {
                even_cnt++;
                even_tot_nx = plus_mod(even_tot_nx, blocks[color][i].number);
                even_tot_x = plus_mod(even_tot_x, blocks[color][i].id);
                even_tot_xnx = plus_mod(even_tot_xnx, (LL)blocks[color][i].number*blocks[color][i].id%MOD);
            }
        
         ans = plus_mod(ans, plus_mod((LL)odd_tot_xnx*(odd_cnt-2)%MOD, (LL)odd_tot_nx*odd_tot_x%MOD));
         ans = plus_mod(ans, plus_mod((LL)even_tot_xnx*(even_cnt-2)%MOD, (LL)even_tot_nx*even_tot_x%MOD));
    }
    cout << ans;
    return 0;
}

0

c-- LV 8 @ 2017-06-29 18:40:23

#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;
struct Flag
{
long long num;
long long value;
long long color;
};
bool cmp(Flag a,Flag b)
{
if(a.color<b.color)
return true;
if(a.color>b.color)
return false;
if(a.num>b.num)
return false;
else
return true;

}
struct S
{
long long n;
vector<long long> a;
vector<long long> v;
S()
{
n=0;
}
};
int main ()
{
long long n,m,count=0;
cin>>n>>m;
Flag flags[n];
S s1[m+1];
for(long long i=0;i<n;i++)
{
cin>>flags[i].value;
flags[i].num=i+1;
}
for(long long i=0;i<n;i++)
cin>>flags[i].color;
sort(flags,flags+n,cmp);
for(long long i=0;i<n;i++)
{
s1[flags[i].color].a.push_back(flags[i].num);
s1[flags[i].color].v.push_back(flags[i].value);
s1[flags[i].color].n++;
}
for(long long i=1;i<=m;i++)
{

for(long long j1=0;j1<s1[i].n-1;j1++)
for(long long j2=j1+1;j2<s1[i].n;j2++)
if((s1[i].a[j1]+s1[i].a[j2])%2==0)
count+=(s1[i].a[j1]+s1[i].a[j2])*(s1[i].v[j1]+s1[i].v[j2]);
if(count>=10007)
count%=10007;
}
cout<<count;
}

0

feidaoluoye LV 9 @ 2016-12-05 21:45:04

#include<iostream>
#include<cstring>
#include<cstdio>
#include<vector>
#define maxa 150100
#define inf 10007
using namespace std;
int a[maxa],c[maxa];
typedef long long ll;
ll ans = 0;
vector<int> v[maxa];
int main()
{
int n,m,i,j,x,y,k;
scanf("%d%d",&n,&m);
for(i=1;i<=n;++i)
scanf("%d",&(a[i]));
for(i=1;i<=n;++i)
scanf("%d",&(c[i]));
for(i=1;i<=n;++i)
v[c[i]].push_back(i);
for(i=1;i<=m;++i)
if(v[i].size()>1)
{
for(j=0;j<v[i].size();++j)
{
for(k=j+1;k<v[i].size();++k)
{
x = v[i][j];
y =v[i][k];
if((x+y)%2==0)
{
int t = x+y;
int s = a[x]+a[y];
int tot = (t%inf)*(s%inf)%inf;
ans+=tot%inf;
ans = ans%inf;
}
}
}
}
printf("%lld\n",ans);
return 0;
}
怪怪的

0

linhui LV 9 @ 2016-11-04 13:17:35

#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstring>
#include <iostream>
#include <vector>
using namespace std;
typedef long long LL;
const int M = 100000 + 5;
const int MOD = 10007;

int num[M];
vector<int> col[M], a, b;

int clac(){
int res = 0, sum = 0;
int lena = a.size(), lenb = b.size();
if(lena > 1){
for(int i = 0; i < lena; i++)
sum = (sum + num[a[i]]) % MOD;
for(int i = 0; i < lena; i++){
LL bri = (LL)a[i] * (LL)num[a[i]] * (LL)(lena - 2);
bri %= MOD;
res = (res + bri) % MOD;
res = (res + sum * a[i]) % MOD;
}
}
if(lenb > 1){
sum = 0;
for(int i = 0; i < lenb; i++)
sum = (sum + num[b[i]]) % MOD;
for(int i = 0; i < lenb; i++){
LL bri = (LL)b[i] * (LL)num[b[i]] * (LL)(lenb - 2);
bri %= MOD;
res = (res + bri) % MOD;
res = (res + sum * b[i]) % MOD;
}
}
return (res + MOD) % MOD;
}

int main()
{
int n, m, ans = 0;
scanf("%d%d", &n, &m);
for(int i = 1; i <= n; i++)
scanf("%d", &num[i]);
for(int i = 1; i <= n; i++){
int x;
scanf("%d", &x);
col[x].push_back(i);
}
for(int i = 1; i <= m; i++){
a.clear();
b.clear();
for(int j = 0; j < col[i].size(); j++){
int x = col[i][j];
if(x & 1)
a.push_back(x);
else
b.push_back(x);
}
ans = (ans + clac()) % MOD;
}
printf("%d", ans);
return 0;
}
math

0

Tokgo LV 4 @ 2016-07-24 11:26:33

/*Tokgo*/
#include <iostream>
#include <vector>
using namespace std;
int ans;
int main()
{
    int m,n,i,j,k;
    cin>>n>>m;
    int color[n+1],number[n+1];
    for(i=1;i<=n;++i) cin>>number[i];
    for(i=1;i<=n;++i) cin>>color[i];
    vector <int> save[m+1];
    for(i=1;i<=n;++i)
        save[color[i]].push_back(i);
    for(i=1;i<=m;++i){ 
        if(save[i].size()){
             for(j=0;j<save[i].size()-1;++j){ 
                 for(k=j+1;k<save[i].size();++k){  
                    if((save[i].at(j)+save[i].at(k))%2==0){ 
                        ans+=((save[i].at(j)+save[i].at(k))%10007)*((number[save[i].at(j)]+number[save[i].at(k)])%10007);
                        ans%=10007;
                    }
                  }
            }
        }
    }
    cout<<ans; 
    return 0;
}

0

王一鸣 LV 7 @ 2016-06-10 21:15:30

代码

var n,m,i,sum:longint;
num,color,t,tc,tn,tm:array[1..100000]of Int64;

begin
read(n,m);
for i:=1 to n do
read(num[i]);
for i:=1 to n do
read(color[i]);
fillchar(t,sizeof(t),0);
fillchar(tc,sizeof(tc),0);
fillchar(tn,sizeof(tn),0);
fillchar(tm,sizeof(tm),0);
sum:=0;
i:=1;
while i<=n do
begin
inc(t[color[i]]);
inc(tc[color[i]],i*num[i]);
inc(tn[color[i]],num[i]);
inc(tm[color[i]],i);
inc(i,2);
end;
for i:=1 to m do
if t[i]>1 then
sum:=(sum+(t[i]-2)*tc[i]+tn[i]*tm[i])mod 10007;
fillchar(t,sizeof(t),0);
fillchar(tc,sizeof(tc),0);
fillchar(tn,sizeof(tn),0);
fillchar(tm,sizeof(tm),0);
i:=2;
while i<=n do
begin
inc(t[color[i]]);
inc(tc[color[i]],i*num[i]);
inc(tn[color[i]],num[i]);
inc(tm[color[i]],i);
inc(i,2);
end;
for i:=1 to m do
if t[i]>1 then
sum:=(sum+(t[i]-2)*tc[i]+tn[i]*tm[i])mod 10007;
writeln(sum);
end.

题解

30 条题解

求和

信息

状态

开发

支持

题解

30 条题解

求和

信息

状态

开发

支持

还没有账户？

登录