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

た入场券 2022-10-29 10:26 149阅读 0赞

### 文章目录 ###

*  前言
 *  题目
 *   *  第八天
     *   *   *  博客
             *  题解
             *  讲解
     *  第九天
     *   *   *  博客
             *  题解
             *  讲解
     *  第十天
     *   *   *  博客
             *  题解
             *  讲解
     *  第十一天
     *   *   *  博客
             *  题解
             *  讲解
     *  第十二天
     *   *   *  博客
             *  题解
             *  讲解
     *  第十三天
     *   *   *  博客
             *  题解
             *  讲解
     *  第十三四
     *   *   *  博客
             *  题解
             *  讲解
 *  总结

# 前言 #

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

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

# 题目 #

## 第八天 ##

#### 博客 ####

[【寒假每日一题】分巧克力（个人练习）详细题解+推导证明（第八天）附带转载程序员壁纸][Link 1]

#### 题解 ####

#include <iostream>
    #include <cstring>
    #include <algorithm>
    
    using namespace std;
    
    typedef long long LL;
    const int N = 100005;
    
    int n, m;
    int h[N], w[N];
    
    bool check(int mid)
    { 
        LL ans = 0;
        for (int i = 0; i < n; ++ i )
        { 
            ans += (LL)(h[i] / mid) * (w[i] / mid);
            if (ans >= m) return true;
        }
        return false;
    }
    
    int main()
    { 
        cin >> n >> m;
        for (int i = 0; i < n; ++ i ) cin >> h[i] >> w[i];
        
        int l = 1, r = 1e5;
        while (l < r)
        { 
            int mid = l + r + 1 >> 1;
            if(check(mid)) l = mid;
            else r = mid - 1;
        }
        cout << r << endl;
        
        return 0;
    }

#### 讲解 ####

这个题是之前一个题的二维空间版本。

## 第九天 ##

#### 博客 ####

[【寒假每日一题】校门外的树（个人练习）详细题解+推导证明（第九天）][Link 2]

#### 题解 ####

#include <iostream>
    #include <cstring>
    #include <algorithm>
    
    #define x first
    #define y second
    
    using namespace std;
    
    typedef pair<int,int> PII;
    const int N = 110;
    
    int n, m;
    PII segs[N];
    
    int main()
    { 
        cin >> n >> m;
        for (int i = 0; i < m; i ++ ) cin >> segs[i].x >> segs[i].y;
        sort(segs, segs + m);
    
        int sum = 0;
        int st = segs[0].x, ed = segs[0].y;
        for (int i = 1; i < m; i ++ )
            if (segs[i].x <= ed) 
                ed = max(ed, segs[i].y);
            else
            { 
                sum += ed - st + 1;
                st = segs[i].x, ed = segs[i].y;
            }
        sum += ed - st + 1;
        cout << n + 1 - sum << endl;
    
        return 0;
    }

#### 讲解 ####

讲道理，区间排序是一个很重要的算法，并且难了不会，会了不难。

## 第十天 ##

#### 博客 ####

[【寒假每日一题】奖学金（个人练习）详细题解+推导证明（第十天）][Link 3]

#### 题解 ####

#include <iostream>
    #include <cstring>
    #include <algorithm>
    
    using namespace std;
    
    const int N = 305;
    
    int n;
    struct Person
    { 
        int id, sum, a, b, c;
    }q[N];
    
    int main()
    { 
        cin >> n;
        for (int i = 1; i <= n; ++ i )
        { 
            int x, y, z;
            cin >> x >> y >> z;
            q[i] = { i, x + y + z, x, y, z};
        }
        sort(q + 1, q + 1 + n, [](Person& x, Person& y){ 
            if (x.sum != y.sum) return x.sum > y.sum;
            if (x.a != y.a) return x.a > y.a;
            return x.id < y.id;
        });
        for (int i = 1; i <= 5; ++ i )
            cout << q[i].id << " " << q[i].sum << endl;
            
        return 0;
    }

#### 讲解 ####

学会使用新版C++的特性，这会增加你的生产力。

## 第十一天 ##

#### 博客 ####

[【寒假每日一题】翻硬币（个人练习）详细题解+推导证明（第十一天）][Link 4]

#### 题解 ####

#include <iostream>
    #include <cstring>
    #include <algorithm>
    
    using namespace std;
    
    const int N = 105;
    
    string a, b;
    
    void turn(int i)
    { 
        if(a[i] == '*') a[i] = 'o';
        else a[i] = '*';
    }
    
    int main()
    { 
        cin >> a >> b;
        int ans = 0;
        for (int i = 0; i < a.size() - 1; ++ i )
            if (a[i] != b[i])
            { 
                ++ ans;
                turn(i), turn(i + 1);
            }
        
        cout << ans << endl;
        return 0;
    }

#### 讲解 ####

分析之后，你会发现从头到尾进行模拟，是时间复杂度的最优解。

## 第十二天 ##

#### 博客 ####

[【寒假每日一题】找硬币（个人练习）详细题解+推导证明（第十二天）][Link 5]

#### 题解 ####

#include <iostream>
    #include <cstring>
    #include <algorithm>
    
    using namespace std;
    
    const int N = 100005;
    
    int n, m;
    int f[N];
    
    int main()
    { 
        cin >> n >> m;
        for (int i = 0; i < n; ++ i ) cin >> f[i];
        sort(f, f + n);
        
        for (int i = 0, j = n - 1; i < j; ++ i )
        { 
            while (i < j && f[i] + f[j] > m) -- j;
            if (i < j && f[i] + f[j] == m)
            { 
                cout << f[i] << " " << f[j] << endl;
                return 0;
            }
        }
        puts("No Solution");
        return 0;
    }

#### 讲解 ####

学会使用哈希表和双指针进行互相优化。

## 第十三天 ##

#### 博客 ####

[【寒假每日一题】十三号星期五（个人练习）详细题解+推导证明（第十三天）][Link 6]

#### 题解 ####

#include <iostream>
    #include <cstring>
    #include <algorithm>
    
    using namespace std;
    
    int months[13] = { 0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};
    int weekdays[7];
    
    int main()
    { 
        int n;
        cin >> n;
        
        int days = 0;
        for (int y = 1900; y < 1900 + n; ++ y )
        { 
            for (int m = 1; m <= 12; ++ m )
            { 
                weekdays[(days + 12) % 7] ++;
                days += months[m];
                if (m == 2)
                    if ((y % 100 && y % 4 == 0) || (y % 400 == 0))
                        ++ days;
            }
        }
        
        for (int i = 5, j = 0; j < 7; i = (i + 1) % 7, ++ j )
            cout << weekdays[i] << " ";
        cout << endl;
        
        return 0;
    }

#### 讲解 ####

需要注意的是输出，从周五开始。

## 第十三四 ##

#### 博客 ####

[【寒假每日一题】平方矩阵 II（个人练习）详细题解+推导证明（第十四天）][II]

#### 题解 ####

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

#### 讲解 ####

这种数学题，建议从一开始看到的最简单的方式去书写代码。

# 总结 #

继续努力，坚持更新，15th打卡。

唤醒鹿鸣，体验暖心陪伴

米哈游真的厉害

[20210212205508209.png]: /images/20221024/08f0d50e237b4a81885924f95ff298e5.png
[Link 1]: https://tefuirnever.blog.csdn.net/article/details/113623851
[Link 2]: https://tefuirnever.blog.csdn.net/article/details/113686150
[Link 3]: https://tefuirnever.blog.csdn.net/article/details/113708054
[Link 4]: https://tefuirnever.blog.csdn.net/article/details/113734376
[Link 5]: https://tefuirnever.blog.csdn.net/article/details/113751551
[Link 6]: https://tefuirnever.blog.csdn.net/article/details/113765996
[II]: https://tefuirnever.blog.csdn.net/article/details/113778887