Shiraz University Local Contest 2011 I, UVa-12385 : Interesting Sequences

UVa その他のコンテスト

問題概要

長さN(<10^5)の数列が与えられる。長さ2以上の区間で両端の値が等しくなるような部分列がいくつとれるか求める問題。ただし端点しか交わってはならない。

考えたこと

  • サンプルが分からない。
  • ああ端点は交わっていいのか。納得。
  • 貪欲で行けそう。区間スケジューリングみたいな感じで。
  • 貪欲でやると決めたら、左端の候補をsetに突っ込んでいけばOK？
  • 10^5でsetとかあまり使いたくないけどTLEになったらそのとき考えよう。
  • 書いた。無事通ってた。

本番で通ったコード

計算量O(N*log N)。

#include <cstdio>
#include <set>
using namespace std;

const int MAX_N = (int)1e5;

int N;
int as[MAX_N];

void init(){
	scanf("%d", &N);
	for(int i=0; i<N; i++){
		scanf("%d", as+i);
	}
}

int solve(){
	int ans = 0;
	set<int> lefts;
	lefts.insert(as[0]);

	for(int i=1; i<N; i++){
		if(!lefts.insert(as[i]).second){
			lefts.clear();
			lefts.insert(as[i]);
			ans++;
		}
	}

	return ans;
}

int main(){
	int T;
	scanf("%d", &T);
	while(T--){
		init();
		printf("%d\n", solve());
	}

	return 0;
}