T2695 桶哥的问题——吃桶

た入场券 2021-11-09 01:50 249阅读 0赞

**现在这里orz [暗い之殇][Link 1] orz大佬的思路~本蒟蒻看懂了~**

**![1317458-20190725101800136-1745225440.png][]**

### ![1317458-20190725101722283-1238777937.png][] ###

**思路详解**

**题目中告诉了套餐的产生情况，即![1317458-20190725102134402-1981339565.png][]**

**所以将x+y=z-2y化简可得=》z-x=3y**

**因为题目中告诉我们套餐产生的价值为：![1317458-20190725102427101-935367928.png][]**

**由此可以看出，套餐的价值和y的值没有关系，所以不知道y的值也可以。**

**由此可以继续推出满足套餐时的情况，即：x<z且(z-x)%3=0（由z-x=3y得到->两边同时%3（3y%3一定为0）*我一时竟然在这个地方卡壳了*）且ax =az**

**所以这道题就很简单了；**

**Tip：暴力的话就不用三重循环了，直接二重就行了**

**AC代码如下：不是我写的，rqy大佬的奇葩解法，涉及高中知识，看不懂**

1 #include<iostream>
     2 #include<cstdio>
     3 #include<algorithm>
     4 #include<queue>
     5 #include<cstring>
     6 using namespace std;
     7 int a[100005],b[100005],sxbx[100005],sx[100005],sbx[100005],s[100005];
     8 int read()
     9 {
    10     char ch=getchar();
    11     int a=0,x=1;
    12     while(ch<'0'||ch>'9')
    13     {
    14         if(ch=='-') x=-x;
    15         ch=getchar();
    16     }
    17     while(ch>='0'&&ch<='9')
    18     {
    19         a=(a<<3)+(a<<1)+(ch-'0');
    20         ch=getchar();
    21     }
    22     return a*x;
    23 }
    24 int n,m;
    25 long long ans;
    26 const int mod=10007;
    27 int main()
    28 {
    29     n=read();
    30     m=read();
    31     for(int i=1;i<=n;i++) b[i]=read()%mod;             //种类a，美味值b 
    32     for(int i=1;i<=n;i++) a[i]=read();
    33     ans=0;
    34     for(int c=1;c<=3;c++)                              //一共三类：mod(3)=1 / 2 / 3 
    35     {
    36         memset(sxbx,0,sizeof(sxbx));                   //千万不要忘了清零，防止对其他类的影响 
    37         memset(s,0,sizeof(s));
    38         memset(sbx,0,sizeof(sbx));
    39         memset(sx,0,sizeof(sx));
    40         for(int z=c;z<=n;z+=3)                         //解决下标差3的倍数的问题 
    41         {
    42             ans=(ans+sxbx[a[z]])%mod;                  //更新ans值，注意要和z同种 
    43             ans=(ans-z%mod*b[z]%mod*s[a[z]]%mod)%mod;  //这里多mod几遍，可能会爆int 
    44             ans=(ans+z*sbx[a[z]]%mod)%mod;
    45             ans=(ans-b[z]*sx[a[z]]%mod)%mod;
    46             sxbx[a[z]]=(sxbx[a[z]]+z*b[z]%mod)%mod;    //加上z的贡献，注意要和z同种 
    47             s[a[z]]=(s[a[z]]+1)%mod;
    48             sbx[a[z]]=(sbx[a[z]]+b[z])%mod;
    49             sx[a[z]]=(sx[a[z]]+z)%mod;
    50         }
    51     }
    52     cout<<(ans+mod)%mod;                               //防止答案为负数 
    53     return 0;
    54 }

转载于:https://www.cnblogs.com/Michael666/p/11242678.html

[Link 1]: https://www.cnblogs.com/xcg123/
[1317458-20190725101800136-1745225440.png]: /images/20211108/68be52c0e11944be9c8b515169ce0556.png
[1317458-20190725101722283-1238777937.png]: /images/20211108/1ad47f4a1d894112bbebc4b7dd74e25f.png
[1317458-20190725102134402-1981339565.png]: /images/20211108/d1d26159a89b49dc871da50d96361db8.png
[1317458-20190725102427101-935367928.png]: /images/20211108/73943a21866b4f36a221fa306b5f1daa.png