专栏文章

8.27下午

kkamikuQAQ
个人记录参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@mio3t5jm
此快照首次捕获于
2025/12/02 12:54
3 个月前
此快照最后确认于
2025/12/02 12:54
3 个月前
查看原文

T1

签到题，简单dp，我的做法是三重循环一重循环天数，一重循环当天选择完成的任务，一重枚举上次可能做过的任务，然后用二维dp来存储每i天选择了第j个任务 状态转移方程：
CPP
if(j!=k) {
  dp[i][j]=max(dp[i][j],dp[i-1][k]+a[i][j]);
}
最后边算边求最大值就行
CPP
#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e5+7;
int a[maxn][3];
int dp[maxn][3];
int main() {
	int n;
	cin>>n;
	for(int i=1;i<=n;i++) {
		for(int j=0;j<3;j++) {
			cin>>a[i][j];
		}
	}
	int maxx=0;
	for(int i=1;i<=n;i++) {
		for(int j=0;j<3;j++) {
			for(int k=0;k<3;k++) {
				if(j!=k) {
					dp[i][j]=max(dp[i][j],dp[i-1][k]+a[i][j]);
				}
				maxx=max(maxx,dp[i][j]);
			}
		}
	}
	cout<<maxx;
	return 0;
}

T2

首先用一个队列存储原来的排序序列，然后因为栈有先进后出的特性，所以用栈来存储插队的人，然后弹出栈内东西加入新的存储答案的队列，标记进入过队列元素，最后将原本没有插队的放入存储答案的队列就行
CPP
#include<bits/stdc++.h>
using namespace std;
stack<int>op;
queue<int>Q;
queue<int>ans;
const int maxn = 1e5+7;
int vis[maxn];
int main() {
	int n,m;
	cin>>n>>m;
	for(int i=1;i<=n;i++) {
		Q.push(i);
	}
	for(int i=1;i<=m;i++) {
		int a;
		cin>>a;
		op.push(a);
	}
	while(!op.empty()) {
		vis[op.top()]++;
		if(vis[op.top()]==1)
			ans.push(op.top());
		op.pop();
	}
	while(!Q.empty()) {
		if(vis[Q.front()]<1) {
			vis[Q.front()]++;
			ans.push(Q.front());
		}
		Q.pop();
	}
	while(!ans.empty()) {
		cout<<ans.front()<<'\n';
		ans.pop();
	}
	return 0;
}

T3

获得了k瓶汽水，说明在获得k瓶汽水之前，会有k-1个积分，可以兑换 ⌊(k−1)/p⌋\lfloor (k-1)/p \rfloor瓶汽水，然后通过画图，我们可以发现除了第一次兑换，后面要兑换一瓶汽水只要买(p-1)瓶汽水，也就是说可以凑出（k-1)/p组，每一组获得p瓶汽水要买(p-1)汽水，然后将总汽水数−1−⌊((k−1)/p)⌋∗p总汽水数-1- \lfloor ((k-1)/p) \rfloor*p(就是不能凑成一组的汽水)加上就行
公式：
CPP
int num=(k-1)/p;
		cout<<1+num*(p-1)+k-1-num*(p)<<'\n';

T4

本题可以通过后面的减所以不能使用dp因为没有后效性
正解由于乘法运算可以达到log级别，但存在大量重复状态，于是我们可以使用记忆化搜索去除重复状态，然后让是2，3，5倍数的数可以直接从它除以2，3，5的因子达到然后再求最小值，而对于有余数的数，对于每一个数，我们都有两种方式
x - x%3的方式-x%3个1
x+3-x%3的方式+3-x%3个1 后面如法炮制即可
CPP
#include<bits/stdc++.h>
using namespace std;
#define int unsigned long long
const int maxn = 1e18;
map<int,int>mp;
int n,a,b,c,d;
int dfs(int x) {
	if (mp.count(x)) {
		return mp[x];
	}
	int ans = x * d;
	if (x % 2) {
		ans = min(ans, min(dfs((x - x % 2) / 2), dfs((x + 2 - x % 2) / 2)) + a + d);
	} else {
		ans = min(ans, dfs(x / 2) + a);
	}
	if (x % 3) {
		ans = min(ans, min(dfs((x - x % 3) / 3) + (x % 3) * d, dfs((x + 3 - x % 3) / 3) + (3 - x % 3) * d) + b);
	} else {
		ans = min(ans, dfs(x / 3) + b);
	}

	if (x % 5) {
		ans = min(ans, min(dfs((x - x % 5) / 5) + (x % 5) * d, dfs((x + 5 - x % 5) / 5) + (5 - x % 5) * d) + c);
	} else {
		ans = min(ans, dfs(x / 5) + c);
	}
	mp[x] = ans;
	return ans;
}
signed main() {
	int t;
	cin>>t;
	while(t--) {
		cin>>n>>a>>b>>c>>d;
		mp.clear();
		mp[0]=0;
		mp[1]=d;
		cout<<dfs(n)<<'\n';
	}
	return 0;
}

T5

40pts

直接暴力枚举每一个区间算中间数

80pts

注意到当一个区间内大于x的数-小于x的数>=0，说明有中位数>=x，所以用前缀和来求出每个区间≥x的数的数量就行
CPP
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int maxn = 1e5+7;
int a[maxn],sum[maxn];
int n,x;
signed main() {
	cin>>n>>x;
	for(int i=1;i<=n;i++) {
		cin>>a[i];
		if(a[i]>=x) {
			a[i]=1;
		} else {
			a[i]=-1;
		}
		sum[i]=sum[i-1]+a[i];
	}
	int ans=0;
	for(int l=1;l<=n;l++) {
		for(int r=l;r<=n;r++) {
			if(sum[r]-sum[l-1]>=0) {
				ans++;
			}
		}
	}
	cout<<ans<<'\n';
	return 0;
}

100pts

基于80pts做法，可以得出sum[r]>=sum[l-1];
此时发现问题可以转化成二维偏序的问题，所以可以用值域树状数组首先枚举r,然后找到<=其值的sum[l-1]的范围
要注意的是：
1：0<=l-1<=n-1,所以别忘记+0 2：有负数的情况，所以要增加一个偏移量
3：lowbit处理0会死循环，所以要让数位偏移
CPP
#include<bits/stdc++.h>
using namespace std;
#define int unsigned long long
const int maxn = 1e18;
map<int,int>mp;
int n,a,b,c,d;
int dfs(int x) {
	if (mp.count(x)) {
		return mp[x];
	}
	int ans = x * d;
	if (x % 2) {
		ans = min(ans, min(dfs((x - x % 2) / 2), dfs((x + 2 - x % 2) / 2)) + a + d);
	} else {
		ans = min(ans, dfs(x / 2) + a);
	}
	if (x % 3) {
		ans = min(ans, min(dfs((x - x % 3) / 3) + (x % 3) * d, dfs((x + 3 - x % 3) / 3) + (3 - x % 3) * d) + b);
	} else {
		ans = min(ans, dfs(x / 3) + b);
	}

	if (x % 5) {
		ans = min(ans, min(dfs((x - x % 5) / 5) + (x % 5) * d, dfs((x + 5 - x % 5) / 5) + (5 - x % 5) * d) + c);
	} else {
		ans = min(ans, dfs(x / 5) + c);
	}
	mp[x] = ans;
	return ans;
}
signed main() {
	int t;
	cin>>t;
	while(t--) {
		cin>>n>>a>>b>>c>>d;
		mp.clear();
		mp[0]=0;
		mp[1]=d;
		cout<<dfs(n)<<'\n';
	}
	return 0;
}

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...