不知不覺剩9天了 剩下的時間越來越少
準備要面對燒雞的現實了(´Ａ｀。)
今年一堆同屆的人都已經上黃了 超可怕
然而我還在青藍中間徘徊 一直都沒什麼進步
至少進全國賽吧 至少在人生第一次的競程比賽中可以得到一點點成績吧
半年的努力 不想白費掉啊 (╥﹏╥)
2014 北市賽
這一年的題目也是除了第四題以外都確定能解出來
保底也有 $400$ 分
對於得獎感覺更有自信了一點
不過北市賽的裸題真的很多 ==
這週末應該會試著生出一本屬於自己的 Codebook 吧
第一題、水晶球（Crystal Ball）
這題的話 我們可以用 dp 來達到這個的詢問
我們可以設 $dp[t][x][y]$ （$t$ 表示第幾次移動，$(x,y)$ 則代表座標)
這樣的時間複雜度會是 $O(10^8)$ 算是有點緊繃
但是當年的時間限制一律是 $5$ 秒 所以不用擔心
不過空間開 $10^8$ 次是會有問題的
我們可以利用「滾動dp」來幫助我們壓縮空間
空間複雜度：$O(2NM)$
程式碼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
using namespace std;
const int N = 105;
int grid[2][N][N];
signed main(){
fastio
int n,m;
cin >> n >> m;
int a,b,c,d;
cin >> a >> b >> c >> d;
grid[0][a][b] = 1;
int k;
cin >> k;
for(int t = 1;t <= k;t++){
memset(grid[t&1],0,sizeof grid[t&1]);
int d;
cin >> d;
for(int i = 0;i < n;i++){
for(int j = 0;j < m;j++){
grid[t&1][i][j] |= grid[(t-1)&1][(i+d%n)%n][j]|
grid[(t-1)&1][(i-d%n+n)%n][j]|
grid[(t-1)&1][i][(j+d%m)%m]|
grid[(t-1)&1][i][(j-d%m+m)%m];
}
}
}
cout << (grid[k&1][c][d] ? "YES" : "NO") << "\n";
}
第二題、得分高手（Master）
裸dp題 跟幾天前解的2018北市賽第四題的轉移式一樣
免費的 $100$ 分
程式碼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,m;
cin >> n >> m;
int grid[n][m];
for(int i = 0;i < n;i++) for(int j = 0;j < m;j++) cin >> grid[i][j];
int dp[n][m];
memset(dp,-0x3f3f3f,sizeof dp);
int ans = INT_MIN;
for(int i = 0;i < n;i++){
for(int j = 0;j < m;j++){
dp[i][j] = max({dp[i][j],grid[i][j],(i==0 ? INT_MIN : dp[i-1][j]+grid[i][j]), (j==0 ? INT_MIN : dp[i][j-1] + grid[i][j])});
ans = max(dp[i][j],ans);
}
}
cout << ans << "\n";
}
第三題、領土（Territory）
裸凸包題 刻個 Andrew’s Monotone Chain
然後用外積算面積就可以過了
程式碼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
using namespace std;
pair<int,int> operator - (pair<int,int> a, pair<int,int> b){
return {a.first-b.first,a.second-b.second};
}
int cross(pair<int,int> a, pair<int,int> b){
return a.first*b.second-a.second*b.first;
}
vector<pair<int,int>> getCH(vector<pair<int,int>> v){
int n = v.size();
sort(v.begin(),v.end());
vector<pair<int,int>> ans;
for(int i = 0;i < 2;i++){
int t = ans.size();
for(auto x : v){
while(ans.size()-t >= 2 && cross(ans.back()-ans[ans.size()-2],x-ans[ans.size()-2])<=0){
ans.pop_back();
}
ans.push_back(x);
}
ans.pop_back();
reverse(v.begin(),v.end());
}
return ans;
}
signed main(){
fastio
int n;
cin >> n;
vector<pair<int,int>> v;
for(int i = 0;i < n;i++){
int x,y;
cin >> x >> y;
v.emplace_back(x,y);
}
int ans = 0;
v = getCH(v);
for(int i = 2;i < v.size();i++){
ans += cross(v[i-1]-v[0],v[i]-v[0]);
}
cout << (ans+1)/2 << "\n";
}
第四題、太空迷走（Astro）
在賽中看到這種題目我應該會先跳過吧
這題我不太確定解法 應該能用 dp 之類的方式解
不過也沒有 judge 給我丟 QQ
第五題、加密密鑰（Key）
這題應該可以用一些字串演算法來找到答案
不過我會的字串演算法只有 Suffix Array
所以就用 Suffix Array 來解吧
這題用 Suffix Array 其實還滿快的
程式碼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
using namespace std;
void count_sort(vector<int> &pos, vector<int> &rank){
int n = pos.size();
vector<vector<int>> cnt(n);
for(int i : pos) cnt[rank[i]].push_back(i);
for(int i = 0, idx = 0;i < n;i++)
for(auto x : cnt[i])
pos[idx++] = x;
}
// 只需要在求完Suffix Array之後順便求LCP就好了
void get_suffix(string s, vector<int> &pos, vector<int> &lcp){
s += '$';
int n = s.size();
vector<int> rank(n);
//k = 0
iota(pos.begin(),pos.end(),0);
sort(pos.begin(),pos.end(),[&](int a, int b){ return s[a] < s[b]; });
for(int i = 0;i < n;i++){
if(i==0){
rank[pos[i]] = 0;
}else{
rank[pos[i]] = rank[pos[i-1]] + (s[pos[i]]!=s[pos[i-1]]);
}
}
//k > 0
vector<int> new_rank(n);
for(int k = 0;(1<<k) <= n;k++){
for(int i = 0;i < n;i++)
pos[i] = (pos[i] - (1<<k)%n + n ) % n;
count_sort(pos,rank);
new_rank[pos[0]] = 0;
for(int i = 1;i < n;i++){
pair<int,int> prev = {rank[pos[i-1]], rank[(pos[i-1]+(1<<k))%n]};
pair<int,int> now = {rank[pos[i]], rank[(pos[i]+(1<<k))%n]};
new_rank[pos[i]] = new_rank[pos[i-1]] + (prev!=now);
}
rank = new_rank;
}
//求LCP Array
int k = 0;
for(int i = 0;i < n;i++){
int pi = rank[i];
int j = pos[pi-1];
while(i+k<n && j+k<n && s[i+k]==s[j+k]) k++;
lcp[pi] = k;
k = max(0,k-1);
}
}
signed main(){
fastio
string s;
cin >> s;
vector<int> ans(s.size()+1), lcp(s.size()+1,0);
get_suffix(s,ans,lcp);
s += '$';
int n = s.size();
int res = 0;
string str = "";
for(int i = 2;i < n;i++){
if(lcp[i] > res) res = max(lcp[i],res), str = s.substr(ans[i],res);
}
cout << str << "\n";
}