- 小麥畝産一千八
- 休息
- 軍訓
T1: 小麥畝産一千八
題目描述
“有了金坷垃，肥料一袋能頂兩袋撒，小麥畝産一千八，吸收兩米下的氮磷鉀……”，話說HYSBZ（Hengyang School for Boys & Zy）學識淵博孩紙們一講到糧食，都會想起印度那個著名的故事：國王要在第一個格子裡放入一粒小麥，接下來的格子放入前面一個格子的兩倍的小麥。這樣所需小麥總數是巨大的，哪是不用金坷垃就能完成的任務？不過為了減輕國王的任務，那個下棋獲勝的宰相換了一個要求：“我隻需要你在棋盤外放一粒小麥，可以将其了解為第0 個格子，然後你需要在第一個格子裡放入 p 粒小麥，之後==每一個格子放入前兩個格子的小麥數之和的小麥，并且要滿足第 a 個格子放 x 粒小麥，第 b 個格子放……”說到這，宰相突然發現自己說的滿足第a 個格子放x 粒小麥的情況可能不存在……欺君可是大罪啊！國王看到宰相遲遲不說，自己也煩了！我自己來算！于是國王拜托你，讓你算出第b 個格子應該放幾粒小麥。當然，就算答案不存在，你也是要告訴國王的。
輸入
該題有多組資料，請讀到檔案末結束。
對于每一組資料僅一行，3 個正整數 a , x , b ,分别表示第 a 個格子放了 x 粒小麥，以及你所需要計算的是第 b 個格子的小麥數量。
輸出
對于每一次詢問，僅1 個整數，為第 b 個格子的小麥數量，若宰相說的情況不存在，那麼請輸出-1。
樣例
輸入
1 1 2
3 5 4
3 4 6
12 17801 19
輸出
2
8
-1
516847
樣例解釋
對于樣例二，f[1]=2 時,能夠滿足f[3]=5，是以宰相沒有撒謊，此時第5 個格子的小麥數應為f[4]=f[2]+f[3]=3+5=8.
資料範圍
對于50%的資料：如果答案存在，那麼p<=50
對于100%的資料：1<=資料組數<=10000，1<=a,b<=20, 資料保證如果答案存在，那麼1<=p<=1000000.
思路
f[n] = f[n - 1] + f[n - 2] ,這熟悉的式子，當然首先應該想到斐波那契數列啦。然後，再試一試手推，然後就能得到小麥個數的通項公式：
g(x) = p * f[a] + f[a - 1]
（g(x) 為第 x 格的小麥數量， p 為第 1 格的小麥數量，f數組為斐波那契數列）
（在本題中，f[0] = 0, f[1] = 1）
因為a，b 都在1~20之間，是以可以先算出斐波那契數列前20項的值
f[1] = 1;
for (int i = 2; i <= 21; i ++)
f[i]=f[i - 1] + f[i - 2];
然後，就要開始驗證了
if ((x - f[a - 1]) % f[a])
{
printf("-1\n");
continue;
}
p = (x - f[a - 1]) / f[a];
printf("%lld\n",f[b] * p + f[b - 1]);
p 一定是個整數，是以不能整除肯定不對，能整除的話，就把 p 算出來然後再用公式推 b 格的麥子數
附
因為有多組資料，是以可以用一個 while 一直讀到文章末尾
EOF ：End Of File
另附
十年OI一場空，不開long long 見祖宗
T2: 休息
題目描述
休息的時候，可以放松放松渾身的肌肉，打掃打掃衛生，感覺很舒服。在某一天，某LMZ 開始整理他那書架。已知他的書有n 本，從左到右按順序排列。他想把書從矮到高排好序，而每一本書都有一個獨一無二的高度Hi。他排序的方法是：每一次将所有的書劃分為盡量少的連續部分，使得每一部分的書的高度都是單調下降，然後将其中所有不少于2 本書的區間全部翻轉。重複執行以上操作，最後使得書的高度全部單調上升。可是畢竟是休息時間，LMZ 不想花太多時間在給書排序這種事上面。是以他劃分并翻轉完第一次書之後，他想計算，他一共執行了多少次翻轉操作才能把所有的書排好序。LMZ 驚奇地發現，第一次排序之前，他第一次劃分出來的所有區間的長度都是偶數。
輸入
第一行一個正整數n, 為書的總數。
接下來一行n個數，第i個正整數Hi，為第i 本書的高度。
輸出
僅一個整數，為LMZ 需要做的翻轉操作的次數。
樣例
輸入
6
5 3 2 1 6 4
輸出
3
樣例解釋
第一次劃分之後，翻轉(5,3,2,1)，（6,4）。之後，書的高度為1 2 3 5 4 6，然後便是翻轉（5,4）即可。
思路
先選出最長的逆序對，然後把它們翻轉，翻轉之後，區間内都是有序的，然後的翻轉隻可能發生在區間連結處，接下來的問題就變成了求逆序對的個數
szsy知名巨佬zwt說：其實就是轉了一次之後的逆序對個數加上2.
一道比較顯然的結論題。
先說解法。首先，找出所有的單調下降序列，然後把他們全部翻轉過來，記錄翻轉的次數。
之後求出翻轉後序列的逆序對數，答案就是逆序對數與翻轉次數之和。
證明如下：
在找出所有的單調下降序列并翻轉後，可以發現，剛剛找到的區間内的元素都已經變得有序。
也就是說，隻有兩個小區間之間的數可以進行交換。
顯然，我們隻會交換兩個降序的數。即逆序對。
是以答案為逆序對數與第一輪翻轉次數之和。
代碼實作
#include<bits/stdc++.h>
using namespace std;
#define N 100010
int n,a[N],tot,b[N];
long long ans;
void merge(int l,int r)//歸并排序
{
if(r - l < 1)
return;
int mid = (l + r) / 2;
merge(l,mid);
merge(mid + 1,r);
int p1 = l, p2 = mid + 1, t = l;
while((p1 <= mid) && (p2 <= r))
{
if(a[p1] > a[p2])//找逆序對
{
b[t ++] = a[p2 ++];
ans += mid - p1 + 1;
}
else b[t ++] = a[p1++];
}
while(p1 <= mid)
b[t ++] = a[p1 ++];
while(p2 <= r)
b[t ++] = a[p2 ++];
for(int i = l; i <= r; i ++)
a[i] = b[i];
}
typedef struct
{
int l, r;
}block;
block p[N];
int main()
{
int cnt = 0;
scanf("%d", &n);
for(int i = 1; i <= n; i ++) {
scanf("%d", &a[i]);
if(a[i] > a[i - 1])
{
p[cnt].r = i - 1;
p[++cnt].l = i;
}
}
p[cnt].r = n;
for(int i = 1; i <= cnt; i++)
reverse(a + p[i].l, a + p[i].r + 1), ans++;
merge(1, n);
printf("%lld",ans);
return 0;
}
T3: 軍訓
題目描述
HYSBZ 開學了！今年HYSBZ 有 n 個男生來上學，學号為1…n，每個學生都必須參加軍訓。在這種比較堕落的學校裡，每個男生都會有 G[i] 個女朋友，而且每個人都會有一個欠扁值Hi。學校為了保證軍訓時教官不會因為學生們都是人生赢家或者是太欠扁而發生打架事故，是以要把學生們分班，并做出了如下要求：
1.分班必須按照學号順序來，即不能在一個班上出現學号不連續的情況。
2.每個學生必須要被分到某個班上。
3.每個班的欠扁值定義為該班中欠扁值最高的那名同學的欠扁值。所有班的欠扁值之和不得超過Limit。
4.每個班的女友指數定義為該班中所有同學的女友數量之和。在滿足條件1、2、3 的情況下，分班應使得女友指數最高的那個班的女友指數最小。
請你幫HYSBZ 的教務處完成分班工作，并輸出女友指數最高的班級的女友指數。
輸入資料保證題目有解。
輸入
第一行僅2個正整數 n , Limit，分别為學生數量，欠扁值之和的上限。
接下來n 行每行2 個正整數 H[i]，G[i]，分别為學号為 i 的學生的欠扁值和女友數。
輸出
僅1 個正整數，表示滿足分班的條件下女友指數最高的班級的女友指數。
樣例
輸入
4 6
4 3
3 5
2 2
2 4
輸出
8
樣例解釋
分班按照（1,2），（3,4）進行，這時班級欠扁值之和為4+2=6<=Limit，而女友指數最高的班級為(1,2)，為8。容易看出該分班方案可得到最佳答案。
（一開始并沒有看懂樣例 。。。）
思路
題目中要求最小值的最大值,這種求最大最小雙最值問題可以很容易想到用二分答案來做。那對于判斷ans的check是否能用貪心求解?顯然對于某一連續段而言,加入一個學生,可以增加其女友指數,但也有可能使得欠扁值增大,并沒有什麼能夠保證正确性和最優性的貪心,那麼可以考慮DP,則可得到轉移方程如下:
dp[ i ] = min{ dp[ j ] + max( H[ k ] ) }
顯然轉移一次複雜度為O(n),總的時間複雜度為O(n^2),顯然是會逾時的.。
但是實際上并非所有的轉移都是有效的,有的實際上是無用的 。
将 pos (位置)和 H (欠扁值)放在二維坐标軸上,目前 i 點,可以從直線 p 以後的點轉移過來( p 表示滿足二分的答案距 i 最遠的位置),在k和 i 之間的點轉移過來的話,實際上是無用的,在這一段的最優轉移是從 k 處切開, k 以後的點一直到i為止分成一個班,因為 k 以後的點, i 是最大的,那麼在這之間一定是不會改變其最大值的,那麼在 k 以後選取點則是最優的,同理 j 也如此.那麼可以用單調隊列來維護一個H單調遞減的序列,便可以達到減少轉移個數實作優化的目的。
(其實可以進一步優化,用小根堆維護dp[j]+max{H[k]| j< k<=i },i<=j< i)
代碼實作
注釋真的很良心吧
#include<bits/stdc++.h>
using namespace std;
#define INF 1 << 30
#define maxn 20001
//一個附贈的快讀模闆
/*
int read()
{
char ch = getchar();
int ret = 0, flag = 1;
while(ch < '0'|| ch > '9')
{
if(ch == '-')
flag = -1;
ch = getchar();
}
while(ch >= '0' && ch <= '9')
{
ret = ret * 10 + ch - '0';
ch = getchar();
}
return ret * flag;
}
*/
/*
hint數組：每個人的欠扁值
girl數組：每個人的女友數
lim：最大限制欠扁值和
n：人數
sum_girl數組：這個人加其之前所有人的女友總和
que：用于維護一個hint單調遞減的序列的單調隊列
狀态轉移方程：dp[i] = min{dp[j] + max(hint[k])}
*/
int hint[maxn], girl[maxn], lim, n;
int dp[maxn], ans,sum_girl[maxn],que[maxn];
//全局變量不賦初值預設為零
bool check(int ans)//判斷ans
{
int head = 1,tail = 0, pos = 1;//pos表示能夠滿足ans的分段臨界位置
for(int i = 1; i <= n; i ++)
{
while((sum_girl[i] - sum_girl[pos - 1]) > ans)
pos ++;//臨界位置向右移動
while((head <= tail) && (que[head] < pos))
head ++;//不能被轉移到的點出隊
while((head <= tail) && (hint[i] >= hint[que[tail]]))
tail --;//将i入隊時,為維護隊列單調性,H比i小的出隊
que[++tail] = i;//i入隊
dp[i] = dp[pos - 1] + hint[que[head]];//考慮特殊位置臨界點處
for(int j = head; j < tail; j ++)
dp[i] = min(dp[i],dp[que[j]] + hint[que[j + 1]]);//使該點的dp值盡可能小
if(dp[i] > lim)
return false;//若最小dp值超過限制,ans不存在
}
return true;
}
//二分答案：僅限答案單調時使用！！！
//如果check(mid)找到了的話，說明最大的答案就是mid了
//繼續往之前找，要是能找到，那就一定是更加ok的答案，那就繼續更新
int find_ans(int l,int r)//從單人最多一直找到全在一班
{
int ans = 0;
while(l <= r)
{
int mid = (l + r) / 2;
if(check(mid))//= if(check(mid) = true)
{
ans = mid;//找到了，就把ans更新為mid
r = mid - 1;//再往前找找
}
else//沒找到
l = mid + 1;//那就隻好往後找找啦
}
return ans;
}
int main()
{
scanf("%d %d", &n, &lim);
int l = 0, r = 0;//記得初始化！！！
for(int i = 1; i <= n; i ++)
{
scanf("%d %d", &hint[i], &girl[i]);
sum_girl[i] = sum_girl[i - 1] + girl[i];//計算總和
l = max(l,girl[i]);//l最後變為單人女友最多的數量
r += girl[i];//r最後為全部女友數
}
int ans = find_ans(l,r);//二分答案
printf("%d",ans);
return 0;
}
![常用的排序算法的空間複雜度和時間複雜度[圖]](data:image/gif;base64,R0lGODlhAQABAIAAAP///wAAACwAAAAAAQABAAACAkQBADs=)