luogu P2119 [NOIP2016 普及组] 魔法阵

我们假设 $X_d-X_c=x$，那么 $X_b-X_a=2\times x$，$X_c-X_b>6\times x$，得到这些关系后，我们可以枚举 $x$，再枚举 $a,d$，发现值域较小，所以用桶来存储，在根据乘法原理算出答案，发现过程中有重复，用前缀和维护即可。

代码

#include <bits/stdc++.h>
using namespace std;
const int N = 50005;
int n, m, a[N], b[N], c[N], d[N], vis[N], x[N];
int main(){
cin >> n >> m;
for(int i = 1; i <= m; i ++)
cin >> x[i], 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; 
}
int pre = 0;
for(int A = n - 9 * t - 1; A >= 1; A --){
int B = A + 2 * t;
int C = B + 6 * t + 1;
int D = A + 9 * t + 1;
pre += vis[C] * vis[D];
a[A] += vis[B] * pre;
b[B] += vis[A] * pre;
} 
}
for(int i = 1; i <= m; i ++)
cout << a[x[i]] << " " << b[x[i]] << " " << c[x[i]] << " " << d[x[i]] << "\n";
return 0;
}

原文地址：https://blog.csdn.net/zc2000911/article/details/136330451

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！