NOIP 提高组初赛 · NOIP 2013 提高组初赛试题 第 28 题

（两元序列）试求一个整数序列中，最长的仅包含两个不同整数的连续子序列。如有多 个子序列并列最长，输出任意一个即可。例如，序列 $\texttt{1 1 2 3 2 3 2 3 3 1 1 1 3 1}$ 中， 有两段满足条件的最长子序列，长度均为 $7$，分别用下划线和上划线标出。

#include <stdio.h> 
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 在当前子序列中出现的次数 
 scanf("%d", &n); 
 for (i = 1; i <= n; i++) 
  scanf("%d", &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++; 


（本题为阅读程序 / 完善程序，完整题目与测试数据见平台）

这题考的是滑动窗口（双指针）维护'最多两种不同整数'的区间。拿到题先想：窗口右端点j一直往右扩，一旦冒出第三种数，就得收缩左端点i，直到把第三种数赶出去。收缩时看a[j-1]是谁，就保谁、淘汰另一个。

最常见的坑是count1初始化写成1，其实i到j-1全是同一种数，个数应为j-i（或j-1）；其次是遇到第三种数时不看a[j-1]直接随便淘汰一个，导致窗口里还留着不该留的数；还有收缩循环里count减到0后没及时更新cur1/cur2，或者把cur1和cur2的更新逻辑写反了，最后ans_length更新条件漏掉等号导致取不到最大值。

考点与概念

这道题核心就是滑动窗口（也叫双指针）。在序列上维护一个区间[i, j]，让区间里至多出现两种不同的整数。j不断右移扩大窗口，一旦窗口里冒出第三种数，就通过移动i来收缩窗口，直到第三种数被挤出去为止。

两元序列的定义很简单：连续的一段，里面只包含两个不同的整数（当然，如果整段都只有一种整数，也满足'至多两种'的条件）。题目要求找出最长的这样的子序列。

命题视角：为什么这么考？

命题人想考察的是： 1. 对滑动窗口思想的掌握——不是死记模板，而是能根据'至多两种'这个动态条件灵活调整左右边界。 2. 细节处理能力——count怎么初始化、遇到第三种数时依据什么决定淘汰谁、收缩循环里count如何递减、更新cur1/cur2的时机等。 3. 数组下标从1开始的习惯——很多初学者会下意识用0开头，导致长度算错。

这类题在NOIP提高组初赛里出现过2次（2013年1次、2023年1次），属于'小而精'的类型：代码不长，但每个空都卡着关键逻辑。