@[M_WHY](/space/show?uid=71130) 太强啦
by M_sea @ 2018-09-15 15:08:29
竟然又是一个来打魔法阵暴力的……
主过程如下:
```cpp
inline void print(int x){//我还加了个inline真是不知道怎么想的
if(x>=10)print(x/10);
putchar(x%10+'0');
}//快速输出
int main(){
scanf("%d%d",&n,&m);
for(register int i=1;i<=m;++i){
scanf("%d",&v[i]);
maxn=maxn>v[i]?maxn:v[i];
w[v[i]]++;//桶排序
}
for(register int i=1;i<=maxn;i++){
if(w[i]){
k[++tot]=i;
sum[i]=w[i];//权值存储至k数组
}
}
for(register int i=1;i<=tot;++i){//register
for(register int j=i+1;j<=tot;++j){//register
if(((k[j]-k[i])&1)==1)continue;//等价于(k[j]-k[i])%2==1
int tmp=(k[j]-k[i])>>1;//>>1等价于/2
if(7*tmp+k[j]>=maxn)break;//7*tmp为更紧的上界,因为k[e]至少要比k[j]大(6+1)*tmp。
for(register int g=j+1;g<=tot;++g){//register
if(k[g]-k[j]<=6*tmp)continue;
if(tmp+k[g]>maxn)break;
e=lower_bound(k+g+1,k+tot+1,k[g]+tmp)-k;//二分
if(k[e]-k[g]!=tmp)continue;
t=sum[k[i]]*sum[k[j]]*sum[k[g]]*sum[k[e]];
s[k[i]][0]+=t/sum[k[i]];
s[k[j]][1]+=t/sum[k[j]];
s[k[g]][2]+=t/sum[k[g]];
s[k[e]][3]+=t/sum[k[e]];
}
}
}
for(register int i=1;i<=m;++i){
for(register int j=0;j<4;++j)print(s[v[i]][j]),putchar(' ');//快速输出&s数组存对应值的次数
printf("\n");
}
}
```
这个是[我的博客](https://www.luogu.org/blog/52913/special-program)里的暴力的例子……
by CreeperK @ 2018-09-15 15:09:07
@[白井黑子1](/space/show?uid=52913) 然而我甚至还没有理解题解是怎么推出9*t的..也就没敲桶排序了..
by M_WHY @ 2018-09-15 15:16:59
@[M_WHY](/space/show?uid=71130) 我的那个是85分暴力……跟您的应该差不多
by CreeperK @ 2018-09-15 15:21:30
大佬
by orzzzzzzzzzzzzzzz @ 2018-09-16 21:04:56
75分dfs回溯了解一下
by jinhaoxian @ 2018-10-07 11:11:29
#include <bits/stdc++.h>
using namespace std;
int n, m;
vector <int> a;
vector <int> num;
int ans[4][40001];
int main()
{
// freopen("magic.in", "r", stdin);
// freopen("magic.out", "w", stdout);
scanf("%d%d", &n, &m);
a.resize(m);
num.resize(n + 1);
for(int i = 0; i < m; i++)
{
scanf("%d", &a[i]);
num[a[i]]++;
}
for(int i = 0; i <= n; i++)
{
if (num[i] == 0) continue;
for (int j = i + 1; j <= n; j++)
{
if (num[j] == 0) continue;
if ((j - i) % 2 == 1) continue;
for (int k = j + (j - i) * 3 + 1; k <= n; k++)
{
if (num[k] == 0) continue;
int q = k + (j - i) / 2;
if (num[q] == 0) continue;
if (q > n) continue;
ans[0][i] += num[j] * num[k] * num[q];
ans[1][j] += num[i] * num[k] * num[q];
ans[2][k] += num[i] * num[j] * num[q];
ans[3][q] += num[i] * num[j] * num[k];
}
}
}
for (int i = 0; i < m; i++)
{
printf("%d %d %d %d\n", ans[0][a[i]], ans[1][a[i]], ans[2][a[i]], ans[3][a[i]]);
}
return 0;
}
by MaxWhite @ 2018-11-09 18:42:35
@[白井黑子1](/space/show?uid=52913)
哟我也是
by Barry_Wang @ 2018-11-09 20:46:26