0%

APCS 2022/1/9

Q1. 程式交易

題目連結:h081: 1. 程式交易 - 高中生程式解題系統

想法

第一天先買,維護一個 bool 變數,分為有持股與無持股兩種情況。

  1. 有持股->若當前價格>=當初買的價格(tp)+D,賣掉,tp 改為當前股價
  2. 無持股->若當前價格<=當初賣的價格(tp)-D,買起來,tp 改為當前股價

細節

若交易結束仍持有股票,則不考慮該股票買進的成本 -> 賣掉的時候再加上獲利

實作

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

bool iss=true;
int n,sum,d,tp;

int main(){
ios::sync_with_stdio(0);cin.tie(0);

cin>>n>>d>>tp;

for(int i=1;i<n;++i){
int now;
cin>>now;
if(iss && tp+d<=now){
sum+=now-tp;
tp=now;
iss=false;
}else if(!iss && tp-d>=now){
tp=now;
iss=true;
}
}

cout<<sum<<"\n";
}

Q2. 贏家預測

題目連結:h082. 2. 贏家預測 - 高中生程式解題系統

想法

將輸贏判斷抽象化,方便除錯。其餘依照題目用 vector 模擬即可。

實作

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
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
#include<bits/stdc++.h>
using namespace std;

#define siz(v) ((int)v.size())
using ll=long long;

struct player{
// s, t, fail times
ll s,t,f;
};

player ps[1005];
int n,m;

bool battle(int a,int b){
bool ret=(ps[a].s*ps[a].t)>=(ps[b].s*ps[b].t);
if(ret){
ll tps=ps[a].s+(ps[b].s*ps[b].t)/(2*ps[a].t);
ll tpt=ps[a].t+(ps[b].s*ps[b].t)/(2*ps[a].s);
ps[a].s=tps;
ps[a].t=tpt;

ps[b].s+=ps[b].s>>1;
ps[b].t+=ps[b].t>>1;
ps[b].f++;
}else{
ll tps=ps[b].s+(ps[a].s*ps[a].t)/(2*ps[b].t);
ll tpt=ps[b].t+(ps[a].s*ps[a].t)/(2*ps[b].s);
ps[b].s=tps;
ps[b].t=tpt;

ps[a].s+=ps[a].s>>1;
ps[a].t+=ps[a].t>>1;
ps[a].f++;
}
return ret;
}

int main(){
ios::sync_with_stdio(0);cin.tie(0);

cin>>n>>m;
for(int i=1;i<=n;++i) cin>>ps[i].s;
for(int i=1;i<=n;++i) cin>>ps[i].t;

vector<int> bt(n);
for(int i=0;i<n;++i) cin>>bt[i];

while(siz(bt)>1){
vector<int> vt,fl;
for(int i=0;i<siz(bt);i+=2){
if(i==siz(bt)-1){
vt.emplace_back(bt[i]);
}else{
if(battle(bt[i],bt[i+1])){
vt.emplace_back(bt[i]);
if(ps[bt[i+1]].f<m) fl.emplace_back(bt[i+1]);
}else{
if(ps[bt[i]].f<m) fl.emplace_back(bt[i]);
vt.emplace_back(bt[i+1]);
}
}
}

while(bt.size()) bt.pop_back();

for(auto i:vt) bt.emplace_back(i);
for(auto i:fl) bt.emplace_back(i);
}

cout<<bt.front();
}

Q3. 數位占卜

題目連結:h083. 3. 數位占卜 - 高中生程式解題系統

前言

這是我唯一沒有滿分的題目,要用 set<long long> 陣列,還要 rolling hash 。 參考資料:2022 01/09 APCS 題解 - HackMD

實作

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
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
#include<bits/stdc++.h>
using namespace std;

using ll=long long;
const ll MOD=2147483647;
const ll X=29;

// pwt[i]=29^i%MOD
// inv[i]=pwt[i] 在 MOD 的反元素
ll pwt[105],inv[105];
// hash value
ll h[50010][105];
// 原始資料
string s[50010];
// 對於長度為 i 的字串的 hash 值
set<ll> ss[105];

// 快速冪
ll POW(ll a,ll x){
ll ret=1;
while(x>0){
if(x&1) ret=ret*a%MOD;
a=a*a%MOD;
x>>=1;
}
return ret;
}

void build(){
pwt[0]=inv[0]=1;
for(int i=1;i<=101;i++){
// X^i%MOD
pwt[i]=X*pwt[i-1]%MOD;
// 模逆元
inv[i]=POW(pwt[i],MOD-2);
}
}

void hah(string &tp,ll p){
int m=tp.size();
// 不加 1 的話 a, aa, aaa 會被視為相同
h[p][0]=tp[0]-'a'+1;
for(int i=1;i<m;++i){
h[p][i]=(h[p][i-1]+(tp[i]-'a'+1)*pwt[i])%MOD;
}
ss[m].insert(h[p][m-1]);
}

// 第 p 個字串的 [l,r] hash 前綴和的值
ll query(ll p,ll l,ll r){
return l==0 ? h[p][r] : (h[p][r]-h[p][l-1]+MOD)%MOD*inv[l]%MOD;
}

ll solve(int n){
ll ans=0;
for(int i=0;i<n;++i){
ll m=s[i].size();
for(int j=1;j<m;++j){
// 從中間開始
if(j*2<=m) continue;
// 若第 i 個字串的 [0,m-j-1] 與 [j,m-1] 相同
if(query(i,0,m-j-1)==query(i,j,m-1)){
// 尋找匹配字串,(j*2-m) 補齊字串長度
if(ss[j*2-m].count(query(i,m-j,j-1)))
ans++;
}
}
}
return ans;
}

int main(){
ios::sync_with_stdio(0);cin.tie(0);

int n;
cin>>n;
build();
for(int i=0;i<n;++i){
cin>>s[i];
hah(s[i],i);
}

cout<<solve(n)<<"\n";
}

Q4. 牆上海報

題目連結:h084. 4. 牆上海報 - 高中生程式解題系統

想法

Greedy + 二分搜。避免有人不知道要搜什麼,是搜尋高度。因為從題目中我們可以發現 -> 越高的地方可以放東西的區間越來越破碎,也越來越少。且若 x 是可以放的下的高度,選 x\‘< x 都不會更好(題目要求越高越好)。這樣就可以一次刪除一半的區間。

那 Greedy 呢?因為有規定擺放順序,因此能放就放,這個區間放不下就移至下個區間。沒有區間可以放就表示這個高度不合法。

實作

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
40
41
42
43
44
45
46
47
48
49
#include<bits/stdc++.h>
using namespace std;

int n,k;
int h[200010],bd[50010];

bool check(int x){
int psum=0;
vector<int> len;
for(int i=1;i<=n;++i){
if(h[i]>=x){
psum++;
}else{
len.emplace_back(psum);
psum=0;
}
}
// 0也無所謂
len.emplace_back(psum);

for(int i=1,j=0;i<=k;++i){
while(len[j]<bd[i]){
j++;
if(j==len.size()) return false;
}
len[j]-=bd[i];
}
return true;
}

int main(){
ios::sync_with_stdio(0);cin.tie(0);

cin>>n>>k;
for(int i=1;i<=n;++i) cin>>h[i];
for(int i=1;i<=k;++i) cin>>bd[i];

int l=0,r=1073741824;
while(r-l>1){
int mid=l+r>>1;
if(check(mid)){
l=mid;
}else{
r=mid;
}
}

cout<<l<<"\n";
}