集训队作业-ural1458war games解题报告_第1页
集训队作业-ural1458war games解题报告_第2页
免费预览已结束,剩余2页可下载查看

付费下载

下载本文档

版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领

文档简介

1、Ural 1458 War Games 解题北江中学【正文】一、问题描述给出一个由B和W组成的 n*n 矩阵 C。一个操作(i,j)指将第 i 行和第j 列的所有元素(一共 2n-1 个)的状态都改变(B变成W,W变成B), 2 = n = 1000, 且n 为偶数。现在给出初始状态,要求用最少的操作将矩阵变成一种颜色(只有W或B)。并将具体方案输出。二、问题分析算法是余方程组。不难发现,如果某个操作(i,j)出现多于一次,那么肯定不优的,因为可以将它 mod 2,使得结果不变,而总操作数减少。另外,操作执行的顺序,对结果也是不影响的。如果用 0 表示W,用 1 表示B,Ai, j表示操作(i

2、, j)出现的次数,那么最后矩阵中 C(i, j)变为(C(i, j) + (Ai, 1 + . + Ai, n) + (A1, j + . + An, j)- Ai,j) mod 2.可以预先假定最后所有元素都变为 0,或 1(分别搜索),用 k 表示。一共有 n2 个未知数,而对于每个元素,都可以列一个方程。所以只需要解出这个方程即可。现在是,如果运用消,时间复杂度将会达到 O(n6)。事实上,任何复杂度高于 n2 的算法已经不可能出解了。 通过观察可以发现,这个方程组有自身的特殊性的。 n 是偶数将使很多表达式关于 2 同余了。对于某个元素 C(i, j),有 (C(i, j) + (A

3、i, 1 + . + Ai, n) + (A1, j + . + An,j) - Ai,j) mod 2 = k将所有 n2 个方程都相加,并化简,可以得知 sum = (n * 2 - 3)* 2(A1, 1 + . + An, n) mod 2 = (A1, 1 + . + An, n) mod的确切值,由于n 为偶数,所以 sum 等于矩阵中 1 的个数 mod2。如果用 ai 表示 (Ci, 1 + Ci, 2 + . Ci, n) mod 2,用 bj 表示 (C1, j + C2,用 yi表示 (Ai, 1 + . +用 xj表示 (A1, j + . +将第i 行所有元素所有的方

4、程相j + Ai,An,.n)j)+ Cn, j) mod 2, mod 2mod 2们可以得出,yi = (ai * (n 2;们得出,xj = (bj * (n - 1)+-1) + sum) mod 2 = (ai + sum)mod同理,将第j 列所有的方程相sum) mod 2 = (bj + sum) mod 2;这时,将 yi,xj代入每个元素的方程中,有(yi + xj + Ci, j - Ai, j) mod 2 = k即 Ai, j = (yi + xj + Ci, j - k) mod 2 = (yi + xj +Ci, j + k) mod 2由于 y, x, c, k

5、 都已知,所以所有的 Ai, j都可以解出来。三、程序说明由于n 可能达到 1000,所以我没有将解出来的 Ai, j存下来(因为大数组的频繁计算地址会耗费很多时间),而是采取临时计算的方式。另外,将 mod 2 转化为位运算 and 1, 也可以大大加快程序的运行速度。【附】constfin = ;/input.in;maxn = 1000;varc: array1 . maxn, 1 . maxnof short;a, b, x, y: array1 . maxnof long;count: array0n, sum: long. 1of long;procedure init; vari

6、, j, k: long ch: char;beginassign(input, readln(n);fin); reset(input);for i:= 1 to n do begin for j:= 1 to n do beginread(ch);if ch = W then k:= 0 else k:= ci, j:= k;inc(sum, k); inc(ai, k);inc(bj, k); end;readln; end;close(input);1;sum:= sum and 1;for i:= 1 to n do beginai:= ai andbi:= bi and end;1

7、;1;end;procedure find(k: long vari, j, ans: longbegin);for i:= 1 to n do begin xi:= (bi + sum) and 1;yi:= (ai + sum) and 1;end;for i:= 1 to n do for j:= 1 to n dobeginans:= (yi + xj + k + ci, j)and1;if ans = 1 thenend;inc(countk);end;procedure prvar(k: long);i, j, ans: long;beginfor i:= 1 to n do begin xi:= (bi + sum) and 1;yi:= (ai + sum) and 1;end;wrin(countk); for i:= 1 to n dofor j:= 1 to n do beginans:= (yi + xj + k +

温馨提示

  • 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
  • 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
  • 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
  • 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
  • 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
  • 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
  • 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

评论

0/150

提交评论