一、第一周学习总结表

  • 本周学习完成情况

    Contest完成情况
    数组和字符串进阶练习11/13
    简单数学题、数组字符串练习13/13
    ACM入门练习-hdu13/13
    枚举算法练习7/7
    总计44/46

  • 个人小结

    1. 个人感悟

      经过一周的训练，收获颇多。题目虽然不难，但是对于英文的快速阅读能力，和不同OJ平台的输入输出的考验是前所未有的。每次写题不再是使用单纯纯暴力写法，更多的会再一开始就去分析题目背后的真正含义，将其转换成一个较为熟悉的问题。

二、本周学习的新内容

本以为第一周的内容都是已经了然于心的基础知识，没想到在刷题中也学到了许多未曾注意的细节。

  • 对于EOF输入结尾的题目可以使用while(~scanf("%d",&n));来处理
  • OJ上浏览大佬代码，学会了使用ios::sync_with_stdio(false);cin.tie(0);来加快io流中cin，cout的读写速度

  • 学会了使用

    clock start,end;
    start=clock();
    end=clock();
    printf("Time used = %.2lf\n", (double)(sta) / CLOCKS_PER_SEC);

    来输出程序花费的时间

  • 熟练掌握了对拍来检查程序与标程的区别，从而检查出自己代码的错误之处
    使用freopen("3output.out","w",stdout);freopen("1input.in","r",stdin);输出重定向至文件，检查不同代码之间的区别
  • 对于询问次数多，复杂度高的问题，用打表做更方便
  • 学会了Joseph的递推公式为$f(N,M)=(f(N−1,M)+M)modN$

三、题解一览

1.ACM入门练习- I - Download Manager

ACM入门练习-hdu - Virtual Judge (vjudge.net)

题目标签

数学；技巧

题目描述

本题要求我们模拟一个下载器，根据输入的最大宽带B，和同时下载文件数n作为限制条件。

针对已给出文件大小和完成进度的多少，计算总任务完成的所需时间。

下载器会根据如下规律下载文件：

  1. 优先挑选大小最小的n个文件，如果文件大小相同则先选择完成进度大的
  2. 一个文件完成后，即开始下一个文件的下载，速度平均分配给每个文件
  3. 如果少于n个文件，那么速度也平均分配给n个文件

题目解析

本题乍一看下，以为是个模拟题，操作步骤极为繁琐。但其实仔细分析，推导出背后的原理，会发现这题非常的简单。

题目要求我们求出的是下载的时间，而难点就在于不同的文件完成进度不一样，大小也不一样。如果用结构体来模拟下载的文件，并循环直至文件全部下载好，这将花费大量的精力在编写运算条件上。

而如果我们不从文件出发，换个角度从下载器下载的大小出发，问题就会变得简单。

根据推导我们可以发现

  • 假如有三个文件时，每个文件的下载速度是总文件大小总共是
  • 假如有两个文件时，每个文件的下载速度是总文件大小总共是
  • 假如有n个文件时，每个文件的下载速度是总文件大小总共是

我们发现无论多少个文件同时下载，下载器的下载总速度是不变的，即

所以只需要将剩余未下载完的所有大小全部加起来再除以最大带宽速度即可

通过代码

#include<bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define maxnum 500005
#define inf 1000000007
using namespace std;
int main()
{
    int T,m,maxn;
        int t=1;
    while(~scanf("%d %d %d",&T,&m,&maxn)){
        if (T==0 && m==0 && maxn==0)
        {
            break;
        }
        double size;double com;double sum=0;
        for (int i = 0; i < T; i++)
        {
            cin>>size>>com;
            sum+=size*(100-com)*0.01;//总下载剩余量
        }
        printf("Case %d: %.2lf\n\n",t,sum/maxn);
        t++;
    }
}

2.数学、字符串 - A - Joseph

约瑟夫环总结：https://blog.csdn.net/mzpqq/article/details/124568918

题目标签

数学；打表

题目描述

给定一个数字n，总共2n个人围成一圈，前n个坏人，后n个好人，求最m为几，使得踢出去的都是坏人

题目解析

n很小所以可以直接枚举，打表输出

根据递推公式$f(N,M)=(f(N−1,M)+M)%N$，枚举m，保证每次出列的人都是坏人，如果是坏人，则运行，如果是好人则退出枚举下一个

通过代码

#include <cstring>
#include <iomanip>
#include <cmath>
#include <string>
#include <iostream>
#include <vector>
#include <algorithm>
#include <set>
#include <numeric>
#include <ctime>
#define ll long long
#define ull unsigned long long
#define maxnum 500005
#define inf 1000000007
using namespace std;
const double PI = acos(-1.0);
ll getf(int n){
    for (ll i = n+1;; i++)//枚举第m个
    {
        int all=2*n;
        bool flag=true;
        ll l=0;    
        while (all>n)
        {
            l=(l+i-1)%all;
            if (l < n)
            {
                flag=false;
                break;
            }
            all--;
        }
        if (flag==true)
        {
            return i;
        }
        
    }
    return 0;
}
int main()
{
    int n;
    ll a[14]={0};
    for (int i = 1; i < 14; i++)
    {
        a[i]=getf(i);
    }
    while (~scanf("%d",&n) && n!=0)
    {
        cout<<a[n]<<endl;
    }
    
    return 0;
}

3.数学、字符串 - B - Number Sequence

题目标签

数学；打表

题目描述

给出A，B，N。根据给出的公式:

$f(1) = 1, f(2) = 1, f(n) = (A f(n - 1) + B f(n - 2)) mod 7$

求出f(N)

题目解析

若使用传统方式一直递推，由于数据量过大，会导致最终超时。

对小的数据进行打表，发现f(x)呈现一个循环，只需求出循环的循环节，再对N取模，即可求出f(n)

根据同余定理，f(n)有7*7种取得方式，所以循环最多有49种情况，只需打表打至49个就可以了，甚至不需要求出循环节，只需要让其对49取余，超出循环节的部分也可以得到

通过代码

#include <cstring>
#include <iomanip>
#include <cmath>
#include <string>
#include <iostream>
#include <vector>
#include <algorithm>
#include <set>
#include <numeric>
#include <ctime>
#define ll long long
#define ull unsigned long long
#define maxnum 500005
#define inf 1000000007
using namespace std;
const double PI = acos(-1.0);
int main()
{
    // freopen("1output.out","w",stdout);
    // freopen("1input.in","r",stdin);
    int a,b;
    ll q;
    while (1)
    {
        ll f[60]={0};
        f[1]=1;f[2]=1;
        cin>>a>>b>>q;
        if (a==0 && b==0 && q==0)
        {
            break;
        }
        int i=0;
        for (i = 3; i < 55; i++)
        {
            f[i]=((f[i-1]*(a))+(f[i-2]*(b)))%7;//公式递推打表
        }
        cout<<f[q%49];
        cout<<endl;
        
    }
}

4.枚举算法练习 - G - Ants

题目标签

思维

题目描述

一个树枝长lcm，上面有n个蚂蚁，蚂蚁以1cm/s的速度运动，蚂蚁相撞会往反方向走，给出n个蚂蚁的位置，但是不知道每只蚂蚁运动的方向，求出每个样例中，最后一只蚂蚁掉落的时间的最大值和最小值

题目解析

如果单纯的枚举，则情况会变得非常复杂，并且没有蚂蚁数量是动态的很难用n个for循环嵌套

即使用搜索也没有给出方向。

而其实这题是考验我们的思维能力，两只蚂蚁相撞，再往反方向走，其实就是可以看成蚂蚁一直往一个方向走。由此题目就变得非常简单，只需要根据距离，不断比较，求出最大和最小的最后一只蚂蚁掉落时间即可

通过代码

#include <cstring>
#include <iomanip>
#include <cmath>
#include <string>
#include <iostream>
#include <vector>
#include <algorithm>
#include <set>
#include <numeric>
#include <ctime>
#define ll long long
#define ull unsigned long long
#define max(x, y) x > y ? x : y
#define min(x, y) x < y ? x : y
#define maxnum 500005
#define inf 1000000007
using namespace std;
const double PI = acos(-1.0);
int main()
{
    int t;cin>>t;
    while (t--)
    {
        ll l;int n;
        cin>>l>>n;
        ll dis[999999]={0};//初始化
        ll minn=-1;
        ll maxn=-1;
        for (int i = 0; i < n; i++)
        {   
            cin>>dis[i];
            int fl,fr;
            fl=l-dis[i];fr=dis[i];
            int mi=min(fl,fr);
            int ma=max(fl,fr);
            minn=max(minn,mi);//求出最小值，虽然是最小值，但是也是最后一个的最小值，所以是max
            maxn=max(maxn,ma);//求出最大值
        }
        cout<<minn<<" "<<maxn<<endl;
    }
}

5.AtCoder Regular Contest 144 - A -Digit Sum of 2x

题目标签

思维；数学

题目描述

给出函数f(n)，即求一个数的各个位数的和

如$f(144)=1+4+4=9$

给出一个正整数N，找到M使得$f(x)=N$ and$f (2x)=M$ ,M有多个答案，要求找到最大的

再找出一个x，使得$f(x)=N$ and$f (2x)=M$ ,x有多个答案要求找出最小的

题目解析

如果直接进行打表，问题将变得非常复杂。

此时分析题面，发现要求如果2*x中有x的某一位>5，则会导致2x，中的该为进位，导致和变小，所以要求找到的x的每一位都必须为小于5，而每一位都小于5，就能保证该数的2倍的各位求和不会变小，所以M=2N

接下来要求找到能够组成M的最小的数x

同上定理，要保证每个位的数都小于5，而小于5的数必须保证为最大，这样保证和不变的情况下，分出的位数为最小，这样求能求得的x才为最小的x。

所以只要把M分解为k个4和分不下去后余下的一个数即可

通过代码

#include<bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define maxnum 500005
#define inf 1000000007
using namespace std;
const double PI = acos(-1.0);
int main()
{
    // ios::sync_with_stdio(false);
    // cin.tie(0);
    // freopen("3output.out","w",stdout);
    
    // freopen("1input.in","r",stdin);
    int n;
    cin>>n;
    int t=n%4;//余下的数
    int k=n/4;//有k个4
    string s;
    if(t!=0){
        s+=char(t+'0');
    }//如果余下的不是零，则再最后加上这个余下的数
    for (int i = 0; i < k; i++)
    {
        s+='4';//加上k个4
    }
    cout<<2*n<<endl<<s;
    // printf("Time used = %.2lf\n", (double)clock() / CLOCKS_PER_SEC);
    return 0;
}