今天學校有很多事情要忙 所以只勉強解了六題
TIOJ
TIOJ 1419 - 飛天李晴 （2016北市賽）
先將每個點依照距離原點的距離排序
之後用前綴最大值減後綴最小值即可
複雜度: $O(nlogn)$
程式碼1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
using namespace std;
struct Point{
int x,y,val;
bool operator < (Point b){
return x*x+y*y < b.x*b.x+b.y*b.y;
}
Point(int x, int y, int val): x(x), y(y), val(val){}
};
signed main(){
fastio
int n;
cin >> n;
vector<Point> v;
for(int i = 0;i < n;i++){
int a,b,c;
cin >> a >> b >> c;
v.emplace_back(a,b,c);
}
sort(v.begin(),v.end());
int pref[n+1], suff[n+1];
pref[0] = 0, suff[n] = INT_MAX;
for(int i = 0;i < n;i++){
pref[i+1] = max(pref[i],v[i].val);
}
int ans = 0;
for(int i = n-1;~i;i--){
suff[i] = min(suff[i+1],v[i].val);
ans = max(ans,pref[i+1]-suff[i+1]);
}
cout << ans << "\n";
}
TIOJ 1029 - A遊戲
這題是區間 $dp$
我們讓 $dp[l][r]$ 為 $[l,r]$ 之間 先手能拿的最大值
因此 $dp[i][i]$ 為 $arr[i]$ 因為先手在區間中能拿的最大值就是 $arr[i]$
$sum(l,r) - dp[l][r]$ 就會是後手拿的最大值
由於先手拿完之後 後手就會變成下一回合的最大值
因此我們如果拿前面 $arr[l]$ 那麼這個區間的最大值就會變成 $arr[l]$ 加上 $[l+1,r]$ 後手的最大值
而那後面也是以此類推
得到轉移式 $dp[l][r] = max(sum(l+1,r)-dp[l+1][r]+arr_l,sum(l,r-1)-dp[l][r+1]+arr_r)$
然後可以用前綴和加速求 $sum(l,r)$
複雜度： $O(n^2)$
程式碼1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
using namespace std;
signed main(){
fastio
int n;
cin >> n;
int arr[n+1], pref[n+1] = {}, dp[n+1][n+1];
for(int i = 1;i <= n;i++){
cin >> arr[i];
dp[i][i] = arr[i];
pref[i] += pref[i-1] + arr[i];
}
for(int j = 1;j <= n;j++){
for(int i = j-1;i;i--){
dp[i][j] = max(pref[j]-pref[i]-dp[i+1][j]+arr[i],pref[j-1]-pref[i-1]-dp[i][j-1]+arr[j]);
}
}
cout << dp[1][n] << " " << pref[n] - dp[1][n] << "\n";
}
TIOJ 1030 - Floor Machine
這題仔細想一下就知道排序後會得到最佳解
然後 $a0 + a_1 + … + a{n-1} + a_{n-1}$ 就是答案
程式碼1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
using namespace std;
signed main(){
fastio
int n;
while(cin >> n){
if(n==0) break;
int arr[n];
for(auto &x : arr) cin >> x;
sort(arr,arr+n);
int ans = 1;
for(auto x : arr) ans += x;
ans += arr[n-1];
cout << ans << "\n";
}
}
TIOJ 1031 - Collecting Beans
當遇到奇數時 丟掉一顆豆子
我們可以用二進位來思考
這個數字不停的除以二並丟掉豆子
最後得到的結論就是每一個數字的二進位的最高位的總和就會是答案
（二進位最高位可以使用 C++ 的 __lg() 來達成）
1 |
|
Codeforces
今天想練練 $dp$ 所以隨便戳了幾題
Codeforces 567C - Geometric Progression
給你一個陣列 問有幾個長度 $3$ 的子序列成一等比數列
（在這裡 $0,0,0$ 也算是等比數列）
想法
要使子序列成等比數列 我們可以由前面掃到後面
我們可以先考慮 $k=1$ 時的情況
當 $k=1$ 時 就是當掃到每一個元素 $a_i$ 時
答案要加上 $cnt[a_i] \times (cnt[a_i]-1) / 2$ (在前面任選兩個相同元素)
當 $k \neq 1$ 時 我們可以多維護一個 $dp$ 陣列
這個 $dp[a_i]$ 存的是每一個元素除以 $k$ 的出現次數
每次在答案中加上 $\displaystyle{dp[\frac{a_i}{k}]}$ 的值
複雜度 ： $O(nlogn)$ （我使用了map）
程式碼
1 |
|
Codeforces 1005D - Polycarp and Div 3
想法
這題的題目是給一個字串 找最多能分為幾個三的倍數
我們可以使用 $dp$ 來做到這一點
首先 我們紀錄 $前綴和 \% 3$ 的值
然後我們用另外一個陣列來紀錄上一個同餘數的位置
這個位置去減去上一個同餘數的位置就會是三的倍數
複雜度： $O(n)$
程式碼
1 |
|
1 |