前言
重回程式設計第一天…
因為種種原因停更好久，直到最近，我決定重新開始寫題目。這次的題目選自 https://codeforces.com/contest/1790 ，剛回來想用 Div3 試個手感，沒想到也卡了許久。
本文
言歸正傳，本質上這還是一個分享網站。那我今天用了 3 個小時總共寫出 5 題(共 7 題)。以下是提示、想法、與程式碼的分享。
pA Polycarp and the Day of Pi
簡單說就是求前 30 位的圓周率他寫對幾位，比較需要注意的是範例已經給一個完整的圓周率。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
| #include
using namespace std;
string ans="314159265358979323846264338327",a;
void solve(){
cin>>a;
int same=0;
for(int i=0;i
int main(){
ios::sync_with_stdio(0);cin.tie(0);
int t;
cin>>t;
while(t--){
solve();
}
}
|
pB Taisia and Dice
題目概要
給你三個數字 \(n, s, r\) ，\(n\) 是骰子數，\(s\) 是點數總和，\(r\) 則是扣掉一個最大的骰子點數後的點數總和。求一個可能的點數序列。
提示 1
最大的點數是 \(s-r\)
提示 2
這序列沒有規定骰子點數不能重複
想法
綜合兩個提示，我們可以發現。盡量先用最大點數 \(s-r\)，最後都用 1 點，中間再補差額就可以了。程式碼的表達正好相反。
程式碼
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
| #include
using namespace std;
void solve(){
int n,s,r;
cin>>n>>s>>r;
int d=s-r,sum=0;
for(int i=1;i<=n;++i){
if(n-i+1==s-sum){
cout<<1<<" ";
sum++;
}else if(n-i
int main(){
ios::sync_with_stdio(0);cin.tie(0);
int t;
cin>>t;
while(t--){
solve();
}
}
|
pC
題目概述
有一個 \(1 \sim n\) 都出現過一次的序列讓你猜，然後不按順序的給你 \(n\) 個數列，每個數列都是原本的序列但會刪除一個元素。求原序列。
例如：
則原序列為 1 2 3。
提示 1
只需要兩個序列就可以求出完整的。
提示 2
頭尾的元素是關鍵。
想法
其實找到兩個關鍵序列就可以了，就是刪掉第一個和刪掉最後一個的。
例如：
就只需要
就可以還原整個序列。
那至於如何尋找，如提示 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
50
51
52
53
54
55
56
57
58
| #include
using namespace std;
int bd[105][105],s[105],sr[105],f,d,r,c;
void solve(){
int n;
cin>>n;
for(int i=1;i<=n;++i){
for(int j=1;j>bd[i][j];
}
}
f=-1;
r=-1;
for(int i=1;i<=n;++i){
s[i]=0;
sr[i]=0;
}
for(int i=1;i<=n;++i){
s[bd[i][1]]++;
sr[bd[i][n-1]]++;
if(s[bd[i][1]]>1){
f=bd[i][1];
}
if(sr[bd[i][n-1]]>1){
r=bd[i][n-1];
}
}
for(int i=1;i<=n;++i){
if(bd[i][1]!=f){
d=i;
}
if(bd[i][n-1]!=r){
c=i;
}
}
for(int i=1;i<=n-1;++i){
cout<
cout<<"\n";
}
int main(){
ios::sync_with_stdio(0);cin.tie(0);
int t;
cin>>t;
while(t--){
solve();
}
}
|
pD Matryoshkas
題目概述
給你一堆俄羅斯娃娃的大小，問你原來最少有幾組。其中，每一組的娃娃大小都必須要是連續整數。例如 1 2 3。
提示 1
能疊越多層越好。
提示 2
動態的資料增刪操作。
想法
能疊越多層越好，因此，每一次都用 while 嘗試往上疊。那就需要尋找一個大小 +1 的娃娃存不存在。可以使用 multiset 或是 map，而我選 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
35
| #include
using namespace std;
void solve(){
int n,a,sum=0;
cin>>n;
map mp;
for(int i=0;i>a;
mp[a]++;
}
for(auto e:mp){
while(e.second>0){
int tp=e.first;
while(mp.count(tp+1) && mp[tp+1]>0){
mp[tp+1]--;
tp++;
}
sum++;
e.second--;
}
}
cout<
cout<<"\n";
}
int main(){
ios::sync_with_stdio(0);cin.tie(0);
int t;
cin>>t;
while(t--){
solve();
}
}
|
pE Vlad and a Pair of Numbers
題目概述
給你一個 \(x\)，找到 \(a,b\)滿足 \(a \oplus b=\frac{a+b}{2}=x\)，其中 \(\oplus\) 是 xor，也就是 C++ 上的
第五題最後有偷看詳解，使用的做法請見-> https://codeforces.com/blog/entry/111948