CodeVs刷题攻略之Silver

CodeVs刷题攻略之Silver

2017.12.18 By gwj1139177410

0x01排序

  1. 明明的随机数

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    #include<iostream>
    using namespace std;
    int n, a[1010], t;
    int main(){
    cin>>n;
    for(int i = 1; i <= n; i++){
    int x; cin>>x;
    if(!a[x]){ a[x]++; t++; }
    }
    cout<<t<<"\n";
    for(int i = 1; i <= 1000; i++)
    if(a[i])cout<<i<<" ";
    return 0;
    }
  2. 排序

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    #include<iostream>
    #include<algorithm>
    using namespace std;
    int n, a[100010];
    int main(){
    cin>>n;
    for(int i = 0; i < n; i++)cin>>a[i];
    sort(a,a+n);
    for(int i = 0; i < n; i++)cout<<a[i]<<" ";
    return 0;
    }

0x02模拟

  1. Cantor表

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    #include<iostream>
    using namespace std;
    int main(){
    int n, k=1; cin>>n;
    //1.第n个数在第k条斜线上(前k条斜线的数的个数为等差数列)
    while((1+k)*k/2 < n)k++;
    int s = n-(1+k-1)*(k-1)/2;
    //2.偶数从上往下
    if(k%2==0)cout<<s<<"/"<<k+1-s<<"\n";
    else cout<<k+1-s<<"/"<<s<<"\n";
    return 0;
    }
  2. 蛇形矩阵

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    #include<iostream>
    using namespace std;
    int a[110][110];
    int main(){
    int n; cin>>n;
    int tot, x, y; a[x=n][y=n] = tot = n*n;
    while(tot > 1){
    while(y-1>=1 && !a[x][y-1])a[x][--y] = --tot;
    while(x-1>=1 && !a[x-1][y])a[--x][y] = --tot;
    while(y+1<=n && !a[x][y+1])a[x][++y] = --tot;
    while(x+1<=n && !a[x+1][y])a[++x][y] = --tot;
    }
    int ans = 0;
    for(int i = 1; i <= n; i++){
    for(int j = 1; j <= n; j++){
    cout<<a[i][j]<<" ";
    if(i==j||i+j==n)ans += a[i][j];
    }
    cout<<"\n";
    }
    cout<<ans<<"\n";
    return 0;
    }

0x03数论入门

  1. 最大公约数和最小公倍数问题

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    #include<iostream>
    using namespace std;
    int gcd(int a, int b){return b==0?a:gcd(b,a%b);}
    int x, y, z, ans;
    int main(){
    cin>>x>>y; z=x*y;
    for(int i = 1; i <= z; i++)
    if(z%i==0 && gcd(i,z/i)==x)
    ans++;
    cout<<ans<<"\n";
    return 0;
    }
  2. 最大公约数

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    #include<iostream>
    using namespace std;
    int gcd(int a, int b){
    return !b ? a : gcd(b,a%b);
    }
    int main(){
    int x, y; cin>>x>>y;
    cout<<gcd(x,y)<<"\n";
    return 0;
    }
  3. 素数判定

    1
    2
    3
    4
    5
    6
    7
    8
    9
    #include<iostream>
    using namespace std;
    int main(){
    int n; cin>>n;
    for(int i = 2; i < n; i++)
    if(n%i==0){cout<<"\\n"; return 0;}
    cout<<"\\t";
    return 0;
    }

0x04进制转换

  1. 十进制转m进制

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    #include<iostream>
    #include<string>
    using namespace std;
    string s="0123456789ABCDEF";
    void dfs(int a, int b){
    if(a == 0)return ;
    else dfs(a/b,b);
    cout<<s[a%b];
    }
    int main(){
    int a, b;
    cin>>a>>b;
    dfs(a,b);
    return 0;
    }
  2. m进制转十进制

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    #include<iostream>
    #include<string>
    using namespace std;
    int main(){
    string s; int m, t=1, ans=0;
    cin>>s>>m;
    for(int i = s.size()-1; i >= 0; i--){
    if(s[i]>='A'&&s[i]<='Z')ans += (s[i]-'A'+10)*t;
    else ans += (s[i]-'0')*t;
    t *= m;
    }
    cout<<ans<<"\n";
    return 0;
    }

0x05递推

  1. 数的计算

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    #include<iostream>
    using namespace std;
    const int maxn = 1010;
    int f[maxn];
    int main(){
    int n; cin>>n;
    for(int i = 1; i <= n; i++){
    f[i] = 1; //左边不加也是一种
    for(int j = 0; j <= i/2; j++)f[i] += f[j];
    }
    cout<<f[n]<<"\n";
    return 0;
    }
  2. Fibonacci数列 3

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    #include<iostream>
    using namespace std;
    const int maxn = 20;
    int f[maxn];
    int main(){
    int n; cin>>n;
    f[1] = f[0] = 1;
    for(int i = 3; i <= n; i++)
    f[i%2]=f[(i-1)%2]+f[(i-2)%2];
    cout<<f[n%2];
    return 0;
    }

0x06递归

  1. 二叉树最大宽度和高度

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    #include<iostream>
    #include<algorithm>
    using namespace std;
    const int maxn = 110;
    int tree[maxn][2], higt, weigt[maxn], ww;//宽度是每一层的
    void dfs(int now, int dep){
    higt = max(higt,dep);
    ww = max(ww, weigt[dep]);
    if(tree[now][0]){ dfs(tree[now][0], dep+1); weigt[dep+1]++; }
    if(tree[now][1]){ dfs(tree[now][1], dep+1); weigt[dep+1]++; }
    }
    int main(){
    int n; cin>>n;
    for(int i = 1; i <= n; i++)
    cin>>tree[i][0]>>tree[i][1];
    dfs(1, 1);
    cout<<ww+1<<" "<<higt<<"\n";
    return 0;
    }
  2. 递归第一次

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    #include<iostream>
    using namespace std;
    int f(int x){
    return x>=0 ? 5 : f(x+1)+f(x+2)+1;
    }
    int main(){
    int n; cin>>n;
    cout<<f(n)<<"\n";
    return 0;
    }
  3. 3n+1问题

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    //-1什么不存在的。
    #include<iostream>
    using namespace std;
    int main(){
    int T; cin>>T;
    while(T--){
    int n, s=0; cin>>n;
    while(n != 1){
    if(n%2==1)n = 3*n+1;
    else n = n/2;
    s++;
    }
    cout<<s<<"\n";
    }
    return 0;
    }
  4. 二叉树的序遍历

    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<iostream>
    using namespace std;
    const int maxn = 110;
    int tree[maxn][2];
    void dfs1(int now){
    cout<<now<<" ";
    if(tree[now][0])dfs1(tree[now][0]);
    if(tree[now][1])dfs1(tree[now][1]);
    }
    void dfs2(int now){
    if(tree[now][0])dfs2(tree[now][0]);
    cout<<now<<" ";
    if(tree[now][1])dfs2(tree[now][1]);
    }
    void dfs3(int now){
    if(tree[now][0])dfs3(tree[now][0]);
    if(tree[now][1])dfs3(tree[now][1]);
    cout<<now<<" ";
    }
    int main(){
    int n; cin>>n;
    for(int i = 1; i <= n; i++)
    cin>>tree[i][0]>>tree[i][1];
    dfs1(1); cout<<"\n";
    dfs2(1); cout<<"\n";
    dfs3(1); cout<<"\n";
    return 0;
    }
  5. 汉诺塔游戏

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    //把大象装进冰箱一共需要几步。。。
    #include<iostream>
    using namespace std;
    int n, ans = 0, t;
    void f(int a, char b, char c){
    ans++;
    if(a == 1){
    if(t)cout<<a<<" from "<<b<<" to "<<c<<"\n";
    return ;
    }
    f(a-1,b,198-b-c);//1.打开冰箱门
    if(t)cout<<a<<" from "<<b<<" to "<<c<<"\n";//2.把大象装进去
    f(a-1,198-b-c,c);//关上冰箱门
    }
    int main(){
    cin>>n;
    f(n,'A','C');
    cout<<ans<<"\n";
    t = 1;
    f(n,'A','C');
    return 0;
    }