$2020.04.08$【$NOIP$普及組】模擬賽$C$組$24$ 總結

概述：

這次比賽我$AK$了，拿了$300$分——其實這次比賽的題目確實很簡單，很多人都是想難了。

第一題：$Social$ $Distancing$ $1$

題目

題目描述 一種新型疾病，COWVID-19，開始在全世界的奶牛之間傳播。Farmer John 正在采取盡可能多的預防措施來防止他的牛群被感染。 Farmer John 的牛棚是一個狹長的建筑物，有一排共 N 個牛欄（2≤N≤10^5）。有些牛欄里目前有奶牛，有些目前空著。得知“社交距離”的重要性，Farmer John 希望使得 D 盡可能大，其中 D 為最近的兩個有奶牛的牛欄的距離。例如，如果牛欄 3 和 8 是最近的有奶牛的牛欄，那么 D=5。 最近兩頭奶牛新來到 Farmer John 的牛群，他需要決定將她們分配到哪兩個之前空著的牛欄。請求出他如何放置這兩頭新來的奶牛，使得 D 仍然盡可能大。Farmer John 不能移動任何已有的奶牛；他只想要給新來的奶牛分配牛欄。輸入 輸入的第一行包含 N。下一行包含一個長為 N 的字符串，由 0 和 1 組成，描述牛棚里的牛欄。0 表示空著的牛欄，1 表示有奶牛的牛欄。字符串中包含至少兩個 0，所以有至少有足夠的空間安置兩頭新來的奶牛。輸出 輸出 Farmer John 以最優方案在加入兩頭新來的奶牛后可以達到的最大 D 值（最近的有奶牛的牛欄之間的距離）。樣例輸入 14 10001001000010樣例輸出 2數據范圍限制 測試點 1-6 滿足 N≤10。 測試點 7-8 滿足 N≤100。 測試點 9-11 滿足 N≤5000。 測試點 12-15 滿足 N≤10^5。提示 在這個例子中，Farmer John 可以以這樣的方式加入奶牛，使得牛欄分配變為 10x010010x0010，其中 x 表示新來的奶牛。此時 D=2。不可能在加入奶牛之后取到更大的 D 值。

解題思路

這道題目的方法是進行枚舉暴力。
我們知道加入奶牛其實有$4$種方法。

在兩個間隙最長的地方分別加入$2$個。

在一個最長的間隙中加入$2$個奶牛。

在開頭加入$1$個奶牛。

在結尾加入$1$個奶牛。

對于這四種方法，我們直接暴力就可以了。時間復雜度為$O(n)$。

得分情況

比賽時得了$100$分。

第二題：$Social$ $Distancing$ $2$

題目

題目描述 由于高傳染性的牛傳染病 COWVID-19 的爆發，Farmer John 非常擔憂他的奶牛們的健康。 盡管他盡了最大努力使他的 N 頭奶牛們（1≤N≤1000）踐行“社交距離”，還是有許多奶牛不幸染上了疾病。編號為 1…N 的奶牛們分別位于一條長直道路上的不同位置（相當于一維數軸），奶牛 i 位于位置 xi。Farmer John 知道存在一個半徑 R，任何與一頭被感染的奶牛距離不超過 R 單位的奶牛也會被感染（然后會傳染給與其距離 R 單位內的奶牛，以此類推）。 不幸的是，Farmer John 并不確切知道 R 的值。他只知道他的哪些奶牛被感染了。給定這個數據，求出起初感染疾病的奶牛的最小數量。輸入 輸入的第一行包含 N。以下 N 行每行用兩個整數 x 和 s 描述一頭奶牛，其中 x 為位置（0≤x≤10^6），s 為 0 表示健康的奶牛，1 表示染病的奶牛，并且所有可能因傳播而染病的奶牛均已染病。輸出 輸出在疾病開始傳播之前已經得病的奶牛的最小數量。樣例輸入 6 7 1 1 1 15 1 3 1 10 0 6 1樣例輸出 3數據范圍限制提示 在這個例子中，我們知道 R<3，否則位于位置 7 的奶牛會傳染給位于位置 10 的奶牛。所以，至少 3 頭奶牛初始時已被感染：位于位置 1 和 3 的兩頭奶牛中的一頭，位于位置 6 和 7 的兩頭奶牛中的一頭，以及位于位置 15 的奶牛。

解題思路

這道題我們首先要計算出$R$的值。
如何求$R$呢？
我們其實可以發現，$R$就是最小的兩個不同的狀態的位置之差。
也就是
$R=min(x_i?x_j)(j<i,s_i=s_j)$
那么我們只要先排序在計算就行了。
我們現在要求的是疾病開始傳播之前已經得病的奶牛的最小數量。
先算出一共有多少塊得病的，設為$A$。
塊的定義是，一連串$1$，沒有$0$。
比如：$110101$
這個字符串就有$3$塊，每一塊的長度分別為$2$，$1$，$1$。
再算出符合$R$的的塊數，設為$B$。
答案就是$A+B$。
具體為什么可以用樣例來試一下。

得分情況

比賽時$100$分。

第三題：$Cowntact$ $Tracing$

題目

題目描述 由于高傳染性的牛傳染病 COWVID-19 的爆發，Farmer John 非常擔憂他的奶牛們（編號為 1…N）的健康。最近，Farmer John 對他的所有奶牛進行了檢測，發現有一部分奶牛對該疾病的檢測結果呈陽性。利用牛棚內的視頻監控，他得以查看最近的奶牛之間的互動行為，結果發現奶牛們互相打招呼時，她們會握蹄，不幸的是這是一種會將疾病從一頭奶牛傳播給另一頭奶牛的行為。Farmer John 匯總了一個添加了時間戳的清單，每條數據的形式為 (t,x,y)，表示在時間 t，奶牛 x 與奶牛 y 握了蹄。Farmer John 同時還知道以下信息： （一）他的農場上恰有一頭奶牛最初帶有攜帶疾病（我們將這頭奶牛稱為“零號病人”）。 （二）一旦一頭奶牛被感染，她會在接下來的 K 次握蹄中傳染疾病（可能會與同一頭奶牛握蹄多次）。握蹄 K 次后，她不再在此后的握蹄中傳染疾病（因為此時她意識到了她會傳染疾病，于是會仔細地洗蹄）。 （三）一旦一頭奶牛被感染，她會持續處于被感染狀態。 不幸的是，Farmer John 不知道他的 N 頭奶牛中的哪一頭是零號病人，也不知道 K 的值！基于他的數據，請幫助他縮小這些未知量的范圍。保證至少有一種可能的情況。輸入 輸入的第一行包含 N（2≤N≤100）和 T（1≤T≤250）。下一行包含一個長為 N 的字符串，每個字符均為 0 或 1，表述目前 Farmer John 的 N 頭奶牛的狀態——0 表示一頭健康的奶牛，1 表示一頭染病的奶牛。以下 T 行每行包含 Farmer John 的互動清單中的一條記錄，由三個整數 t、x 和 y組成，其中 t 為一次互動發生的正整數時間（t≤250），x 和 y 為范圍 1…N 內的不同整數，表示時間 t 握蹄的兩頭奶牛。在每一時刻至多只有一次互動發生。輸出 輸出一行，包含三個整數 x、y 和 z，其中 x 為可能為零號病人的奶牛數量，y 為與數據一致的最小可能 K 值，z 為與數據一致的最大可能 K 值（如果通過數據無法推斷 K 的上界，z 輸出 "Infinity"）。注意可能有 K=0。樣例輸入 4 3 1100 7 1 2 5 2 3 6 2 4樣例輸出 1 1 Infinity數據范圍限制提示 唯一可能是零號病人的是奶牛 1。對于所有的 K>0，奶牛 1 在時刻 7 感染奶牛 2，而奶牛 3 和奶牛 4 均不會被感染。

解題思路

這道題的方法是暴力枚舉。
我們直接枚舉$0$號病人和$K$，然后判斷是否正確。
具體判斷：
我們先把$0$號病人給標記為有病，然后看是否可以傳染（次數$+1$還是小于等于$K$），如果可以，就把那個跟他握手的人標記為有病。
最后只要看一下最后標記的是否與輸入的一致，就行了。

得分情況

比賽時$100$分。

總結：

這次比賽難度不算大，下次繼續努力！

總結

以上是生活随笔為你收集整理的2020.04.08【NOIP普及组】模拟赛C组24 总结的全部內容，希望文章能夠幫你解決所遇到的問題。

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