这次考试还算可以（吧），暴力都没打满，但是还差很多。

T1 强烈推荐我的打法，很好理解（虽然稍长）

  1 #include<cstdio>
  2 #include<iostream>
  3 using namespace std;
  4 const int N=1e8+7e7+9e6+4e5+2e4+5e3;
  5 char v[N+5];
  6 int s[10000000+5],tot,prime[10000000+45];
  7 void pre()
  8 {
  9     for(register int i=2;i<=N;i++)
 10     {
 11         if(!v[i]) prime[++tot]=i;
 12         for(register int j=1;j<=tot&&prime[j]*i<=N;j++)
 13         {
 14             v[i*prime[j]]=1;
 15             if(i%prime[j]==0) break;
 16         }
 17     }
 18     return ;
 19 }
 20 int c[20000001];//维护指向的值，以及该值的第几个数
 21 struct node{
 22     int val,num;
 23     inline void moveleft()
 24     {
 25         if(num>1) {num--;return ;}
 26         num=0;val--;
 27         while(!c[val]) val--;
 28         num=c[val];
 29     }
 30     inline void moveright()
 31     {
 32         if(num<c[val]){num++;return ;}
 33         val++;
 34         while(!c[val]) val++;
 35         num=1;
 36     }
 37     inline void del(int x)
 38     {
 39         if(x==val)
 40         {
 41             if(c[x]<num) moveright();
 42             return ;
 43         }
 44         if(x<val) moveright();
 45     }
 46     inline void add(int x)
 47     {
 48         if(x<val) moveleft();
 49     }
 50 }tl,tr;
 51 int main()
 52 {
 53     pre();
 54     int n,k,w;double ans=0;
 55     scanf("%d%d%d",&n,&k,&w);
 56     for(register int i=1;i<=n;i++) s[i]=(1ll*prime[i]*i)%w;
 57     for(register int i=n;i>=1;i--) s[i]=s[i]+s[i/10+1];
 58     for(register int i=1;i<=k;i++) c[s[i]]++;
 59     if(k&1)
 60     {
 61         int tmp=0;
 62         for(register int i=0;i<=w*2;i++)
 63         {
 64             if(tmp+c[i]>=k/2+1) 
 65             {
 66                 tl.val=i;
 67                 tl.num=k/2+1-tmp;
 68                 break;
 69             }
 70             tmp+=c[i];
 71         }
 72         for(register int i=1;i<=n-k+1;i++)
 73         {
 74             ans+=tl.val;
 75             --c[s[i]],tl.del(s[i]);
 76             if(i+k<=n) ++c[s[i+k]],tl.add(s[i+k]);
 77         }
 78     }
 79     else
 80     {
 81         int tmp=0;
 82         for(register int i=0;i<=w*2;i++)
 83         {
 84             if(!tl.num&&tmp+c[i]>=k/2)
 85                 tl.val=i,tl.num=k/2-tmp;
 86             if(tmp+c[i]>=k/2+1) 
 87             {
 88                 tr.val=i;
 89                 tr.num=k/2+1-tmp;
 90                 break;
 91             }
 92             tmp+=c[i];
 93         }
 94         for(register int i=1;i<=n-k+1;i++)
 95         {
 96             ans+=1.0*(tl.val+tr.val)/2;
 97             --c[s[i]];
 98             tl.del(s[i]);tr.del(s[i]);
 99             if(i+k<=n) ++c[s[i+k]],tl.add(s[i+k]),tr.add(s[i+k]);
100         }
101     }
102     printf("%.1lf",ans);
103 }

View Code