前三个题的代码都是考完复盘的 最后一个题是当时写的
A.给定n个猴子 每个猴子有个食量，每个猴子轮流拿香蕉，要求拿的数量为min(remain/2,eat*2)且该数量>eat，其中remain是当前剩余食物数量，eat是食量。最后一个猴子可以全部拿走，求最小的食物数量使得每个人都能吃饱。
1<=n<=200
题解：考虑到这个食物数量肯定是单调的，那么二分答案即可。
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <unordered_map>
#include <vector>
#define fir first
#define se second
#define ll long long
#define pb push_back
#define mp make_pair
#define ull unsigned long long
#define cl(a, b) memset(a, b, sizeof(a))
#define quickio(a) ios::sync_with_stdio(a)
#define datatest() freopen("data.in", "r", stdin)
#define makeans() freopen("data.out", "w", stdout)
#define makedata() freopen("data.in", "w", stdout)
#define pii pair<int, int>
#define pll pair<ll, ll>
#define pdd pair<double, double>
using namespace std;
const int maxn = 1e6 + 10;
const int maxm = 1e6 + 10;
const int inf = 0x3f3f3f3f;
const ll mod = 1e9 + 7;
const int maxblock = sqrt(maxn) + 10;
const double eps = 1e-7;
const ll INF = 1e16;
vector<int> v;
int a;
int check(int mid) {
for (int i = 0; i + 1 < v.size(); i++) {
int num = min(mid / 2, v[i] * 2);
if (num < v[i]) return 0;
mid -= num;
}
if (mid < v.back()) return 0;
return 1;
}
int main() {
while (cin >> a) {
v.pb(a);
}
int l = 1, r = 1e9 + 7;
while (l < r) {
int mid = (l + r) >> 1;
if (check(mid)) {
r = mid;
} else {
l = mid + 1;
}
}
printf("%d\n", l);
return 0;
} B.给定一个长度为n的序列，选出一段和最大且长度不超过M的子数组
1<=n<=1e5, -100<=a[i]<=100,1<=m<=n
题解：枚举子数组的右端点，可以用线段树查询出能取的左端点的前缀和最小值，更新答案即可
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <unordered_map>
#include <vector>
#define fir first
#define se second
#define ll long long
#define pb push_back
#define mp make_pair
#define ull unsigned long long
#define cl(a, b) memset(a, b, sizeof(a))
#define quickio(a) ios::sync_with_stdio(a)
#define datatest() freopen("data.in", "r", stdin)
#define makeans() freopen("data.out", "w", stdout)
#define makedata() freopen("data.in", "w", stdout)
#define pii pair<int, int>
#define pll pair<ll, ll>
#define pdd pair<double, double>
using namespace std;
const int maxn = 1e6 + 10;
const int maxm = 1e6 + 10;
const int inf = 0x3f3f3f3f;
const ll mod = 1e9 + 7;
const int maxblock = sqrt(maxn) + 10;
const double eps = 1e-7;
const ll INF = 1e16;
int n, m;
int a[100010];
int sum[100010];
int tree[100010 << 4];
void build(int rt, int l, int r) {
if (l == r) {
tree[rt] = sum[l - 1];
return;
}
int mid = (l + r) >> 1;
build(rt << 1, l, mid);
build(rt << 1 | 1, mid + 1, r);
tree[rt] = min(tree[rt << 1], tree[rt << 1 | 1]);
}
int query(int rt, int l, int r, int L, int R) {
if (l >= L && r <= R) return tree[rt];
int res = 1e9 + 7;
int mid = (l + r) >> 1;
if (L <= mid) {
res = min(res, query(rt << 1, l, mid, L, R));
}
if (R >= mid + 1) {
res = min(res, query(rt << 1 | 1, mid + 1, r, L, R));
}
return res;
}
int main() {
scanf("%d %d", &n, &m);
for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
sum[0] = 0;
for (int i = 1; i <= n; i++) sum[i] = sum[i - 1] + a[i];
build(1, 1, n + 1);
int Max = 0;
for (int i = 1; i <= n; i++) {
int qu = query(1, 1, n + 1, max(1, i - m + 1), i);
Max = max(Max, sum[i] - qu);
}
printf("%d\n", Max);
return 0;
} C：现在给你一个空字符串s，给定三个操作：
1.倍增s，花费为a
2.末尾添加一个A,花费为b
3.末尾去掉一个A,花费为b
问要让序列为n个A的时候的最小花费
1<=n<=1e18,1<=a,b<=1e9
题解：从最终的状态往前dp，若当前为偶数，肯定是切成一半，若当前为奇数，要么是去掉一个，要么是补上一个然后再切成两半，用map记忆化就可以了
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <unordered_map>
#include <vector>
#define fir first
#define se second
#define ll long long
#define pb push_back
#define mp make_pair
#define ull unsigned long long
#define cl(a, b) memset(a, b, sizeof(a))
#define quickio(a) ios::sync_with_stdio(a)
#define datatest() freopen("data.in", "r", stdin)
#define makeans() freopen("data.out", "w", stdout)
#define makedata() freopen("data.in", "w", stdout)
#define pii pair<int, int>
#define pll pair<ll, ll>
#define pdd pair<double, double>
using namespace std;
const int maxn = 1e6 + 10;
const int maxm = 1e6 + 10;
const int inf = 0x3f3f3f3f;
const ll mod = 1e9 + 7;
const int maxblock = sqrt(maxn) + 10;
const double eps = 1e-7;
const ll INF = 1e16;
map<ll, ll> dp;
ll n, a, b;
ll dfs(ll n) {
if (n == 0) return 0;
if (n == 1) return b;
if (n == 2) return min(a + b, b + b);
if (dp.count(n)) return dp.find(n)->second;
if (n % 2 == 0) {
ll res = 1e18;
if ((1.0 * a) / b > n / 2) {
res = min(res, dfs(n / 2) + b * n / 2);
} else {
res = min(res, dfs(n / 2) + a);
}
return dp[n] = res;
} else {
ll res = 1e18;
res = min(res, dfs(n - 1) + b);
res = min(res, dfs((n + 1) / 2) + b + a);
return dp[n] = res;
}
}
int main() {
scanf("%lld %lld %lld", &n, &a, &b);
printf("%lld\n", dfs(n));
return 0;
} D:给你一个字符串S跟一个长度为2的字符串T,一次操作可以更改S里的一个字母，问在不超过k次操作的前提下，S中与T相同的子序列最多。
1<=strlen(S)<=200,1<=k<=strlen(S)
题解：dp(i,j,l）表示S的前i个字母改了j个，且有l个T[1]的最大子序列数 状态转移即可
#include <cstdio>
#include <vector>
#include <iostream>
#include <cassert>
#include <map>
using namespace std;
int n,k;
char s[210];
char t[10];
//前i个,改了j次，有k个t[1]
int dp[220][220][220];
int vis[220][220][220];
int main(){
scanf("%d %d",&n,&k);
scanf("%s",s+1);
scanf("%s",t+1);
for (int i=0;i<=n;i++){
for (int j=0;j<=k+1;j++){
for (int l=0;l<=n;l++) dp[i][j][l]=0;
}
}
vis[0][0][0]=1;
for (int i=1;i<=n;i++){
for (int j=0;j<=k;j++){
for (int l=0;l<=i;l++){
if (!vis[i-1][j][l]) continue;
//不改
if (s[i]==t[1]&&s[i]!=t[2]){
dp[i][j][l+1]=max(dp[i][j][l+1],dp[i-1][j][l]);
vis[i][j][l+1]=1;
}
else if (s[i]==t[1]&&s[i]==t[2]){
dp[i][j][l+1]=max(dp[i][j][l+1],dp[i-1][j][l]+l);
vis[i][j][l+1]=1;
}
else if (s[i]!=t[1]&&s[i]==t[2]){
dp[i][j][l]=max(dp[i][j][l],dp[i-1][j][l]+l);
vis[i][j][l]=1;
}
else{
dp[i][j][l]=max(dp[i][j][l],dp[i-1][j][l]);
vis[i][j][l]=1;
}
//改
if (t[1]==t[2]){
if (s[i]==t[1]) continue;
//改成t[1]
dp[i][j+1][l+1]=max(dp[i][j+1][l+1],dp[i-1][j][l]+l);
vis[i][j+1][l+1]=1;
}
else{
//改成t[1]
if (s[i]!=t[1]){
dp[i][j+1][l+1]=max(dp[i][j+1][l+1],dp[i-1][j][l]);
vis[i][j+1][l+1]=1;
}
//改成t[2]
if (s[i]!=t[2]){
dp[i][j+1][l]=max(dp[i][j+1][l],dp[i-1][j][l]+l);
vis[i][j+1][l]=1;
}
}
}
}
}
int Max = 0;
for (int j=0;j<=k;j++){
for (int l=0;l<=n;l++) Max = max(Max,dp[n][j][l]);
}
printf("%d\n",Max);
return 0;
} 
全部评论
(21) 回帖