前言
看完題目大意母赵，先思考，再看解析具滴；覺得題目大意不清晰市咽，點擊題目鏈接看原文。
A
題目鏈接
題目大意：n個數字a[i]抵蚊，從中找出最長連續(xù)上升子序列的長度施绎。
a1,?a2,?...,?an (1?≤?a[i]?≤?1e9)
n (1?≤?n?≤?1e5)
Examples
input
5
1 7 2 11 15
output
3
代碼實現：
int maxNum = 1, k = 1;
for (int i = 1; i < n; ++i) {
if (a[i] > a[i - 1]) {
++k;
maxNum = max(maxNum, k);
}
else {
k = 1;
}
}
題目解析：
對于一串序列，假如是以a[i]結尾贞绳，如果a[i+1] > a[i] 那么a[i+1]會讓序列+1谷醉；如果a[i+1] <= a[i] 那么a[i+1]會重新開始新的序列。
B
題目鏈接
題目大意：給出n個數字 a1,?a2,?...,?an冈闭，尋找a[i] + a[j] = 2^x俱尼，并且i < j（x為任意數字）。算出總共有多少對存在萎攒？
n (1?≤?n?≤?1e5)
a1,?a2,?...,?an (1?≤?ai?≤?1e9).
Examples
input
4
7 3 2 1
output
2
方法1
代碼實現：
for (int i = 0; i < n; ++i) {
long long k = 1;
while (k <= a[i]) {
k = k << 1;
}
k -= a[i];
long long left = 0, right = i - 1;
long long l = left, r = right;
while (left < right) { // 尋找 == k的左邊界
// printf("%d %d %d \n", i, left, right);
long long mid = (left + right) / 2;
if (a[mid] > k) {
right = mid - 1;
}
else if (a[mid] < k) {
left = mid + 1;
}
else {
l = mid;
right = mid;
}
}
// printf("%d %d %d \n ------ \n", i, left, right);
if (a[left] == k) {
l = left;
}
left = 0;
right = i - 1;
while (left < right) { //選擇 == k的右邊界
// printf("%d %d %d \n", i, left, right);
long long mid = (left + right) / 2;
if (a[mid] > k) {
right = mid - 1;
}
else if (a[mid] < k) {
left = mid + 1;
}
else {
r = mid;
left = mid + 1;
}
}
// printf("%d %d %d \n", i, left, right);
if (a[right] == k) {
r = right;
}
if (a[l] == k && a[r] == k && r >= l) {
count += r - l + 1;
// if (a[l] == a[i]) {
// --count; // 排除自己
// }
}
題目解析：
對數組進行從小到大排序遇八，假設有a[i] + a[j] = 2 ^x，并且i < j耍休，x為大于a[j]的最小的2的冪刃永。
那么在[1, j - 1]的區(qū)間內，不存在a[i] + a[j] = 2 ^ (x - 1)和 a[i] + a[j] = 2 ^ (x + 1)羊精。
故而排序后斯够，對于a[j]，只要求出值為(2^x - a[j])的區(qū)間即可喧锦。用二分查找读规。
方法2
代碼實現：
#include <map>
map<int,int> M;
long long ans=0;
int main(){
int n,a;
cin>>n;
while(n--){
cin>>a;
for(int i=0;i<=31;i++) ans+=M[(1LL<<i) - a];
M[a]++;
}
cout<<ans;
}
題目解析：
對于每個數，只考慮前面的組合燃少。
已知束亏，最大數字不會超過2^31，那么對于每個數字枚舉一遍即可阵具，用map來存之前出現的數字碍遍。
C
題目鏈接
題目大意：
一維坐標軸上有n個目標點a[i]，m個源點b[i]怔昨，求最小的距離r雀久，使得每個目標點的r范圍內至少存在一個源點。
n and m (1?≤?n,?m?≤?1e5)
輸入數據：n趁舀、m赖捌，然后是a[i]，b[i]。(?-?109?≤?a[i], b[i]?≤?109)
Examples
input
3 2
-2 2 4
-3 0
output
4
代碼實現：
long long ret = (long long)2 * 10E9;
long long left = 0, right = ret;
while (left < right) {
long long mid = (left + right) / 2;
int j = 0;
for (int i = 0; i < n; ++i) {
while (j < m) {
if (a[i] >= b[j] - mid && a[i] <= b[j] + mid) {
break;
}
++j;
}
}
if (j < m) {
ret = mid;
right = mid;
}
else {
left = mid + 1;
}
}
題目解析：
如果r可行越庇，那么r+1必然可行罩锐，符合二分要求。
同時卤唉，為了枚舉更加迅速涩惑，可以先對a[i]和b[i]進行排序。對于每一個目標點i桑驱，我們從小開始選b[j]竭恬，值得出現一個符合要求；那么當目標點i對應的源點為j熬的，那么有i+1目標點的源點>=j痊硕。
D
題目鏈接
題目大意：
小明要從家里去郵局，已知起點到終點的距離為d押框。
小明有一輛自行車岔绸，騎車速度為a秒/公里；他也可以走路橡伞，走路速度為b秒/公里(a < b)盒揉。
但是車子很舊，每走k公里就要修理一次兑徘，時間為t秒刚盈。（如果不修就要推著車子，速度和走路是一樣）
車子最初k公里不需要修理道媚，問最短的時間到達終點扁掸。
d,?k,?a,?b,?t (1?≤?d?≤?1e12; 1?≤?k,?a,?b,?t?≤?1e6; a?<?b)
Examples
input
5 2 1 4 10
output
14
代碼實現：
long long d, k, a, b, t;
cin >> d >> k >> a >> b >> t;
if (d <= k) {
ret = d * a;
}
else {
d -= k;
ret = a * k;
long long left = d % k;
long long c = d / k;
ret += min(k * a + t, k * b) * c;
ret += min(t + left * a, left * b);
}
題目解析：
先讓車子走k公里（因為a<b)，接下來把剩下的路分成若干段最域，每段k公里，最后剩下的部分為left公里锈麸。
對于每段的k公里镀脂，根據k * a + t 和 k * b 的大小決定走路還是騎車；
最后的left公里忘伞，根據t + left * a 和 left * b的大小決定走路還是騎車薄翅；
是否存在前面走路，后面騎車的情況氓奈？
假設最后一段是騎車翘魄，那么前面的k公里必然也是騎車。
總結
題目不難舀奶，需要一點點思維能力暑竟。
