2019 CSP-J
P5660 数字游戏（语法）
题意
给定一个长度最大为 \(8\) 的01字符串，求字符串中有多少个 \(1\)。
题解
#include<bits/stdc++.h>
using namespace std;
/*====================*/
#define endl "\n"
/*====================*/
typedef long long lnt;
/*====================*/
void Solve(void)
{
string str;
cin >> str;
int ans = 0;
for (auto c : str)
{
if (c == '1')
{
ans++;
}
}
cout << ans << endl;
}
/*====================*/
int main()
{
#ifndef ONLINE_JUDGE
freopen("IN.txt", "r+", stdin);
#endif
ios::sync_with_stdio(false);
cin.tie(NULL), cout.tie(NULL);
int T = 1; //cin >> T;
while (T--)Solve();
return 0;
}
P5661 公交换乘（模拟，STL）
题意
搭乘一次地铁后可以获得一张优惠票，有效期为 \(45\) 分钟，在有效期内（即：\(t_{bus} - t_{subway} \leq 45\)）可以消耗这张优惠票，免费搭乘一次票价不超过地铁票价的公交车。
搭乘公交车时，如果可以使用优惠票一定会使用优惠票；如果有多张优惠票满足条件，则优先消耗获得最早的优惠票。
现给出交通出行记录，计算花费。
数据规模与约定
对于 \(100\%\) 的数据，\(n \leq 10^5\)，\(t_i \leq 10^9\)，\(1 \leq price_i \leq 1000\)。
题解
将乘车记录按时间排序（本题已经有序）。
遍历乘车记录，边遍历边维护当前时间还有效的优惠票。因为有效期最大为 \(45\) 分钟，而数据保证不存在两次乘车记录时间相同，所以当前还有效的优惠票最多 \(45\) 张。
从有效的优惠票中查找是否有能够使用的优惠票，如果有，就删去该优惠票，否则计入答案。
总结一下对有效优惠票的维护需要支持的操作：
- 以时间为关键字有序。
- 查找时间最早的，满足条件的优惠票。
- 删除优惠票。
我们使用 set 维护即可。
如果本题数据范围改成 \(t_i \leq 10^{18}\)，有效期为 \(10^5\) 分钟，该怎么做？
上面做法时间复杂度是正确的原因是最多有 \(45\) 张优惠票。现在增强后最多有 \(10^5\) 张优惠票，遍历查找会 TLE。
所以我们只需要优化查找过程就可以。使用平衡树，线段树等数据结构代替 set 维护优惠票即可。
#include<bits/stdc++.h>
using namespace std;
/*====================*/
#define endl "\n"
/*====================*/
typedef long long lnt;
/*====================*/
const int N = 1e5 + 10;
/*====================*/
int n;
/*====================*/
struct Record
{
int transportation;
int price;
int t;
Record(int _transportation = 0, int _price = 0, int _t = 0)
{
transportation = _transportation;
price = _price;
t = _t;
}
friend bool operator<(const Record& a, const Record& b)
{
return a.t < b.t;
}
};
Record record[N];
/*====================*/
void Solve(void)
{
do
{
cin >> n;
for (int i = 1; i <= n; ++i)
{
int transportation; cin >> transportation;
int price; cin >> price;
int t; cin >> t;
record[i] = Record(transportation, price, t);
}
} while (false);//读入
do
{
int ans = 0;
set<Record>lib;//优惠票
for (int i = 1; i <= n; ++i)
{
if (record[i].transportation == 0)//地铁
{
ans += record[i].price;
lib.insert(record[i]);
}
if (record[i].transportation == 1)//公交车
{
//清除过期票
while (!lib.empty() && record[i].t - lib.begin()->t > 45)
{
lib.erase(lib.begin());
}
//寻找最早有效票
bool flag = false;//默认没有使用票
for (auto it = lib.begin(); it != lib.end(); ++it)
{
if (record[i].price <= it->price)
{
flag = true;
lib.erase(it);
break;
}
}
//更新答案
if (!flag)
{
ans += record[i].price;
}
}
}
cout << ans << endl;
} while (false);//模拟
}
/*====================*/
int main()
{
#ifndef ONLINE_JUDGE
freopen("IN.txt", "r+", stdin);
#endif
ios::sync_with_stdio(false);
cin.tie(NULL), cout.tie(NULL);
int T = 1; //cin >> T;
while (T--)Solve();
return 0;
}
P5662 纪念品（dp，滚动数组）
题意
给定未来 \(T\) 天 \(N\) 种物品每天买入与卖出的价格。
每天对于每种物品可以买入与卖出无限次。
每天卖出物品换回的金币可以当日用于买入物品。
每天买入的物品可以当日用于卖出换回金币。
第 \(T\) 天卖出所有物品换回金币。
求第 \(T\) 天能获得的最大金币数量。
数据规模与约定
对于 \(100\%\) 的数据，\(T \leq 100, N \leq 100, M \leq 10^3\)，所有价格 \(1 \leq P_{i,j} \leq 10^4\)。
数据保证任意时刻，持有的金币数不超过 \(10^4\)。
题解
首先，直觉经验告诉我们这题很可能是 dp，那我们不妨考虑一下到底是不是 dp。
我们发现，每天的交易其实是前一天和当前天转移的过程，而前一天的状态确定的时候，我们不在乎更前的天数是怎么操作的。
有了最优子结构，有了转移，就有了 dp。现在我们思考状态怎么设计。
如果把每种货物的数量都放到状态里，时间和空间都无法承受，因为货物的组合是乘法原理。
我们发现，当前天可以卖出再买入，也可以买入再卖出。所以我们可以把前一天剩下的货物，在当前天全部卖出变现。而如果这一天需要再买一些货物留到之后的天数去卖，我们可以直接买。因为卖出和买入的价格是一致的，不会发生亏损。
于是我们不需要具体记录每种货物到底各有多少个，我们只需要记录前一天到底最多能给我多少钱就可以。
而每一种货物的数量和其他种货物的数量无关，只和我今天花了多少钱买货物有关。
于是我们可以设计出状态 \(dp_{i,j,k}\)，在第 \(i\) 天，一共花了 \(k\) 元买前 \(j\) 种货物，能在第 \(i+1\) 天卖出多少钱。
那么考虑转移，第 \(j\) 种货物有买和不卖两种决策。
\(dp_{i,j,k}=max\begin{cases}dp_{i,j-1,k}&不买第j种货物\\dp_{i,j,k-price_{i,j}}+(price_{i+1,j}-price_{i,j})&买第j种货物，多花了price_{i,j}元，第{i+1}天多赚了(price_{i+1,j}-price_{i,j})元\end{cases}\)
然后我们发现第一维天数可以优化掉，跑天数轮就可以。
于是状态变成 \(dp_{i,j}\) ，当前天花了 \(j\) 元钱买前 \(i\) 种物品，第二天全部卖出能赚的最大钱数。
\(dp_{i,j}=max\begin{cases}dp_{i-1,j}&不买第i种货物\\dp_{j,k-price_{today,i}}+差价&买第i种货物\end{cases}\)
然后我们发现这个是完全背包的转移式，把第一维前 \(i\) 种货物也给滚动掉。最终就是跑若干天完全背包。详见代码。
思考一下，dp 的初值是什么？
#include<bits/stdc++.h>
using namespace std;
/*====================*/
#define endl "\n"
/*====================*/
typedef long long lnt;
/*====================*/
const int D = 1e2 + 10;
const int N = 1e2 + 10;
const int V = 1e4 + 10;
/*====================*/
int d, n, m;
int price[D][N];
int dp[V];
/*====================*/
void Solve(void)
{
do
{
cin >> d >> n >> m;
for (int i = 1; i <= d; ++i)
{
for (int j = 1; j <= n; ++j)
{
cin >> price[i][j];
}
}
} while (false);//读入
do
{
for (int day = 1; day < d; ++day)
{
dp[0] = m;
//memset(dp, 0, sizeof(dp));
//这句话可以删除，因为dp压缩掉一维后求的是最大值。
//而最大值单调不减，所以初始值为0和初始值为原先的最大值并没有影响。
//因为dp过程中最大值只会更大，不会更小，所以只要初始值转移是对的即可。
int maxmoney = m;
for (int i = 1; i <= n; ++i)
{
for (int j = price[day][i]; j <= m; ++j)
{
maxmoney = max(maxmoney, dp[j] = max(dp[j], dp[j - price[day][i]] + price[day + 1][i] - price[day][i]));
}
}
m = maxmoney;
}
cout << m << endl;
} while (false);//dp
}
/*====================*/
int main()
{
#ifndef ONLINE_JUDGE
freopen("IN.txt", "r+", stdin);
#endif
ios::sync_with_stdio(false);
cin.tie(NULL), cout.tie(NULL);
int T = 1; //cin >> T;
while (T--)Solve();
return 0;
}
P5663 加工零件（最短路）
题意
工厂里有 \(n\) 位工人，工人们从 \(1 \sim n\) 编号。某些工人之间存在双向的零件传送带。保证每两名工人之间最多只存在一条传送带。
如果 \(x\) 号工人想生产一个被加工到第 \(L\,(L \gt 1)\) 阶段的零件，则所有与 \(x\) 号工人有传送带直接相连的工人，都需要生产一个被加工到第 \(L - 1\) 阶段的零件（但 \(x\) 号工人自己无需生产第 \(L - 1\) 阶段的零件）。
如果 \(x\) 号工人想生产一个被加工到第 \(1\) 阶段的零件，则所有与 \(x\) 号工人有传送带直接相连的工人，都需要为 \(x\) 号工人提供一个原材料。
轩轩是 \(1\) 号工人。现在给出 \(q\) 张工单，第 \(i\) 张工单表示编号为 \(a_i\) 的工人想生产一个第 \(L_i\) 阶段的零件。轩轩想知道对于每张工单，他是否需要给别人提供原材料。
数据规模与约定
对于 \(100\%\) 的数据，\(1 \leq n, m, q \leq 10^5\)，\(1 \leq L \leq 10^9\)。
题解
不难发现题目给了一张无向图。
考虑 \(x\) 号点到 \(1\) 号点的路径：
-
存在 \(x \rightarrow y \rightarrow ... \rightarrow 1\) 这样一条路径。
-
存在 \(x \rightarrow y \rightarrow x \rightarrow y \rightarrow ... \rightarrow 1\) 这样一条路径。
-
存在 \(x \rightarrow y \rightarrow x \rightarrow y \rightarrow x \rightarrow y \rightarrow ... \rightarrow 1\) 这样一条路径。
-
\(...\)
这说明对于 \(x\) 号点到 \(1\) 号点，所有长度为 \(dis+2*k\)，\(k\) 为任意非负整数的路径都存在。
于是我们只需要判断 \(1\) 号点到所有点的最短路是否小于等于 \(L\) 即可。
但是这样存在一个问题，那就是，所有的 \(dis+2*k\) 奇偶性和 \(dis\) 一致。
所以我们要求出最短的奇数 \(dis\) 和最短的偶数 \(dis\)。
我们求最短路的时候在状态里记录一下奇偶性即可。
#include<bits/stdc++.h>
using namespace std;
/*====================*/
#define endl "\n"
/*====================*/
typedef long long lnt;
/*====================*/
const int N = 1e5 + 10;
const int M = 1e5 + 10;
const int Q = 1e5 + 10;
/*====================*/
int n, m, q;
/*====================*/
namespace _Graph
{
struct Edge
{
int u, v;
Edge(int _u = 0, int _v = 0)
{
u = _u, v = _v;
}
int node(int x)const
{
return x == u ? v : u;
}
};
/*====================*/
int cntedge;
Edge edge[M];
vector<int>G[N];
/*====================*/
void AddEdge(int u, int v)
{
edge[++cntedge] = Edge(u, v);
G[u].push_back(cntedge);
G[v].push_back(cntedge);
}
}
/*====================*/
namespace _Dijkstra
{
using namespace _Graph;
/*====================*/
struct Unit
{
int tag, v, w;
Unit(int _tag = 0, int _v = 0, int _w = 0)
{
tag=_tag,v = _v, w = _w;
}
friend bool operator<(const Unit& a, const Unit& b)
{
return a.w > b.w;
}
};
/*====================*/
int dis[2][N]; bool vis[2][N];
/*====================*/
void Init(int s)
{
memset(dis, 0X3F, sizeof(dis));
memset(vis, false, sizeof(vis));
priority_queue<Unit>q;
q.push(Unit(0, s, dis[0][s] = 0));
while (!q.empty())
{
int cur = q.top().v, tag = q.top().tag; q.pop();
if (vis[tag][cur])continue; vis[tag][cur] = true;
for (int i = 0; i < G[cur].size(); ++i)
{
int nxt = edge[G[cur][i]].node(cur);
if (dis[tag ^ 1][nxt] > dis[tag][cur] + 1)
{
dis[tag ^ 1][nxt] = dis[tag][cur] + 1;
q.push(Unit(tag ^ 1, nxt, dis[tag ^ 1][nxt]));
}
}
}
}
}
/*====================*/
void Solve(void)
{
cin >> n >> m >> q;
for (int i = 1; i <= m; ++i)
{
int u, v; cin >> u >> v;
_Graph::AddEdge(u, v);
}
_Dijkstra::Init(1);
for (int i = 1; i <= q; ++i)
{
int a, l; cin >> a >> l;
if (_Dijkstra::dis[l % 2][a] <= l)
{
cout << "Yes" << endl;
}
else
{
cout << "No" << endl;
}
}
}
/*====================*/
int main()
{
#ifndef ONLINE_JUDGE
freopen("IN.txt", "r+", stdin);
#endif
ios::sync_with_stdio(false);
cin.tie(NULL), cout.tie(NULL);
int T = 1; //cin >> T;
while (T--)Solve();
return 0;
}