C是个有意思的贪心。
A
给出一种构造:
奇 偶 奇 偶...
偶 奇 偶 奇...
...
列表可以发现,n增加后,奇数偶数的差为1个定值
n 奇数 偶数
2 2 2
3 5 4
4 8 8
5 13 12
当n为奇数,奇数比偶数多1
否则,奇数偶数一致
而[1,n2]的所有自然数也有此种规律
故而可以这样构造可以实现,
考察每一个偶数,周围均为奇数,奇数周围均是偶数,而奇数+偶数=奇数,符合题意
#include<bits/stdc++.h>
using namespace std;
#define INF 1e18
#define maxx 8822
#define maxx2 0x3f3f3f3f
int n;
int ji=-1;
int ou=0;
signed main()
{
cin>>n;
for(int i=1;i<=n;++i)
for(int j=1;j<=n;++j)
{
if(i%2==1)
{
if(j%2==0) ou=ou+2,cout<<ou;
else ji=ji+2,cout<<ji;
}
else
{
if(j%2==1) ou=ou+2,cout<<ou;
else ji=ji+2,cout<<ji;
}
if(j==n) cout<<"\n";
else cout<<" ";
}
}
B
sqrt(n)枚举约数,然后验证是否符合条件
#include<bits/stdc++.h>
using namespace std;
#define INF 1e30
#define maxx 8822
#define int long long
#define maxx2 0x3f3f3f3f
int a,b,d,k,m,t,n,ansmax,Smax,x,ans1,ans2,c;
signed main()
{
cin>>t;
for(int i=1;i<=t;++i)
{
cin>>n;
int x=sqrt(n);
int ans=n;
for(int i=1;i<=x;++i)
{
if(n%i==0)
{
if(i*i>n) ans=min(ans,i);
if((n/i)*(n/i)>n) ans=min(ans,n/i);
}
}
cout<<ans<<"\n";
}
}
C
贪心
观察分割的时候,我们保证小数点后尽量少,小数点前尽量多,因为小数点后的数字不如直接独立,增加小数点后的数字相当于增加小于1的结果,直接独立相等于增加大于等于1的结果,类似的,小数点前尽量多,所以小数点直到上一个小数点的数字连在一起,小数点后仅给1位,保证合法。
#include<bits/stdc++.h>
using namespace std;
#define INF 1e18
#define maxx 8822
#define int long long
#define maxx2 0x3f3f3f3f
int a,b,d,k,m,t,n,ansmax,Smax,x,ans1,ans2,c;
map<int,int> M;
double ans=0;
string s;
string s1;
signed main()
{
cin>>s;
for(int i=0;i<s.size();++i)
{
s1=s1+s[i];
if(s[i]=='.')
{
++i;
s1=s1+s[i];
ans=ans+stod(s1);
s1.clear();
}
}
if(s1.size()!=0) ans=ans+stoi(s1);
printf("%.1lf",ans);
}
D
二分
题目有单调性,因为最大值越大越难以实现。
故二分最大值。
#include<bits/stdc++.h>
using namespace std;
#define INF 1e18
#define int long long
#define maxx 400000
int n,a,b,d,k,m,t,ansmax,Smax,ans,x,ans1,ans2,neww,c;
int l,r;
int all[maxx];
int check(int y)
{
int qq=0;
for(int i=1;i<=n;++i)
if(all[i]-y>0)
{
qq=qq+((all[i]-y)/x);
if((all[i]-y)%x!=0) ++qq;
if(qq>k) return 0;
}
if(qq<=k) return 1;
else return 0;
}
signed main()
{
cin>>n>>k>>x;
for(int i=1;i<=n;++i)
cin>>all[i];
l=-INF;
r=INF;
while(l<r)
{
if(abs(l-r)==1) break;
int mid=(l+r)/2;
if(!check(mid)) l=mid+1;
else r=mid;
}
if(check(l)==1) {cout<<l; return 0;}
if(check(r)==1) {cout<<r; return 0;}
}



京公网安备 11010502036488号