NYOJ109 数列转换 【守恒法】

数列转换

时间限制： 3000 ms  |  内存限制： 65535 KB 难度： 3 描写叙述

有一个数列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 来源 《世界大学生程序设计竞赛高级教程·第一冊》 上传者 张云聪

题解：假设用暴力模拟出全部结果然后再比較的话非常easy超时，并且编程复杂度高。可是在网上看到了一个非常奇妙的守恒法，不是在细节上关注这些变化。而是从总体上看到某些不变的东西，用S[i]表示A[0...i]的和，当对A[i]进行变化的时候。直接结果是S[i]和S[i-1]交换了位置。所以为题就转换成了求S数组，排序。然后比較两个S数组是否相等。

#include <stdio.h> #include <string.h> #include <algorithm> #define maxn 1010 int A[maxn], B[maxn]; int main() { int t, n, i; scanf("%d", &t); while(t--) { scanf("%d", &n); for(i = 0; i < n; ++i) { scanf("%d", &A[i]); if(i) A[i] += A[i-1]; } for(i = 0; i < n; ++i) { scanf("%d", &B[i]); if(i) B[i] += B[i-1]; } std::sort(A, A + n); std::sort(B, B + n); if(std::equal(A, A + n, B)) printf("Yes\n"); else printf("No\n"); } return 0; }

转载于:https://www.cnblogs.com/bhlsheji/p/5358637.html

相关资源：数据结构—成绩单生成器