2022年3月20日22:13:05
4376. 数圈圈
1.【题目描述】
输入样例1：
11
输出样例1：
2
输入样例2：
14
输出样例2：
0
2.【题解】
进制转换+字符串遍历
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int,int> pii;
const int inf=0x3f3f3f3f;
const int maxn=1e6+5;
string func(int n){
string s;
int t = n / 16;
int l = n % 16;
if (t > 0)
s += func(t);
if (l < 10)
s += (l + '0');
else
s += ('A' + l - 10);
return s;
}
void solve(){
int n;
cin >> n;
string ss = func(n);
int sum = 0;
for (int i = 0; i < ss.size();i++){
if(ss[i]=='0'||ss[i]=='4'||ss[i]=='6'||ss[i]=='9'||ss[i]=='A'||ss[i]=='D'){
sum += 1;
}else if(ss[i]=='8'||ss[i]=='B'){
sum += 2;
}
}
cout << sum;
}
int main(){
solve();
return 0;
}
4377. 农田灌溉
1.【题目描述】
输入样例：
3
5 1
3
3 3
1 2 3
4 1
1
输出样例：
3
1
4
2.【题解】
暴力按题意模拟，找到最大的距离
ans=max(两喷嘴之间的最大值，靠边喷嘴距边的最大值）
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int,int> pii;
const int inf=0x3f3f3f3f;
const int maxn=1e6+5;
void solve(){
int n, k;
cin >> n >> k;
int sa[205] = {0};
int llen,rlen;
for (int i = 0; i < k;i++){
int x;
cin >> x;
if(i==0)llen=x;
if(i==k-1)rlen=n-x+1;
sa[x] = 1;
}
sa[0] = 1;
sa[n+1] = 1;
int maxx = -1;
int l, r;
for (int i = 0; i <= n+1;i++){
if(sa[i]){
int cnt = 0;
for (int j = i + 1; j <= n+1;j++){
if(sa[j]){
cnt = j - i;
if(maxx<cnt){
l = i;
r = j;
maxx = cnt;
}
break;
}
}
}
}
//cout << l << " " << r << " " << maxx<<endl;
int m=max(llen,rlen);//靠边喷嘴距边的最大值
if(ceil(maxx/2+0.5)>m){
m=ceil(maxx/2+0.5);//两喷嘴之间的最大值
}
if(n==k){
cout << 1 << endl;
}else if(l==1&&r==n){
cout << m << endl;
}else if (r==n+1||l==0){
cout << maxx << endl;
}else{
cout << m << endl;
}
}
int main(){
ios::sync_with_stdio(0);
int t;
cin>>t;
while(t--)
solve();
return 0;
}
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int,int> pii;
const int inf=0x3f3f3f3f;
const int maxn=1e6+5;
void solve(){
int n, k;
cin >> n >> k;
q[0] = 1;
for (int i = 1; i < k + 1;i++)
cin >> q[i];
int res = q[1] - q[0] + 1;
for (int i = 2; i < k + 1;i++)
res = max(res, (q[i] - q[i - 1]) / 2 + 1);
res = max(res, n - q[k] + 1);
cout << res << endl;
}
int main(){
ios::sync_with_stdio(0);
int t;
cin>>t;
while(t--)
solve();
return 0;
}
4378. 选取数对
1.【题目描述】
输入样例1：
5 2 1
1 2 3 4 5
输出样例1：
9
输入样例2：
7 1 3
2 10 7 18 5 33 0
输出样例2：
61
2.【题解】
前缀和+01背包
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int,int> pii;
const int inf=0x3f3f3f3f;
const int maxn=5020;
ll a[maxn];
ll sum[maxn], f[maxn][maxn];
int main(){
int n, m, k;
cin >> n >> m >> k;
for (int i = 1; i <= n;i++) cin >> a[i];
for (int i = 1; i <= m;i++) sum[1] += a[i];
for (int i = 2; i + m - 1 <= n;i++)
sum[i] = sum[i-1] - a[i-1] + a[i+m-1];
for (int i = 1; i + m - 1 <= n;i++)
for (int j = 0; j <= k;j++){
f[i][j] = f[i-1][j];
if (i >= m && j >= 1){
f[i][j] = max(f[i][j], f[i-m][j-1] + sum[i]);
}else if(j>=1){
f[i][j] = max(f[i][j], sum[i]);
}
}
cout << f[n-m+1][k] << endl;
}