|
COGS 1825 [USACO Jan11]道路与航线由于 $T \leq 25000,R+P \leq 100000$ ，优先考虑SPFA，
#include <bits/stdc++.h>
using namespace std;
vector<pair<int, int> > v[25005];
int d[25005];
bool vis[25005];
int p[25005];
int T, R, P, S;
void SPFA(int s) {
memset(d, 0x3f, sizeof(d));
memset(vis, 0, sizeof(vis));
memset(p, 0, sizeof(p));
queue<int> q;
q.push(s);
vis[s] = true;
d[s] = 0;
while (!q.empty()) {
int x = q.front();
q.pop();
vis[x] = 0;
for (int i = 0; i < v[x].size(); i++) {
if (d[v[x][i].first] > d[x] + v[x][i].second) {
d[v[x][i].first] = d[x] + v[x][i].second, p[v[x][i].first] = x;
if (!vis[v[x][i].first]) q.push(v[x][i].first), vis[v[x][i].first] = true;
}
}
}
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
cin >> T >> R >> P >> S;
for (int i = 1; i <= R; i++) {
int a, b, c;
cin >> a >> b >> c;
v[a].push_back(make_pair(b, c));
v[b].push_back(make_pair(a, c));
}
for (int i = 1; i <= P; i++) {
int a, b, c;
cin >> a >> b >> c;
v[a].push_back(make_pair(b, c));
}
SPFA(S);
for (int i = 1; i <= T; i++) {
if (d[i] == 0x3f3f3f3f) cout << "NO PATH" << endl;
else cout << d[i] << endl;
}
return 0;
}
最终评测T两个点，考虑换方法。 查看资料注意到SPFA有双端队列优化和优先队列优化，优先队列复杂度 $O(logn)$，故不考虑。双端队列优化思路是：将要加入的节点与队头比较，小于等于插到队头，大于则插到队尾，时间复杂度接近 $O(1)$。 重写代码
#include <bits/stdc++.h>
using namespace std;
vector<pair<int, int> > v[25005];
int d[25005];
bool vis[25005];
int p[25005];
int T, R, P, S;
void SPFA(int s) {
memset(d, 0x3f, sizeof(d));
memset(vis, 0, sizeof(vis));
memset(p, 0, sizeof(p));
deque<int> q;
q.push_back(s);
vis[s] = true;
d[s] = 0;
while (!q.empty()) {
int x = q.front();
q.pop_front();
vis[x] = 0;
for (int i = 0; i < v[x].size(); i++) {
if (d[v[x][i].first] > d[x] + v[x][i].second) {
d[v[x][i].first] = d[x] + v[x][i].second, p[v[x][i].first] = x;
//主要改动如下
if (!vis[v[x][i].first]) {
if (d[v[x][i].first] <= d[q.front()]) q.push_front(v[x][i].first);
else q.push_back(v[x][i].first);
vis[v[x][i].first] = true;
}
}
}
}
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
cin >> T >> R >> P >> S;
for (int i = 1; i <= R; i++) {
int a, b, c;
cin >> a >> b >> c;
v[a].push_back(make_pair(b, c));
v[b].push_back(make_pair(a, c));
}
for (int i = 1; i <= P; i++) {
int a, b, c;
cin >> a >> b >> c;
v[a].push_back(make_pair(b, c));
}
SPFA(S);
for (int i = 1; i <= T; i++) {
if (d[i] == 0x3f3f3f3f) cout << "NO PATH" << endl;
else cout << d[i] << endl;
}
return 0;
}
后记在知乎上看到文章关于SPFA的各种优化以及对应hack，可以参考（如何看待 SPFA 算法已死这种说法？ - 知乎 (zhihu.com)）。
题目1825 [USACO Jan11]道路与航线
 2
评论
2025-07-01 10:55:47
|
|
|
Pro4034 罚站 题解
×
…提示!该题解未通过审核，建议分享者本着启发他人，照亮自己的初衷以图文并茂形式完善之，请勿粘贴代码。........................................................................ 该题解等待再次审核........................................................................(剩余 0 个中英字符)
题目4034 罚站
AAAAAAAAAA
2025-06-02 18:24:29
|
|
|
$题目大意$ ${求}\sum_{i=1}^{n}\sum _{j=1}^{m}{lcm(i,j)} {且} 1\le n,m\le 1e7$ ${正解:}$ ${有}{lcm(i,j)=\frac{i\cdot j}{\gcd(i,j)}}$ ${所以原式为:}$ $ans(n,m)=\sum_{i=1}^{n}\sum _{j=1}^{m}{\frac{i\cdot j}{\gcd(i,j)}}$ $~\qquad\qquad =\sum_{i=1}^{n}\sum _{j=1}^{m}{ \sum_{d\mid i,d\mid j,\gcd(\frac{i}{d},\frac{j}{d})}{}{\frac{i\cdot j}{d}}}$ ${现在需要将d给提出来,默认}{n\le m,}{我们设}i=i'\cdot d,j=j'\cdot d,{则}i'=\frac{i}{d},j'=\frac{j}{d},将i,j替换进上式得:$ $ans(n,m)=\sum_{d=1}^{\min(n,m)}{\sum_{i'=1}^{\left \lfloor \frac{n}{d} \right \rfloor}{\sum_{j'=1}^{\left \lfloor \frac{m}{d} \right \rfloor}{[\gcd(i',j')=1]\cdot d\cdot i'\cdot j'}}}$ $~\qquad\qquad=\sum_{d=1}^{n}{d\cdot\sum_{i=1}^{\left \lfloor \frac{n}{d} \right \rfloor}{\sum_{j=1}^{\left \lfloor \frac{m}{d} \right \rfloor}{[\gcd(i,j)=1]\cdot i\cdot j}}}$ ${接着将d后面的部分再提出来考虑,化简枚举约数,运用莫比乌斯反演:} [\gcd(i,j)=1]=\sum_{d\mid gcd}{\mu{(d)}}:$ ${设} \ {g(n,m)}=\sum_{i=1}^{n}{\sum_{j=1}^{m}{[\gcd(i,j)=1]\cdot i\cdot j}}$ $~\qquad\qquad=\sum_{d=1}^{n}{\sum_{d\mid i}^{n}{\sum_{d\mid j}^{m}{\mu(d)\cdot i\cdot j}}}$ ${再设}\ i=i' \cdot d,j=j' \cdot d \ {带入,将}\mu{提出来}$ ${即}\ g(n,m)=\sum_{d=1}^{n}{\mu(d)}\cdot{d^{2}\cdot{\sum_{i=1}^{\left\lfloor \frac{n}{d} \right \rfloor}{\sum_{j=1}^{\left \lfloor \frac{m}{d} \right \rfloor}{i\cdot j}}}}$ $~\qquad\qquad = \sum_{d=1}^{n}{\mu(d)}\cdot{d^{2}}\cdot\frac{{\left \lfloor \frac{n}{d} \right \rfloor}\cdot ({\left \lfloor \frac{n}{d} \right \rfloor}+1)\cdot {\left \lfloor \frac{m}{d} \right \rfloor}\cdot({\left \lfloor \frac{m}{d} \right \rfloor}+1)}{4}$ ${最后将g(n,m)带入ans(n,m)中得:}$ $ans(n,m)=\sum_{d=1}^{n}{d}\cdot{g(\left\lfloor \frac{n}{d}\right\rfloor,\left\lfloor \frac{m}{d}\right\rfloor)}$ ${用数论分块求出来}~{g(n,m)}~{再用数论分块求出来}~{ans(n,m),}~{就在{\Theta(n+m)内}}{得到答案了}~{(∠・ω< )⌒★}$
题目1886 [国家集训队 2011] Crash的数字表格
AAAAAAAAAAAAAAAAAAAA
4
1 条 评论
2025-05-24 21:56:25
|
|
|
Pro896 圈奶牛 题解896. 圈奶牛 题解题意描述给定有 n 头奶牛，要把这些奶牛用栅栏围起来，栅栏的总长度即为花费，求花费的最小值。 题解例如有这么几头牛：
显然，一个想法是用一个圈把这些牛全部围起来：
但是这样显然不是花费最小的，那我们就让这个椭圆一直缩小，直到和边缘上的点碰触就停止缩小：
这样就是花费最小的啦！ 如果再往里缩小的话，花费就会反而变长！
如图，在 $\triangle GHI$ 中，根据三边关系显然有 $GI + IH \gt GH$，所以 $GH$ 就是 $G$ 到 $H$ 花费最小的连接方式。
注意到这个连接方式的顶点连线的斜率是递减的 即： $$k_{HG} > k_{GE} > k_{ED} > k_{HD}$$ 那么，我们如何找到这个连接方式呢？ 首先找到一个 $x$ 坐标或 $y$ 坐标最大/最小的点，例如图中的点 $H$、点 $G$、点 $E$、点 $D$。 我们以点 $H$ 为例，将这些点排序，按照其他点与点 $H$ 的连线的斜率降序排序（从小到大也可以，只不过实现略有不同）：
struct NODE {
double x, y;
} node[MAXN];
double getk(NODE x, NODE y) {
return (x.y - y.y) / (x.x - y.x);
}
int main() {
... // 读入
sort(node + 1, node + n + 1, [](NODE x, NODE y) {
if (x.x != y.x) return x.x < y.x;
return x.y > y.y;
}); // 先进行一个排序，按照 x 坐标为第一关键字升序
// y 坐标为第二关键字降序，也就是要把最左上角的点放到第一个
sort(node + 2, node + n + 1, [](NODE x, NODE y) {
return getk(x, node[1]) > getk(y, node[1]);
});
}
但是 [code](x.x - y.x)[\code] 容易等于零，除数等于零就错误了！那我们就将除法比较改成乘法叭 也就是： $$\frac{a_{1,y} - a_{2,y}}{a_{1,x} - a_{2.x}} \le \frac{b_{1,y} - b_{2,y}}{b_{1,x} - b_{2,x}} \\ \Downarrow \\ (a_{1,y} - a_{2,y})(b_{1,x} - b_{2,x}) \le (b_{1,y} - b_{2,y})(a_{1,x} - a_{2.x})$$
struct NODE {
double x, y;
} node[MAXN];
bool check(NODE a1, NODE a2, NODE b1, NODE b2) {
return (a1.y - a2.y) * (b1.x - b2.x) <= (b1.y - b2.y) * (a1.x - a2.x);
}
double dis(NODE x, NODE y) {
return sqrt(pow(x.x - y.x, 2) + pow(x.y - y.y, 2));
}
int main() {
...
// 找到左上角的点
sort(node + 1, node + n + 1, [](NODE x, NODE y) {
if (x.x != y.x) return x.x < y.x;
return x.y > y.y;
});
// 其余点按照与左上角的点连线的斜率降序排列
sort(node + 2, node + n + 1, [](NODE x, NODE y) {
return !check(x, node[1], y, node[1]);
});
...
}
接下来就是考虑怎么样把 $G,H,D,E$ 四个点选中啦！ 我们用一个栈来维护选中的点。 首先点集是这样的：
按照排序后的顺序取扫描，首先扫描到点 $H$，此时栈为空，直接把点 $H$ 加入栈：
接着扫描到点 $G$，站内只有一个元素，直接把点 $G$ 加入栈：
接着扫描到点 $E$，发现其与栈顶的点 $G$ 连线的斜率 与之前的所有连线的斜率 满足递减关系，直接入栈：
接着扫描到点 $B$，发现其与栈顶的点 $E$ 连线的斜率 与之前的所有连线的斜率 满足递减关系，直接入栈：
接着扫描到点 $F$！它与栈顶的点 $B$ 的连线斜率比之前大了！
所以把点 $B$ 踢出栈，重复检查点 $F$ 和点 $E$ 的连线是否符合要求。发现其与栈顶的点 $E$ 连线的斜率 与之前的所有连线的斜率 满足递减关系，直接入栈：
接着扫描到点 $C$，发现其与栈顶的点 $F$ 连线的斜率 与之前的所有连线的斜率 满足递减关系，直接入栈：
接着扫描到点 $A$，发现其与栈顶的点 $C$ 连线的斜率 与之前的所有连线的斜率 满足递减关系，直接入栈：
接着扫描到点 $D$！它与栈顶的点 $A$ 连线斜率比之前大！
所以把点 $A$ 踢出栈，重复检查点 $D$ 与栈顶点 $C$ 的连线，发现斜率仍然比之前大！
所以把点 $C$ 踢出栈，重复检查点 $D$ 与栈顶点 $F$ 的连线，发现斜率仍然比之前大！
所以把点 $F$ 踢出栈，重复检查点 $D$ 与栈顶点 $E$ 的连线：
终于满足条件了！点 $D$ 与栈顶点 $E$ 连线的斜率 与之前所有连线的斜率 满足递减关系，所以入栈：
所有的点都扫描完啦！所以把最后的点 $D$ 和第一个点 $H$ 连上就好啦！
和前面的图一模一样哦！这个过程模拟就好啦！ （其实判断斜率是否满足要求就看这些线段是不是一直在右转就好嘿嘿） NODE sta[MAXN]; int top;
int main() {
...
sta[++top] = node[1];
for (int i = 2; i <= n; ++i) {
while (top > 1 && !check(node[i], sta[top], sta[top], sta[top - 1])) top--;
sta[++top] = node[i];
}
...
}
此时，栈里面的元素就是要求的点集啦！ 最后求花费不是难事： double dis(NODE x, NODE y) {
return sqrt(pow(x.x - y.x, 2) + pow(x.y - y.y, 2));
}
double ans;
int main() {
...
for (int i = 2; i <= top; ++i) {
ans += dis(sta[i], sta[i - 1]);
}
ans += dis(sta[top], sta[1]);
...
}
最终代码：
#include <cstdio>
#include <algorithm>
#include <cmath>
using ::std::sort;
using ::std::pow;
using ::std::sqrt;
const int MAXN = 1e5 + 10;
struct NODE {
double x, y;
} node[MAXN];
bool check(NODE a1, NODE a2, NODE b1, NODE b2) {
return (a1.y - a2.y) * (b1.x - b2.x) <= (b1.y - b2.y) * (a1.x - a2.x);
}
double dis(NODE x, NODE y) {
return sqrt(pow(x.x - y.x, 2) + pow(x.y - y.y, 2));
}
int n;
NODE sta[MAXN];
int top;
double ans;
int main() {
freopen("fc.in", "r", stdin);
freopen("fc.out", "w", stdout);
scanf("%d", &n);
for (int i = 1; i <= n; ++i) {
scanf("%lf %lf", &node[i].x, &node[i].y);
}
sort(node + 1, node + n + 1, [](NODE x, NODE y) {
if (x.x != y.x) return x.x < y.x;
return x.y > y.y;
});
sort(node + 2, node + n + 1, [](NODE x, NODE y) {
return !check(x, node[1], y, node[1]);
});
sta[++top] = node[1];
for (int i = 2; i <= n; ++i) {
while (top > 1 && !check(node[i], sta[top], sta[top], sta[top - 1])) top--;
sta[++top] = node[i];
}
for (int i = 2; i <= top; ++i) {
ans += dis(sta[i], sta[i - 1]);
}
ans += dis(sta[top], sta[1]);
printf("%.2lf\n", ans);
return 0;
}
这个代码交到 COGS 上就能过啦！但是是错误的！ HACK输入： 18 0 1 0 2 0 3 0 4 0 5 0 6 0 7 0 8 0 9 0 10 0 11 0 12 0 13 0 14 0 15 0 16 0 17 0 18输出： 48.00正确答案： 34.00出现这个问题的原因是所有的点出现在了同一条竖直的线上，数据范围超出了阈值，[code]::std::sort[/code] 函数选择使用快速排序，那么这些点原来按 $y$ 坐标降序的顺序就无法被保证，而这些点传入 [code]check[/code] 函数总是会返回 [code]true[/code]，因为 [code]b1.x - b2.x[/code] 和 [code]a1.x - a2.x[/code] 都为 0。最终导致花费计算过多。
解决的办法是排序的时候加上特判。对于在同一条水平的线上的点也用同样的方法就好啦！
sort(node + 2, node + n + 1, [](NODE x, NODE y) {
if (x.x == node[1].x && y.x == node[1].x) return x.y > y.y; // 特判 x 坐标都一样
if (x.y == node[1].y && y.y == node[1].y) return x.x < y.x; // 特判 y 坐标都一样
return !check(x, node[1], y, node[1]);
});
最最终代码：
#include <cstdio>
#include <algorithm>
#include <cmath>
using ::std::sort;
using ::std::pow;
using ::std::sqrt;
const int MAXN = 1e5 + 10;
struct NODE {
double x, y;
} node[MAXN];
bool check(NODE a1, NODE a2, NODE b1, NODE b2) {
return (a1.y - a2.y) * (b1.x - b2.x) <= (b1.y - b2.y) * (a1.x - a2.x);
}
double dis(NODE x, NODE y) {
return sqrt(pow(x.x - y.x, 2) + pow(x.y - y.y, 2));
}
int n;
NODE sta[MAXN];
int top;
double ans;
int main() {
freopen("fc.in", "r", stdin);
freopen("fc.out", "w", stdout);
scanf("%d", &n);
for (int i = 1; i <= n; ++i) {
scanf("%lf %lf", &node[i].x, &node[i].y);
}
sort(node + 1, node + n + 1, [](NODE x, NODE y) {
if (x.x != y.x) return x.x < y.x;
return x.y > y.y;
});
sort(node + 2, node + n + 1, [](NODE x, NODE y) {
if (x.x == node[1].x && y.x == node[1].x) return x.y > y.y;
if (x.y == node[1].y && y.y == node[1].y) return x.x < y.x;
return !check(x, node[1], y, node[1]);
});
sta[++top] = node[1];
for (int i = 2; i <= n; ++i) {
while (top > 1 && !check(node[i], sta[top], sta[top], sta[top - 1])) top--;
sta[++top] = node[i];
}
for (int i = 2; i <= top; ++i) {
ans += dis(sta[i], sta[i - 1]);
}
ans += dis(sta[top], sta[1]);
printf("%.2lf\n", ans);
return 0;
}
时间复杂度：$O(n \log{n} + n)$，瓶颈在排序。
|
|
|
Pro7 通信线路 题解通信线路 题解题目描述见 通信线路 整体思路只是一个最小生成树的模板题，数据量也没有很大 第一种方法：kruskal算法
两种实现：边集数组：时间复杂度$O(M log M + M(N + M))$； 第二种方法：Prim算法时间复杂度：$O(N^2)$（heap优化$O(M long M)$） 读者可以自行实现 代码实现最小生成树的两个主要算法都可以在讲义中找到，点击这个 本题解采用并查集 + kruskal 好孩子不可以抄代码哦 #include <bits/stdc++.h> // 万能头
using namespace std;
int n; // n是城市数
const int N = 1510,M = 1e4 + 10; // N是最大城市数，M是最大边数
struct Edge // 将边的参数定义到结构体里
{
int x,y,w; // x起点，y终点，w是权重
}e[M];
bool cmp(Edge &a,Edge &b) // 排序按照权重从小到大
{
return a.w < b.w;
}
int f[N]; // 并查集数组
void init()
{ // 并查集初始化
for(int i = 1; i <= N; ++i) f[i] = i;
}
int get(int x)
{ // 递归地查询x属于哪个集
if(x == f[x]) return x;
return f[x] = get(f[x]);
}
void merge(int x,int y)
{ // 将两个集合并
int fx = get(x),fy = get(y);
if(fx != fy) f[fy] = fx;
}
void kruskal()
{ // kruskal本体
init(); // 初始化
int ans = 0;
for(int i = 1;i <= M;i++)
{
int x = e[i].x,y = e[i].y,w = e[i].w; // 每次从边集中取出一个权重较小的
if(get(x) != get(y)) // 如果这条边的两个顶点不属于同一个集（就是不相连的意思）
{
merge(x,y); // 合并，即采用这条边
ans += w; // 总和记得加哦O(∩_∩)O
}
}
cout << ans << endl; // 输出就好乐，也可以返回ans在主函数里输出
}
int main()
{
freopen("mcst.in","r",stdin); // 文件输入输出
freopen("mcst.out","w",stdout);
cin >> n; // 输入城市数
int ind = 0;
for(int i = 0;i < n;i++)
{
for(int j = 0;j < n;j++)
{
int op; // 双重循环读入输入的矩阵（确信
cin >> op; // 第i+1个顶点到第j+1顶点之间边的权重
if(op != -1) e[ind].x = i + 1,e[ind].y = j + 1,e[ind].w = op,ind++;
// 如果两个顶点可以有边相连，就放在边集数组
}
}
sort(e,e+M,cmp); // 用cmp来排序
kruskal(); // kruskal，启动！
return 0; // 记得return是美德
}
|
|
|
×
提示!该题解未通过审核，建议分享者本着启发他人，照亮自己的初衷以图文并茂形式完善之，请勿粘贴代码。#include<iostream> using namespace std; int find(int x,int y,int n){ int num=x;
if(n-x+1<num) n 该题解等待再次审核........................................................................(剩余 790 个中英字符)
题目1811 [NOIP 2014PJ]螺旋矩阵
2025-05-10 07:27:49
|
