題目一

描述

exchange

背景
有n個(gè)人一同出去玩，每個(gè)人有一張火車票。由于火車票實(shí)行實(shí)名制，每張火車票也對應(yīng)一個(gè)人。
描述
由于某種原因，現(xiàn)在出現(xiàn)了以下情況：每個(gè)人手中有一張票，這張票可能是自己的也可能是別人的。現(xiàn)在任意兩個(gè)人之間可以交換手中的票，求最少進(jìn)行多少次交換使得每個(gè)人都拿到自己的票。假定交換是依次進(jìn)行的，即同一時(shí)刻只進(jìn)行一次交換，我們也想知道，第一步有多少種方案，能保證交換次數(shù)最少。
輸入格式
輸入有2行，第一行有兩個(gè)用空格隔開的正整數(shù)n、k(k代表任務(wù)種類，詳見輸出格式)，第二行有n個(gè)用空格隔開的正整數(shù)，第i個(gè)為Pi，代表著第i個(gè)人手中的票是第Pi個(gè)人的。
輸出格式
如果k=1，那么輸出只有一個(gè)整數(shù)，表示最少交換的次數(shù)；如果k=2，那么輸出有兩行，第一行是一個(gè)整數(shù)，表示最少交換的次數(shù)，第二行有一個(gè)整數(shù)，表示第一步的方案數(shù)。

---

分析

• 找到所有的循環(huán), 每個(gè)循環(huán)中置換次數(shù)是這個(gè)循環(huán)中元素的個(gè)數(shù)-1. 把所有的都加起來就得到總次數(shù). 這個(gè)可以參考codevs的排序的代價(jià), 不過這里代價(jià)都是0.
• 如果再來做第二問, 在一個(gè)循環(huán)中, 假設(shè)循環(huán)中元素的個(gè)數(shù)是n, 第一步選兩個(gè)元素交換, 第一個(gè)元素有n種選擇, 第二個(gè)元素有n-1種選擇. 最終交換a和b與交換b和a是一樣的, 所以這個(gè)循環(huán)中第一步選擇的方案數(shù)是n*(n-1)/2.

---

題目二

描述

在某一時(shí)刻，存活的獅子有地位高低之分，能力值高的地位高，能力值相同的當(dāng)中年齡大的地位高。任何時(shí)刻，地位最高的獅子可以吃掉地位最低的獅子，但如果這樣做，地位最高的獅子能力值會(huì)減少它吃掉的獅子的能力值。假定所有獅子都足夠聰明，并且在保證自己不死的前提下會(huì)盡量吃掉別的獅子。現(xiàn)給出每個(gè)獅子的年齡和能力值，求哪些獅子死了。

輸入格式
輸入有2行，第一行有一個(gè)正整數(shù)n。第二行有n個(gè)用空格隔開的正整數(shù)，按年齡從小到大依次給出每個(gè)獅子的能力值，并按輸入順序編號(hào)為1~n。
輸出格式
輸出有2行，第一行有一個(gè)整數(shù)m，表示死去的獅子的個(gè)數(shù)。第二行有m個(gè)用空格隔開的正整數(shù)，為死去的獅子在輸入中的編號(hào)（請從小到大輸出）。

---

分析

• 看來直接遞歸是最好的辦法了.
  在遞歸過程中用一個(gè)棧來保存先后死掉的獅子. 先假設(shè)當(dāng)前最厲害的獅子A吃掉了最弱的獅子B, 遞歸下一層直到只剩一只獅子, 然后返回處理, 如果當(dāng)前A在后來被吃掉了, 那么獅子A一定不會(huì)吃掉B, 就在棧中找到B, 把它和以上的元素都退棧. 吃掉的獅子個(gè)數(shù)修改為當(dāng)前的遞歸層數(shù).

• 還有其他辦法不用遞歸, 但都看不太懂. 遞歸最直接了.

• 獅子的信息可以用pair存, 自動(dòng)按兩維排序.

---

題目四

描述

背景
有兩種液體A和B，等量混合時(shí)完全反應(yīng)生成氣體揮發(fā)不留渣；不等量混合時(shí)等量部分發(fā)生上述反應(yīng)，多出部分留下。
描述
現(xiàn)有n個(gè)杯子排成一排，每個(gè)杯子里裝有一種液體。我們可以進(jìn)行若干次如下操作：選擇兩個(gè)相鄰的杯子，這兩個(gè)杯子中的液體種類必須是不同的，將其中一個(gè)杯子里的液體全部倒入另一個(gè)杯子中（杯子容積很大，不考慮溢出），反應(yīng)充分之后拿走所有空杯子（拿走空杯子可以使原本不相鄰的杯子變得相鄰）。給出一個(gè)初始狀態(tài)，求最少剩下多少個(gè)杯子。
輸入格式
輸入有n+1行，第一行有一個(gè)正整數(shù)n，接下來的n行，每行格式為“Vi Ki”,Vi為一正整數(shù)，表示這排杯子從左數(shù)第i個(gè)杯子的液體量，Ki為一個(gè)字符A或B，表示這排杯子從左數(shù)第i個(gè)杯子里液體的種類。
輸出格式
輸出有一個(gè)整數(shù)，表示最少剩下的杯子數(shù)。

---

分析

• 見官方題解http://pan.baidu.com/s/1eQjateM
• 平衡樹想了想用splay寫的

---

代碼

https://code.csdn.net/snippets/615224

總結(jié)

以上是生活随笔為你收集整理的CH-Round-#63-OrzCC杯#2省选热身赛的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。