正文
題目1
題目連結
題目大意：
給出一個圖形，下面是n=1、2、3、4的時候：
現在需要把上面的圖形染色，由若幹個菱形組成；
問，有多少種染色方法？
輸入：
第一行，整數?表示有t個樣例數量 (1≤?≤1000)
接下來每個樣例一行，整數? (1≤?≤10^9).
輸出：
每個樣例一行，染色的方法數量。
Examples
input
2
2
1
output
2
1
樣例解釋：
對于樣例1，當n=2的時候一共有2種染色方法：
對于樣例2，當n=1的時候，隻有1種染色方法：
題目解析：
找規律的問題，先從n=1開始考慮，隻有一種方案；
n=2的時候，我們可以采用染色方案1，将第一個豎着的菱形染色；也可以先上下斜着放，将第二個豎着的菱形染色；
同理n=3時，有将第1、2、3個菱形染色的方案；
總結規律， ans=n；
代碼實作：
int main(int argc, const char * argv[]) {
// insert code here...
int t;
cin >> t;
while (t--) {
int n;
cin >> n;
cout << n << endl;
}
return 0;
} 複制
題目2
題目連結
題目大意：
有n個砝碼，每個砝碼的重量是一樣的；
由于砝碼的重量辨別已經模糊，隻能大概知道的重量區間是在 [a-b, a+b]這個區間内；
現在想知道，這n個砝碼的重量，能否在區間[c-d, c+d]内；
如果可以，則輸出YES；如果不可以，則輸出NO；
輸入：
第一行，整數?表示有t個樣例數量 (1≤?≤1000)
接下來每個樣例一行，5個整數 n,?,?,?,? (1≤?≤1000, 0≤?<?≤1000, 0≤?<?≤1000)
輸出：
每個樣例一行，如果可以，則輸出YES；如果不可以，則輸出NO；
Examples
input
5
7 20 3 101 18
11 11 10 234 2
8 9 7 250 122
19 41 21 321 10
3 10 8 6 1
output
Yes
No
Yes
No
Yes
題目解析：
因為a和b比較小，枚舉下a和b的區間，可以解決問題；
但是假如，a和b很大呢？（0≤?<?≤10^9, 0≤?<?≤10^9）
我們用[l, r]來表示[c-d, c+d]的區間；
我們用[gapL, gapR] 來表示[(a-b)n, (a+b)n]的區間；
隻要這倆個區間有重疊，則表示存在可能性；
這樣就不用枚舉，複雜度從O(N^2)變成O(1)。
代碼實作：
int main(int argc, const char * argv[]) {
// insert code here...
int t;
cin >> t;
while (t--) {
lld n, a, b, c, d;
cin >> n >> a >> b >> c >> d;
lld l = (c - d), r = (c + d);
lld ans = -1;
lld gapL = (a - b) * n, gapR = (a + b) * n;
bool ok = 0;;
if (gapL <= l && l <= gapR) {
ok = 1;
}
else if (gapL <= r && r <= gapR) {
ok = 1;
}
else if (l <= gapL && gapL <= r) {
ok = 1;
}
else if (l <= gapR && gapR <= r) {
ok = 1;
}
if (ok) {
cout << "YES" << endl;
}
else {
cout << "NO" << endl;
}
}
return 0;
} 複制
題目3
題目連結
題目大意：
有n個整數組成的數組，現在對數組的元素重新組織，希望新的數組滿足：
|?[1]−?[2]| ≤ |?[2]−?[3]| ≤ … ≤ |?[?−1]−?[?]|
求新的數組。
輸入：
第一行，整數?表示有t個樣例數量 (1≤?≤1000)
接下來每t個樣例，第一行， 整數? (3≤?≤10^5)
第二行是n個整數，?1,?2,…,?? (−10^9≤??≤10^9).
輸出：
每個樣例一行，新數組的n個整數；
Examples
input
2
6
5 -2 4 8 6 5
4
8 1 4 2
output
5 5 4 6 8 -2
1 2 4 8
題目解析：
假設n個數字散落在一維數軸上，那麼任意兩個數字的絕對值之差，就是兩個數字在數軸之間的間距；
題目的問題轉化為，求一個排列，使得相鄰兩個數字的間距越來越大；
假設從小到大排序完之後，數組是a[N]；容易知道，所有數字中間距的是a[n]-a[1]，那麼可以将這個數字放到最右邊；
同理，第二大的數字要麼是a[1]和a[n-1]，要麼是a[2]和a[n]，我們任取其中一種，假設是a[1]和a[n-1]；
同理，第三大的數字就是a[2]和a[n-1]；
同理，第四大的數字就是a[3]和a[n-1]；
如此交替選擇，會使得間距越來越小，得到了一種滿足題意的解法；
代碼實作：
int a[N];
int ans[N];
int main(int argc, const char * argv[]) {
// insert code here...
int t;
cin >> t;
while (t--) {
int n;
cin >> n;
for (int i = 0; i < n; ++i) cin >>a[i];
sort(a, a + n);
int l = 0, r = n - 1, k = n - 1;
while (l <= r) {
ans[k--] = a[r--];
if (l <= r) {
ans[k--] = a[l++];
}
}
for (int i = 0; i < n; ++i) {
cout << ans[i] << " ";
}
cout << endl;
}
return 0;
} 複制
題目4
題目連結
題目大意：
n個數字的數組，如果某個數字比相鄰左右兩個數字大，則稱為峰；
從n個數字裡面選出連續的k個數字，希望包括盡可能多的山峰；
如果有多種可能，使得第一個位置盡可能小；
輸入：
第一行，整數?表示有t個樣例數量 (1≤?≤1000)
接下來每個樣例第一行，整數n和k (3≤?≤?≤2⋅1e5)
第二行n個整數, ?1,?2,…,?? (0≤??≤1e9, ?? ≠ ?[?+1])
輸出：
每個樣例一行，輸出整數t和l，分别表示k個連續數字最多能被峰分為幾部分，以及區間開始位置；
Examples
input
2
8 6
1 2 4 1 2 4 1 2
5 3
3 2 3 2 1
output
3 2
2 2
樣例解釋：
樣例一選擇的數字區間是[2, 7]，峰的數字有4和4，可以把區間分為3部分，區間開始位置是2；
樣例二的區間是[2, 4]，峰的數字隻有3，可以把區間氛圍2部分，區間開始位置是2；
題目解析：
先找出所有的山峰，假設是m個，周遊這些山峰；
對于第1個山峰，直接放入隊列q；
對于第2個山峰，直接放入隊列q，接下來判斷隊列中的距離是否超過k：如果滿足q.back() - q.front() + 2 >= k 則表示隊列中山峰已經無法用連續的k個數字來包括；
此時需要pop掉隊頭的山峰，也是最早加入的數字。
每加入一個數字到山峰，檢查完隊列數字的合法性，接着計算這個隊列的結果是否更優；
代碼實作：
int a[N];
queue<int> q;
int main(int argc, const char * argv[]) {
// insert code here...
int t;
cin >> t;
while (t--) {
int n, k;
cin >> n >> k;
for (int i = 0; i < n; ++i) {
cin >> a[i];
}
while (!q.empty()) {
q.pop();
}
int ans = 0, start = 0;
for (int i = 1; i < n - 1; ++i) {
if (a[i] > a[i - 1] && a[i] > a[i + 1]) {
q.push(i);
while (q.back() - q.front() + 2 >= k) {
q.pop();
}
if (q.size() > ans) {
ans = q.size();
start = q.back() + 1 - (k - 1);
}
}
}
cout << ans + 1 << " " << max(0, start) + 1 << endl;
}
return 0;
} 複制
題目5
題目連結
題目大意：
給出n個整數的數組，現在每秒可以對數組進行一次操作：
第x秒，可以從數組中選擇出來若幹個數，将每個數加上2^(x-1）；
現在希望數組滿足?1≤?2≤…≤?? ，問最少需要多少秒；
輸入：
第一行，整數?表示有t個樣例數量 (1≤?≤1000)
接下來t個樣例，第一行，整數? (1≤?≤10^5)
第二行，n個整數 ?1,?2,…,?? (−109≤??≤109).
輸出：
最少需要秒數；
Examples
input
3
4
1 7 6 5
5
1 2 3 4 5
2
0 -4
output
2
3
題目解析：
按照題意，分别可以加上數字1、2、4、8、16、、、
由于數字遞增很快（指數級），可以遇見不會添加很多次；
那麼可以考慮暴力來解決，枚舉x=0、1、2、3、4、5、6的情況是否滿足要求，每次枚舉的複雜度是O（NLogM）；M是數字大小，最多枚舉LogM次；
接着，需要找一種能快速驗證，當x=k的時候，是否滿足要求；
由貪心的思想，我們知道對于數字a[n]，由于預期a[n]是最大的數字，可以直接将所有的數字加到a[n]上；
對于數字a[n-1]，我們希望a[n-1]在滿足a[n-1]<=a[n]的情況下，盡可能的大；
同理，我們希望a[n-2]、a[n-3]、、、都是如此的處理；
那麼問題變成，如何保證a[i-1]在滿足a[i-1]<=a[i]的情況下，a[i-1]盡可能的大？
答案就是：從大到小的加數字(2^(x-1))，直到數字無法添加，此時數字就是最大；
注意，這裡不是從小到大；比如說數字6變成12，如果從大到小有6+4+2=12，但是如果變成從小開始，則會出現取了數字1、2之後，無法取4，最大值就是9；
代碼實作：
typedef long long lld;
lld p[N];
lld a[N];
bool check(int n, int k) {
lld last = llinf;
for (int i = n - 1; i >= 0; --i) {
lld tmp = a[i];
for (int j = k; j >= 1; --j) {
if (tmp + p[j-1] <= last) {
tmp += p[j - 1];
}
}
if (tmp > last) {
return false;
}
last = tmp;
}
return true;
}
int main(int argc, const char * argv[]) {
// insert code here...
p[0] = 1;
for (int i = 1; i < 31; ++i) p[i] = p[i-1] * 2;
int t;
cin >> t;
while (t--) {
int n;
cin >> n;
for (int i = 0; i < n; ++i) cin >> a[i];
int k = 0;
while (1) {
if (check(n, k)) {
cout << k << endl;
break;
}
k++;
}
}
return 0;
} 複制
總結
題目1是找規律，注意看樣例；
題目2是區間重疊，其實是判斷兩個區間是否存在重疊；
題目3是構造，需要一點點想法，借住數軸更容易想通；
題目4是貪心，盡量保證最長的一個隊列，然後枚舉每一個位置；
題目5是暴力+貪心，發現題目計算次數不多，尋找一個快速驗證的方法。