XJOI网上同步训练DAY3 T1

思路:看来我真是思博了，这么简单的题目居然没想到，而且我对复杂度的判定也有点问题。。

首先我们选了一个位置i的b，那一定只对i和以后的位置造成改变，因此我们可以这样看:

我们从前往后选，发现一个位置的s和r相等，然后我们就选这个位置的bi，由于bi会改变当前位置，因此当前位置的vi我们就能吃到了。所以，每个位置的vi我们都能拿到，所以答案就是Σvi,然后只要模拟过去就可以了。。

我真是太弱鸡了。。还有这个算法的复杂度是O(N^1.5)，我一直以为是O(N^2)。。

 #include<cstdio>

 #include<cmath>

 #include<iostream>

 #include<algorithm>

 #include<cstring>

 #define ll long long

 ll sum,r[],s[];

 int n,b[],v[],ans[],d[];

 ll read(){

     ll t=,f=;char ch=getchar();

     while (ch<''||ch>'') {if (ch=='-') f=-;ch=getchar();}

     while (''<=ch&&ch<=''){t=t*+ch-'';ch=getchar();}

     return t*f;

 }

 int main(){

     n=read();

     for (int i=;i<=n;i++) b[i]=read();

     for (int i=;i<=n;i++) r[i]=read();

     for (int i=;i<=n;i++) v[i]=read(),sum+=v[i];

     for (int i=;i<=n;i++)

      for (int j=i;j<=n;j+=i)

       d[j]++;

     for (int i=;i<=n;i++)

      if (s[i]==r[i])  {

             ans[i]=;

             for (int j=n/i;j>=;j--)

              s[i*j]+=(ll)b[i]*d[j];

      }

     printf("%lld\n",sum);

     for (int i=;i<=n;i++) printf("%d ",ans[i]);

 }

秒客网

XJOI网上同步训练DAY3 T1

相关文章