題目描述

組合子邏輯是 Moses Sch?nfinkel 和 Haskell Curry 發明的一種符號系統，用于消除數理邏輯中對于變量的需要。本題考察一種與真實世界的組合子演算略有差別的組合子系統。

一個組合子項是下列形式之一：

PP

(E_1\;E_2)(E1?E2?)

其中?PP?表示一個基本函數，E_1E1?以及E_2E2?表示一個組合子項(可以相同)。不滿足以上形式表達式均非組合子項。

我們將一個組合子項?EE?的參數個數?np(E)np(E)如下：

np(P)np(P)?= 基本函數?PP?的參數個數；

np((E_1\;E_2)) = np(E_1) - 1np((E1?E2?))=np(E1?)?1。

本題中，我們用一個正整數同時表示一個基本函數，以及該基本函數的參數個數。

對于一個組合子項?EE，如果它和它包含的所有組合子項的參數個數?npnp?均為正整數，那么我們稱這個?EE?為范式。

我們經常組合子項簡化表示：如果一個組合子項EE含有連續子序列(… ((E_1\;E_2)\;E_3) …E_n)(…((E1?E2?)E3?)…En?)?(其中?n ≥ 3n≥3)，其中E_kEk?表示組合子項(可以是簡化表示的)，那么將該部分替換為(E_1\;E_2\;E_3 … E_n)(E1?E2?E3?…En?)，其他部分不變，得到表達式?EE?的一個簡化表示。一個組合子項可以被簡化表示多次。

給定一個基本函數序列，問至少需要添加多少對括號，才能使得該表達式成為一個范式的簡化表示(即滿足范式的性質)；如果無論如何怎樣添加括號，均不能得到范式的簡化表示，輸出-1?1。

?

題解

• 題面真的害死人
• k?表示當前的最大值還能再包含多少位，當前的最大值不一定要包含當前位，只要求出正確結果即可

?

代碼

1 #include <queue> 2 #include <cstdio> 3 #include <cstring> 4 #include <iostream> 5 using namespace std; 6 int T,n,a[2000010]; 7 priority_queue<int> Q; 8 int main() 9 { 10 for (scanf("%d",&T);T;T--) 11 { 12 scanf("%d",&n); 13 for (int i=1;i<=n;i++) scanf("%d",&a[i]); 14 if (n==1) { puts(a[1]?"0":"-1"); continue; } 15 int k=a[1]-1,ans=1; 16 while (!Q.empty()) Q.pop(); 17 for (int i=2;i<=n;i++) 18 { 19 if (k) k--; 20 else 21 { 22 if (Q.empty()||Q.top()<2) { ans=-1; break; } 23 ans++,k=Q.top()-2,Q.pop(); 24 } 25 Q.push(a[i]); 26 } 27 printf("%d\n",ans); 28 } 29 }

?

轉載于:https://www.cnblogs.com/Comfortable/p/11280301.html

總結

以上是生活随笔為你收集整理的[优先队列][堆] Luogu P4505 组合子逻辑的全部內容，希望文章能夠幫你解決所遇到的問題。

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