這週一沒有打這場比賽 因為時間實在是沒有辦法打 இдஇ
今天突然想到 就決定來Virtual一下了
打完之後覺得自己真的是太久沒有打 Div.3 了
Problem A - Floor Number
還沒看題目 看到範測 直接砸了 $\lceil \frac{n}{x} \rceil$
然後就WA了 (☍﹏⁰)
看了題目才知道 他是第一樓只能住 $2$ 個人
所以改成 $\lfloor \frac{n}{x} \rfloor+2$ 然後特判 $n \leq 2$ 就過了
程式碼1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
using namespace std;
void solve(){
int n,x;
cin >> n >> x;
cout << (n<= 2 ? 1 : (n-3)/x+2) << "\n";
}
signed main(){
fastio
int t = 1;
cin >> t;
while(t--) solve();
}
Problem B - Symmetric Matrix
題目很長 不太想讀
不過意思是他會給 $n$ 個 $2\times2$ 的矩陣無限多個
問是否能排出 $m \times m$ 對稱對角線的矩陣
這題有兩個條件
第一個是 $m$ 要是二的倍數
第二個是至少一個矩陣的右上和左下要相等
這兩個條件符合就過了
程式碼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
using namespace std;
void solve(){
int n,m;
cin >> n >> m;
bool ok = false;
for(int i = 0;i < n;i++){
int a,b,c,d;
cin >> a >> b >> c >> d;
if(b==c){
ok = true;
}
}
if(m%2) ok = false;
cout << (ok ? "YES\n" : "NO\n");
}
signed main(){
fastio
int t = 1;
cin >> t;
while(t--) solve();
}
Problem C - Increase And Copy
看著題目想了一下子 一直都沒有想法
不過仔細想過之後會發現
要達到最好的解一定是先增加之後再一併複製
因此我們只要一直對一開始的 $1$ 去加 $1$
最後再乘以一個數字就好了
我們可以用枚舉的方式達到這一點
程式碼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;
void solve(){
int n;
cin >> n;
int ans = INT_MAX;
for(int i = 0;i <= sqrt(1e9);i++){
int tmp = (n-1)/(i+1);
ans = min(ans,tmp+i);
}
cout << ans << "\n";
}
signed main(){
fastio
int t = 1;
cin >> t;
while(t--) solve();
}
Problem D - Non-zero Segment
這題看到題目 就會想到要用前綴和 （使區間和不等於 $0$）
區間和為 $0$ 的狀況就是有兩個前綴和值相等
而我們要加幾次才能讓前綴和兩兩不相等呢
仔細想一下 會發現如果我們每次都加一個非常非常大的值
沒有加到這個值的前綴和一定不會和後面相等
所以我們只要在相等的時候 重置 map 的值就好
然後當前綴和為 $0$ 的時候也要重製 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
using namespace std;
signed main(){
fastio
int n;
cin >> n;
map<int,int> m;
int now = 0, ans = 0;
m[0] = 1;
for(int i = 0;i < n;i++){
int tmp;
cin >> tmp;
now+=tmp;
if(m[now]){
m.clear();
ans++;
now = tmp;
m[0]++;
}
m[now]++;
}
cout << ans << "\n";
}
Problem E - Rock, Paper, Scissors
這題的話就是兩個人剪刀石頭布
其實想一下很快就解出來了
不知道為什麼會放這種題在pE (*´･д･)?
程式碼1
2
3
4
5
6
7
8
9
10
11
12
13
14
using namespace std;
signed main(){
fastio
int n;
cin >> n;
int a,b,c,d,e,f;
cin >> a >> b >> c >> d >> e >> f;
cout << min(max(0,a-d-f),e)+min(max(0,b-e-d),f)+min(max(0,c-f-e),d) <<" " << min(a,e)+min(b,f)+min(c,d);
}
Problem F - Number of Subsequences
總算不是 Ad-Hoc 題了 前面幾題都是 Ad-Hoc 超痛苦
這題一看到 就知道要使用 dp 來解了
所以就列出轉移式 然後就 AC 了
複雜度: $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
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
using namespace std;
const int MOD = 1e9+7;
signed main(){
fastio
int n;
cin >> n;
string s;
cin >> s;
int dp[n][3] = {}, cnt = 1;
for(int i = 0;i < n;i++){
if(s[i]=='a'){
dp[i][0] = (dp[i][0] + cnt)%MOD;
}else if(s[i]=='b'){
if(i>0)
dp[i][1] = (dp[i][1] + dp[i-1][0])%MOD;
}else if(s[i]=='c'){
if(i>0)
dp[i][2] = (dp[i][2] + dp[i-1][1])%MOD;
}else{
dp[i][0] = (dp[i][0]*3 + cnt)%MOD;
if(i>0)
dp[i][1] = (dp[i][1]*3 + dp[i-1][0])%MOD;
if(i>0)
dp[i][2] = (dp[i][2]*3 + dp[i-1][1])%MOD;
cnt = cnt*3%MOD;
}
if(i!=n-1){
dp[i+1][0] = dp[i][0];
dp[i+1][1] = dp[i][1];
dp[i+1][2] = dp[i][2];
}
}
cout << dp[n-1][2] << "\n";
}