P2119 魔法阵
理解题意
一个无聊的人拿四个物品制造魔法阵,这四个物品满足题目给出的三个式子,输出一个矩阵,记录每个物品作为魔法阵中A,B,C,D物品的次数
稳定情绪
莫得慌,博 主 是 一 个 极 其不负 责 任 的 歪 星 人
题解
Part 1 50‘ 暴力
暴力枚举 四层for循环
首先记录每件物品的魔法值和物品编号(按输入的顺序就好啦)
由于魔法阵的四个物品是按照递增顺序来的,所以按照魔法值从小到大sort一遍
然后四层枚举for循环,check函数判断是否符合题意的三个式子,满足则记录下来每个物品作为魔法阵中对应ABCD物品的次数+1
最后还要按照物品编号排回来,输出每个物品对应作为魔法阵ABCD物品的次数
50‘ 暴力代码
#include<bits/stdc++.h> using namespace std; int n,m; struct node { int x,num; int a,b,c,d; }obj[40010]; bool cmp1(node aa,node bb) { return aa.x <bb.x ; } bool cmp2(node aa,node bb) { return aa.num <bb.num ; } bool check(int aa,int bb,int cc,int dd) { if(obj[aa].x < obj[bb].x &&obj[aa].x < obj[cc].x&&obj[aa].x < obj[dd].x&&obj[bb].x < obj[cc].x &&obj[bb].x < obj[dd].x&&obj[cc].x < obj[dd].x) { if((obj[bb].x -obj[aa].x) ==2*(obj[dd].x -obj[cc].x )) if((obj[bb].x -obj[aa].x)<(obj[cc].x -obj[bb].x )*1.0/3.0) return true; } return false; } int main() { scanf("%d%d",&n,&m); for(int i=1;i<=m;i++) { scanf("%d",&obj[i].x ); obj[i].num=i; } sort(obj+1,obj+m+1,cmp1); for(int i=1;i<=m;i++) for(int j=i+1;j<=m;j++) for(int k=j+1;k<=m;k++) for(int l=k+1;l<=m;l++) { if(check(i,j,k,l)) { obj[i].a ++; obj[j].b ++; obj[k].c ++; obj[l].d ++; } } sort(obj+1,obj+m+1,cmp2); for(int i=1;i<=m;i++) printf("%d %d %d %d ",obj[i].a,obj[i].b,obj[i].c,obj[i].d); return 0; }
然后就hin开心的T成酱紫
Part2 下面谈正解
上面50'暴力之后发现一个问题,n根本没有什么用!!!
那么n真的没有用么??
n看上去是个青铜,其实他已经是个王者啦
实际上这是一个数学推断题
我们来看这三个式子
暗中观察,仔细思索
<1> A B C D四个物品的魔法值是严格递增的
<2> Xd - Xc 是最小单位 ,我们假设它是 t
然后得到以下关系式
Xd - Xc = t
Xb - Xa = 2t
Xc - Xb > 3(Xb-Xa) = 6t
于是我们想到把这些魔法值在一个坐标轴上表示出来(泥萌看n现在有用了吧)
考虑怎样枚举
枚举的话一定要枚举 t
把A,B看成一个整体,当我们知道了A或B中其中一个,就可以准确求出另一个
把C,D看成一个整体,当我们知道了C或D中其中一个,就可以准确求出另一个
so,把暴力枚举A B C D转化为枚举 t A或B C或D
窝枚举 t A D (知三求五)
注意此处枚举的是魔法值:
因为前面三个式子是又魔法值推出来的,窝推出来的枚举也是建立在魔法值的基础上推出来的,所以枚举的都是魔法值鸭
看着这个图:
枚举 t ,最外层枚举
考虑枚举范围: 1 ~ n/9
因为 AD>9t ,A最小为1 ,D最大为n ,最极端的情况就是A在1处,D在n处,9t 一定满足<n
为了避免枚举的时候出现除法,枚举范围就变成了:t:1 ~ 9t<n
枚举D
枚举范围:9t+2 ~ n
(1+9t+1 ~ n)
当我们枚举出了一个 D1 ,就会确定一个C1 (t 在最外层枚举)
那么由于BC的距离并不确定,只知道他们>6t,所以并不能准确地得到A,B
我们先考虑距离C1,D1最近的A1,B1,也就是假设BC之间的距离最小,也就是 6t+1 ,于是乎确定了A1,B1
(所以当BC之间的距离增大怎么办??)
那么当我们继续往后枚举D,得到一个新的D2,新的D2比原来的D1魔法值更大
那么对应的C2 ,B2,A2都会整体在数轴上右移,此时我们发现B1,C2的距离比B2,C2 的更大,那么当然也可以和新的D2构成一个魔法阵
D还会继续往后枚举,启发我们可以维护一个前缀和
由以上推断我们就可以确定出D的枚举顺序:从小到大
同时维护一个前缀和
数组记录实现
d[D]记录 魔法值为D的物品作为魔法阵D物品的次数
(回到图)
对于当前的这个D,数轴对应着A,B,C
但是A,B,C的数量是不确定的(因为题面描述可能会有相同的魔法值,对于这些相同的魔法值处理当然一摸一样)
但是无论取A,B,C中各类的哪一个,都会满足一个合法的魔法阵
由乘法原理可得
d[D]=sum[A]*sum[B]*sum[C]
同理得到C
c[C]=sum[A]*sum[B]*sum[D]
我们枚举D的时候只记录更新D和C,因为由D可以准确确定C,却不能准确确定A和B
由于BC距离不同,我们还要把前缀和维护加进去(就是前面讲到的维护前缀和)
那么式子就变成了:
注意累加(+=)
sum是维护的前缀和
tong 是用桶排序记录了每个魔法值有几个,也就是上面提到的数量不确定
同理,枚举A
枚举范围:A:n-9t-1~1
那么A的枚举顺序就是从大到小
维护后缀和 c,d
输出答案
for(1~m)
对于这m个物品,对应着一个魔法值
对于每一个魔法值,都对应着成为魔法阵A B C D 物品的次数
输出即可
特判
(回到图)
因为t最小是1(递增的ABCD物品),A最小是1
那么n一定要大于10,否则就会无解啊,就找不到d了啊
AC代码了解一下:
变量介绍:
x[ i ] i 物品的魔法值
tong[ i ] 用桶记录魔法值为i的物品的数目
a[ i ] 魔法值为 i 的物品作为魔法阵的A物品的次数
b[ i ] 魔法值为 i 的物品作为魔法阵的B物品的次数
c[ i ] 魔法值为 i 的物品作为魔法阵的C物品的次数
d[ i ] 魔法值为 i 的物品作为魔法阵的D物品的次数
sum 维护的前缀和,后缀和
AC代码
#include<bits/stdc++.h> using namespace std; const int maxn=15010; int n,m; int x[40010],tong[maxn]; int a[maxn],b[maxn],c[maxn],d[maxn]; inline int read() { int ans=0; char last=' ',ch=getchar(); while(ch<'0'||ch>'9') last=ch,ch=getchar(); while(ch>='0'&&ch<='9') ans=ans*10+ch-'0',ch=getchar(); if(last=='-') ans=-ans; return ans; } int main() { n=read();m=read(); if(n<11) { for(int i=1;i<=m;i++) printf("0 0 0 0 "); return 0; } for(int i=1;i<=m;i++) { x[i]=read(); tong[x[i]]++; } for(int t=1;t*9<n;t++) { int sum=0; for(int D=9*t+2;D<=n;D++) { int C=D-t; int B=D-7*t-1; int A=D-9*t-1; sum+=tong[A]*tong[B]; c[C]+=sum*tong[D]; d[D]+=sum*tong[C]; } sum=0; for(int A=n-9*t-1;A>0;A--) { int B=A+t*2; int C=A+8*t+1; int D=A+9*t+1; sum+=tong[C]*tong[D]; a[A]+=sum*tong[B]; b[B]+=sum*tong[A]; } } for(int i=1;i<=m;i++) { printf("%d %d %d %d ",a[x[i]],b[x[i]],c[x[i]],d[x[i]]); } return 0; }
----------------------- The End --------------------
xiang quan ao sai tong xue xie zui