/ Vijos / 题库 / 求和 /

题解

28 条题解

  • 3
    @ 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

    • @ 2016-08-22 21:18:51

      orz大神

    • @ 2016-11-17 19:23:12

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

  • 1
    @ 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
    @ 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
    @ 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
    @ 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
    @ 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
    @ 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
    @ 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
    @ 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
    @ 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
    @ 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
    @ 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
    @ 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
    @ 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
    @ 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
    @ 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
    @ 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
    @ 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.

  • 0
    @ 2015-12-08 22:10:07

    #include <cstdio>
    2 #include <cstring>
    3
    4 int color[100005], num[100005], next[100005], n, m, c;
    5
    6 int main(int argc, char *argv[]){
    7 scanf("%d%d", &n, &m);
    8 for(int i = 1; i <= n; ++i){
    9 scanf("%d", &num[i]);
    10 }

    11 memset(color, -1, sizeof(color));
    12 for(int i = 1; i <= n; ++i){
    13 scanf("%d", &c);
    14 next[c] = color[c];
    15 color[c] = i;
    16 }

    17 int s = 0;
    18 for(int i = 1; i <= m; ++i){
    19 for(int z = color[i]; z != -1; z = next[z]){
    20 for( int x = next[z]; x != -1; x = next[x]){
    21 if((x + z) % 2 == 0 ){
    22 s += (x + z) % 10007 * (num[x] + num[z]) % 10007;;
    23 }

    24 }

    25 }

    26 }

    27 printf("%d", s);
    28 return 0;
    29 }

    ~

    ~

    ~

    ~

    ~

    ~

    ~

    ~

    ~

    ~

    ~

    ~

    ~

  • 0
    @ 2015-12-07 08:59:33

    #include<iostream>
    #include<cmath>
    #include<cstdio>
    #include<cstring>
    #include<algorithm>
    using namespace std;
    int n,m,s[100005],y[100005],ans,sb[100005][2],bian[100005][2],sbsbsbsb[100005][2],duang[100005][2];
    int main()
    {
    freopen("p.in","r",stdin);
    freopen("p.out","w",stdout);
    cin>>n>>m;
    for(int i=1;i<=n;i++)
    {
    scanf("%d",&s[i]);
    s[i]=s[i]%10007;
    }
    for(int i=1;i<=n;i++)
    {
    scanf("%d",&y[i]);
    sb[y[i]][i%2]+=s[i];
    sb[y[i]][i%2]%=10007;
    bian[y[i]][i%2]+=i;
    bian[y[i]][i%2]%=10007;
    sbsbsbsb[y[i]][i%2]++;
    duang[y[i]][i%2]+=(i*s[i])%10007;
    duang[y[i]][i%2]%=10007;
    //printf("%d %d %d %d\n",sb[y[i]][i%2],bian[y[i]][i%2],sbsbsbsb[y[i]][i%2],duang[y[i]][i%2]);
    }
    for(int i=1;i<=m;i++)
    {
    if(sbsbsbsb[i][0]>=2)
    {
    ans+=(sbsbsbsb[i][0]-2)%10007*duang[i][0];
    ans%=10007;
    }
    if(sbsbsbsb[i][1]>=2)
    {
    ans+=(sbsbsbsb[i][1]-2)%10007*duang[i][1];
    ans%=10007;
    }
    }
    for(int i=1;i<=m;i++)
    {
    if(sbsbsbsb[i][0]>=2)
    {
    ans=ans+(bian[i][0]*sb[i][0])%10007;
    ans%=10007;
    }
    if(sbsbsbsb[i][1]>=2)
    {
    ans=ans+(bian[i][1]*sb[i][1])%10007;
    ans%=10007;
    }
    //cout<<bian[i][1]<<' '<<sb[i][1]<<endl;
    }
    cout<<ans;
    return 0;
    }

信息

ID
1976
难度
8
分类
(无)
标签
递交数
2950
已通过
380
通过率
13%
上传者