/ Vijos / 题库 / 求和 /

题解

30 条题解

  • 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;
    }

  • 0
    @ 2015-12-03 07:53:37

    #include <cstdio>
    #include <iostream>
    using namespace std;
    long long s[100050][2],ss[100050][2],sss[100050][2],ssss[100050][2],ans=0;
    int e[100050],c[100050];
    const int q=10007;
    int main() {
    int n,m,i,tc,fdc;
    freopen("sum.in","r",stdin);
    freopen("sum.out","w",stdout);
    scanf("%d%d",&n,&m);
    for (i=1;i<=n;i++) scanf("%d",&e[i]);
    for (i=1;i<=n;i++) scanf("%d",&c[i]);

    for (i=1;i<=n;i++) {
    tc=c[i]; fdc=i %2;
    if (ssss[tc][fdc]>0) ans=1LL*ans + 1LL*s[tc][fdc] + 1LL*i*ss[tc][fdc] + 1LL*sss[tc][fdc]*e[i] + 1LL*ssss[tc][fdc]*i*e[i];
    s[tc][fdc]=1LL*s[tc][fdc]+1LL*i*e[i];
    ss[tc][fdc]=1LL*ss[tc][fdc]+1LL*e[i];
    sss[tc][fdc]=1LL*sss[tc][fdc]+1LL*i;
    ssss[tc][fdc]=1LL*ssss[tc][fdc]+1LL;
    }

    cout << ans % q;
    }

  • 0
    @ 2015-11-27 13:37:28

    我就说怎么只对前四个点,仔细一看发现乘法会使int溢出...

  • 0
    @ 2015-11-23 18:56:04

    车神恒妹儿fromslyz说不开longlong会爆,yveh%%%orz因为我真的爆了,但有什么关系呢,反正我现在AC了

    #include<cstdio>
    #include<cstring>
    #include<algorithm>
    using namespace std;
    long long n,color[100003],number[100003],num[200003],sum[200003],sc1[200003];
    long long m,sc2[200003],ss[200003];
    bool p[200003];
    int main()
    {
    scanf("%I64d %I64d\n",&n,&m);
    long long i,k,ans=0;
    for (i=1;i<=n;++i) scanf("%I64d",&number[i]);
    for (i=1;i<=n;++i) scanf("%I64d",&color[i]);
    memset(p,0,sizeof(p));
    memset(ss,0,sizeof(ss));
    memset(sc1,0,sizeof(sc2));
    memset(sc2,0,sizeof(sc2));
    memset(sum,0,sizeof(sum));
    memset(num,0,sizeof(num));
    for (i=1;i<=n;++i)
    {
    k=color[i]*2+i%2;
    if (p[k]==0)
    {
    p[k]=1; num[k]=1;
    sc1[k]=number[i]; sc2[k]=i;
    ss[k]=sc1[k]*sc2[k];
    }
    else
    {
    sum[k]=(sum[k]+((number[i]*i)%10007*num[k])%10007)%10007;
    sum[k]=(sum[k]+(number[i]*sc2[k])%10007+(i*sc1[k])%10007)%10007;
    sum[k]=(sum[k]+ss[k])%10007;
    ss[k]=(ss[k]+(number[i]*i)%10007)%10007;
    num[k]++;
    sc1[k]=(sc1[k]+number[i])%10007; sc2[k]=(sc2[k]+i)%10007;
    }
    }
    for (i=1;i<=m*2+1;++i)
    if (num[i]>1)
    ans=(ans+sum[i])%10007;
    printf("%I64d\n",ans);
    return 0;
    }

  • 0
    @ 2015-11-23 18:55:18

    #include <iostream>
    #include <stdio.h>
    #include <string.h>
    #include <stdlib.h>
    #include <math.h>
    using namespace std;
    int i,j,n,m,va[100010],xx,gs[2][100010],xhl[2][100010]; long long zz;
    long long lj[4][100010];
    long long kal,p;
    int main()
    {
    scanf("%d%d",&n,&m);
    for (i=1; i<=n; i++) scanf("%d",&va[i]);
    for (i=1; i<=n; i++)
    {
    scanf("%d",&xx);
    kal=lj[i%2+2][xx]; kal%=10007;
    zz=xhl[i%2][xx]; zz*=va[i];
    kal+=zz; kal%=10007;
    zz=lj[i%2][xx]; zz%=10007; zz*=i;
    kal+=zz; kal%=10007;
    zz=gs[i%2][xx]; zz%=10007; zz*=i; zz%=10007; zz*=va[i];
    kal+=zz; kal%=10007;
    p+=kal; p=p%10007;
    lj[i%2][xx]+=va[i]; gs[i%2][xx]++; xhl[i%2][xx]+=i;
    zz=va[i]; zz*=i; lj[i%2+2][xx]+=zz;
    }
    printf("%I64d",p);
    return 0;
    }

  • 0
    @ 2015-11-20 17:29:44

    哎呀,看了题解,码了半天,过了不容易!

    type arr1=array[0..100000,0..1]of longint;

    var n,m,i,j,tot,r,k,color:longint;sumi,sum,sumnum,count:arr1;

    number:array[0..100000]of longint;

    begin

    readln(n,m);tot:=0;

    for i:=1 to n do read(number[i]);

    readln;

    for i:=1 to n do
    begin
    read(color);

    inc(count[color,i mod 2]);

    sumi[color,i mod 2]:=(sumi[color,i mod 2]+i)mod 10007;

    sumnum[color,i mod 2]:=(sumnum[color,i mod 2]+number[i])mod 10007;

    sum[color,i mod 2]:=(sum[color,i mod 2]+number[i]mod 10007 *i)mod 10007;

    end;
    for i:=1 to n do

    for j:=0 to 1 do

    if count[i,j]>1 then

    tot:=(tot+sum[i,j]*(count[i,j]-2)+sumi[i,j]*sumnum[i,j])mod 10007;

    writeln(tot mod 10007);

    end.

  • 0
    @ 2015-11-15 11:27:57

    其实对于三元组(x,y,z)根本不需要管y,只要x与z同奇或者同偶并且colour[x]==colour[z](x!=z)就可以满足
    纯粹公式,扫一遍就A了···然而之前多写一句废话一直wa

    从前往后扫的话,对于编号i,颜色colour[i]的点,那么它与它前面所有和它同奇偶的编号为j,颜色为coulur[i]的三元组的和可以表示为i*(前面所有number[j]的和)+number[i]*(前面所有j的和)+(前面所有number[j]*j)+(前面所有颜色为colour[i]的点的个数)*i*number[i]

    相当于把三元组的分数的(x+z)*(number[x]+number[z])拆成number[x]*x+number[x]*z+number[z]*x+number[z]*z

    如果前面有n个符合的点,那么就是number[x1]*x1+number[x2]*x2+···+number[xn]*xn///分割线///+(number[x1]+number[x2]+···+number[xn])*z///分割线///+(x1+x2+···+xn)*number[z]///分割线///+n*(number[z]*z)

    ps:和楼下的楼下的楼下差不多,可以去看详细解释

    #include<iostream>
    #include<cstdio>
    #include<cstring>
    using namespace std;
    struct hehe{
    long long w1,w2,w3,w4;
    };
    hehe a[2][100005];
    long long number[100005],colour[100005];
    long long ans=0,n,m;
    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",&colour[i]);
    for (int i=1;i<=n;i++){
    ans=(ans+((long long)a[i%2][colour[i]].w1*(long long)number[i])%10007+((long long)a[i%2][colour[i]].w2*(long long)i)%10007+a[i%2][colour[i]].w3+((long long)a[i%2][colour[i]].w4*(long long)(((long long)number[i]*(long long)i)%10007))%10007)%10007;
    a[i%2][colour[i]].w1=(a[i%2][colour[i]].w1+i)%10007;
    a[i%2][colour[i]].w2=(a[i%2][colour[i]].w2+number[i])%10007;
    a[i%2][colour[i]].w3=(a[i%2][colour[i]].w3+((long long)number[i]*(long long)i)%10007)%10007;
    a[i%2][colour[i]].w4=(a[i%2][colour[i]].w4+1)%10007;
    }
    printf("%d",ans%10007);
    }

  • 0
    @ 2015-11-09 08:27:32

    考试时我没把题目写出来,回来后我想到这样写:
    ∵x,y,z之间的差b为等值
    ∴可以用等差数列的想法去写
    用一条for语句确定x的值,就能得到,y和z
    再加上b的值和colour的判断。

  • -1
    @ 2016-11-02 07:37:18

    评测结果

    编译成功

    测试数据 #0: Accepted, time = 15 ms, mem = 2128 KiB, score = 10

    测试数据 #1: Accepted, time = 0 ms, mem = 2128 KiB, score = 10

    测试数据 #2: Accepted, time = 0 ms, mem = 2124 KiB, score = 10

    测试数据 #3: Accepted, time = 0 ms, mem = 2120 KiB, score = 10

    测试数据 #4: Accepted, time = 250 ms, mem = 2124 KiB, score = 10

    测试数据 #5: Accepted, time = 265 ms, mem = 2128 KiB, score = 10

    测试数据 #6: TimeLimitExceeded, time = 1031 ms, mem = 2128 KiB, score = 0

    测试数据 #7: Accepted, time = 359 ms, mem = 2128 KiB, score = 10

    测试数据 #8: Accepted, time = 265 ms, mem = 2124 KiB, score = 10

    测试数据 #9: Accepted, time = 312 ms, mem = 2132 KiB, score = 10

    TimeLimitExceeded, time = 2497 ms, mem = 2132 KiB, score = 90
    代码

    #include<iostream>
    #include<cstring>
    #include<cstdlib>
    #include<cstdio>
    #include<algorithm>
    using namespace std;
    int n,m,cl[100010],sum;
    struct node
    {
    int x,n,c;
    }st[100010];
    bool cmp(node a,node b)
    {
    if(a.c!=b.c) return a.c<b.c;
    else return a.x<b.x;
    }
    int main()
    {
    //freopen("p.in","r",stdin);
    //freopen("p.out","w",stdout);
    cin>>n>>m;
    for(int i=1;i<=n;i++) cin>>st[i].n;
    for(int i=1;i<=n;i++) cin>>st[i].c;
    for(int i=1;i<=n;i++) st[i].x=i;
    sort(st+1,st+1+n,cmp);
    for(int i=1;i<=n;i++)
    {
    if(st[i].c!=st[i+1].c) cl[st[i].c]=i;
    }
    for(int i=1;i<n;i++)
    {
    for(int j=i+1;j<=cl[st[i].c];j++)
    {
    if(st[i].c==st[j].c && (st[j].x-st[i].x)%2==0)
    {
    sum+=((st[i].x+st[j].x)%10007)*((st[i].n+st[j].n)%10007)%10007;
    sum%=10007;
    }
    }
    }
    cout<<sum;
    return 0;
    }

    这样有90分???(手动滑稽

    • @ 2016-11-03 07:31:56

      评测结果

      编译成功

      测试数据 #0: Accepted, time = 0 ms, mem = 2128 KiB, score = 10

      测试数据 #1: Accepted, time = 0 ms, mem = 2124 KiB, score = 10

      测试数据 #2: Accepted, time = 0 ms, mem = 2128 KiB, score = 10

      测试数据 #3: Accepted, time = 0 ms, mem = 2124 KiB, score = 10

      测试数据 #4: Accepted, time = 250 ms, mem = 2128 KiB, score = 10

      测试数据 #5: Accepted, time = 265 ms, mem = 2124 KiB, score = 10

      测试数据 #6: Accepted, time = 906 ms, mem = 2124 KiB, score = 10

      测试数据 #7: Accepted, time = 406 ms, mem = 2128 KiB, score = 10

      测试数据 #8: Accepted, time = 265 ms, mem = 2124 KiB, score = 10

      测试数据 #9: Accepted, time = 265 ms, mem = 2128 KiB, score = 10

      Accepted, time = 2357 ms, mem = 2128 KiB, score = 100
      代码

      #include<iostream>
      #include<cstring>
      #include<cstdlib>
      #include<cstdio>
      #include<algorithm>
      using namespace std;
      int n,m,cl[100010],sum;
      struct node
      {
      int x,n,c;
      }st[100010];
      bool cmp(node a,node b)
      {
      if(a.c!=b.c) return a.c<b.c;
      else return a.x<b.x;
      }
      int main()
      {
      //freopen("p.in","r",stdin);
      //freopen("p.out","w",stdout);
      cin>>n>>m;
      for(int i=1;i<=n;i++) cin>>st[i].n;
      for(int i=1;i<=n;i++) cin>>st[i].c;
      for(int i=1;i<=n;i++) st[i].x=i;
      sort(st+1,st+1+n,cmp);
      for(int i=1;i<=n;i++)
      {
      if(st[i].c!=st[i+1].c) cl[st[i].c]=i;
      }
      for(int i=1;i<n;i++)
      {
      for(int j=i+1;j<=cl[st[i].c];j++)
      {
      if(st[i].c==st[j].c && (st[j].x-st[i].x)%2==0)
      {
      sum+=((st[i].x+st[j].x)%10007)*((st[i].n+st[j].n)%10007)%10007;
      sum%=10007;
      }
      }
      }
      cout<<sum;
      return 0;
      }

      再试一次AC了????exm?????

信息

ID
1976
难度
8
分类
(无)
标签
递交数
3003
已通过
400
通过率
13%
被复制
16
上传者