P9748 小苹果（模拟）
题意
\(n\) 个苹果从左到右排成一列，编号为从 \(1\) 到 \(n\)。
每天从左侧第 \(1\) 个苹果开始，每隔 \(2\) 个苹果拿走 \(1\) 个苹果。
求出多少天能拿完所有的苹果，编号为 \(n\) 的苹果是在第几天被拿走。
数据规模与约定
对于 \(100\%\) 的数据，\(1 \le n\le 10^9\)。
题解
#include<bits/stdc++.h>
using namespace std;
/*====================*/
#define endl "\n"
/*====================*/
typedef long long lnt;
/*====================*/
void Solve(void)
{
int n; cin >> n;
int ans1 = 0, ans2 = 0;
while (n != 0)
{
ans1++;
if (n % 3 == 1 && ans2 == 0)
{
ans2 = ans1;
}
n -= n / 3 + (n % 3 == 0 ? 0 : 1);
}
cout << ans1 << " " << ans2 << 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;
}
P9749 公路（贪心，模拟）
题意
公路上一共有 \(n\) 个站点，编号为从 \(1\) 到 \(n\)。其中站点 \(i\) 与站点 \(i + 1\) 的距离为 \(v_i\) 公里。
公路上每个站点都可以加油，编号为 \(i\) 的站点一升油的价格为 \(a_i\) 元，且每个站点只出售整数升的油。
现在要从站点 \(1\) 开车到站点 \(n\)，一开始在站点 \(1\) 且车的油箱是空的。已知车的油箱足够大，可以装下任意多的油，且每升油可以让车前进 \(d\) 公里。问从站点 \(1\) 开到站点 \(n\)，至少要花多少钱加油？
数据规模与约定
对于 \(100\%\) 的数据，\(1 \le n \le 10^5,1 \le d \le 10^5,1 \le v_i \le 10^5,1 \le a_i \le 10^5\)。
题解
一个很重要的性质：假设当前有两个站点 \(x,y\)，\(y\) 站点在 \(x\) 站点后面；要在 \(x\) 站点加 \(k_x\) 升油，单位油价为 \(a_x\)；要在 \(y\) 站点加 \(k_y\) 升油，单位油价为 \(a_y\)。如果 \(a_y \ge a_x\)，那我为什么不在 \(x\) 站点就把这 \(k_y\) 升油买了？
于是我们发现，我们要买油的站点，一定价格是严格单调递减的。然后模拟就可以了。模拟细节详见代码。
#include<bits/stdc++.h>
using namespace std;
/*====================*/
#define endl "\n"
/*====================*/
typedef long long lnt;
/*====================*/
const int N = 1e5 + 10;
/*====================*/
int n;
lnt d;
lnt v[N];//从1号站到i号站的距离
lnt a[N];//i号站一升油的价格
/*====================*/
void Solve(void)
{
do
{
cin >> n >> d;
for (int i = 2; i <= n; ++i)
{
cin >> v[i];
}
for (int i = 1; i <= n; ++i)
{
cin >> a[i];
}
} while (false);
do
{
for (int i = 2; i <= n; ++i)
{
v[i] += v[i - 1];
}
} while (false);
vector<int>station;//需要到达的站
do
{
for (int i = 1; i < n; ++i)
{
if (station.empty())
{
station.push_back(i);
}
else
{
if (a[i] < a[station.back()])
{
station.push_back(i);
}
}
}
station.push_back(n);
} while (false);
do
{
lnt lastmeter = 0, money = 0;//还能跑多少米，花的钱数
for (int i = 1; i < station.size(); ++i)
{
int cur = station[i - 1];//当前所处的站点编号
int nxt = station[i + 0];//下一个要到达的站点编号
lnt dis = v[nxt] - v[cur];//两站相差的距离
lnt k = max((dis - lastmeter + d - 1) / d, 0ll);//至少要加多少升油
lastmeter += d * k; money += a[cur] * k;//加油
lastmeter -= dis;//跑完这一段距离
}
cout << money << 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;
}
P9750 一元二次方程（模拟）
题意
现在给定一个一元二次方程的系数 \(a, b, c\)，其中 \(a, b, c\) 均为整数且 \(a \neq 0\)。你需要判断一元二次方程 \(a x ^ 2 + bx + c = 0\) 是否有实数解，并按要求的格式输出。
在本题中输出有理数 \(v\) 时须遵循以下规则：
- 由有理数的定义，存在唯一的两个整数 \(p\) 和 \(q\)，满足 \(q > 0\)，\(\gcd(p, q) = 1\) 且 \(v = \frac pq\)。
- 若 \(q = 1\)，则输出
{p}，否则输出{p}/{q}，其中{n}代表整数 \(n\) 的值；
对于方程的求解，分两种情况讨论：
-
若 \(\Delta = b ^ 2 - 4ac < 0\)，则表明方程无实数解，此时你应当输出
NO； -
否则 \(\Delta \geq 0\)，此时方程有两解（可能相等），记其中较大者为 \(x\)，则：
-
若 \(x\) 为有理数，则按有理数的格式输出 \(x\)。
-
否则根据上文公式，\(x\) 可以被唯一表示为 \(x = q _ 1 + q _ 2 \sqrt r\) 的形式，其中：\(q _ 1, q _ 2\) 为有理数，且 \(q _ 2 > 0\)\(r\) 为正整数且 \(r > 1\)，且不存在正整数 \(d > 1\) 使 \(d ^ 2 \mid r\)（即 \(r\) 不应是 \(d ^ 2\) 的倍数）；
此时：
- 若 \(q _ 1 \neq 0\)，则按有理数的格式输出 \(q _ 1\)，并再输出一个加号
+； - 否则跳过这一步输出；
随后：
-
若 \(q _ 2 = 1\)，则输出
sqrt({r})； -
否则若 \(q _ 2\) 为整数，则输出
{q2}*sqrt({r})； -
否则若 \(q _ 3 = \frac 1{q _ 2}\) 为整数，则输出
sqrt({r})/{q3}； -
否则可以证明存在唯一整数 \(c, d\) 满足 \(c, d > 1, \gcd(c, d) = 1\) 且 \(q _ 2 = \frac cd\)，此时输出
{c}*sqrt({r})/{d}；
上述表示中
{n}代表整数{n}的值，详见样例。如果方程有实数解，则按要求的格式输出两个实数解中的较大者。否则若方程没有实数解，则输出
NO。 -
数据规模与约定
对于 \(100\%\) 的数据，\(1 \leq T \leq 5000\)，\(1 \leq M \leq 10 ^ 3\)，\(|a|,|b|,|c| \leq M\)，\(a \neq 0\)。。
题解
#include<bits/stdc++.h>
using namespace std;
/*====================*/
#define endl "\n"
/*====================*/
typedef long long lnt;
/*====================*/
int gcd(int a, int b)
{
return b == 0 ? a : gcd(b, a % b);
}
/*====================*/
void Reduction(int& up, int& dw)
{
if (dw < 0)dw *= -1, up *= -1;
int d = gcd(abs(up), abs(dw)); up /= d, dw /= d;
}
void Simplification(int& up, int& dw, int& r)
{
for (int d = 2; d * d <= r; ++d)
{
while (r % (d * d) == 0)
{
up *= d, r /= d * d;
}
}
}
bool PutFraction(int up, int dw)
{
if (up == 0)
{
return false;
}
else
{
Reduction(up, dw);
if (dw == 1)
{
cout << up;
}
else
{
cout << up << "/" << dw;
}
return true;
}
}
/*====================*/
void Solve(void)
{
int a, b, c; cin >> a >> b >> c;
int delta = b * b - 4 * a * c;
if (delta < 0)
{
cout << "NO";
}
else
{
int up1 = -b, dw1 = 2 * a;
int up2 = 1, dw2 = 2 * abs(a), r = delta; Simplification(up2, dw2, r);
if (r == 0)
{
if (PutFraction(up1, dw1) == false)
{
cout << 0;
}
}
else if (r == 1)
{
if (PutFraction(up1 * dw2 + up2 * dw1, dw1 * dw2) == false)
{
cout << 0;
}
}
else
{
if (PutFraction(up1, dw1) == true)
{
cout << "+";
}
Reduction(up2, dw2);
if (up2 == 1 && dw2 == 1)
{
cout << "sqrt(" << r << ")";
}
else if (dw2 == 1)
{
cout << up2 << "*" << "sqrt(" << r << ")";
}
else if (up2 == 1)
{
cout << "sqrt(" << r << ")" << "/" << dw2;
}
else
{
cout << up2 << "*" << "sqrt(" << r << ")" << "/" << dw2;
}
}
}
cout << 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;
int M = 1; cin >> M;
while (T--)Solve();
return 0;
}
P9751 旅游巴士（最短路）
题意
给定一张 \(n\) 点 \(m\) 边的有向图，每条边需要花费的时间为 \(1\)。
每条边存在开放时间 \(a_i\)，只有不早于 \(a_i\) 时间到达该条边的起点才能通行。
现在要从 \(1\) 号点到 \(n\) 号点，到达 \(1\) 号点的时间和离开 \(n\) 号点的时间必须是 \(k\) 的倍数，且不允许在点或边上停留。
问最少花费的时间是多少。
数据规模与约定
对于 \(100\%\) 的数据，\(2 \le n \le 10^4 ,1 \le m \le 2*10^4,1 \le k \le 10^2,1 \le u,v \le n,0 \le a_i \le 10^6\)。
题解
首先我们发现，如果提前到达了一条边我们需要等待。而等待时间如果是 \(k\) 的倍数，我们相当于在起点先等待。
而路上花费的时间不一定是 \(k\) 的倍数，所以我们需要对 \(k\) 进行取模来分类讨论。
跑最短路即可。
#include<bits/stdc++.h>
using namespace std;
/*====================*/
#define endl "\n"
/*====================*/
typedef long long lnt;
/*====================*/
const int N = 1e4 + 10;
const int M = 2e4 + 10;
const int K = 1e2 + 10;
/*====================*/
const int INF = 0X3F3F3F3F;
/*====================*/
int n, m, k;
/*====================*/
namespace _Graph
{
struct Edge
{
int u, v, a;
Edge(int _u = 0, int _v = 0, int _a = 0)
{
u = _u, v = _v, a = _a;
}
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, int a)
{
edge[++cntedge] = Edge(u, v, a);
G[u].push_back(cntedge);
}
}
/*====================*/
namespace _Dijkstra
{
using namespace _Graph;
/*====================*/
struct Unit
{
int v, r, w;
Unit(int _v = 0, int _r = 0, int _w = 0)
{
v = _v, r = _r, w = _w;
}
friend bool operator<(const Unit& a, const Unit& b)
{
return a.w > b.w;
}
};
/*====================*/
int dis[N][K]; bool vis[N][K];
/*====================*/
void Init(int s, int r)
{
memset(dis, INF, sizeof(dis));
memset(vis, false, sizeof(vis));
priority_queue<Unit>q;
q.push(Unit(s, r, dis[s][r] = 0));
while (!q.empty())
{
int cur_v = q.top().v, cur_r = q.top().r; q.pop();
if (vis[cur_v][cur_r])continue; vis[cur_v][cur_r] = true;
for (int i = 0; i < G[cur_v].size(); ++i)
{
int val = 1 + max(0, (edge[G[cur_v][i]].a - dis[cur_v][cur_r] + k - 1) / k) * k;
int nxt_v = edge[G[cur_v][i]].node(cur_v), nxt_r = (cur_r + 1) % k;
if (dis[nxt_v][nxt_r] > dis[cur_v][cur_r] + val)
{
dis[nxt_v][nxt_r] = dis[cur_v][cur_r] + val;
q.push(Unit(nxt_v, nxt_r, dis[nxt_v][nxt_r]));
}
}
}
}
}
/*====================*/
void Solve(void)
{
cin >> n >> m >> k;
for (int i = 1; i <= m; ++i)
{
int u, v, a;
cin >> u >> v >> a;
_Graph::AddEdge(u, v, a);
}
_Dijkstra::Init(1, 0);
int ans = _Dijkstra::dis[n][0];
if (ans == INF)ans = -1;
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;
}