|
http://218.28.19.228:8081/cogs/index.php书架二题解
|
|
|
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
|
|
|
$题目大意$ ${求}\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
|
|
|
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是美德
}
|
|
|
有一说一，其实挺水
做一个以身高为关键字的单调栈储存每个奶牛的序号，再单独以一个数组存储身高，在弹出时处理它对答案的贡献，显然为当前序号到它的序号的差减一
最后注意一下数据大小开个longlong
#include<bits/stdc++.h>
using namespace std;
int n,a[110086],tmp,c[110086],num;
int main () {
freopen("hair.in","w",stdin);
freopen("hair.out","r",stdout);
cin>>n;
for(int i = 1; i<=n; i++){
int y;
cin>>y;
while(y>=c[a[tmp-1]]&&tmp>0){
num+=i-a[tmp-1]-1;
tmp--;
}
c[i]=y;
a[tmp++]=i;
}
while(tmp>0){
if(a[tmp-1]!=n)num+=n-a[tmp-1];
tmp--;
}
cout<<num;
return 0;
}
题目1746 [POJ 3250]乱头发节
AAAAAAAAAA
3
1 条 评论
2025-03-29 11:35:26
|
|
|
考场一个小时切不出来T1于是暴力及时止损，看题解才想到的贪心，，
首先我们要知道，对任意数列进行有限次邻项交换后，必定能得到该数列的全排列。这样你就拿到了 $n\leq10$ 的20分。 如果你能想到在 $t_1$ 和 $t_2$ 中的由连续的1组成的连通块内，对应的 $s_1$ 与 $s_2$ 的部分可以任意排列，那你就拿到了 $t_1=t_2$ 的20分。 如果你能想到当 $s_1$ 全是0或1的时候不管 $s_2$ 如何排列答案都不会变，那你就拿到了性质A的20分。
（性质C太难了不讨论了）（）（）
暴力的60分该拿还是得拿的）
然后是正解 从前往后扫，如果这个位置 $s_1$ 和 $s_2$ 有一个不能能换，那就从对应连通块内挑一个数放上去配对就好了 如果都能换，同上，挑0挑1都一样 如果都不能换，直接算答案
感性地贪一下，如果这个位置不配对，那就是给后面的位置留了一个0或1，但这个数在后面至多也只有1的贡献，还不如拿到就马上配了（
换之前记得先看看这个块剩下的0和1数量还够不够 （其实用并查集维护会方便一点）
#include<bits/stdc++.h>
#define ll long long
#define lowbit(x) (x&(-x))
#define mem(a,b) memset(a,b,sizeof a)
#define rev(x) reverse(x.begin(),x.end())
using namespace std;
struct node{
int n0,n1;
node operator+(const node&q)const{return (node){n0+q.n0,n1+q.n1};}
}siz[100010][2];
int fa[100010][2];
inline int find(int x,int p){
if(x==fa[x][p]) return x;
return fa[x][p]=find(fa[x][p],p);
}
inline void merge(int x,int y,int p){
x=find(x,p),y=find(y,p);
if(x!=y) siz[y][p]=siz[y][p]+siz[x][p],fa[x][p]=y;
}
int main(){
int t;cin>>t;
while(t--){
int n;cin>>n;
string s1,s2,t1,t2;cin>>s1>>s2>>t1>>t2;
for(int i=0;i<n;i++) fa[i][0]=fa[i][1]=i;
for(int i=0;i<n;i++){
siz[i][0].n0=s1[i]=='0';
siz[i][0].n1=s1[i]=='1';
siz[i][1].n0=s2[i]=='0';
siz[i][1].n1=s2[i]=='1';
}
for(int i=1;i<n;i++){
if(t1[i]=='1'&&t1[i-1]=='1') merge(i-1,i,0);
if(t2[i]=='1'&&t2[i-1]=='1') merge(i-1,i,1);
}
int ans=0;
for(int i=0;i<n;i++){
int p1=find(i,0);
int p2=find(i,1);
if(siz[p1][0].n0>0&&siz[p2][1].n0>0) siz[p1][0].n0--,siz[p2][1].n0--,ans++;
else if(siz[p1][0].n1>0&&siz[p2][1].n1>0) siz[p1][0].n1--,siz[p2][1].n1--,ans++;
}
cout<<ans<<endl;
}
return 0;
}
题目4089 [NOIP 2024]编辑字符串
2
评论
2024-12-07 19:38:07
|
