【寒假每日一题】总结（第七天）

痛定思痛。 2022-10-27 01:47 157阅读 0赞

### 文章目录 ###

*  前言
 *  题目
 *   *  第一天
     *   *   *  博客
             *  题解
             *  讲解
     *  第二天
     *   *   *  博客
             *  题解
             *  讲解
     *  第三天
     *   *   *  博客
             *  题解
             *  讲解
     *  第四天
     *   *   *  博客
             *  题解
             *  讲解
     *  第五天
     *   *   *  博客
             *  题解
             *  讲解
     *  第六天
     *   *   *  博客
             *  题解
             *  讲解
 *  总结

# 前言 #

今天是复习，总结一下这六天的题目和代码！！！

![在这里插入图片描述][20210203083951274.png]

# 题目 #

## 第一天 ##

#### 博客 ####

[【寒假每日一题】货仓选址（个人练习）详细题解+推导证明（第一天）][Link 1]

#### 题解 ####

#include <iostream>
    #include <cstring>
    #include <algorithm>
    
    using namespace std;
    
    const int N = 100005;
    
    int n;
    int f[N];
    
    int main()
    { 
        cin >> n;
        for (int i = 0; i < n; ++ i ) cin >> f[i];
        sort(f, f+n);
        int ans = 0;
        for (int i = 0; i < n; ++ i ) ans += abs(f[i] - f[n >> 1]);
        cout << ans << endl;
        return 0;
    }

#### 讲解 ####

这个题其实是一个数学题的计算机思维的典型题，通过穷举的方式完成数学公式的证明，所以关键点在于中位数。

![在这里插入图片描述][20210203085720110.png]

## 第二天 ##

#### 博客 ####

[【寒假每日一题】数字三角形（个人练习）详细题解+推导证明（第二天）][Link 2]

#### 题解 ####

#include <iostream>
    #include <cstring>
    #include <algorithm>
    
    using namespace std;
    
    const int N = 10005;
    
    int n;
    int f[N][N];
    
    int main()
    { 
        cin >> n;
        for (int i = 1; i <= n; ++ i )
            for (int j = 1; j <= i; ++ j )
                cin >> f[i][j];
                
        for (int i = n - 1; i >= 0; -- i )
            for (int j = 1; j <= i; ++ j )
                f[i][j] += max(f[i+1][j], f[i+1][j+1]);
                
        cout << f[1][1] << endl;
        return 0;
    }

#### 讲解 ####

动态规划的难度还是很大，不过根据我看过和学过的视频，以及题目来说，经验才是克服的方法。

## 第三天 ##

#### 博客 ####

[【寒假每日一题】蛇形矩阵（个人练习）详细题解+推导证明（第三天）][Link 3]

#### 题解 ####

#include <iostream>
    #include <cstring>
    #include <algorithm>
    
    using namespace std;
    
    const int N = 105;
    
    int n, m;
    int f[N][N];
    
    int main()
    { 
        cin >> n >> m;
        int dx[] = { -1, 0, 1, 0}, dy[] = { 0, 1, 0, -1};
        int x = 0, y = 0, d = 1;
        
        for (int i = 1; i <= n*m; ++ i )
        { 
            f[x][y] = i;
            int a = x + dx[d], b = y + dy[d];
            if (a < 0 || a >= n || b < 0 || b >= m || f[a][b])
            { 
                d = (d + 1) % 4;
                a = x + dx[d], b = y + dy[d];
            }
            x = a, y = b;
        }
        
        for (int i = 0; i < n; ++ i )
        { 
            for (int j = 0; j < m; ++ j )
            { 
                cout << f[i][j] << " ";
            }
            cout << endl;
        }
        return 0;
    }

#### 讲解 ####

经典面试题

## 第四天 ##

#### 博客 ####

[【寒假每日一题】红与黑（个人练习）详细题解+推导证明（第四天）][Link 4]

#### 题解 ####

#include <iostream>
    #include <cstring>
    #include <algorithm>
    #include <queue>
    
    #define x first
    #define y second
    
    using namespace std;
    
    const int N = 25;
    typedef pair<int, int> PII;
    
    int n, m;
    char f[N][N];
    
    int bfs(int sx, int sy)
    { 
        queue<PII> q;
        q.push({ sx, sy});
        f[sx][sy] = '#';
        int ans = 0;
        
        int dx[] = { -1, 0, 1, 0}, dy[] = { 0, 1, 0, -1};
        
        while (q.size())
        { 
            auto t = q.front();
            q.pop();
            ++ ans;
            for (int i = 0; i < 4; ++ i )
            { 
                int x = t.x + dx[i], y = t.y + dy[i];
                if (x < 0 || x >= n || y < 0 || y >= m || f[x][y] != '.') continue;
                f[x][y] = '#';
                q.push({ x, y});
            }
        }
        return ans;
    }
    
    int main()
    { 
        while (cin >> m >> n, n || m)
        { 
            for (int i = 0; i < n; ++ i ) cin >> f[i];
            int x, y;
            for (int i = 0; i < n; ++ i )
                for (int j = 0; j < m; ++ j )
                    if (f[i][j] == '@')
                        x = i, y = j;
                        
            cout << bfs(x, y) << endl;
        }
        return 0;
    }

#### 讲解 ####

bfs 和 dfs 都是必须会的方法，bfs 可能更好理解一些。

## 第五天 ##

#### 博客 ####

[【寒假每日一题】回文平方（个人练习）详细题解+推导证明（第五天）][Link 5]

#### 题解 ####

#include <iostream>
    #include <cstring>
    #include <algorithm>
    
    using namespace std;
    
    char get(int x)
    { 
        if (x <= 9) return x + '0';
        return x - 10 + 'A';
    }
    
    string base(int n, int b)
    { 
        string num;
        while (n)
        { 
            num += get(n % b);
            n /= b;
        }
        reverse(num.begin(), num.end());
        return num;
    }
    
    bool check(string num)
    { 
        for (int i = 0, j = num.size() - 1; i < j; ++ i, -- j )
            if(num[i] != num[j]) return false;
        return true;
    }
    
    int main()
    { 
        int b;
        cin >> b;
        for (int i = 1; i <= 300; ++ i)
        { 
            auto num = base(i * i, b);
            if (check(num))
                cout << base(i, b) << " " << num << endl;
        }
        return 0;
    }

#### 讲解 ####

回文数加上字符串处理加上短除法，分函数编写的重要性。

## 第六天 ##

#### 博客 ####

[【寒假每日一题】剪绳子（个人练习）详细题解+推导证明（第六天）][Link 6]

#### 题解 ####

#include <iostream>
    #include <cstring>
    #include <algorithm>
    
    using namespace std;
    
    const int N = 100005;
    
    int n, m;
    int f[N];
    
    bool check(double mid)
    { 
        int cnt = 0;
        for (int i = 0; i < n; ++ i )
        { 
            cnt += f[i] / mid;
        }
        return cnt >= m;
    }
    
    int main()
    { 
        cin >> n >> m;
        for (int i = 0; i < n; ++ i ) cin >> f[i];
        
        double left = 0, right = 1e9;
        while (right - left > 1e-4)
        { 
            double mid = (left + right) / 2;
            if (check(mid)) left = mid;
            else right = mid;
        }
        printf("%.2lf", right);
        
        return 0;
    }

#### 讲解 ####

浮点数二分法你会了吗

# 总结 #

继续努力，坚持更新，7th打卡。  
![在这里插入图片描述][20210203094352960.png]

[20210203083951274.png]: /images/20221024/c0efd7efdf4a45daadfacc1942f81c0b.png
[Link 1]: https://tefuirnever.blog.csdn.net/article/details/113239325
[20210203085720110.png]: /images/20221024/4b2ede209d8a42ca8e25a7ff6b1eed64.png
[Link 2]: https://tefuirnever.blog.csdn.net/article/details/113363308
[Link 3]: https://tefuirnever.blog.csdn.net/article/details/113415542
[Link 4]: https://tefuirnever.blog.csdn.net/article/details/113483012
[Link 5]: https://tefuirnever.blog.csdn.net/article/details/113493006
[Link 6]: https://tefuirnever.blog.csdn.net/article/details/113538008
[20210203094352960.png]: /images/20221024/f5700bfb64534578b0d6fbc203e3ebad.png