nyoj-109 数列转换 (守恒定律)

数列转换

描述

有一个数列a₁,a₂,a₃...a_n,每次可以从中任意选三个相邻的数a_i-1 ,a_i , a_{i+1 ,}进行如下操作（此操作称为“对a_i进行操作”）

(a_i-1,a_i,a_i+1)->(a_i-1+a_i,-a_i,a_i+a_i+1)

给定初始和目标序列，是否能通过以上操作，将初始序列转换成为目标序列？例如，初始序列(1 6 9 4 2 0)目标序列（7 -6 19 2 -6 6)可经过如下操作：

(1 6 9 4 2 0)->( 1 6 13 -4 6 0)->(1 6 13 2 -6 6)->(7 -6 19 2 -6 6)

请你判断给定的初始状态和目标状态，输出Yes（能够转换）或No（不能转换）

输入

第一行是一个正整数N,表示测试数据的组数。(N<=100)
每组测试数据的第一行是一个整数M(3<=M<=1000),表示该组测试数据的起始状态与结束状态都有M个数。
每组测试数据的第二行是M个整数Ai(-1000<=Ai<=1000)，表示起始状态。
每组测试数据的第三行是M个整数Bi(-1000<=Bi<=1000),表示终止状态。

输出

如果能够转换，输出Yes
如果不能转换，输出No

样例输入

2
3
1 2 3
1 3 2
6
1 6 9 4 2 0
7 -6 19 2 -6 6

样例输出

No
Yes

思路：

看似很费解的搜索，实际可利用“守恒定律”轻松解决

参考资料：http://www.cnblogs.com/dongsheng/archive/2013/03/04/2943099.html

其精髓在于：只要两个序列顺序求和，经排序后，元素按位对应相等，他们就能通过操作互达。

例如：1， 2， 3 => 1， 3， 2 这组示例，顺序求和后转换为 1， 3， 6 => 1, 4, 6； 升序排序后显然不能按位对应相等（3 ！= 4），所以他们不能互达；

再如：1，6， 9， 4， 2， 0 => 7, -6, 19, 2, -6, 6 这组, 顺序求和后转换为 1， 7， 16， 20， 22， 22 => 7， 1， 20， 22， 16， 22; 将其升序排序后恰能按位对应相等，所以他们能够互达。

代码：

#include 
      
       
#include 
       
         #define N 1001 using namespace std; int a[N] = {0}; int b[N] = {0}; int main() { int loop, n, i; cin >> loop; while(loop --){ cin >> n; for(i = 0; i < n; i ++){ cin >> a[i]; a[i] = a[i] + a[i - 1]; } for(i = 0; i < n; i ++){ cin >> b[i]; b[i] = b[i] + b[i - 1]; } sort(a, a + n); sort(b, b + n); /* for(i = 0; i < n; i ++){ if(a[i] != b[i]){ break; } } if(i != n + 1) cout << "NO" << endl; else cout << "Yes" << endl; */ if( equal(a, a + n - 1, b) ) // STL equal() 判断两个数组是否相等 cout << "Yes" << endl; else cout << "No" << endl; } return 0; }
       
      

<script type="text/java script">

<script type="text/java script">BAIDU_CLB_fillSlot("771048");

点击复制链接 与好友分享! 回本站首页

<script> function copyToClipBoard(){ var clipBoardContent=document.title + '\r\n' + document.location; clipBoardContent+='\r\n'; window.clipboardData.setData("Text",clipBoardContent); alert("恭喜您！复制成功"); }

分享到： 更多

<script type="text/java script" id="bdshare_js" data="type=tools&uid=12732"> <script type="text/java script" id="bdshell_js"> <script type="text/java script"> var bds_config = {'snsKey':{'tsina':'2386826374','tqq':'5e544a8fdea646c5a5f3967871346eb8'}}; document.getElementById("bdshell_js").src = "http://bdimg.share.baidu.com/static/js/shell_v2.js cdnversion=" + Math.ceil(new Date()/3600000)

您对本文章有什么意见或着疑问吗？请到 论坛讨论您的关注和建议是我们前行的参考和动力

上一篇： C++ Primer 学习笔记_23_函数（续2） --局部对象、内联函数、类的成员函数

下一篇： C++单元测试总结（一）

相关文章

<script type="text/java script">BAIDU_CLB_fillSlot("182716");

<script type="text/java script">BAIDU_CLB_fillSlot("517916");

图文推荐

<script type="text/java script">BAIDU_CLB_fillSlot("771057");