[题解]第十一届北航程序设计竞赛预赛—

题目描述

一张n*m的地图，每个格子里面有一定数量的神奇宝贝，求一个最优位置，使得所有神奇宝贝到该位置的曼哈顿距离最小。

一共有T组数据，每组数据包含两行，第一行是n和m(1<=n,m<=2000)，第二行是三个整数x,y,q，表示处于（i，j）(1<=i<=n,1<=j<=m)的神奇宝贝的数量为((x^i) + (y^j))mod q，其中1<=x,y<=2000，1<=q<=10。

输出最小的曼哈顿距离和。

解题思路

这道题与2015编程之美挑战赛的基站选址类似（其实可以说是简单版），当时我没有做出来，给个地址吧：http://hihocoder.com/problemset/problem/1150

分析题目可以发现，由于是求曼哈顿距离，所以横行和竖行可以分开考虑，于是问题就变成了求加权平均数的问题。

公式：ans_x = ∑(ai*i) / ∑ai，ans_y = ∑(bj*j) / ∑bj，其中ai表示第i行的神奇宝贝数量，bi表示第i列的神奇宝贝数量，当然有∑ai == ∑bj。

这里有两点需要注意：

1、当结果不是整数时，涉及到向上取整还是向下取整的问题，由于与所有非零点的分布有关，所以最简单的办法是有可能成为答案的四个点都做一次判断就好了。

2、这里涉及到除法，所以可能会出现分母为零的情况，即地图上木有神奇宝贝【o(≧口≦)o摔桌子】，所以要特判…… 我才不会说我因为这个wa了好久QAQ

附：c++代码

（代码中有被注释掉的高精度的部分，因为我之前对数据规模的估计出错了…… 目前的高精度的代码还有错误，所以借鉴需要注意……）

时间复杂度O(n^2)

  1 #include <iostream>

  2 #include <cstdio>

  3 #include <cmath>

  4

  5 using namespace std;

  6 #define MaxN 2020

  7 #define MLen 14

  8

  9 typedef int hp[MLen];

 10 typedef long long llt;

 11

 12 llt H[MaxN], L[MaxN];

 13 int n, m;

 14

 15 inline void Add(hp a, hp b, hp &Ret)

 16 {

 17     int i, Len = max(a[0], b[0]) + 1;

 18     hp c;

 19     for(i = 1; i <= Len; i++)

 20         c[i] = 0;

 21     for(i = 1; i <= Len; i++)

 22     {

 23         c[i] += a[i] + b[i];

 24         c[i + 1] += c[i] / 10;

 25         c[i] %= 10;

 26     }

 27     while(Len > 1 && c[Len] == 0)

 28         Len--;

 29     c[0] = Len;

 30     for(i = 0; i <= Len; i++)

 31         Ret[i] = c[i];

 32 }

 33

 34 inline void Add_Num(hp a, int b, hp &Ret)

 35 {

 36     int i, Len = a[0] + 1;

 37     hp c;

 38     for(i = 1; i <= Len - 1; i++)

 39         c[i] = a[i];

 40     c[i] = 0;

 41     c[1] += b;

 42     for(i = 1; i <= Len; i++)

 43     {

 44         c[i + 1] += c[i] / 10;

 45         c[i] %= 10;

 46     }

 47     while(Len > 1 && c[Len] == 0)

 48         Len--;

 49     c[0] = Len;

 50     for(i = 0; i <= Len; i++)

 51         Ret[i] = c[i];

 52 }

 53

 54 inline void Mul_Num(hp a, int b, hp &Ret)

 55 {

 56     int i, Len = a[0] + 5;

 57     hp c;

 58     for(i = 1; i <= a[0]; i++)

 59         c[i] = a[i] * b;

 60     for(i = a[0] + 1; i <= Len; i++)

 61         c[i] = 0;

 62     for(i = 1; i <= Len; i++)

 63     {

 64         c[i + 1] += c[i] / 10;

 65         c[i] %= 10;

 66     }

 67     while(Len > 1 && c[Len] == 0)

 68         Len--;

 69     c[0] = Len;

 70     for(i = 0; i <= Len; i++)

 71         Ret[i] = c[i];

 72 }

 73

 74 inline bool Check(hp a, hp b) // a<b

 75 {

 76     if(a[0] < b[0])

 77         return true;

 78     if(a[0] > b[0])

 79         return false;

 80     for(int i = a[0]; i >= 1; i--)

 81         if(a[i] < b[i])

 82             return true;

 83         else if(a[i] > b[i])

 84             return false;

 85     return true;

 86 }

 87

 88 inline int Chu(hp a, hp b) // a/b

 89 {

 90     int Low = 0, High = 2020, Mid;

 91     hp tmp;

 92     int op;

 93     while(Low < High) //[,)

 94     {

 95         Mid = Low + (High - Low) / 2;

 96         Mul_Num(b, Mid, tmp);

 97         if(Check(tmp, a)) //tmp < a

 98         {

 99             Low = Mid + 1;

100             op = 0;

101         }

102         else

103         {

104             High = Mid;

105             op = 1;

106         }

107     }

108     if(!op)

109         return Low - 1;

110     else

111         return High - 1;

112 }

113

114 inline void Cal_Dis(int ph, int pl, llt &Ret)

115 {

116     int i, j;

117     //hp Ans;

118     llt Ans = 0;

119     //Ans[0] = 1; Ans[1] = 0;

120     for(i = 1; i < ph; i++)

121         //Add_Num(Ans, (ph - i) * H[i], Ans);

122         Ans += (llt)(ph - i) * H[i];

123     for(i = ph + 1; i <= n; i++)

124         //Add_Num(Ans, (i - ph) * H[i], Ans);

125         Ans += (llt)(i - ph) * H[i];

126     for(j = 1; j < pl; j++)

127         //Add_Num(Ans, (pl - j) * L[j], Ans);

128         Ans += (llt)(pl - j) * L[j];

129     for(j = pl + 1; j <= m; j++)

130         //Add_Num(Ans, (j - pl) * L[j], Ans);

131         Ans += (llt)(j - pl) * L[j];

132     //for(i = 0; i <= Ans[0]; i++)

133     //    Ret[i] = Ans[i];

134     Ret = Ans;

135 }

136

137 inline void Print(hp a)

138 {

139     for(int i = a[0]; i >= 1; i--)

140         printf("%d", a[i]);

141     printf("\n");

142 }

143

144 int main()

145 {

146     int T;

147     int x, y, q;

148     int i, j, Num;

149     llt Ans, tmp;

150     //hp Sum_h, Sum_l, Psum_h, Psum_l;

151     llt Sum_h, Sum_l, Psum_h, Psum_l;

152     double ph, pl;

153     scanf("%d", &T);

154     while(T--)

155     {

156         scanf("%d%d", &n, &m);

157         scanf("%d%d%d", &x, &y, &q);

158         Psum_h = Psum_l = Sum_h = Sum_l = 0;

159         //Psum_h[0]  = Psum_l[0] = Sum_h[0] = Sum_l[0] = 1;

160         //Psum_h[1]  = Psum_l[1] = Sum_h[1] = Sum_l[1] = 0;

161         for(j = 1; j <= m; j++)

162             L[j] = 0;

163         for(i = 1; i <= n; i++)

164         {

165             H[i] = 0;

166             for(j = 1; j <= m; j++)

167             {

168                 Num = ((x ^ i) + (y ^ j)) % q;

169                 H[i] += Num;

170                 L[j] += Num;

171             }

172             Sum_h += H[i];

173             Psum_h += (llt)i * H[i];

174             //Add_Num(Sum_h, H[i], Sum_h);

175             //Add_Num(Psum_h, i * H[i], Psum_h);

176         }

177         for(j = 1; j <= m; j++)

178         {

179             Sum_l += L[j];

180             Psum_l += (llt)j * L[j];

181             //Add_Num(Sum_l, L[j], Sum_l);

182             //Add_Num(Psum_l, j * L[j], Psum_l);

183         }

184         //ph = Chu(Psum_h, Sum_h);

185         //pl = Chu(Psum_l, Sum_l);

186         if(!Sum_h) //Sum_h == Sum_l

187         {

188             printf("0\n");

189             continue;

190         }

191         ph = Psum_h / Sum_h;

192         pl = Psum_l / Sum_l;

193         Cal_Dis(ph, pl, Ans);

194         Cal_Dis(ph + 1, pl, tmp);

195         //if(Check(tmp, Ans))

196             //for(i = 0; i <= tmp[0]; i++)

197             //    Ans[i] = tmp[i];

198         if(tmp < Ans)

199             Ans = tmp;

200         Cal_Dis(ph, pl + 1, tmp);

201         //if(Check(tmp, Ans))

202             //for(i = 0; i <= tmp[0]; i++)

203             //    Ans[i] = tmp[i];

204         if(tmp < Ans)

205             Ans = tmp;

206         Cal_Dis(ph + 1, pl + 1, tmp);

207         //if(Check(tmp, Ans))

208             //for(i = 0; i <= tmp[0]; i++)

209             //    Ans[i] = tmp[i];

210         if(tmp < Ans)

211             Ans = tmp;

212         printf("%lld\n", Ans);

213         //Print(Ans);

214     }

215     return 0;

216 }

另一种思路

这是官方给的题解，没太明白O(n)是怎样实现的。

题目链接：https://biancheng.love/contest-ng/index.html#/29/problems

巴特西

[题解]第十一届北航程序设计竞赛预赛——I.神奇宝贝大师

最新文章

热门文章