[数据结构与算法]2021-08-09 SDUT 2021 Summer Individual Contest - 5

8月9号下午——第五次个人赛

这次的表现很拉跨，AC了一个题，不嫌丢人，继续努力就好啦，下面是部分题目的题解：

H - Theater Square

大致题意：在一个nm的矩形格子体中，有一个喷泉，给出了喷泉之外的地方贴上瓷砖，由于瓷砖是12的，且只能横着贴，因为有些地方得贴一半，也就是11的瓷砖，问：用的这些11的半块瓷砖最少来自多少整块瓷砖？

我们分两种情况来进行计算，一种是喷泉所在行，另一种就是普通行，代码如下：

#include<bits/stdc++.h>
using namespace std;
int main()
{
    int n,m;
    int x1,y1,x2,y2;
    cin>>n>>m;  //代表一个 n*m 的矩形格子块
    cin>>x1>>y1>>x2>>y2;   //(x1,y1) 与 (x2,y2)是喷泉左上角的方块和右下角的方块

    int row_fountain=x2-x1+1;       //有喷泉的行数
    int row_normal=n-row_fountain;  //没有喷泉的行数

    int num=0;      //num表示 1*1 方块的数量
    
    //有喷泉的那几行，模式都是一样的
    int sum=0;
    if(y1!=1&&(y1-1)%2!=0)
        sum++;
    if(y2!=m&&(m-y2)%2!=0)
        sum++;
    num+=row_fountain*sum;
    //没有喷泉的那几行，模式也是一样的
    if(m%2!=0)
        num+=row_normal*1;

    if(num%2!=0)  //输出
        cout<<num/2+1<<endl;
    else
        cout<<num/2<<endl;

    return 0;
}

I - Heist

题意就是先输入一个整数n，代表下面有n个键盘，每个键盘都有一个编号，这些键盘的编号原本是连在一起的，比如说5，6，7，8，9，但是经历一场抢劫之后就剩下了上面的n个键盘，问：最少损失了多少个键盘？

#include<bits/stdc++.h>
using namespace std;

int main()
{
    int n;
    cin>>n;
    
    long long int a[10001];
    cin>>a[1];
    
    long long int maxi=a[1];
    long long int mini=a[1];
    
    for(int i=2;i<=n;i++)
    {
        scanf("%lld",&a[i]);
        if(maxi<a[i])
        {
            maxi=a[i];
        }
        if(mini>a[i])
        {
            mini=a[i];
        }
    }
    
    cout<<maxi-mini+1-n<<endl;
    return 0;
}

这个题还可以先用sort函数进行排序，然后两个两个地进行比较，当两个键盘的编号差值不为1时，那就是中间编号的键盘被偷走了，这两种方法都可以，核心代码如下：

#include<bits/stdc++.h>
using namespace std;
int main()
{
    int n;
    cin>>n;
    int a[n];
    for(int i=0;i<n;i++)
    {
        cin>>a[i];
    }
    sort(a,a+n);
    int num=0;
    for(int i=0;i<n-1;i++)
    {
        num+=a[i+1]-a[i]-1;
    }
    cout<<num;
    return 0;
}

J - Buying a TV Set

一句话题意：给你a,b,x,y，求满足 w/h=q/p 的(w,h)对数，其中1 <= w <= a，1 <= h <= b。

题解：
显然面对10^18范围内的a,b，不能枚举。

我们考虑，将 x/y 化简为最简分数 q/p ;
那么w 有ceil(a/q)种取值，h有ceil(b/p)种取值;
//ceil()函数是向下取整的意思，eg:ceil(3.9)=3;
那么答案为：min(ceil(a/q),ceil(b/p));

时间复杂度：O(log(min(x,y)))（求gcd所用时间）

#include<iostream>
#include<algorithm>
#include<math.h>
using namespace std;
int main()
{
    long long int a,b,x,y,t;
    long long int q,p;
    cin>>a>>b>>x>>y;
    t=__gcd(x,y);
    q=x/t;
    p=y/t;

    long long int ans;
    ans=min(ceil(a/q),ceil(b/p));
    cout<<ans<<endl;

    return 0;
}