背景
2024-10-5做 \(CSP-J\) 复赛模拟,作补题报告。
成绩
- \(T1\) \(AC\)
- \(T2\) \(40\)
- \(T3\) \(0\)
- \(T4\) \(0\)
\(T1\) 牛奶 (\(milk\))
经典 \(T1\) 赛时 \(A\).
概述
要采购牛奶，有\(n\)种，每种有各自的\(a_i\)和\(b_i\)，需要\(m\)盒，求最小花销
思路
题目描述中说，作为一只学过动态规划的猫，就往 \(DP\) 方面想了想，最后还是做了贪心
其实很基础，先按价格从大到小排序，
如果 \(a_i\) 比 \(m\) 大，花费加上 \(m \times b_i\) ，
否则，花费加上 \(a_i \times b_i\) , \(m\) 减去 \(a_i\)
若\(m\leqslant 0\) ,结束计算
代码
Code
#include <cstdio>
#include <iostream>
#include <algorithm>
typedef long long ll;
using namespace std;0
const int maxn = 1e5+111;
struct node {
int sum;
ll cost;
} e[maxn];
int n,m;
ll ans;
bool cmp(node x,node y) {
return x.cost < y.cost;
}
signed main() {
// freopen("milk.in","r",stdin);
// freopen("milk.out","w",stdout);
scanf("%d%d",&n,&m);
for(int i=1; i<=n; ++i)
scanf("%d%lld",&e[i].sum,&e[i].cost);
sort(e+1,e+n+1,cmp);
for(int i=1; i<=n; ++i) {
if(m <= 0)
break;
ans += min(e[i].sum,m) * e[i].cost;
m -= e[i].sum;
}
printf("%lld",ans);
// fclose(stdin);
// fclose(stdout);
return 0;
}
\(T2\) 树组 (\(Traary\))
推规律，推出来，过样例，40分(悲
概述
有\(n\)棵树苗，在数组每个位置种上，每天过后，会增加\(1\)单位长度。
种树持续\(m\)天，你有魔法，在每天早上，有\(3\)种操作：
\(op = 1\) : 对树\(x\)施魔法,效果持续 \(k\)天，若之前该树就有魔法，覆盖(即取消上次，加上这次)；；
\(op = 2\) : 对树\(x\)祛魔，可能会对没有施魔法的树使用；
\(op = 3\) ：查询树\(x\)的高度。
当 \(op = 3\) 时，输出该树高度。
思路
每次操作，都对当前树进行处理，用 \(cnt\) 数组当前魔法生长阶段增加了多少
输出时加上
虽然但是 40分
代码
Code(错)
#include <cstdio>
#include <iostream>
using namespace std;
const int maxn = 2e5+9999;
int n,m,k;
int cnt[maxn];//记录操作该树之前总共额外加了多少
pair <int,int> p[maxn];//记录每次使用魔法的初始时间和结束时间
int tag[maxn];//标记上次操作节点
signed main() {
// freopen("traary.in","r",stdin);
// freopen("traary.out","w",stdout);
scanf("%d%d%d",&n,&m,&k);
for(int i=1; i<=m; ++i) {
int op,x;
scanf("%d%d",&op,&x);
if(op == 1) {
if(p[x].first != 0 && p[x].second != 0) {
//玄学记录
cnt[x] += min(i,p[x].second+1)-max(p[x].first,tag[x]);
//打标记
tag[x] = i;
}
p[x].first = i;
p[x].second = k + i - 1;
} else if(op == 2) {
if(p[x].first != 0 && p[x].second != 0) {
cnt[x] += min(i,p[x].second+1)-max(p[x].first,tag[x]);
tag[x] = i;
}
p[x].first = 0;
p[x].second = 0;
} else if(op == 3) {
if(p[x].first != 0 && p[x].second != 0) {
cnt[x] += min(i,p[x].second+1)-max(p[x].first,tag[x]);
tag[x] = i;
}
printf("%d\n",i-1+cnt[x]);
}
}
// fclose(stdin);
// fclose(stdout);
return 0;
}
正解
也是我的思路
但是代码是对的 ：）
代码
对
#include <cstdio>
#include <vector>
#include <cstring>
using namespace std;
const int maxn = 1e5+1111;
int n,m,k;
int a[maxn];
vector <pair<int,int> >v[maxn];
int ans[maxn];
int main(){
memset(ans,-1,sizeof(ans));
scanf("%d%d%d",&n,&m,&k);
for(int i=1;i<=m;++i){
int op,x;
scanf("%d%d",&op,&x);
v[x].push_back({op,i});
}
for(int i=1;i<=n;++i){
int tag = -1;
int add = 0;
for(int j=0;j<v[i].size();++j){
int x = v[i][j].first;
int y = v[i][j].second;
if(x==1){
if(tag > 0) add += min(y-tag,k);
tag = y;
}else if(x==2){
if(tag > 0) add += min(y-tag,k);
tag = -1;
}else{
ans[y] = y - 1 + add + (tag > 0 ? min(y-tag,k) : 0);
}
}
}
for(int i=1;i<=m;++i)
if(ans[i] >= 0) printf("%d\n",ans[i]);
return 0;
}
\(T3\) 智乃的兔子(\(usagi\))
\(0\)
概述
有 \(n\) 只兔子，他们有可爱值 \(a_i\) 和祝福值 \(b_i\)，
如果祝福值超过 \(H\),就会被吃！
求，怎么挑选兔子，是可爱值和为\(7\)的倍数可爱和最大还不会被吃掉
正解
\(01\) 背包+ \(k\) 约束
状态转移方程: \(f[i][j] = \max(f[i][j][k],f[i-1][j-b[i]][k-a[i]])\)
虽然但是，\([k]\)这一维没啥用，可以压了
代码
正解代码
#include <cstdio>
#include <iostream>
#define ll long long
#define maxn 1e4+111
#define maxh 1100
using namespace std;
int n,m;
int a[maxn],b[maxn];
ll t[maxn][7],f[maxh][7],g[maxh][7];
int main() {
scanf("%d%d",&n,&m);
for(int i=1; i<=n; ++i)
scanf("%d",&a[i]);
for(int i=1; i<=n; ++i)
scanf("%d",&b[i]);
if(m == 998244353) { //特判
for(int i=1; i<7; ++i)
t[0][i] = -1e18;
for(int i=1; i<=n; ++i) {
for(int j=0; j<7; ++j) {
t[i][j] = max(t[i-1][((j-a[i])%7+7)%7] + a[i],t[i-1][j]);
}
}
cout << t[n][0];
return 0;
}
for(int i=0; i<maxh; ++i) {
for(int j=0; j<7; ++j)
g[i][j] = -1e18;
}
g[0][0] = 0;
for(int i=1; i<=n; ++i) {
for(int w=0; w<=m; ++w) {
for(int j=0; j<7; ++j) {
f[w][j] = g[w][j];
if(w >= b[i])
f[w][j] = max(g[w-b[i]][((j-a[i])%7+7)%7] + a[i],f[w][j]);
}
}
swap(f,g);
}
ll ans = 0;
for(int i=0; i<=m; ++i)
ans = max(ans,g[i][0]);
cout << ans;
return 0;
}
\(T4\) 一颗成熟的奥术飞弹(\(missiles\))
\(0\)
概述
有一个连通无向图，点是\(1\)~\(n\),这个飞弹要从\(1\)飞到\(n\),求最短飞行弹道条数和最大的可能偏离数。
\(PS\) : 可能偏离数怎么算 : 在一个点上，如果有多条最短路径到达终点，则可能偏离数\(+1\)
思路
依然骗分\(0\)分。
正解
最短路计数
进行\(2\)次广搜( \(BFS\) )
第一次：记录点 \(i\) 到点 \(n\)的最短路长度
第二次：以 \(n\) 为起点，宽搜每个点，求出 \(n\) 到每个点的最短路，同时标记父亲方便计算可能偏离数。
最后求 \(1\) 到 \(n\) 的的最短路计数！
代码
Code
#include <queue>
#include <cstdio>
#include <vector>
#include <iostream>
#define ll long long
using namespace std;
const int maxn = 1e5+111;
int n,m;
queue <int> q;
bool vis[maxn];
vector <int> v;
vector <int> son[maxn];
int fa[maxn],dis[maxn],ans[maxn],cnt[maxn];
// 还是逆序记录
//经典BFS
void bfs() {
q.push(n);
vis[n] = 1;
while(!q.empty()) {
int x = q.front();
q.pop();
v.push_back(x);
for(int i=0; i<son[x].size(); ++i) {
int y = son[x][i];//y是x的邻接点
if(!vis[y]) {
vis[y] = 1;
q.push(y);
fa[y] = x;
dis[y] = dis[x] + 1; //长度+1
}
}
}
}
signed main() {
scanf("%d%d",&n,&m);
for(int i=1; i<=m; ++i) {
int x,y;
scanf("%d%d",&x,&y);
son[x].push_back(y);
son[y].push_back(x);
}
bfs(); // 先进行一次广搜，记录fa数组、记录距离数组
cnt[n] = 1; // 记录最短飞行弹道条数
for(int i=0; i<v.size(); ++i) {
bool flag=0;
int x = v[i];
for(int j=0; j<son[x].size(); ++j) {
if(dis[x] == dis[son[x][j]] + 1) {// 相邻两个点，距离也相差1，说明在最短路边上。
ans[x] = max(ans[x],ans[son[x][j]]);
cnt[x] += cnt[son[x][j]];// 所有能到son[vec[i]][j]的点都能走到vec[i]去，因此累加到vec[i]中。
cnt[x] %= 998244353;
if(son[x][j] != fa[x])// 记录时不能走回父亲点去
flag = 1;
}
}
ans[x] += flag;
}
printf("%d %d",cnt[1],ans[1]);
return 0;
}
后记
哈哈哈哈哈哈哈哈，集训结束咧！(大喜
标签：报告,int,ll,tag,maxn,补题,ans,include From： https://www.cnblogs.com/Picecone-zzs/p/18448426