2020牛客暑期多校訓練營(第六場)[K] K-Bag

来源:https://www.cnblogs.com/ikkvix/archive/2020/07/27/13388448.html

K-Bag定義為K的多個任意全排列的組合(eg:1 2 3 2 3 1 1 2 3),給定一個長為n的數組,判斷是否為K-Bag的一部分。 題解: (1≤n≤5⋅105,1≤k≤109),k<=n時,用g[i]判斷前i個數是否不相等,h[i]判斷i~n是否不相等,f[i]判斷i~i+k是否不相等,b ...


K-Bag定義為K的多個任意全排列的組合(eg:1 2 3 2 3 1 1 2 3),給定一個長為n的數組,判斷是否為K-Bag的一部分。

題解: (1n5105,1k109),k<=n時,用g[i]判斷前i個數是否不相等,h[i]判斷i~n是否不相等,f[i]判斷i~i+k是否不相等,b[i]表示i出現次數,num表示當前區域出現超過1次的數的個數。

    當k>n時,最多只會有兩個段(...2 3 4 / 2 1 3...),離散化後判斷。

 1 #include<cstdio>
 2 #include<cstdlib>
 3 #include<algorithm>
 4 #include<cstring> 
 5 #include<queue>
 6 using namespace std;
 7 int const N=5e5+10;
 8 int n,k;
 9 bool f[N],g[N],h[N];
10 int a[N],b[N];
11 bool find(int s){
12   int i;
13   for (i=s;i+k-1<=n;i+=k)
14     if (!f[i]) return false;
15   if (i<=n && !h[i]) return false;
16   return true;
17 }
18 void work(){
19   for (int i=1;i<=n;i++){
20     scanf("%d",&a[i]);
21     b[i]=0;
22     f[i]=false;
23     g[i]=false;  //前尾碼 
24     h[i]=false;
25    }
26    int num=0;
27    for (int i=1;i<=k;i++){
28       b[a[i]]++;
29       if (b[a[i]]==2) num++;
30       if (num==0) g[i]=true;
31     }
32     if (num==0) f[1]=true;
33     for (int i=k+1;i<=n;i++){
34      b[a[i-k]]--;
35      if (b[a[i-k]]==1) num--;
36      b[a[i]]++;
37       if (b[a[i]]==2) num++;
38       if (num==0) f[i-k+1]=true;
39     }
40     for (int i=n-k+1;i<=n;i++){
41       b[a[i-1]]--;
42      if (b[a[i-1]]==1) num--;
43      if (num==0) h[i]=true;
44     }
45     g[0]=true;
46     for (int i=0;i<k;i++)
47       if (g[i] && find(i+1)) {
48         printf("YES\n");
49         return;
50       }
51   printf("NO\n");
52 }
53 void work2(){
54     for (int i=1;i<=n;i++){
55       scanf("%d",&a[i]);
56       b[i]=a[i];
57       g[i]=false;
58       h[i]=false;
59     }
60     sort(b+1,b+n+1);
61     int temp=unique(b+1,b+n+1)-b-1;
62     for (int i=1;i<=n;i++){
63       a[i]=lower_bound(b+1 , b+temp+1 , a[i]) - b;
64     }
65     for (int i=1;i<=n;i++)
66      b[i]=0;
67     int num=0;
68     for (int i=1;i<=n;i++){
69       b[a[i]]++;
70       if (b[a[i]]==2) num++;
71       if (num==0) g[i]=true;
72     }
73     for (int i=1;i<=n;i++){
74       b[a[i-1]]--;
75      if (b[a[i-1]]==1) num--;
76      if (num==0) h[i]=true;
77     }
78     g[0]=true;
79     h[n+1]=true;
80     for (int i=0;i<=n;i++)
81       if (h[i+1] && g[i]){
82        printf("YES\n");
83         return;
84       }
85   printf("NO\n");
86 }
87 int main(){
88   int t;
89   scanf("%d",&t);
90   while (t--){
91     scanf("%d%d",&n,&k);  //k<n 時 
92     if (k<=n) work();
93      else work2();
94   }
95 return 0;
96 }

 


您的分享是我們最大的動力!

更多相關文章
  • 1.js 前端將平級數據轉為樹形數據的方法 轉,實測成功 https://segmentfault.com/a/1190000022444269 // 將同級數據轉化為樹形結構 listToTree(dataSource) { // datasource是平級的數據來源 return dataSou ...
  • 給出一個 32 位的有符號整數,你需要將這個整數中每位上的數字進行反轉 示例 1: 輸入: 123 輸出: 321 示例 2: 輸入: -123 輸出: -321 示例 3: 輸入: 120 輸出: 21 /** * @param {number} x * @return {number} */ v ...
  • 利用隊列我們可以解決很多問題,js數組也可以實現隊列,隊列的思想為先近先出,js可以用 push和 shift() 很容易的實現一個隊列 給你一個二叉樹,請你返回其按 層序遍歷 得到的節點值。 (即逐層地,從左到右訪問所有節點)。 示例: 二叉樹:[3,9,20,null,null,15,7], 3 ...
  • JS獲取URL信息類 主要功能有: 1.獲取URL基本信息,包括:網址,協議,埠號等。 2.地址欄獲取參數。 3.將json格式的參數對象轉換成字元串。 //獲取URL信息 var shaoURL = shaoURL || {}; (function (n){ var d = { pathname ...
  • 前言 單例模式應該是我們最熟悉的模式了,如果說要隨便抓一個程式員,讓他說一說最熟悉的集中設計模式,我想肯定有單例模式。 我們這節就全面的來講解一下單例模式。 為什麼要用單例模式 單例模式理解起來非常簡單。在一個系統中,一個類只允許創建一個對象,那這個類就是單例類,這種設計模式就叫做單例設計模式。 為 ...
  • Strategy Pattern enables selecting an algorithm at runtime. In more detail, code receives run-time instructions as to which in a family of algorithms ...
  • 代理模式的目地是為對象提供一種代理以控制對這個對象的訪問。為什麼會出現“通過一個代理對象,控制其他對象訪問目標對象”這種場景,而不知直接new()出一個對象直接使用呢?這是因為在有些場景下對象的訪問比較複雜,且需要一些額外的控制,這時如果直接new()出實例,併在調用端處理這些繁雜的細節,會增加系統 ...
  • 簡介 在企業級開發中、我們經常會有編寫資料庫表結構文檔的時間付出,從業以來,待過幾家企業,關於資料庫表結構文檔狀態:要麼沒有、要麼有、但都是手寫、後期運維開發,需要手動進行維護到文檔中,很是繁瑣、如果忘記一次維護、就會給以後工作造成很多困擾、無形中製造了很多坑留給自己和後人,於是需要一個插件工具 s ...
一周排行
  • 比如要拆分“呵呵呵90909086676喝喝999”,下麵當type=0返回的是中文字元串“呵呵呵,喝喝”,type=1返回的是數字字元串“90909086676,999”, private string GetStrings(string str,int type=0) { IList<strin ...
  • Swagger一個優秀的Api介面文檔生成工具。Swagger可以可以動態生成Api介面文檔,有效的降低前後端人員關於Api介面的溝通成本,促進項目高效開發。 1、使用NuGet安裝最新的包:Swashbuckle.AspNetCore。 2、編輯項目文件(NetCoreTemplate.Web.c ...
  • 2020 年 7 月 30 日, 由.NET基金會和微軟 將舉辦一個線上和為期一天的活動,包括 微軟 .NET 團隊的演講者以及社區的演講者。本次線上大會 專註.NET框架構建微服務,演講者分享構建和部署雲原生應用程式的最佳實踐、模式、提示和技巧。有關更多信息和隨時瞭解情況:https://focu... ...
  • #abp框架Excel導出——基於vue #1.技術棧 ##1.1 前端採用vue,官方提供 UI套件用的是iview ##1.2 後臺是abp——aspnetboilerplate 即abp v1,https://github.com/aspnetboilerplate/aspnetboilerp ...
  • 前言 本文的文字及圖片來源於網路,僅供學習、交流使用,不具有任何商業用途,版權歸原作者所有,如有問題請及時聯繫我們以作處理。 作者:碧茂大數據 PS:如有需要Python學習資料的小伙伴可以加下方的群去找免費管理員領取 input()輸入 Python提供了 input() 內置函數從標準輸入讀入一 ...
  • 從12年到20年,python以肉眼可見的趨勢超過了java,成為了當今It界人人皆知的編程語言。 python為什麼這麼火? 網路編程語言搜索指數 適合初學者 Python具有語法簡單、語句清晰的特點,這就讓初學者在學習階段可以把精力集中在編程對象和思維方法上。 大佬都在用 Google,YouT ...
  • 在社會上存在一種普遍的對培訓機構的學生一種歧視的現象,具體表現在,比如:當你去公司面試的時候,一旦你說了你是培訓機構出來的,那麼基本上你就涼了,那麼你瞞著不說,然後又通過了面試成功入職,但是以後一旦在公司被髮現有培訓經歷,可能會面臨被降薪,甚至被辭退,培訓機構出來的學生,在用人單位眼裡就是能力低下的 ...
  • from typing import List# 這道題看了大佬寫的代碼,經過自己的理解寫出來了。# 從最外圍的四周找有沒有為O的,如果有的話就進入深搜函數,然後深搜遍歷# 判斷上下左右的位置是否為Oclass Solution: def solve(self, board: List[List[s ...
  • import requests; import re; import os; # 1.請求網頁 header = { "user-agent":'Mozilla/5.0 (Macintosh; Intel Mac OS X 10_15_5) AppleWebKit/537.36 (KHTML, li ...
  • import requests; import re; import os; import parsel; 1.請求網頁 header = { "user-agent":'Mozilla/5.0 (Macintosh; Intel Mac OS X 10_15_5) AppleWebKit/537. ...