牛客周赛 Round 24

最后一题没想到用二分做，可惜可惜，思考的方向错了

A 小红的矩阵构造

思路：

主要是区分一下n是奇数还是偶数，是奇数的话就正常输出就行，是偶数的话就可以把偶数行逆着输出

代码：

#include<bits/stdc++.h>
using namespace std;
void solve(){
	int n;
	cin>>n;
	int l=1;
	if(n%2){
		for(int i=1;i<=n;i++){
			for(int j=1;j<=n;j++){
				cout<<l++<<" ";
			}
			cout<<endl;
		}
	}
	else{
		for(int i=1;i<=n;i++){
			if(i%2){
				for(int j=1;j<=n;j++){
					cout<<l++<<" ";
				}
				cout<<endl;
			

			}
			else{
				l=l+n-1;
				for(int j=1;j<=n;j++){
					cout<<l--<<" ";
				}
				l+=n+1;
				cout<<endl;

			}
		}
	}
	
	return ;
	
}
signed main(){
	int t=1;
	while(t--){
		solve();
	}
}

B 小红的因子

题目链接

思路：

因子都是两两成对的，如果要到一个因子p使得p * p > n
那么我们就可以取中间那个因子，那后向前枚举第一个因子，他的另一半就是适合题意的最小因子p

代码：

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

int prime(int x){
    if(x==1||x==0){
        return 0;
    }
    if(x==2){
        return 1;

    }
    for(int i=2;i<=sqrt(x);i++){
        if(x%i==0){
            return 0;
        }
    }
    return 1;
    
}
void solve(){
    int n;
    cin>>n;
    if(prime(n)){
        cout<<n<<endl;
        return ;

    }
    int x=sqrt(n);
    if(x*x!=n){
        x+=1;
        
    }
    for(int i=x-1;i>=1;i--){
        if(n%i==0){
            // cout<<i<<endl;
            
            cout<<n/i<<endl;
            return ;
        }
    }
}
signed main(){
    int t=1;
    cin>>t;
    while(t--){
        solve();
    }
    return 0;

}

C小红的小数点串

题目链接

思路：

看样例，我们肯定是不可以让小数点后面的位数超过1位的，贪心的思想吧

代码：

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

void solve(){
    string s;
    cin>>s;
    double ans=0;
    string s1="";
    for(int i=0;i<s.size();i++){
        if(s[i]=='.'){
            s1+=s[i];
            s1+=s[i+1];
            ans+=stod(s1);
            s1="";
            i+=1;

        }
        else{
            s1+=s[i];

        }
    }
    ans+=stod(s1);
    printf("%.1f",ans);
    cout<<endl;
    
    return ;
    
    
}
signed main(){
    int t=1;
    // cin>>t;

    while(t--){
        solve();
    }
    return 0;

}

D小红的数组操作

题目链接

思路：

其实看到要求尽可能小的最大值，我们应该要想到二分，但是好久不做二分的题了，导致根本没有往哪一方面去思考
为什么我二分除以2超时，但是位运算却没超时！！！

代码：

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=1e5+10;
int a[N];
int n,k,x;
bool check(int mid){
    int ans=0;
    for(int i=1;i<=n;i++){
        if(a[i]>mid){
            ans+=(a[i]-mid+x-1)/x;
            if(ans>k){
                return false;
            }
        }
    }
    return true;

}
void solve(){
    cin>>n>>k>>x;
    for(int i=1;i<=n;i++){
        cin>>a[i];
    }
    int l=-1e18;
    int r=1e18;
    while(l<r){
        int mid=(l+r)>>1;
        if(check(mid)){
            r=mid;
        }
        else{
            l=mid+1;
        }
    }
    cout<<l<<endl;
    return ;
    
}
signed main(){
    int t=1;
    while(t--){
        solve();
    }
    return 0;

}