今天是入芽考呢！
雖然沒有到很緊張 但還是希望自己能打好這場比賽
(1/25更)
結果燒雞了 ｡ﾟヽ(ﾟ´Д`)ﾉﾟ｡
只拿了 $320$ 分
不過聽說去年門檻是 $200$，波神說今年門檻還會更低
那應該就沒那麼擔心了吧
Atcoder Beginner Contest 189
其實這是昨天的比賽呢
不過還是放到今天來寫了
這場共解出 (5/6) 題 第454名
不過第六題是期望值dp 所以我不太熟QQ
Problem A - Slot
ABC 的第一題總是送分題呢
就照著做就好了
不過因為要輸出 Won 打成 Win 吃了一次 WA (๑•́ ₃ •̀๑)
程式碼：
1
2
3
4
5
6
7
8
9
10
11
12
13
| #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;
cout << (s[0]==s[1]&&s[1]==s[2] ? "Won\n" : "Lost\n");
}
|
Problem B - Alcoholic
這題就也是照著做 只是用浮點數比較的話容易出錯
因此我們將 $X$ 以及 $P$ 都乘上 $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
| #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,x;
cin >> n >> x;
x *= 100;
int num = 0;
for(int i = 0;i < n;i++){
int a,b;
cin >> a >> b;
num += a*b;
if(num > x){
cout << i+1 << "\n";
return 0;
}
}
cout << -1 << "\n";
}
|
Problem C - Mandarin Orange
題意：
給一個 $N$ 項的陣列，問 $(r-l+1) \times min(a_l,…,a_r)$ 的最大值
想法：
看到這題的時候也想了一下，不過這個測資範圍 $N \leq 10^4$
基本上 $O(N^2)$ 會過，就直接枚舉 $l,r$ 即可
程式碼：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
| #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 ans = 0;
int n;
cin >> n;
int arr[n];
for(auto &x : arr) cin >> x;
for(int i = 0;i < n;i++){
int mi = INT_MAX;
for(int j = i;j < n;j++){
mi = min(mi, arr[j]);
ans = max(ans,mi*(j-i+1));
}
}
cout << ans << "\n";
}
|
Problem D - Logical Expression
題意：
給 $N$ 個布林運算子，問有幾種 $True$ 和 $False$ 的排列能使最後的答案為 $True$
想法：
這題我一開始沒仔細看題目，以為 AND 和 OR 有優先順序
再加上範圍是 $N \leq 60$
$60$ 這個數字，會讓人想到的是 $2^{60}$ 次方以及可能可以折半枚舉 $2^{31}$ 次方
不過不管是哪個都太大了 而且折半枚舉對於 ABC pD 可能也太難
因此仔細想過之後，會發現其實這題就只是 dp
設 $dp[i][0|1]$ 為做完 $i$ 次運算後 出來的是 $True$ 與 $False$ 的選法
程式碼：
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>
#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 dp[n+1][2] = {};
dp[0][0] = 1, dp[0][1] = 1;
for(int i = 1;i <= n;i++){
string s;
cin >> s;
if(s[0]=='A'){
dp[i][0] = 2*dp[i-1][0]+dp[i-1][1];
dp[i][1] = dp[i-1][1];
}else{
dp[i][0] = dp[i-1][0];
dp[i][1] = dp[i-1][0]+2*dp[i-1][1];
}
}
cout << dp[n][1] << "\n";
}
|
Problem E - Rotate and Flip
題意：
給 $N$ 個點以及 $M$ 個操作
共有四種操作
（一）順時針旋轉 $90$ 度
（二）逆時針旋轉 $90$ 度
（三）對稱 $x=p$
（四）對稱 $y=p$
一共有 $Q$ 個詢問 每次詢問第 $B$ 個點經過 $A$ 個操作後會到哪個點
想法：
這題我一開始卡了滿久的 一直在思考該使用哪個資料結構來維護
不過仔細想過之後
第一個操作對於 $(x,y)$ 的影響是變成 $(y,-x)$
第二個操作對於 $(x,y)$ 的影響是變成 $(-y,x)$
第三個操作對於 $(x,y)$ 的影響是變成 $(2p-x,y)$
第四個操作對於 $(x,y)$ 的影響是變成 $(x,2p-y)$
我們只要維護每次操作後，$x$ 座標要乘多少加多少，以及 $y$ 座標要乘多少加多少即可
程式碼：
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
| #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;
const int N = 2e5+5;
pair<int,int> mul[N], add[N];
int rev[N];
vector<pair<int,int>> points;
signed main(){
fastio
int n;
cin >> n;
for(int i = 0;i < n;i++){
int x,y;
cin >> x >> y;
points.push_back({x,y});
}
mul[0] = {1,1}, add[0] = {0,0}, rev[0] = 0;
int m;
cin >> m;
for(int i = 1;i <= m;i++){
mul[i] = mul[i-1], add[i] = add[i-1], rev[i] = rev[i-1];
int op;
cin >> op;
if(op==1){
rev[i] ^= 1;
swap(mul[i].first,mul[i].second);
swap(add[i].first,add[i].second);
mul[i].second *= -1;
add[i].second *= -1;
}else if(op==2){
rev[i] ^= 1;
swap(mul[i].first,mul[i].second);
swap(add[i].first,add[i].second);
mul[i].first *= -1;
add[i].first *= -1;
}else if(op==3){
int x;
cin >> x;
mul[i].first *= -1;
add[i].first *= -1;
add[i].first += 2*x;
}else if(op==4){
int x;
cin >> x;
mul[i].second *= -1;
add[i].second *= -1;
add[i].second += 2*x;
}
}
int q;
cin >> q;
for(int i = 0;i < q;i++){
int id, num;
cin >> num >> id;
id--;
auto [x,y] = points[id];
if(rev[num]) swap(x,y);
cout << mul[num].first*x + add[num].first << " " << mul[num].second*y + add[num].second << "\n";
}
}
|
入芽考
偷偷把 pdf 存回來了
反正整個燒雞 只拿了 $320$ 分 QQ
精神分數應該是有 $440$ 的
但也是深深讓我體會到我現場比賽真的會很緊張導致拿不到分
pA - 教授我想學魔法
想法：
就照著題目模擬（？
不過我在考慮 $100$ 分的人的時候沒想清楚
使用了 multiset 來維護最大值的人
不過其實只要維護 $100$ 分的人就好了（？
反正就是燒雞只拿了60分 應該是能拿滿的
pB - 忒修斯之船
想法：
這題是我最慘的一題
我原本想說這題能拿到滿分
不過被自己卡住QQ 沒考慮移動 $0$ 的狀況
用 vector 存還 MLE 然後被波神笑
只拿到了 $20$ 分 應該要拿滿的 QQ
pC - 好的數對
想法：
這題算是滿裸的雙指標題 由於數字只到 $10$ 所以複雜度 $O(10n)$
原本是打算看完所有題目再開始打的
不過這題太簡單所以就直接刻
因為忘記開 long long，卡了一下子
pD - 警戒範圍
想法
一開始看到只要去做子題一、二就能夠拿到 $70$ 分呢
很划算 所以先喇了這 $70$ 分
不過在做子題一的時候想到滿分解 （就是做類似區間聯集的作法）
但是因為後來卡在 pA 和 pB 就沒去寫完滿分解了
pE - 大整數
想法：
這題看到的時候就沒有打算去想滿分解了
因為 $70$ 分暴力就拿的到了
不過聽了解答之後才覺得如果有想應該是想得到的
就是暴力是一次加 $1$ 個數字
如果我們一次加 $1000000$ 個數字之類的
就可以在很快的時間內找到答案了
Virtual Contest - Educational Codeforces Round 46
這場其實是半夜打的 因為 Xuan 突然說他想 vir 一場
意外的打的還不錯 總共 $7$ 題 我會 $6$ 題
Problem A - Codehorses T-shirts
題意：
有各種不同 Size 的 T-shirt 以及 兩個 List
問最少要修改 List 上面的幾個字才能使兩個 List 相同
想法：
一開始以為是修改字元 想了好久
結果只是修改字
就直接用 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
| #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
map<string,int> a,b;
int n;
cin >> n;
for(int i = 0;i < n;i++){
string tmp;
cin >> tmp;
a[tmp]++;
}
for(int i = 0;i < n;i++){
string tmp;
cin >> tmp;
b[tmp]++;
}
int ans = n;
for(auto [x,y] : a){
ans -= min(y,b[x]);
}
cout << ans << "\n";
}
|
Problem B - Light It Up
題意：
有一個陣列 $a$ ，而在第 $0$ 秒的時候打開燈，第 M 秒時關燈
在 $a$ 當中的每一秒也會做開關燈的動作
你可以加入最多一個元素 使得
問最多有幾秒燈會是開的
想法：
如果要加入元素，那麼一定是加在開完燈或者關燈後一秒
才會有最大值
而關燈後，後面的秒數的開關燈也會因此反轉
因此就先維護前綴和 然後再去做即可
程式碼：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
| #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,m;
cin >> n >> m;
int arr[n+1] = {}, pref[n+2] = {};
for(int i = 1;i <= n;i++){
cin >> arr[i];
pref[i] = pref[i-1]+(i&1) * (arr[i]-arr[i-1]);
}
pref[n+1] = pref[n] + ((n+1)&1) * (m-arr[n]);
int ans = pref[n+1];
for(int i = 1;i <= n;i++){
ans = max(ans, pref[i]+m-arr[i]-(pref[n+1]-pref[i])-1);
}
cout << ans << "\n";
}
|
Problem C - Cover Points Count
題意：
給 $n$ 個線段 $[l,r]$，輸出有幾個點被 $1$ ~ $n$ 個線段覆蓋
想法：
這題跟 ABC 188D 很像 而且我當初也卡過那題
我當初的寫法是離散化 可是後來才知道根本不需要
只需要一次排序就好了
程式碼：
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
| #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;
const int N = 2e5+5;
int cnt[N];
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.push_back({x,1});
v.push_back({y+1,-1});
}
v.push_back({(int)1e18+5,0});
sort(v.begin(),v.end());
int now = 0, x = 0;
for(auto [l,v] : v){
cnt[now] += l-x;
now += v;
x = l;
}
for(int i = 1;i <= n;i++) cout << cnt[i] << " ";
}
|
Problem D - Yet Another Problem On a Subsequence
題意：
定義一個好陣列，他的第一項為陣列長度+1
給一個 $n$ 項的陣列，問有幾個子序列可以被切成多個好陣列，且每個元素只屬於一個好陣列
想法：
如果我們固定左界，那麼要找到他開始的好陣列很簡單，就直接取 $C$ 即可
而要找到子序列呢？
我們可以枚舉一個元素右邊的第二個元素，看有幾個子序列滿足題目
解法：
設 $dp[i]$ 為從第 $i$ 個元素開始的子序列數量
然後就去枚舉 複雜度: $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
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>
#define int long long
#define fastio ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
using namespace std;
const int N = 1e3+5, MOD = 998244353;
int fact[N];
void init(){
fact[0] = 1;
for(int i = 1;i < N;i++)
fact[i] = fact[i-1]*i%MOD;
}
int fastpow(int n, int p){
int res = 1;
while(p){
if(p&1) res = (res * n) % MOD;
n = (n * n) % MOD;
p>>=1;
}
return res;
}
int nCr(int n, int r){
if(n < r||r < 0) return 0;
return fact[n]*fastpow(fact[n-r],MOD-2)%MOD*fastpow(fact[r],MOD-2)%MOD;
}
signed main(){
fastio
init();
int n;
cin >> n;
int arr[n], dp[n] = {};
int ans = 0;
for(auto &x : arr) cin >> x;
for(int i = n-1;~i;i--){
if(i+arr[i]>=n||arr[i] <= 0) continue;
dp[i] = nCr(n-i-1,arr[i]);
for(int j = arr[i]+i+1; j < n;j++){
dp[i] = (dp[i]+nCr(j-i-1,arr[i])*dp[j]%MOD)%MOD;
}
}
for(int i = 0;i < n;i++) ans = (ans + dp[i])%MOD;
cout << ans << "\n";
}
|
Problem E - We Need More Bosses
題意：
給一張無向圖，問如何選擇路徑的起點與終點才能使得路徑上經過的橋最多？
想法：
這題其實是裸題，我們可以使用橋連通分量的縮點，使圖變為一棵樹
之後再去找樹直徑即可
程式碼：
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
| #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;
const int N = 3e5+5;
vector<int> adj[N], adj2[N];
int d[N], l[N], dis[N], bcc[N], bccid, t, x, mxdis;
stack<int> st;
void dfs(int u, int par = -1){
d[u] = l[u] = t++;
st.emplace(u);
for(int v : adj[u]){
if(v == par) continue;
if(!d[v]){
dfs(v,u);
l[u] = min(l[u],l[v]);
}
l[u] = min(l[u],d[v]);
}
if(l[u]==d[u]){
bccid++;
int tmp;
do{
tmp = st.top(); st.pop();
bcc[tmp] = bccid;
}while(tmp!=u);
}
}
void dfs2(int u, int par = -1){
for(auto v : adj2[u]){
if(v==par) continue;
dis[v] = dis[u]+1;
if(dis[v] > mxdis) mxdis = dis[v], x = v;
dfs2(v,u);
}
}
signed main(){
fastio
int n,m;
cin >> n >> m;
for(int i = 0;i < m;i++){
int u,v;
cin >> u >> v;
adj[u].push_back(v);
adj[v].push_back(u);
}
dfs(1);
for(int u = 1;u <= n;u++){
for(auto v : adj[u]){
if(bcc[u]!=bcc[v]) adj2[bcc[u]].push_back(bcc[v]);
}
}
dis[1] = 0;
dfs2(1);
memset(dis,0,sizeof dis);
mxdis = 0;
dfs2(x);
cout << mxdis << "\n";
}
|
Problem F - One Occurrence
題意：
給一個 $n$ 項的陣列，以及 $q$ 個詢問
每次詢問區間 $[l,r]$，在每次詢問後輸出只出現一次的那個元素
想法：
這題我看到 $5 \times 10^5$ 還有要計算元素數量
想到的第一個解法就是莫隊算法
不過要維護只出現一次的數字，一般會想到可以使用set來輔助
但是 set 和 unordered_set 的常數太大 無法通過這題
因此可以用分塊的方式 去紀錄那一塊當中有只出現一次的數字 之後再暴力去找那個元素
這樣複雜度就會是 $O(q\sqrt{n})$ 了
不過這樣還是過不了
因此還要在搭配莫隊算法的奇偶優化 這樣就能過這題了
（不過正解好像是線段樹 QQ）
程式碼：
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
| #pragma optimize("Ofast")
#include <bits/stdc++.h>
#define fastio ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
using namespace std;
const int N = 5e5+5;
int k;
int a[N], cnt[N], bid[N], bcnt[N], l = 1, r = 0, ok;
struct query{
int l,r, id;
bool operator < (const query b){
if(l/k!=b.l/k) return l < b.l;
if((l/k) &1) return r < b.r;
return r > b.r;
}
};
void add(int pos){
if(cnt[a[pos]]==1) bcnt[bid[a[pos]]]--, ok--;
cnt[a[pos]]++;
if(cnt[a[pos]]==1) bcnt[bid[a[pos]]]++, ok++;
}
void sub(int pos){
if(cnt[a[pos]]==1) bcnt[bid[a[pos]]]--, ok--;
cnt[a[pos]]--;
if(cnt[a[pos]]==1) bcnt[bid[a[pos]]]++, ok++;
}
int findnum(){
if(!ok) return 0;
for(int i = 0;i <= k;i++){
if(!bcnt[i]) continue;
for(int j = i*k;j < min((i+1)*k,N);j++){
if(cnt[j]==1){
return j;
}
}
}
}
signed main(){
fastio
int n;
cin >> n;
k = sqrt(n);
for(int i = 0;i < N;i++){
bid[i] = i/k;
}
for(int i = 1;i <= n;i++) cin >> a[i];
int m;
cin >> m;
vector<query> Q;
int ans[m];
for(int i = 0;i < m;i++){
int ql, qr;
cin >> ql >> qr;
Q.push_back({ql,qr,i});
}
sort(Q.begin(),Q.end());
for(auto q : Q){
while(l < q.l) sub(l++);
while(l > q.l) add(--l);
while(r < q.r) add(++r);
while(r > q.r) sub(r--);
ans[q.id] = findnum();
}
for(auto x : ans) cout << x << "\n";
}
|