0%

競程訓練 2020 10/19 (共解6題水題)

今天學校有很多事情要忙 所以只勉強解了六題

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
#include <bits/stdc++.h>

#define int long long
#define fastio ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

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
#include <bits/stdc++.h>

#define int long long
#define fastio ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

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
#include <bits/stdc++.h>

#define int long long
#define fastio ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

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
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include <bits/stdc++.h>

#define int long long
#define fastio ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

using namespace std;

signed main(){
fastio
int n;
while(cin >> n){
if(n==0) break;
int ans = 0;
ans += (1<<__lg(n));
while(cin >> n){
if(n==0) break;
ans += (1<<__lg(n));
}
cout << ans << "\n";
}
}

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
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
#include <bits/stdc++.h>

#define int long long
#define fastio ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

using namespace std;

map<int,int> m;
map<int,int> dp;
signed main(){
fastio
int n,k;
cin >> n >> k;
int ans = 0;
if(k==1){
for(int i = 0, tmp;i < n;i++){
cin >> tmp;
ans += m[tmp]*(m[tmp]-1)/2;
m[tmp]++;
}
}else{
for(int i = 0, tmp;i < n;i++){
cin >> tmp;
if(tmp==0){
ans += m[tmp]*(m[tmp]-1)/2;
m[tmp]++;
continue;
}
if(tmp%k==0) dp[tmp] += m[tmp/k], ans += dp[tmp/k];
m[tmp]++;
}
}
cout << ans << "\n";
}

Codeforces 1005D - Polycarp and Div 3

想法

這題的題目是給一個字串 找最多能分為幾個三的倍數

我們可以使用 $dp$ 來做到這一點

首先 我們紀錄 $前綴和 \% 3$ 的值

然後我們用另外一個陣列來紀錄上一個同餘數的位置

這個位置去減去上一個同餘數的位置就會是三的倍數

複雜度: $O(n)$

程式碼

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
#include <bits/stdc++.h>

#define int long long
#define fastio ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

using namespace std;

signed main(){
fastio
string s;
cin >> s;
int n = s.size();
s = "$" + s;
int now = 0;
int idx[3], dp[n+1];
idx[0] = dp[0] = 0, idx[1] = idx[2] = -1;
for(int i = 1;i <= n;i++){
now = (now + s[i]-'0')%3;
dp[i] = dp[i-1];
if(idx[now]!=-1) dp[i] = max(dp[i],dp[idx[now]] + 1);
idx[now] = i;
}
cout << "\n";
cout << dp[n] << "\n";
}
1