请问Dancing Link恢复状态时为什么要倒着遍历十字链表？
题目描述
给定一个由 n 个点和 m 条边组成的无向连通加权图。
设点 1 到点 i 的最短路径长度为 di。
现在，你需要删掉图中的一些边，使得图中最多保留 k 条边。
如果在删边操作全部完成后，点 1 到点 i 的最短路径长度仍为 di，则称点 i 是一个优秀点。
你的目标是通过合理进行删边操作，使得优秀点的数量尽可能大。
算法
重要结论：1到每个点最短路径构成的链的并集可以为一棵树
证明：
为了保留尽量少的边，当最短路路径有多种可能时，我们设1->u的最短路每次都走同一条
即如果1->v最短路径经过u，那么1->v中1->u的路径和1->u的最短路路径相同
这样就不可能有环了
d[v]-d[u]==e[i].c判断u->v是否在最短路树上
每个v只能被第一个找到它的u更新，保证树形结构
时间复杂度
C++ 代码
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5;
typedef long long LL;
int n,m,k;
struct Node{
int v,c,nxt,id;
}e[N<<1];
int tot,h[N];
void addEdge(int u,int v,int c,int id)
{
tot++;
e[tot].v=v;e[tot].c=c;e[tot].nxt=h[u];h[u]=tot;
e[tot].id=id;
}
struct Point{
int x;
LL y;
bool operator <(const Point &t)const
{
return y>t.y;
}
};
priority_queue<Point>q;
LL d[N];
bool used[N];
void dijk()
{
memset(d,0x3f,sizeof(d));
d[1]=0;
q.push({1,0});
while(!q.empty())
{
int u=q.top().x;
q.pop();
if(used[u])
{
continue;
}
used[u]=1;
for(int i=h[u];i;i=e[i].nxt)
{
int v=e[i].v;
if(d[v]>d[u]+e[i].c)
{
d[v]=d[u]+e[i].c;
q.push({v,d[v]});
}
}
}
}
int vis[N],ans[N];
int main()
{
int u,v,c;
scanf("%d%d%d",&n,&m,&k);
for(int i=1;i<=m;i++)
{
scanf("%d%d%d",&u,&v,&c);
addEdge(u,v,c,i);
addEdge(v,u,c,i);
}
dijk();
int q[N];
int hh=1,tt=0;
q[++tt]=1;vis[1]=1;
while(hh<=tt)
{
u=q[hh];
for(int i=h[u];i;i=e[i].nxt)
{
v=e[i].v;
if(vis[v])
{
continue;
}
if(d[v]-d[u]==e[i].c)
{
q[++tt]=v;
vis[v]=1;
ans[++ans[0]]=e[i].id;
}
}
hh++;
}
ans[0]=min(ans[0],k);
printf("%d\n",ans[0]);
for(int i=1;i<=ans[0];i++)
{
printf("%d ",ans[i]);
}
return 0;
}
活动打卡代码
AcWing 3547. 特殊数字
#include<bits/stdc++.h>
using namespace std;
int n;
bool check(int x)
{
int sum=0;
while(x)
{
sum+=x%10;
x/=10;
}
if(sum%4==0)
{
return 1;
}
return 0;
}
int main()
{
scanf("%d",&n);
for(int i=n;i;i++)
{
if(check(i))
{
printf("%d",i);
break;
}
}
return 0;
}
活动打卡代码
AcWing 3548. 双端队列
#include<bits/stdc++.h>
using namespace std;
const int N=2e5+5;
int n,x,pl,pr,l[N],r[N],tp,pos[N];
char ch[2];
int main()
{
scanf("%d",&n);
while(n--)
{
scanf("%s%d",ch,&x);
if(ch[0]=='L')
{
pl++;
tp++;
l[tp]=-pl,r[tp]=tp-1;
pos[x]=tp;
}
if(ch[0]=='R')
{
pr++;
tp++;
l[tp]=tp-1,r[tp]=-pr;
pos[x]=tp;
}
if(ch[0]=='?')
{
// cout<<r[pos[x]]<<endl;
printf("%d\n",min(l[pos[x]]+pl,r[pos[x]]+pr));
}
}
return 0;
}
活动打卡代码
AcWing 3548. 双端队列
#include<bits/stdc++.h>
using namespace std;
const int N=2e5+5;
int n,x,pl,pr,l[N],r[N],tp,pos[N];
char ch[2];
int main()
{
scanf("%d",&n);
while(n--)
{
scanf("%s%d",ch,&x);
if(ch[0]=='L')
{
pl++;
tp++;
l[tp]=-1,r[tp]=tp-1;
pos[x]=tp;
}
if(ch[0]=='R')
{
pr++;
tp++;
l[tp]=tp-1,r[tp]=-1;
pos[x]=tp;
}
if(ch[0]=='?')
{
printf("%d\n",min(l[pos[x]]+pl,r[pos[x]]+pr));
}
}
return 0;
}
活动打卡代码
AcWing 3547. 特殊数字
#include<bits/stdc++.h>
using namespace std;
int n;
bool check(int x)
{
int sum=0;
while(x)
{
sum+=x%10;
x/=10;
}
if(sum%4==0)
{
return 1;
}
return 0;
}
int main()
{
scanf("%d",&n);
for(int i=n;i;i++)
{
if(check(i))
{
printf("%d",i);
break;
}
}
return 0;
}
活动打卡代码
AcWing 3122. 多项式乘法
#include<bits/stdc++.h>
using namespace std;
const int N=4e6+6;
const double pi=acos(-1);
int n,m;
struct Complex
{
double x,y;
Complex operator +(const Complex &t)const
{
return {x+t.x,y+t.y};
}
Complex operator -(const Complex &t)const
{
return {x-t.x,y-t.y};
}
Complex operator *(const Complex &t)const
{
return {x*t.x-y*t.y,x*t.y+y*t.x};
}
}a[N],b[N];
int rev[N],bit,tot;
void fft(Complex a[],int inv)
{
for(int i=0;i<tot;i++)
{
if(i<rev[i])
{
swap(a[i],a[rev[i]]);
}
}
for(int mid=1;mid<tot;mid<<=1)
{
Complex w1=Complex({cos(pi/mid),inv*sin(pi/mid)});
for(int i=0;i<tot;i+=mid*2)
{
Complex wk=Complex({1,0});
for(int j=0;j<mid;j++,wk=wk*w1)
{
Complex x=a[i+j],y=wk*a[i+j+mid];
a[i+j]=x+y,a[i+j+mid]=x-y;
}
}
}
}
int main()
{
scanf("%d%d",&n,&m);
for(int i=0;i<=n;i++)
{
scanf("%lf",&a[i].x);
}
for(int i=0;i<=m;i++)
{
scanf("%lf",&b[i].x);
}
while((1<<bit)<n+m+1)
{
bit++;
}
tot=1<<bit;
for(int i=0;i<tot;i++)
{
rev[i]=(rev[i>>1]>>1)|((i&1)<<(bit-1));
}
fft(a,1),fft(b,1);
for(int i=0;i<tot;i++)
{
a[i]=a[i]*b[i];
}
fft(a,-1);
for(int i=0;i<=n+m;i++)
{
printf("%d ",(int)(a[i].x/tot+0.5));
}
return 0;
}
活动打卡代码
AcWing 2702. problem b
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N=5e4+4,M=5e4;
int n,u[N],k,s[N];
int p[N],tp;
bool pd[N];
LL query(int x,int y)
{
LL ans=0;
for(int l=1,r;k*l<=min(x,y);l=r+1)
{
r=min((x/k)/(x/k/l),(y/k)/(y/k/l));
ans+=(s[r]-s[l-1])*((LL)x/k/l*(y/k/l));
}
return ans;
}
int main()
{
int a,b,c,d;
scanf("%d",&n);
u[1]=1;
for(int i=2;i<=M;i++)
{
if(pd[i]==0)
{
p[++tp]=i;
u[i]=-1;
}
for(int j=1;j<=tp&&i*p[j]<=M;j++)
{
pd[i*p[j]]=1;
if(i%p[j]==0)
{
u[i*p[j]]=0;
break;
}
u[i*p[j]]=u[i]*u[p[j]];
}
}
for(int i=1;i<=M;i++)
{
s[i]=s[i-1]+u[i];
}
while(n--)
{
scanf("%d%d%d%d%d",&a,&b,&c,&d,&k);
printf("%lld\n",query(b,d)-query(a-1,d)-query(b,c-1)+query(a-1,c-1));
}
return 0;
}
活动打卡代码
AcWing 3124. BSGS
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N=10007,M=4e5+4;
struct Hash{
int v,c,nxt;
}e[M];
int h[N],tot;
inline void addEdge(int u,int v,int c)
{
tot++;
e[tot].v=v;e[tot].c=c;e[tot].nxt=h[u];
h[u]=tot;
}
int hash(int x)
{
for(int i=h[x%N];i;i=e[i].nxt)
{
if(e[i].v==x)
{
return e[i].c;
}
}
return -1;
}
int bsgs(int a,int b,int p)
{
b=b%p;
if(b==1)
{
return 0;
}
int k=sqrt(p)+1,ak=1;
for(int i=0,j=b;i<k;i++,j=(LL)j*a%p)
{
addEdge(j%N,j,i);
// cout<<j<<endl;
ak=(LL)ak*a%p;
}
for(int i=1,j=ak;i<=k;i++,j=(LL)j*ak%p)
{
if(hash(j)!=-1)
{
// cout<<i<<' '<<hash(j)<<endl;
return k*i-hash(j);
}
}
return -1;
}
int exgcd(int a,int b,int &x,int &y)
{
if(b==0)
{
x=1,y=0;
return a;
}
int ans=exgcd(b,a%b,y,x);
y-=a/b*x;
return ans;
}
int exbsgs(int a,int b,int p)
{
b=(b%p+p)%p;
if(1%p==b%p)
{
return 0;
}
int x,y;
int d=exgcd(a,p,x,y);
if(d>1)
{
if(b%d)
{
return -1;
}
exgcd(a/d,p/d,x,y);
return exbsgs(a,(LL)b/d*x%(p/d),p/d)+1;
}
return bsgs(a,b,p);
}
int main()
{
int a,p,b;
scanf("%d%d%d",&p,&a,&b);
int ans=bsgs(a,b,p);
if(ans==-1)
{
printf("no solution\n");
}else{
printf("%d\n",ans);
}
return 0;
}
