前言
咕咕咕了好久，终于今天把 T3 的坑给补回来了，于是打算写一波题解。
勿吐槽码风，丑是必然的，毕竟好久前写的代码了。
T1 数字游戏
大意：给定长度为 8 的 01 串，求 1 的个数
sb 题，考察字符串基本使用，当时好像 2:30 还没到就已经切完了
考场代码：
#include <iostream>
#include <cstdio>
#include <string>
//#define LOCAL
using namespace std;
int main()
{
#ifndef LOCAL
freopen("number.in","r",stdin);
freopen("number.out","w",stdout);
#endif
string s;
cin>>s;
int ans=0;
for(int i=0;i<s.size();i++)
{
if(s[i]=='1') ans++;
}
printf("%d\n",ans);
return 0;
}
T2 公交换乘
大意：坐一次地铁可以获取一张有效期 45 分钟的优惠券，可以凭券免费坐票价不超过地铁票价的公交车，优惠票可累积，使用时优先使用最先获得的
模拟即可，这里使用 vector 模拟优惠票的队列，代码并不优美但是能过。
坑点就在于
- 使用票要使用最先获得的
- 优惠票用过要删掉
记得当时在考场上发现队列不能用之后还自己研究 vector::erase 的用法
#include <cstdio>
#include <vector>
using namespace std;
typedef long long ll;
//#define LOCAL
struct ticket{
int price;
ll time;
};
vector<ticket> q;
int main()
{
#ifndef LOCAL
freopen("transfer.in","r",stdin);
freopen("transfer.out","w",stdout);
#endif
int n;
scanf("%d",&n);
ll ans=0;
while(n--)
{
int type,price;
ll t;
scanf("%d %d %lld",&type,&price,&t);
if(type==0)//如果坐地铁
{
ans+=price;//更新答案
ticket tt={price,t};
q.push_back(tt);//插入候选队
}
else if(type==1)//如果是公交
{
while(!(q.empty())&&t-q.front().time>45) q.erase(q.begin());//先删掉超时的优惠票
bool flag=0;
for(int i=0;i<q.size();i++)//查询符合标准的第一张优惠票
{
if(q[i].price>=price)
{
q.erase(q.begin()+i);//直接删掉
flag=1;
break;
}
}
if(!flag) ans+=price;//如果不存在就需要付原价
}
}
printf("%lld\n",ans);
return 0;
}
T3 纪念品
谁叫我太菜，当时考场上骗了 10 分走人，现在看题解才写出正解。
大意：T 天，N 种纪念品，每天不同的纪念品都有不同的价格，小伟一开始有 M 金币，每天可以卖掉手中的纪念品换取金币，买进纪念品花费金币或者什么都不做。在第 T 天一定会卖出手中所有纪念品，求最高收益
分析题意，可以发现需要使用 dp，发现状态貌似很复杂，又可以买进又可以卖出，然而，注意到买进和卖出都可以进行无数次，因此我们可以把所谓一直持有的纪念品看成先将其卖出，又将其买进，效果是一样的，实质上就是每一天都做一次完全背包。
令 f_{i,j,k} 表示第 i 天，考虑前 j 种物品，手里有 k 金币时，在下一天全部卖出能达到的最大收益，则有方程
f_{i,j,k}=\max(f_{i,j,k},f_{i,j-1,k+p_i,j}+p_{i,j}-p_{i+1,j})
表示如果要了第 j 个物品，那么净收益即为 p_{i,j}-p_{i+1,j}，从 f_{i,j-1,k+p_i,j} 转移而来，利用完全背包思想压一下维度然后改循环顺序即可以达到正确结果。
（第一维的天数是可以不要的，第二维的物品也是可以用滚动数组优化掉的，保留第三维即可）
#include <cstdio>
#include <cctype>
#include <cstring>
inline int read()
{
char c = getchar();
int s = 0;
while (!isdigit(c))
c = getchar();
while (isdigit(c))
s = 10 * s + c - '0', c = getchar();
return s;
}
inline int max(int a,int b)
{
return a>b?a:b;
}
int n,t,p[105][105],f[10005];
int main()
{
t=read(),n=read();
int m=read();
for(int i=1;i<=t;i++)
for(int j=1;j<=n;j++)
p[i][j]=read();
int ans=m;
for(int i=1;i<t;i++)
{
memset(f,~0x3f,sizeof(f));//先赋负无穷
f[ans]=ans;//初始值，什么都不干的情况
for(int j=1;j<=n;j++)//枚举物品，从小到大即为完全背包
for(int k=ans;k>=p[i][j];k--)//枚举金钱
f[k-p[i][j]]=max(f[k-p[i][j]],f[k]+p[i+1][j]-p[i][j]);
int maxn=0;//统计最优答案用
for(int j=0;j<=ans;j++)
maxn=max(maxn,f[j]);
ans=maxn;
}
printf("%d\n",ans);
return 0;
}
T4 加工零件
大意：一个工厂正在生产零件，工人从 1 到 n 标号，某些工人之间有双向传送带。
如果 x 号工人想生产一个被加工到第 L (L \gt 1) 阶段的零件，则所有与 x 号工人有传送带直接相连的工人，都需要生产一个被加工到第 L – 1 阶段的零件（但 x 号工人自己无需生产第 L – 1 阶段的零件）。
如果 x 号工人想生产一个被加工到第 1 阶段的零件，则所有与 x 号工人有传送带直接相连的工人，都需要为 x 号工人提供一个原材料。
给定一些工单，即需要某工人生产某阶段的零件，求 1 号是否需要提供原材料。
先将其抽象成图论问题，以工人为节点，传送带为边来建图。
考虑暴力，虽然一定超时，但还是能给我们一些启示，不难发现暴力就是在看 a 与 1 之间是否存在长度为 L 的路径，同时我们又注意到：如果 L 为奇数，且从 1 到 a 存在一条奇数路径，且最小奇数路径长小于等于 L，那么 1 就必须提供原材料（为什么可以：你可以两个传送带之间来回跳，比如 1->2->1->2->1…，但如果最小的奇数路径大于 L，说明从 a 走 L 个阶段也轮不到 1，就不行）同样的，如果 L 为偶数，且从 1 到 a 存在一条偶数路径，且最小偶数路径长小于等于 L，那么 1 就必须提供原材料。
这就给我们了正解的方法：找到每个点距离 1 点的最小奇数路径与偶数路径即可，这一过程实现可以使用 bfs（因为我当时还没学过最短路），然后判定每一个工单的时候按照奇偶数去找最短奇偶路径是否小于等于工单给定阶段就可以判定 Yes 或 No 了
当然，我写的考场代码有一个小 bug，就是没有判断 1 点不连通的情况，然而 ccf 的数据没有这种特殊情况，所以也就 A 了这道题
考场代码：
#include <cstdio>
#include <vector>
#include <queue>
#include <cstring>
//#define LOCAL
#define inf 0x3f3f3f3f
typedef long long ll;
using namespace std;
vector<int> g[100020];//存图
bool vis0[100020],vis1[100020];//bfs用
int minans0[100020],minans1[100020];//存储奇偶最短路
struct node{
int n,time;
};
queue<node> q;
void bfs()
{
memset(minans0,inf,sizeof(minans0));
memset(minans1,inf,sizeof(minans1));
q.push((node){1,0});
while(!q.empty())
{
int curn=q.front().n;//当前的点
int nxtc=q.front().time+1;//下一个点会经过的路径长
q.pop();
for(int i=0;i<g[curn].size();i++)
{
int nxt=g[curn][i];
if(nxtc%2==0)//如果下一个点是偶数到达
{
if(vis0[nxt]==0)//如果未访问
{
vis0[nxt]=1;
q.push((node){nxt,nxtc});
minans0[nxt]=min(nxtc,minans0[nxt]);//就更新这里的结果
//cout<<"no."<<nxt<<" "<<nxtc<<endl;
}
}
if(nxtc%2==1)//反之如果是奇数，也一样
{
if(vis1[nxt]==0)
{
vis1[nxt]=1;
q.push((node){nxt,nxtc});
minans1[nxt]=min(nxtc,minans1[nxt]);
//cout<<"no."<<nxt<<" "<<nxtc<<endl;
}
}
}
}
return;
}
void add_edge(int u,int v)
{
g[u].push_back(v);//注意是无向图
g[v].push_back(u);
return;
}
int main()
{
#ifndef LOCAL
freopen("work.in","r",stdin);
freopen("work.out","w",stdout);
#endif
int n,m,q;
scanf("%d %d %d",&n,&m,&q);
while(m--)
{
int u,v;
scanf("%d %d",&u,&v);
add_edge(u,v);
}
bfs();//预处理
while(q--)
{
int a,l;
scanf("%d %d",&a,&l);
bool flag=0;
if(l%2==0&&vis0[a]==1&&minans0[a]<=l) flag=1;//如果是偶数阶段并且能到达
if(l%2==1&&vis1[a]==1&&minans1[a]<=l) flag=1;
if(flag) printf("Yes\n");
else printf("No\n");
}
return 0;
}