CSES Introductory Problems

發表於 更新於 分類於 ， 閱讀次數： 文章字數： 674 所需閱讀時間 ≈ 1 分鐘

前言

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 << num << ' ' << pos << ' ' << u[pos-1] << ' ' << (pos-((cmd-u[pos-1]-1)%pos)) << '\n';
        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，用來刷成就感的😏