头像

sichengzhou




离线:1天前


最近来访(26)
用户头像
ysc
用户头像
2805734199h
用户头像
cocodzh
用户头像
Cognition
用户头像
JavaScriptVue
用户头像
ZIMA
用户头像
Kafuu_Chino
用户头像
众生皆苦
用户头像
ZB_6
用户头像
jchhh
用户头像
AvastandhazyM
用户头像
baigeiguai
用户头像
敲代码敲代码
用户头像
雾慢了风景
用户头像
tibiks
用户头像
想胖成肥牛
用户头像
谢谢你
用户头像
篮网
用户头像
月色
用户头像
Tkybk_dz


请问Dancing Link恢复状态时为什么要倒着遍历十字链表?




sichengzhou
3个月前

为什么Tarjan求强连通分量算法中,在栈中的点就可以更新当前节点?




sichengzhou
2021-06-07 15:56

题目描述

给定一个由 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. 特殊数字

sichengzhou
2021-05-22 20:05
#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. 双端队列

sichengzhou
2021-05-22 19:41
#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. 双端队列

sichengzhou
2021-05-22 19:39
#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. 特殊数字

sichengzhou
2021-05-22 19:22
#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. 多项式乘法

sichengzhou
2021-05-13 17:43
#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

sichengzhou
2021-05-13 17:42
#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

sichengzhou
2021-05-13 17:41
#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;
}