牛客周赛 Round 24

A.小红的矩阵构造

题目描述

小红想让你构造一个n行n列的矩阵，矩阵中的元素为1到n^2，每个数只出现1次。小红希望每两个相邻的数之和均为奇数，你能帮帮她吗？

输入描述:

一个正整数n
1≤n≤100

输出描述:

n行，每行输出n个正整数。有多解时输出任意合法解。

示例1

输入

3

输出

3 6 1
2 5 8
9 4 7

解题思路:

结论:奇数行从奇数开始奇偶交替，偶数行从偶数开始偶奇交替

例子1:对于n=3时，构造如下

1 2 3

4 5 6

7 8 9 

例子2:对于n=4,构造如下

1 2 3 4

6 5 8 7

9 10 11 12 

证明:我们可以分俩种情况进行讨论

(1)当n是奇数时，那么就会有的行数为[1,2,...,n]这些行，所以有n/2+1个奇数行，有n/2个偶数行.奇数行比偶数行的行数多1，对于上述例子1中的构造方式，奇数行中的奇数比偶数的个数多1，偶数行中偶数的个数比奇数的个数多1，有n/2+1个奇数行,那么这些行中奇数总共比偶数多n/2+1个，有n/2个偶数行，这些行中偶数总共比奇数多n/2个，最终按照上述构造方式需要使用的奇数比偶数多1个，我们总共拥有的数为[1,n*n],由于n为奇数，所以n*n为奇数，所以以奇数1开始以奇数n*n结束，所以我们拥有的数里面奇数比偶数多1个，刚好符合这种构造方式。

(2)当n是偶数时，那么就会有的行数为[1,2,...,n]这些行，所以有n/2个奇数行，有n/2个偶数行.奇数和偶数行的个数相同，对于上述例子2中的构造方式，奇数行中奇数的个数和偶数的个数一样，偶数行中奇数和偶数的个数也相同，奇偶行数相同，每一行奇数和偶数的个数也相同，所以对于这种构造方式最终需要使用的奇数的个数和偶数的个数一样，而我们拥有的数为[1,2,...,n*n],n为偶数，所以n*n为偶数，以奇数1开头，偶数n*n结束，那么奇数和偶数的个数相同，符合这种构造方式

通过上述证明我们可以知道这种构造方式是合法的

cpp代码如下

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
 
typedef long long LL;
 
const int N = 1e5 + 10;
 
int T, n, m, k;
 
int main()
{
    cin>>n;
    int l=1,r=2;
    for(int i=0;i<n;i++)
    {
        if(i%2==0){
            for(int j=0;j<n;j++)
                if(j%2==0)printf("%d ",l),l+=2;
                else printf("%d ",r),r+=2;
        }else {
            for(int j=0;j<n;j++)
                if(j%2==1)printf("%d ",l),l+=2;
                else printf("%d ",r),r+=2;
        }
        puts("");
    }
    return 0;
}

B.小红的因子

题目描述

小红拿到了一个正整数n，她希望找到n的一个最小因子p，满足p∗p>n。你能帮帮她吗？
一共有t组询问。

输入描述:

第一行输入一个正整数t，代表询问的次数。
接下来的t行，每行输入一个正整数n。
1≤t≤10
2≤n≤1e12

输出描述:

满足条件的最小因子。

示例1

输入

2
36
37

输出

9
37

解题思路:

首先对于一个正整数n可以表示为1个小于等于sqrt(n)的数和一个大于等于sqrt(n)的数的乘积

我们令n的小于等于sqrt(n)的这个因子为a,大于等于sqrt(n)的这个因子为b,那么a*b=n,所以我们只要找到a就可以通过n/a计算出b,由于a,b都是n的因子所以n/a是可以整除的，不存在误差，然后n的范围是1e12,符合条件的a有很多，那么哪个a能够使得b最小呢,首先a*b=n是一个定值，所以肯定a越大,b越小，所以我们只需要在[1,sqrt(n)]之间找到n的最大的约数即可，但是还需要注意一个特殊情况，a不能等于sqrt(n),因为当a=sqrt(n)，那么b也等于sqrt(n),那么b*b=n,题目要求b*b>n,就不符合要求，所以a必须小于sqrt(n);

然后我们考虑一下时间复杂度，找a的时间为1e6,最多只有十个数据,那么时间复杂度1e7,这个时间复杂度是肯定可以过的。

cpp代码如下

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
 
typedef long long LL;
 
const int N = 1e5 + 10;
 
int T, m, k;
LL n;
 
LL f(LL x)
{
    LL v=1;
    for(int i=2;i<=x/i;i++)
        if(x%i==0 && (LL)i*i!=x){
            v=i;
        }
    v=x/v;
    return v;
}
int main()
{
    cin>>T;
    while(T--)
    {
        scanf("%lld",&n);
        LL ans=f(n);
        cout<<ans<<endl;
    }
    return 0;
}

C.小红的小数点串

题目描述

小红拿到了一个仅包含数字和小数点（'.'）的字符串。她准备把这个字符串切分，使得切分后的每个数（整数或小数）都合法。小红想知道，切分后所有数之和的最大值是多少。
我们定义，合法的小数为：只包含一个小数点，且小数点的左和右均为数字字符。例如"0.23"、"125.24"、"7.0"为合法小数，而".45"、"345."为不合法小数。

输入描述:

一个长度不超过1e5的字符串，保证连续数字的长度不低于2，不超过10。

输出描述:

切分后的和的最大值。保留一位小数。

示例1

输入

12.23.45

输出

20.6

说明

12.2  3.4  5  切成这三个数。

示例2

输入

220.022

输出

242.0

说明

220.0 22 切成这两个数。

解题思路:

由于小数点后面必须要带小数，考虑贪心，我们只让切割的每个部分的小数部分的小数点后面只带一位数字，那么就可以让后面切割出来的那部分整数部分的位数最多，那么值就最大，对于任意的数字贡献给整数部分肯定比小数部分的收益大，那么切割之后所有部分的值的和就是最大的。

cpp代码如下

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
 
typedef long long LL;
 
const int N = 1e5 + 10;
 
int T, n, m, k;
 
int main()
{
    string s;
    cin>>s;
    double ans=0.0,v=0.0;
    for(int i=0;i<s.size();i++)
    {
        if(s[i]=='.'){
            i++;
            v+=((s[i]-'0')*0.1);
            ans+=v;
            v=0.0;
        }else {
            v=v*10+(s[i]-'0');
        }
    }
    ans+=v;
    printf("%.1lf",ans);
    return 0;
}

D.小红的数组操作

题目描述

小红拿到了一个数组，她每次可以进行如下操作：
选择一个数，使其减去 x。
小红希望 k 次操作之后，该数组的最大值尽可能小。请你求出这个尽可能小的最大值。

输入描述:

第一行输入三个正整数 n、k 和 x，代表数组长度、操作次数以及每次操作减的数。
第二行输入 n 个正整数 ai，代表小红拿到的数组。

1≤n≤1e5
1≤ai,k,x≤1e9

输出描述:

一个整数，代表 k 次操作后，数组尽可能小的最大值。

示例1

输入

5 3 5
4 3 11 2 1

输出

3

说明

第一个数操作 1 次，第三个数操作 2 次，数组变成 [-1,3,1,2,1]，最大值为 3。

解题思路:

对于这个题目，题目已经提示的很明显了，看到让最大值最小值这句话，熟悉二分的人就应该知道这个题目很可能和二分有关了,我们可以二分最大值mid，我们需要在k次之内的操作让所有数都小于等于mid,我们计算一下让所有数小于等于mid的次数，如果次数小于等于k,说明这个值是可以取到的，我们可以发现二分的值mid越大，需要的操作次数越少，满足要求的可能性越大，二分的mid值越小，需要的操作次数越大，满足要求的可能性越小，这就具有二段性了，所以我们直接二分答案即可。

二分上界：由于ai<=1e9,只能执行减法操作，所以上界就是1e9

二分下界:   可以把所有的操作放在最小的数，下界就是mn-k*x(mn表示a数组中最小的数)

特别注意：一般来说上下界开大一点没有影响，但是这个题目不行，下界最好开精确一点，开成mn-k*x,二分下界开的如果不精确那么可能有些地方计算的时候会爆long long 

cpp代码如下

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
 
typedef long long LL;
 
const int N = 1e5 + 10;
const LL INF=1e18;
 
int T, n, x, k;
int a[N];
 
bool check(LL mid)
{
    LL cnt=0;//cnt记录让所有的数小于等于mid的操作次数
    for(int i=1;i<=n;i++)
    {
        LL diff=(LL)a[i]-mid;
        if(diff<=0)continue; //a[i]已经小于等于mid,不需要进行操作
        LL num=((LL)diff+x-1)/x;  //这里要向上取整
        cnt+=num;
    }
    return cnt<=k; 
}
int main()
{
    cin>>n>>k>>x;
    int mn=2e9;
    for(int i=1;i<=n;i++)scanf("%d",&a[i]),mn=min(mn,a[i]);
    LL l=(LL)mn-(LL)k*x,r=1e9;
    
    while(l<r){
        LL mid=l+r>>1;
        if(check(mid))r=mid;
        else l=mid+1;
    }
    cout<<r<<endl;
    return 0;
}