/ Vijos / 题库 / 求和 /

题解

30 条题解

  • 3
    @ 9 年前

    测试数据 #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.

  • 1
    @ 2 年前

    记得使用万能头文件 #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;
    }

    Copy
  • 1
    @ 3 年前 
    #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;
}
    Copy
  • 1
    @ 6 年前 
    /*
一道有趣的题目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;
}
    Copy
  • 1
    @ 7 年前

    #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
    @ 7 年前

    #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
    @ 7 年前

    #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
    @ 7 年前

    #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
    @ 7 年前

    #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
    @ 7 年前

    #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
    @ 7 年前

    #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
    @ 7 年前

    #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
    @ 7 年前

    #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
    @ 8 年前

    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
    @ 8 年前 
    #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;
}
    Copy
  • 0
    @ 7 年前

    #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
    @ 8 年前

    #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
    @ 8 年前

    #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
    @ 8 年前 
    /*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;
}
    Copy
  • 0
    @ 8 年前

    代码

    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.

求和

信息

ID
1976
难度
8
分类
(无)
标签
递交数
3004
已通过
401
通过率
13%
被复制
17
上传者
  1. 关于
  2. 联系我们
  3. 隐私
  4. 服务条款
  5. 版权申诉
  6. Language
  1. © 2005 - 2023 Vijos.org
  2. uibuild-2f1065f
  3. 沪ICP备14040537号-1