牛客周赛 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;
}