IQテスト

jzoj 5048

テーマの大意

シーケンスaが与えられ、m個のクエリが与えられ、各クエリはシーケンスaがいくつかの数を削除して得られるかどうかを尋ねる.

入力サンプル

7
1 5 4 5 7 8 6
4
5
1 5 5 8 6
3
2 2 2
3
5 7 8
4
1 5 7 4

出力サンプル

TAK
NIE
TAK
NIE

データ範囲

30%のデータ:nе1000,mе1000 nleqslant 1000,mleqslant 1000,mleqslant 1000 nе1000,mе1000 100%のデータ:1еa i,b iе100000,ΣLе100000,n,mе100000 1 100000 1leqslant ai,bi leqslant 100000,sum Lleqslant 100000,n,mleqslant 100000,100,100,mleqslant 100000,100,10,000 Bi⩽100000,ΣL⩽100000,n,m⩽100000

問題を解く構想.

データは100000という大きさで、それはo(n)o(n)o(n)程度のデータがΣL現在の数字が見つかった場合、シーケンスaの各数を順番に見つけることができる場合、それは一致しますが、各シーケンスが検索されると、T L E TLE TLE TLE TLEポインタがある数字を指すシーケンスについてどのようなものがあるかを記録するために1つの配列を使用することができます.

コード#コード#

#include
#include
#include
#include
#include
#define ll long long
using namespace std;
int n, m, w, g, a[1000010], s[1000010];
vector<int>h[1000010], b[1000010];// vector 
int main()
{
	scanf("%d", &n);
	for (int i = 1; i <= n; ++i)
		scanf("%d", &a[i]);
	scanf("%d", &m);
	for (int i = 1; i <= m; ++i)
	{
		scanf("%d", &w);
		for (int j = 1; j <= w; ++j)
		{
			scanf("%d", &g);
			b[i].push_back(g);
		}
		h[b[i].front()].push_back(i);// 
	}
	for (int i = 1; i <= n; ++i)
	{
		w = h[a[i]].size();// a[i] 
		for (int j = 0; j < w; ++j)
		{
			g = h[a[i]][j];// 
			s[g]++;// 
			if (s[g] < b[g].size()) h[b[g][s[g]]].push_back(g);// ， 
		}
		h[a[i]].erase(h[a[i]].begin(), h[a[i]].begin() + w);// 
	}
	for (int i = 1; i <= m; ++i)
		if (s[i] >= b[i].size()) printf("TAK
");// 
		else printf("NIE
");
	return 0;
}