前言 CSES Introductory Problems 的 AC 程式碼
CSES Problem Set
我的 Profile
我的程式們
Weird Algorithm Weird Algorithm 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 #include <bits/stdc++.h> #define int long long using namespace std; signed main () { ios::sync_with_stdio (0 ); cin.tie (0 ), cout.tie (0 ); int x; cin >> x; cout << x << ' ' ; while (x!=1 ){ if (x%2 ) x=x*3 +1 ; else x=x/2 ; cout << x << ' ' ; } return 0 ; }
Missing Number Missing Number 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 #include <bits/stdc++.h> #define int long long using namespace std; signed main () { ios::sync_with_stdio (0 ); cin.tie (0 ), cout.tie (0 ); int n; cin >> n; bool arr[200005 ]; memset (arr, 0 , sizeof (arr)); for (int i = 0 , tmp; i<n-1 ; i++) cin >> tmp, arr[tmp]=1 ; int ans; for (int i = 1 ; i<=n; i++) if (!arr[i]) ans = i; cout << ans << '\n' ; return 0 ; }
Repetitions Repetitions 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 #include <bits/stdc++.h> #define int long long #define eb emplace_back #define pb push_back #define tomax(a, b) ((a)=max(a,b)) #define tomin(a, b) ((a)=min(a,b)) using namespace std; signed main () { ios::sync_with_stdio (0 ); cin.tie (0 ), cout.tie (0 ); string in; cin >> in; int ans = 1 ; vector<char > rep; rep.eb (in[0 ]); for (int i=1 ; in[i]; i++){ if (in[i] != rep.back ()) tomax (ans, (int )rep.size ()), rep.clear (); rep.eb (in[i]); }cout << tomax (ans, (int )rep.size ()) << '\n' ; return 0 ; }
Increasing Array Increasing Array 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 #include <bits/stdc++.h> #define int long long #define eb emplace_back #define pb push_back #define tomax(a, b) ((a)=max(a,b)) #define tomin(a, b) ((a)=min(a,b)) using namespace std; signed main () { ios::sync_with_stdio (0 ); cin.tie (0 ), cout.tie (0 ); int n; cin >> n; int ans = 0 , last; cin >> last; for (int i = 1 , tmp; i<n; i++) cin >> tmp, ans+=(last-tmp)*(tmp<last), tomax (last, tmp); cout << ans << '\n' ; return 0 ; }
Permutations Permutations 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 eb emplace_back #define pb push_back #define tomax(a, b) ((a)=max(a,b)) #define tomin(a, b) ((a)=min(a,b)) using namespace std; signed main () { ios::sync_with_stdio (0 ); cin.tie (0 ), cout.tie (0 ); int n; cin >> n; if (n==1 ) cout << "1\n" ; else if (n<=3 ) cout << "NO SOLUTION\n" ; else if (n==4 ) cout << "3 1 4 2\n" ; else { for (int i = 1 ; i<=n; i+=2 ) cout << i << ' ' ; for (int i = 2 ; i<=n; i+=2 ) cout << i << ' ' ; } return 0 ; }
Number Spiral Number Spiral 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 #include <bits/stdc++.h> #define int long long #define eb emplace_back #define pb push_back #define tomax(a, b) ((a)=max(a,b)) #define tomin(a, b) ((a)=min(a,b)) using namespace std; signed main () { ios::sync_with_stdio (0 ); cin.tie (0 ), cout.tie (0 ); int t; cin >> t; while (t--){ int y, x; cin >> y >> x; if (x >= y) if (x%2 ) cout << x*x-(y-1 ) << '\n' ; else cout << (x-1 )*(x-1 )+(y) << '\n' ; else if (y%2 ==0 ) cout << y*y-(x-1 ) << '\n' ; else cout << (y-1 )*(y-1 )+(x) << '\n' ; } return 0 ; }
Two Knights Two Knights 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 #include <bits/stdc++.h> #define int long long #define eb emplace_back #define pb push_back #define tomax(a, b) ((a)=max(a,b)) #define tomin(a, b) ((a)=min(a,b)) using namespace std; signed main () { ios::sync_with_stdio (0 ); cin.tie (0 ), cout.tie (0 ); int n; cin >> n; cout << "0\n" ; for (int i = 2 ; i<=n; i++){ cout << ((i*i)*(i*i-1 ))/2 - 2 *(2 *(i-1 )*(i-2 )) << '\n' ; } return 0 ; }
Two Sets Two Sets 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 #include <bits/stdc++.h> #define int long long #define eb emplace_back #define pb push_back #define tomax(a, b) ((a)=max(a,b)) #define tomin(a, b) ((a)=min(a,b)) #define rep(i, a, b) for(int i = (a); i<=(b); ++i) #define rev(i, a, b) for(int i = (a); i>=(b); --i) using namespace std; signed main () { ios::sync_with_stdio (0 ); cin.tie (0 ), cout.tie (0 ); int n; cin >> n; if ((n*(n+1 )/2 ) % 2 ) cout << "NO\n" ; else { cout << "YES\n" ; if (n%4 == 0 ){ cout << n/2 << '\n' ; rep (i, 1 , (n/4 )) cout << i << ' ' << n+1 -i << ' ' ; cout << '\n' << n/2 << '\n' ; rep (i, (n/4 )+1 , n/2 ) cout << i << ' ' << n+1 -i << ' ' ; }else { cout << n/2 + 1 << '\n' ; rep (i, 1 , n/2 ) cout << i++ << ' ' ; rep (i, n/2 +1 , n-1 ) cout << i++ << ' ' ; cout << '\n' << n/2 << '\n' ; rep (i, 2 , n/2 -1 ) cout << i++ << ' ' ; rep (i, n/2 +2 , n) cout << i++ << ' ' ; } } return 0 ; }
Bit Strings Bit Strings 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 #include <bits/stdc++.h> #define int long long #define eb emplace_back #define pb push_back #define tomax(a, b) ((a)=max(a,b)) #define tomin(a, b) ((a)=min(a,b)) #define rep(i, a, b) for(int i = (a); i<=(b); ++i) #define rev(i, a, b) for(int i = (a); i>=(b); --i) using namespace std; const int mod = 1E9 + 7 ; signed main () { ios::sync_with_stdio (0 ); cin.tie (0 ), cout.tie (0 ); int n, ans = 1 ; cin >> n; rep (i, 1 , n) ans = (ans<<1 ) % mod; cout << ans % mod << '\n' ; return 0 ; }
Trailing Zeros Trailing Zeros 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 eb emplace_back #define pb push_back #define tomax(a, b) ((a)=max(a,b)) #define tomin(a, b) ((a)=min(a,b)) #define rep(i, a, b) for(int i = (a); i<=(b); ++i) #define rev(i, a, b) for(int i = (a); i>=(b); --i) using namespace std; const int mod = 1E9 + 7 ; signed main () { ios::sync_with_stdio (0 ); cin.tie (0 ), cout.tie (0 ); int n, ans=0 ; cin >> n; for (int i = 5 ; i<=n; i*=5 ){ ans += n/i; } cout << ans << '\n' ; return 0 ; }
Coin Piles Coin Piles 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 ios ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0); #define pii pair<int, int> #define int long long #define rep(i, a, b) for(int i = a; i<=b; i++ ) #define rev(i, a, b) for(int i = a; i>=b; i-- ) #define tomax(a, b) (a)=max((a), (b)) #define tomin(a, b) (a)=min((a), (b)) #define pb push_back #define eb emplace_back using namespace std; signed main () { ios int t; cin >> t; while (t--){ int a, b; cin >> a >>b; if (2 *a-b>=0 && 2 *b-a>=0 && (2 *a-b)%3 ==0 && (2 *b-a)%3 ==0 ) cout << "YES\n" ; else cout << "NO\n" ; } return 0 ; }
Palindrome Reorder Palindrome Reorder 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 #include <bits/stdc++.h> #define ios ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0); #define pii pair<int, int> #define int long long #define rep(i, a, b) for(int i = a; i<=b; i++ ) #define rev(i, a, b) for(int i = a; i>=b; i-- ) #define tomax(a, b) (a)=max((a), (b)) #define tomin(a, b) (a)=min((a), (b)) #define pb push_back #define eb emplace_back using namespace std; signed main () { ios string s; char res[1000006 ]; int ch[30 ], odd=0 ; fill (ch, ch+27 , 0 ); cin >> s; for (int i = 0 ; s[i]; i++) ch[s[i]-'A' ]++; for (int i = 0 ; i<26 ; i++) odd+=ch[i]%2 ; if (odd>0 && s.size ()%2 ==0 ){cout << "NO SOLUTION\n" ; return 0 ;} if (odd!=1 && s.size ()%2 ){cout << "NO SOLUTION\n" ; return 0 ;} int idx = 0 , n=s.size ()-1 ; rep (i, 0 , 25 ){ if (ch[i]%2 ) ch[i]--, res[n/2 ]='A' +i; rev (j, ch[i], 1 ) res[idx]=res[n-idx]='A' +i, idx++, j--; }rep (i, 0 , n) cout << res[i]; cout << '\n' ; return 0 ; }
Gray Code 這題我有寫題解,這邊 Gray Code 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 ios ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0); #define pii pair<int, int> #define int long long #define rep(i, a, b) for(int i = a; i<=b; i++ ) #define rev(i, a, b) for(int i = a; i>=b; i-- ) #define tomax(a, b) (a)=max((a), (b)) #define tomin(a, b) (a)=min((a), (b)) #define pb push_back #define eb emplace_back using namespace std; signed main () { ios int n; cin >> n; rep (i, 0 , (1 <<n)-1 ){ cout << (i>>(n-1 )); rev (j, n-2 , 0 ) cout << (((i>>j)&1 ) ^ ((i>>(j+1 ))&1 )); cout << '\n' ; } return 0 ; }
Tower of Hanoi Tower of Hanoi 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 #include <bits/stdc++.h> #define int long long #define pii pair<int, int> #define F first #define S second #define rep(i, a, b) for(int i = a; i<=b; i++) #define rev(i, a, b) for(int i = a; i>=b; i--) #define tomax(a,b) (a)=max((a), (b)) #define tomin(a,b) (a)=min((a), (b)) #define pb push_back #define eb emplace_back #define ios ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0) using namespace std; vector<pii> ans; void move (int num, int from, int to) { int use = 6 -from-to; if (num == 1 ) ans.eb (from,to); else move (num-1 ,from,use), move (1 ,from,to), move (num-1 ,use,to); } signed main () { ios; int n; cin >> n; move (n, 1 , 3 ); cout << ans.size () << '\n' ; for (pii i : ans) cout << i.F << ' ' << i.S << '\n' ; return 0 ; }
Creating Strings Creating Strings 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 #include <bits/stdc++.h> #define int long long #define pii pair<int, int> #define F first #define S second #define rep(i, a, b) for(int i = a; i<=b; i++) #define rev(i, a, b) for(int i = a; i>=b; i--) #define tomax(a,b) (a)=max((a), (b)) #define tomin(a,b) (a)=min((a), (b)) #define pb push_back #define eb emplace_back #define ios ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0) using namespace std; set<string> ans; string s; int len; void select (int pos, string cur, bool used[10 ]) { if (pos == len) {ans.insert (cur); return ;} rep (i, 0 , len-1 ){ if (!used[i]) used[i]=1 , select (pos+1 , cur+s[i], used),used[i] = 0 ;; } } signed main () { ios; cin >> s; len = s.size (); string tmp; bool tmp2[10 ]; memset (tmp2, 0 , sizeof (tmp2)); select (0 ,tmp,tmp2); cout << ans.size () << '\n' ; for (string i : ans) cout << i << '\n' ; return 0 ; }
Apple Division Apple Division 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 pii pair<int, int> #define F first #define S second #define rep(i, a, b) for(int i = a; i<=b; i++) #define rev(i, a, b) for(int i = a; i>=b; i--) #define tomax(a,b) (a)=max((a), (b)) #define tomin(a,b) (a)=min((a), (b)) #define pb push_back #define eb emplace_back #define ios ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0) using namespace std; signed main () { ios; int n, app[21 ]; cin >> n; rep (i, 0 , n-1 ) cin >> app[i]; int ans = 1e11 ; rep (i, 0 , (1 <<n)-1 ){ int a=0 , b=0 ; rep (j, 0 , n-1 ) a+=app[j]*((i>>j)&1 ), b+=app[j]*(((i>>j)&1 )^1 ); tomin (ans, abs (a-b)); }cout << ans << '\n' ; return 0 ; }
Chessboard and Queens Chessboard and Queens 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 #include <bits/stdc++.h> #define int long long #define pii pair<int, int> #define F first #define S second #define rep(i, a, b) for(int i = a; i<=b; i++) #define rev(i, a, b) for(int i = a, i>=b; i--) #define tomax(a, b) (a)=max((a),(b)) #define tomin(a,b) (a)-min((a),(b)) #define pb push_back #define eb emplace_back #define ios ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0) using namespace std; bool go[10 ][10 ];int ans = 0 ; bool check (int board[10 ]) { bool ok = true ; rep (i, 1 , 8 ){ if (!go[i][board[i]]) ok = false ; rep (j, 1 , 8 ) if (i!=j) ok = (ok && (board[j]!=board[i]+(j-i)) && (board[j]!=board[i]-(j-i))); } return ok; } void test (int pos, int board[10 ], bool dont[10 ]) { if (pos == 9 ){ans+=check (board); return ;} rep (i, 1 , 8 ) if (!dont[i]) board[pos]=i, dont[i]=1 , test (pos+1 , board, dont), dont[i]=0 ; } signed main () { ios; char cmd; rep (i,1 ,8 ) rep (j, 1 , 8 ) cin >> cmd, go[j][i]=(cmd=='.' ); int blank[10 ]; bool blank2[10 ]; memset (blank2, 0 , sizeof (blank2)); test (1 , blank, blank2); cout << ans << '\n' ; return 0 ; }
Digit Queries Digit Queries 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 #include <bits/stdc++.h> #define int long long #define pii pair<int, int> #define F first #define S second #define rep(i, a, b) for(int i = a; i<=b; i++) #define rev(i, a, b) for(int i = a, i>=b; i--) #define tomax(a, b) (a)=max((a),(b)) #define tomin(a,b) (a)-min((a),(b)) #define pb push_back #define eb emplace_back #define ios ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0) #define take(num, pos) ((pos==1) ? (num%10) : (num%pow[pos+1])/pow[pos]) using namespace std; signed main () { ios; int q, u[20 ], pow[20 ]; u[0 ]=0 ; for (int i = 1 , add=1 ; i<=1e18 ; add++, i*=10 ) u[add] = u[add-1 ]+(i*10 -i)*add, pow[add]=i; cin >> q; while (q--){ int cmd; cin >> cmd; int pos = 0 ; while (cmd>u[pos]) pos++; int num = cmd<10 ? cmd : ((cmd-u[pos-1 ]-1 )/(pos) + pow[pos]); cout << (cmd<10 ? cmd : (take (num, pos-((cmd-u[pos-1 ]-1 )%pos))) ) << '\n' ; } return 0 ; }
Grid Paths 唯一一題卡住跑去看別人題解的,因為直接暴力一定爆,發現有神奇判別不可能的方法,幫上下都走過左右沒走過,左右都走過上下沒走過就一定不可能,否則就有可能繞完整張圖,這樣就只會有 88418 次,超酷的。Grid Paths 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 #include <bits/stdc++.h> #define int long long #define pii pair<int, int> #define F first #define S second #define rep(i, a, b) for(int i = a; i<=b; i++) #define rev(i, a, b) for(int i = a, i>=b; i--) #define tomax(a, b) (a)=max((a),(b)) #define tomin(a,b) (a)-min((a),(b)) #define pb push_back #define eb emplace_back #define ios ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0) using namespace std; int ans = 0 , board[10 ][10 ];string s; bool vis[10 ][10 ]; void dfs (int go, int x, int y) { if (vis[x][y]) return ; if (x==1 && y==7 ){ ans+=(go==48 ); return ; } if (vis[x][y+1 ] && vis[x][y-1 ] && !vis[x-1 ][y] && !vis[x+1 ][y]) return ; if (!vis[x][y+1 ] && !vis[x][y-1 ] && vis[x-1 ][y] && vis[x+1 ][y]) return ; vis[x][y]=1 ; if (s[go]=='D' || s[go]=='?' ) dfs (go+1 , x, y+1 ); if (s[go]=='U' || s[go]=='?' ) dfs (go+1 , x, y-1 ); if (s[go]=='L' || s[go]=='?' ) dfs (go+1 , x-1 , y); if (s[go]=='R' || s[go]=='?' ) dfs (go+1 , x+1 , y); vis[x][y]=0 ; } signed main () { ios; cin >> s; memset (vis, 0 , sizeof (vis)); rep (i, 0 , 8 ) vis[i][0 ]=vis[i][8 ]=vis[0 ][i]=vis[8 ][i]=1 ; dfs (0 , 1 , 1 ); cout << ans << '\n' ; return 0 ; }
結語 其實寫 Introductory Problem 蠻爽的,幾乎一次就 AC,用來刷成就感的😏