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;} }