幾天前寫的，忘了放了，在此填坑
10月16的題我出的不寫題解了
lzxkj
題目背景
眾所不周知的是， 酒店之王 xkj 一個經常迷失自我的人 有一天， 當起床鈴再一次打響的時候， TA 用 O(1)的時間在 TA 那早就已經生銹的大腦中自動生成了一串數字， 天啊 TA 們實在是太亂了 盡管 xkj 對眼前的世界不屑一顧， 可是 TA 知道， 如果繼續迷失的話， 自己會被那個該死的樓管記上然后站在級部門口的， TA 再迷失也終究逃不過現實主義的摧殘。所以， TA 靜下心來， 希望把數字整理一下(順道再睡一會兒)
題目描述
在酒店之王 xkj 腦海當中生成的數字十分的雜亂無序， 一點也不當年信哥要求的一步到位,合理合法
例如， 有的是這樣的 92839489， 165651， 23 ， 9， 00000000
但是有的又是這樣的 283748.2398479， 239.39， 0.0， 00002333.333000000
所以 TA 希望自己可以先把 TA 們整理的科學一下(直接說科學計數法不就完事了)，總而使 TA 們看起來十分的優美
例如 92839489 整理成 9.2839489E7
再例如 9 整理成 9E0
還是例如 0.0 或者說是 0 整理成 0
最后比如 00002333.333000000 整理成 2.333333E3
亦或比如 0.0023333 整理成 2.3333E-3
酒店之王 xkj 現在由于還需要加工一下自己的樣品被， 把自己的邊邊角角修一下，所以 TA 只好把任務交給了已經開始讀操前讀的 cdycdy 同志加油!!!xkj 在勝利的彼岸等你!!!
輸入格式
一行,一串數字可能是整數,也可能是浮點數
輸出格式
一行， 表示這一串數字用科學計數法表示的格式
樣例輸入1
92839489樣例輸出1
9.2839489E7樣例輸入2
00002333.333000000樣例輸出2
2.333333E3樣例輸入3
0.0樣例輸出3
0樣例輸入 4
10000樣例輸出4
1E4樣例輸入5
10樣例輸出5
1E1樣例輸入6
0.0023333樣例輸出6
2.3333E-3溫馨提示
請您盡量思考一下科學計數法的特殊情況 最好不要被一些稀奇古怪的東東 hack 掉(^_^ ^_^ ^_^ ^_^)
數據范圍
保證對于 100%的數據給出數的長度不超過 15000 位請您放心的使用各種算法本題十分良心 絕對不卡時間(但是不要太過分) -----沃茲基碩德
題解
xjb膜
先判斷是不是整數，如果是整數就強制把它末尾加上點，轉化為小數
然后把前導0和后導0刪除
然后找小數點位置，有四種情況：
(1)只有.一個字符，說明肯定是0
(2).后面沒有字符，說明是整數。輸出第1位，然后一個小數點，然后輸出后面的位即可。注意末尾的0不能輸出。最后輸出E和小數點與第一位的距離
(3).前面沒有字符，說明是個0點幾的小數，同上。注意前導0不能輸出。
(4).的前后都有字符，那么就直接輸出整個數即可，在第一個數后面加上.，中間的.不輸出，最后還是輸出E和小數點與第一位的距離
對于負數我們判一下開頭是不是負號，并把負號扔了，如果是，那么我們輸出加上負號就行了。
death
題目背景
眾所不周知的是， 酒店之王 xkj 一個經常埋葬死去自己的人當 TA 再一次從迷失的困境之中走出來的時候， TA 被某錘姓男子告知:“你違紀了”違紀就意味著精神的死亡， 靈魂的無處安放也許這才是最好的歸途......
題目描述
xkj 的靈魂不斷的飄蕩,飄蕩到了食堂的打飯口,TA 無助的望了一眼,下定決心:先把肚 子填飽再說食堂現在還有 n個食物,每一個食物都有一個美味程度 wi,但是同樣也存在一個費用vi,xkj 當然希望吃到美食的美味程度總和最大,但是想必你也知道,TA 的飯卡最近有一些拮據最多只可以消費 W 元,由于 TA 的靈魂在飄蕩的時候忘記了帶上腦子(唉,腦子是一個好東西),所以 TA 找到了還在站級部的 cdy,希望 cdy 幫 TA 計算一下,TA 在飯卡不破產的情況下,該如何消費使自己吃到食物的美味程度總和最大
輸入格式
第一行一個整數 n 表示一共有 n 個食物
接下第 2 行至第 n+1 行每行兩個整數 vi,wi 表示該食物的費用以及美味程度
最后一行一個整數 W 表示最多可以消費 W 元
輸出格式
一行， 表示合法消費情況下的最大美味程度總和
樣例輸入
4
2 3
1 2
3 4
2 2
5樣例輸出
7樣例解釋
選擇 1,2,4 號物品
溫馨提示
這不就是一個裸的 01 背包嗎??????
數據范圍
保證對于 100%的數據1<=n<=100 1<=wi<=1000 1<=vi<=10^7 1<=W<=10^9
題解
根據數據范圍，我們把消費的價格作為下標肯定會各種TLE和MLE，但是美味程度是1000的，所以我們可以把美味程度作為下標
f[i][j]表示選取前i個物品中的若干個，物品的價值為j時的最小體積。
f[i][j]=min(f[i-1][j],f[i-1][j-w[i]]+v[i])
然后直接遞推滾動一下就行了
relive
題目背景
眾所不周知的是， 酒店之王 xkj 一個經常死去活來的人現在就連 TA 自己都不知道到底該不該醒過來。 也許在黑暗中醒著在光明中睡著未嘗不是一種逃避現實的方法可是 TA 早已飽受現實主義的摧殘,也許是是時候該做一個了斷了.好吧天亮之后總是潦草一場,清醒的人最荒唐清醒歸慶清醒 xkj 知道:有的時候急急忙忙襪子會反穿.所以 TA 認為一切都應該有 序， 畢竟有序才是人間大美嘛但是 xkj 是一個十分懶惰的人,所以盡管已經存在了 c++11 的 STL 提供的強力 sort()了,TA 還是不愿意自己動手,所以 TA 十分邪惡把 cdy 也拉上了 TA 的賊船。cdy 還想好好的多活幾年,所以 TA 才不愿意同 xkj 一同搭乘通往天堂的高鐵(除非十分好看的高鐵服務小姐)。 由于 xkj 使用拼多多購買的高鐵車票是由新興紅牛黨 wzy倒買的所以 cdy 才有逃出來的機會， 但是 xkj 在車票上又設下了機關， 所以 cdy 必須完成挑戰才可以復活,而挑戰的謎底竟然是 xkj 一直偏愛的有序性
題目描述
挑戰分為三重
第一重 排序
第二重 求逆序對
第三重 排序最小成本
科普時間:最小成本排序就是按升序排序排序的代價,譬如說 1,2,3,5,4 排序只需要交換 4,5 即可所以代價就是(4+5)=9;也就是交換兩個數的代價 再比如說 83,17,8 按照升序排好序就是交換 83 與 8 代價和為 91
輸入格式
第一行 一個整數 n 表示序列數的個數
第二行,一個整數數量為 n 的序列
輸出格式
共三行,第一行為按照原數列排好序之后的數列第二行為逆序對數第三行為排序最小成本
樣例輸入
5
1 2 3 5 4樣例輸出
1 2 3 4 5
1
9樣例解釋
這還需要解釋????
溫馨提示
這回就木有提示了
數據范圍
保證對于 30%的數據 n<=10000
保證對于 100%的數據 n<=100000
每一個數的大小 ni 保證(1<=ni<=10^9)
保證數列的數互不重復
題解
T1+T2：cdq分治。略。
T3：《挑戰程序設計競賽》（第二版）上的最小成本排序（xkj問我這個問了好幾遍問我會不會）
顯然排序后的序列相對于排序前的序列是一個置換，對于置換里的某個環，我們可以考慮兩種情況，一種是某個元素繞著這個環逆時針走一圈，直到這個元素到了他的后繼位置，那么其它元素和它交換也都到了它的后繼位置。顯然我們必須讓這個元素最小。此時答案為sum+(n-2)min。第二種情況是請一個外來元素幫助替換，替換完了再把它攆回去，那么答案為sum+(n+1)nage+min，當然那個元素要取最小的啦，就是排序之后第一小的元素對于每個環，這兩個數取min。
