20092013年NOIP初赛提高组C++语言试题及参考答案

有多个子序列并列最长,输出任意一个即可。例如,序列“1 1 2 3 2 3 2 3 3 1 1 1 3 1”中,有两段满足条件的最长子序列,长度均为7,分别用下划线和上划线标出。Р#include <iostream> Рusing namespace std; Р Рint main() Р{ Р const int SIZE = 100; Рint n, i, j, a[SIZE], cur1, cur2, count1, count2, Рans_length, ans_start, ans_end; Р//cur1, cur2分别表示当前子序列中的两个不同整数Р//count1, count2分别表示cur1, cur2在当前子序列中出现的次数 Рcin>>n; Рfor (i = 1; i <= n; i++) Рcin>>a[i]; Р i = 1; Рj = 1; Р//i, j分别表示当前子序列的首尾,并保证其中至多有两个不同整数 Рwhile ((j <= n) && (a[j] == a[i]))  Рj++; Р cur1 = a[i];Рcur2 = a[j]; Р count1 =      (1)       //(3分)Рcount2 = 1; Рans_length = j - i + 1; Рwhile (j < n) { Рj++; Рif (a[j] == cur1) Рcount1++; Рelse if (a[j] == cur2) Рcount2++; Рelse { Рif (a[j - 1] ==     (2)    ) {  //(3分)Рwhile (count2 > 0) { Рif (a[i] == cur1) Р count1--; Рelse Рcount2--; Р i++; Р} Р cur2 = a[j];