202209第27次
视频题解（暂无）
暂无
第 1 题 如此编码
题目链接: 如此编码
TAG: 贪心
思路:
由题目描述易知数组c是数组a的前缀积数组，而m是对每个c[i]分别乘上一个系数的和，题目要求每个c[i]前面的系数。
由于a[i]>0，则可知其前缀积数组是非单调递减的，那么我们不妨贪心地来考虑：从后向前c[i]是单调递增的，那么我们优先选择靠后的c[i]的系数，使其尽可能大。因为前缀积的某些性质保证了这样做是一定有解的（在题目保证有解的前提下，具体证明略）。
代码:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25 | #include<bits/stdc++.h>
using namespace std;
int main(){
int n,m;
cin>>n>>m;
vector<int> a(n+1),c(n+1);
c[0]=1; // 初始化
for(int i=1;i<=n;i++){
cin>>a[i]; // 读入原数组a[]
c[i]=c[i-1]*a[i]; // 求前缀积
}
stack<int> stk; // stk用于存系数，由于我们选系数是从后往前，输出是从前往后，所以用栈来存系数
for(int i=n-1;~i;i--){ // ~i的写法与i!=-1等价
int tmp=m/c[i]; // tmp即为能够选择的最大系数
stk.push(tmp); // 压入栈中
m-=tmp*c[i]; // 将m减去最大系数*当前前缀积
}
while(!stk.empty()){ // 遍历栈
int tt=stk.top(); // 获取栈顶元素值
stk.pop(); // 弹出栈顶元素
cout<<tt<<" "; // 输出栈顶元素
}
return 0;
}
|
第 2 题 何以包邮？
题目链接: 何以包邮？
TAG: DP 01背包
思路:
典型的01背包问题（有n个物品和一个能装物体总重量不超过m的背包，每个物品都需要占用一定的空间，且具有一定的价值，问背包能装的物品的最大价值）
在这题中，x是背包能装的重量，书的重量和价值均为a[i]，跑一遍01背包，然后从头遍历一遍，找到第一个重量大于x的价值，即为答案
下面代码中关于01背包求解的部分看不懂的话可以去oi-wiki这个网站上学一学：https://oi-wiki.org/dp/knapsack/#0-1-%E8%83%8C%E5%8C%85
代码:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23 | #include<bits/stdc++.h>
using namespace std;
int main(){
int n,m;
cin>>n>>m;
vector<int> a(n),f(300010); // f[i]表示重量不超过i能选择的最大价值，因为这题中背包最大重量等于最大价格，为书的最大数量*书的最大价格：30*10000=300000
for(int i=0;i<n;i++){
cin>>a[i];
}
for(int i=0;i<n;i++){ // 01背包模板
for(int j=300000;j>=a[i];j--){
f[j]=max(f[j],f[j-a[i]]+a[i]); // 状态转移
}
}
for(int i=m;i<=300000;i++){ // 遍历每一个重量，因为数据范围很小，所以直接枚举即可，若数据范围较大可考虑二分查找
if(f[i]>=m){ // 如果价值超过m
cout<<f[i]; // 输出价值
return 0; // 输出后直接结束程序即可
}
}
return 0;
}
|
第 3 题 防疫大数据
题目链接: 防疫大数据
TAG: 大模拟 STL
思路:
不算太复杂的大模拟吧，把要存的信息和题目中各个条件搞清楚就行了，具体见注释
代码:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62 | #include<bits/stdc++.h>
using namespace std;
struct Node{ // 用于表示用户
int d,u,r; // 用户u在第d天访问了地区r
};
map<int,bool> risk[1010]; // risk[i][j]表示第i天时地区j是否为风险地区
vector<set<int>> ans(1010); // ans[i]存储第i天的风险用户，即答案（set自带去重和排序）
vector<Node> member[1010]; // member[i][j]表示第i天时的第j条漫游数据
int main(){
int n;
cin>>n;
for(int i=0;i<n;i++){
int reg,mem; // reg为风险地区数，mem为漫游数据数
cin>>reg>>mem;
while(reg--){ // 读入当天的每个风险地区
int tmp;
cin>>tmp; // 风险地区
for(int j=i;j<=i+6;j++){ // 该地区往后连续7天都是风险地区
risk[j][tmp]=true;
}
}
while(mem--){ // 读入当天的每个漫游数据
int d,u,r;
cin>>d>>u>>r;
member[i].push_back({d,u,r});
}
}
for(int i=0;i<n;i++){ // 处理所有的漫游数据
int num=member[i].size(); // num为第i天的漫游数据
for(int k=0;k<num;k++){
int d=member[i][k].d,u=member[i][k].u,r=member[i][k].r; // 从member中取出漫游数据
if(d<0||i-d>6)continue; // d<0用于去除负天数（从题目中可以知道负天数一定不存在风险问题），i-d>6用于去除超过7天的记录
bool ok=true; // ok表示是否存在风险，默认存在
for(int j=d;j<=i;j++){ // 从发生风险的时间一直循环到今天
if(risk[j][r]==false){ // 若其中有一天不是风险地区
ok=false; // 则不存在风险
break; // 结束训练
}
}
if(ok){ // 若存在风险
for(int j=i;j<=d+6;j++){ // 往后遍历7天
if(risk[j][r]){ // 如果第j天时地区r是风险地区
ans[j].insert(u); // 则第j天的风险用户加上u
}else{ // 否则
break; // 直接结束循环（碰到第一个断开的就结束，不能继续找）
}
}
}
}
}
for(int i=0;i<n;i++){ // 遍历i天
cout<<i;
for(auto &e:ans[i]){ // 遍历第i天的风险用户
cout<<" "<<e;
}
cout<<"\n";
}
return 0;
}
|
第 4 题 吉祥物投票
题目链接: 吉祥物投票
TAG: 暂无
思路:
暂无
代码:
第 5 题 高维亚空间超频物质变压缩技术
题目链接: 高维亚空间超频物质变压缩技术
TAG: 暂无
思路:
暂无
代码:
最后更新:
2022-12-19 10:18:04