NOIP2016T4 魔法阵

henry_y · 2018-08-01 20:19:11 · 题解

博客阅读效果更佳qwq

很好的一道数学推导题

45分做法

所以②可化为xb-xa=2t ④

将④代入③

移项一下，就变成

由图可得AD=9t+k

所以我们可以尝试着枚举t，用t来表示各个魔法值的值

由上易得t的范围为1<=t<=(n-1)/9

在代码中为了避免除法写成t*9<n

再枚举D，因为我们已经枚举出了t，所以C的值是可以直接算出来的

又因为使A,B,C,D满足条件的k的最小值为1，所以对于当前的C和D，最大的A和B为A=D-9t-1,B=D-7t-1

那么如果A和B更小怎么办？

观察到在其他条件不变的情况下，只要C和B满足Xc-Xb>6t，那么这个魔法阵就一定成立，所以当(a1<a2,b1<b2)时，只要a2和b2能够和C,D组成魔法阵，a1,b1也一定能和C,D组成魔法阵，所以可以使用前缀和优化

然后又由乘法原理可得，当前魔法值作为D物品的个数为SumD=SumA*SumB*SumC

所以我们利用前缀和优化SumA*SumB

C的情况可以顺便在算D的时候算出来

那么还有一个问题是，我们枚举的D的范围是多少？

因为要统计前缀和，所以一定是要顺推下去的，由上面那张图我们可以知道，D的最大值为n，最小值则为当k=1且A=1的时候，所以D的最小值为9*t+2，再小是无法组成魔法阵的

同理可以枚举A

但是这个的情况又和枚举D的情况有一点不同

在其他条件不变的情况下，只要C和B满足Xc-Xb>6t，那么这个魔法阵就一定成立，所以当(c1<c2,d1<d2)时，只要c1和d1能够和A,B组成魔法阵，c2,d2也一定能和A,B组成魔法阵，所以可以使用后缀和优化

因为需要统计后缀和，所以需要逆推

枚举的范围：A的最大值为(n-t*9-1)(因为当k=1，D=n的时候A才最大)，A的最小值则为1

所以就可以算出每个魔法值作为A,B,C,D物品的次数了，输出时直接输出当前魔法物品的魔法值的次数就可以了

#include <cstdio>
#include <algorithm>
using namespace std;
inline int read(){
    int x=0,f=1;char c=getchar();
    while(c<'0'||c>'9'){if(c=='-')f=-f;c=getchar();}
    while(c>='0'&&c<='9'){x=(x<<1)+(x<<3)+c-'0';c=getchar();}
    return x*f;
}
#define N 50010
int n,m;
int a[N],b[N],c[N],d[N];
int x[N],vis[N];
int main(){
    n=read();m=read();
    for(int i=1;i<=m;i++)
        x[i]=read(),vis[x[i]]++;
    for(int t=1;t*9<n;t++){
        int sum=0;
        for(int D=9*t+2;D<=n;D++){
            int A=D-9*t-1;
            int B=A+2*t;
            int C=D-t;
            sum+=vis[A]*vis[B];
            c[C]+=vis[D]*sum;
            d[D]+=vis[C]*sum;
        }
        sum=0;
        for(int A=n-9*t-1;A;A--){
            int B=A+2*t;
            int C=B+6*t+1;
            int D=A+9*t+1;
            sum+=vis[C]*vis[D];
            a[A]+=vis[B]*sum;
            b[B]+=vis[A]*sum;
        }
    }
    for(int i=1;i<=m;i++){
        printf("%d %d %d %d\n",a[x[i]],b[x[i]],c[x[i]],d[x[i]]);
    }
    return 0;
}