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$
對于100%的數據：$1?ai,bi?1000000，\sum L?1000000，n,m?1000000$

解題思路

數據有1000000這么大，那應該就是$o（n）$左右的
數據寫到$\sum L?1000000$，那他就一定有他的作用
我們把所有序列放在一起看
我們可以枚舉序列a，對于每一個數
如果和某個序列的指針所指向的數字相同，那我們就把這個序列的指針指向下一位，就是當前數字已找到
如果一個序列可以按順序在序列a中找到它的每一個數，那它就是符合的
但如果每一個序列都搜一遍的話就會$TLE$
我們可以用一個數組來記錄指針指向某個數字的序列有哪些

代碼

#include<vector> #include<cstdio> #include<cstring> #include<iostream> #include<algorithm> #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\n");//遍歷完的else printf("NIE\n");return 0; }

總結

以上是生活随笔為你收集整理的IQ测试（jzoj 5048）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。