头像

ZTEG

ZTOI




离线:4天前


活动打卡代码 AcWing 342. 道路与航线

ZTEG
5天前
#include<bits/stdc++.h>

using namespace std;

const int amou=2e5+90;
typedef pair<int,int> PII;

int cnt,nxt[amou],head[amou],ver[amou],edge[amou];
int n,mcp,msg,S;
int col[amou],colcnt;
int hh[amou],inde[amou],dis[amou];
queue<int> kl;
vector<int> V[amou];
bool we[amou];

void add(int a,int b,int c){
    nxt[++cnt]=head[a],head[a]=cnt,ver[cnt]=b,edge[cnt]=c;
}

void dfs_col(int i,int j){
    col[i]=j;
    V[j].push_back(i);
    for(int io=head[i];io;io=nxt[io])
    {
        int v=ver[io];
        if(!col[v]) dfs_col(v,j);
    }
}

void add2(int a,int b,int c){
    nxt[++cnt]=hh[a],hh[a]=cnt,ver[cnt]=b,edge[cnt]=c;
    inde[col[b]]++;
}

void work_huh(){
    memset(dis,0x3f,sizeof dis);
    dis[S]=0;
    while(!kl.empty())
    {
        int tou=kl.front();
        kl.pop();
        priority_queue<PII,vector<PII>,greater<PII> > pri;
        for(int j=0;j<V[tou].size();j++)
        {
            int v=V[tou][j];
            if(dis[v]!=0x3f3f3f3f) pri.push({dis[v],v});
            for(int io=hh[v];io;io=nxt[io])
            {
                int hh=ver[io];
                if(--inde[col[hh]]==0) kl.push(col[hh]);
            }
        }
        while(!pri.empty())
        {
            PII t=pri.top();
            pri.pop();
            int i=t.second;
            if(we[i]) continue;
            we[i]=1;
            for(int io=head[i];io;io=nxt[io])
            {
                int v=ver[io];
                if(dis[v]>dis[i]+edge[io])
                {
                    dis[v]=dis[i]+edge[io];
                    pri.push({dis[v],v});
                }
            }
            for(int io=hh[i];io;io=nxt[io])
            {
                int v=ver[io];
                dis[v]=min(dis[v],dis[i]+edge[io]);
            }
        }
    }
}

void put_it_out(){
    for(int i=1;i<=n;i++)
    {
        if(dis[i]==0x3f3f3f3f) printf("NO PATH\n");
        else printf("%d\n",dis[i]);
    }
}

int main(){
    scanf("%d%d%d%d",&n,&mcp,&msg,&S);
    for(int i=1;i<=mcp;i++)
    {
        int a,b,c;
        scanf("%d%d%d",&a,&b,&c);
        add(a,b,c);add(b,a,c);
    }
    for(int i=1;i<=n;i++)
        if(!col[i]) dfs_col(i,++colcnt);
    for(int i=1;i<=msg;i++)
    {
        int a,b,c;
        scanf("%d%d%d",&a,&b,&c);
        add2(a,b,c);
    }
    for(int i=1;i<=colcnt;i++) if(!inde[i]) kl.push(i);
    work_huh();
    put_it_out();

    return 0;
}


活动打卡代码 AcWing 341. 最优贸易

ZTEG
6天前
#include<bits/stdc++.h>
#define x first
#define y second

using namespace std;

const int N=2e5+90,amou=2e6+90;
typedef pair<int,int> PII;

int a[N];
int cnt,head[2*N],nxt[amou],ver[amou];
int D[amou],F[amou];
bool we[amou];
int hh[amou];
int n,m;

void add(int a,int b){
    nxt[++cnt]=head[a],head[a]=cnt,ver[cnt]=b;
    nxt[++cnt]=hh[b],hh[b]=cnt,ver[cnt]=a;
}

void Dijkstra(){
    priority_queue<PII,vector<PII>,greater<PII> >kl;
    memset(D,0x3f,sizeof D);
    memset(we,0,sizeof we);
    D[1]=a[1];
    kl.push({a[1],1});
    while(!kl.empty())
    {
        PII tou=kl.top();
        kl.pop();
        int i=tou.y;
        if(we[i]) continue;
        we[i]=1;
        for(int io=head[i];io;io=nxt[io])
        {
            int v=ver[io];
            if(D[v]>min(D[i],a[v]))
            {
                D[v]=min(D[i],a[v]);
                kl.push({D[v],v});
            }
        }
    }
}

void DDDij(){
    priority_queue<PII> kl;
    memset(we,0,sizeof we);
    kl.push({a[n],n});
    F[n]=a[n];
    while(!kl.empty())
    {
        PII tou=kl.top();
        kl.pop();
        int i=tou.y;
        if(we[i]) continue;
        we[i]=1;
        for(int io=hh[i];io;io=nxt[io])
        {
            int v=ver[io];
            if(F[v]<max(F[i],a[v]))
            {
                F[v]=max(F[i],a[v]);
                kl.push({F[v],v});
            }
        }
    }
}

int main(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++) scanf("%d",&a[i]);
    for(int i=1;i<=m;i++)
    {
        int a,b,c;
        scanf("%d%d%d",&a,&b,&c);
        add(a,b);
        if(c==2) add(b,a);
    }
    Dijkstra();
    DDDij();
    int as=0;
    for(int i=1;i<=n;i++) as=max(F[i]-D[i],as);
    printf("%d",as);

    return 0;
}


活动打卡代码 AcWing 340. 通信线路

ZTEG
7天前
#include<bits/stdc++.h>
#define x first
#define y second

using namespace std;

const int amou=2e5+90;
typedef pair<int,int> PII;

int n,m,k;
int nxt[amou],head[amou],ver[amou],cnt,edge[amou];
int maxl;
deque<PII> kl;
bool we[amou];
int dis[amou];

void add(int a,int b,int c){
    nxt[++cnt]=head[a],head[a]=cnt,ver[cnt]=b,edge[cnt]=c;
}

bool check(int x){
    kl.push_front({1,0});
    memset(we,0,sizeof we);
    memset(dis,0x3f,sizeof dis);
    dis[1]=0;
    while(!kl.empty())
    {
        PII tou=kl.front();
        kl.pop_front();
        int i=tou.x;
        if(we[i]) continue;
        we[i]=1;
        for(int io=head[i];io;io=nxt[io])
        {
            int v=ver[io];
            int t=(edge[io]>x);
            if(dis[v]>tou.y+t)
            {
                dis[v]=tou.y+t;
                if(t) kl.push_back({v,tou.y+t});
                else kl.push_front({v,tou.y+t});
            }
        }
    }
    return dis[n]<=k;
}

void work(){
    int l=1,r=maxl,as=0;
    while(l<=r)
    {
        int mid=l+r>>1;
        if(check(mid)) as=mid,r=mid-1;
        else l=mid+1;
    }
    if(as) printf("%d",as);
    else printf("-1");
}

int main(){
    scanf("%d%d%d",&n,&m,&k);
    for(int i=1;i<=m;i++)
    {
        int a,b,c;
        scanf("%d%d%d",&a,&b,&c);
        add(a,b,c);add(b,a,c);
        maxl=max(maxl,c);
    }
    work();

    return 0;
}


活动打卡代码 AcWing 181. 回转游戏

ZTEG
15天前
#include<bits/stdc++.h>

using namespace std;

const int amou=56;

int a[amou];
int maxdep;
int oppo[9];
char op[10]={'A','B','C','D','E','F','G','H'};
int pos[8]={7,8,9,12,13,16,17,18};
int f[1<<15];
int help[9][9]={
    {1,3,7,12,16,21,23},
    {2,4,9,13,18,22,24},
    {11,10,9,8,7,6,5},
    {20,19,18,17,16,15,14},
    {24,22,18,13,9,4,2},
    {23,21,16,12,7,3,1},
    {14,15,16,17,18,19,20},
    {5,6,7,8,9,10,11},
};

int H(){
    int s[4]={0};
    for(int i=0;i<8;i++) s[a[pos[i]]]++;
    if(s[1]>=s[2]&&s[1]>=s[3]) return 8-s[1];
    if(s[2]>=s[1]&&s[2]>=s[3]) return 8-s[2];
    else return 8-s[3];
}

bool check_right(){
    int s[4]={0},r=0;
    for(int i=0;i<8;i++) s[a[pos[i]]]++;
    for(int i=1;i<=3;i++) if(s[i]) r++;
    return r==1;
}

void operation(int x){
    int t=a[help[x][0]];
    for(int i=0;i<6;i++) a[help[x][i]]=a[help[x][i+1]];
    a[help[x][6]]=t;
}

bool dfs(int dep,int pre){
    if(dep+H()>maxdep) return false;
    if(check_right()) return true;
    for(int io=0;io<8;io++)
    {
        if(oppo[io]==pre) continue;
        operation(io);
        f[dep]=io;
        if(dfs(dep+1,op[io])) return true;
        operation(oppo[io]);
    }
    return false;
}

int main(){
    oppo[0]=5,oppo[5]=0,oppo[1]=4,oppo[4]=1;
    oppo[2]=7,oppo[7]=2,oppo[3]=6,oppo[6]=3;

    while(cin>>a[1],a[1])
    {
        for(int i=2;i<=24;i++) scanf("%d",&a[i]);
        maxdep=0;
        while(!dfs(0,-1)) maxdep++;
        if(!maxdep) printf("No moves needed");
        for(int i=0;i<maxdep;i++) printf("%c",'A'+f[i]);
        printf("\n%d\n",a[7]);
    }

    return 0;
}


活动打卡代码 AcWing 180. 排书

ZTEG
16天前
#include<bits/stdc++.h>

using namespace std;

const int amou=16;

int a[amou],n;
int maxdep;
int temp[7][amou];

int H(){
    int as=0;
    for(int i=1;i<n;i++)
        if(a[i]+1!=a[i+1]) as++;
    return ceil(1.0*as/3);
}

bool check_right(){
    for(int i=1;i<=n;i++)
        if(a[i]!=i) return false;
    return true;
}

bool IDA_star(int dep){
    if(dep+H()>maxdep) return false;
    if(check_right()) return true;

    for(int l=1;l<=n;l++)
    {
        for(int r=l;r<=n;r++)
        {
            for(int k=r+1;k<=n;k++)
            {
                memcpy(temp[dep],a,sizeof a);
                int t=l;
                for(int p=r+1;p<=k;p++) a[t++]=temp[dep][p];
                for(int p=l;p<=r;p++) a[t++]=temp[dep][p];
                if(IDA_star(dep+1)) return true;
                memcpy(a,temp[dep],sizeof a);
            }
        }
    }
    return false;
}

int main(){
    int t;
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d",&n);
        for(int i=1;i<=n;i++)
            scanf("%d",&a[i]);
        for(maxdep=0;maxdep<5;maxdep++)
            if(IDA_star(0)) break;
        if(maxdep<5) printf("%d\n",maxdep);
        else printf("5 or more\n");
    }

    return 0;
}


活动打卡代码 AcWing 171. 送礼物

ZTEG
16天前
#include<bits/stdc++.h>
#define in long long

using namespace std;

const int amou=47;

int wlim,n;
int w[amou],k;
int cnt,weight[1<<25];
in as;

void dfs(int i,in alr){
    if(i==k+1)
    {
        weight[++cnt]=alr;
        return;
    }
    dfs(i+1,alr);
    if(alr+w[i]<=wlim) dfs(i+1,alr+w[i]);
}

void dfs2(int i,in alr){
    if(i==n+1)
    {
        int l=1,r=cnt,h=1;
        while(l<=r)
        {
            int mid=l+r>>1;
            if(alr+weight[mid]<=wlim) l=mid+1,h=mid;
            else r=mid-1;
        }
        as=max(as,alr+weight[h]);
        return;
    }
    dfs2(i+1,alr);
    if(alr+w[i]<=wlim) dfs2(i+1,alr+w[i]);
}

int main(){
    scanf("%d%d",&wlim,&n);
    for(int i=1;i<=n;i++) scanf("%d",&w[i]);
    sort(w+1,w+n+1);
    reverse(w+1,w+n+1);
    k=n/2;
    dfs(1,0);

    sort(weight+1,weight+cnt+1);
    cnt=unique(weight+1,weight+cnt+1)-weight-1;
    dfs2(k+1,0);
    printf("%lld",as);

    return 0;
}


活动打卡代码 AcWing 170. 加成序列

ZTEG
16天前
#include<bits/stdc++.h>

using namespace std;

const int amou=250;

int n;
int maxdep;
int f[amou];

bool dfs(int dep){
//  printf("%d ",f[dep-1]);
    if(dep==maxdep+1) return n==f[maxdep];
    bool we[amou]={0};
    for(int i=dep-1;i>=1;i--)
    {
        for(int j=i;j>=1;j--)
        {
            int s=f[i]+f[j];
            if(we[s]||s>n||s<=f[dep-1]) continue;
            we[s]=1;
            f[dep]=s;
            if(dfs(dep+1)) return true;
        }
    }
    return false;
}

int main(){
    f[1]=1;
    while(cin>>n,n)
    {
//      memset(f,0,sizeof f);
        for(maxdep=2;maxdep<=n;maxdep++)
            if(dfs(2)) break;
        for(int i=1;i<=maxdep;i++) printf("%d ",f[i]);
        printf("\n");
    }

    return 0;
}


活动打卡代码 AcWing 168. 生日蛋糕

ZTEG
16天前
#include<bits/stdc++.h>
using namespace std;
int n,m;
int area;
int minarea=0x3f3f3f3f;
void dfs(int x,int v,int maxr,int maxh){
    if(!x)
    {
        if(v) return;
        else
        {
            minarea=min(minarea,area);
            return;
        }
    }
    if(v/maxr+area>minarea) return;
    if(v<x*x*x) return;
    if(v<=0||area>minarea||area+2*x*x>minarea) return;
    for(int rr=maxr;rr>=x;rr--)
    {
        if(x==m) area=rr*rr;
        for(int hh=maxh;hh>=x;hh--)
        {
            area+=2*rr*hh;
            dfs(x-1,v-rr*rr*hh,rr-1,hh-1);
            area-=2*rr*hh;
        }
    }
}
int main(){
    scanf("%d%d",&n,&m);
    dfs(m,n,sqrt(n),n);
    if(minarea==0x3f3f3f3f) printf("0");
    else printf("%d",minarea);
    return 0;
}


活动打卡代码 AcWing 167. 木棒

ZTEG
18天前
#include<bits/stdc++.h>

using namespace std;

const int amou=67;

int n,a[amou];
int sum;
bool we[amou];
int aimn,len,las[amou];

bool cmp(int a,int b){
    return a>b;
}

bool dfs(int i,int st,int rem){
    if(!rem)
    {
        if(i==aimn)
        {
            printf("%d\n",len);
            return true;
        }
        for(int j=1;j<=n;j++)
        {
            if(!we[j])
            {
                we[j]=1;
                if(dfs(i+1,j,len-a[j])) return true;
                we[j]=0;
                return false;
            }
        }
    }
    int l=st+1,r=n;
    while(l<r)
    {
        int mid=l+r>>1;
        if(a[mid]<=rem) r=mid;
        else l=mid+1;
    }
    for(int j=r;j<=n;j++)
    {
        if(!we[j])
        {
            we[j]=1;
            if(dfs(i,j,rem-a[j])) return true;
            we[j]=0;
            if(rem==a[j]) return false;
            j=las[j];
        }
    }
    return false;
}

int main(){
    while(scanf("%d",&n),n)
    {
        sum=0;
        memset(we,0,sizeof we);
        for(int i=1;i<=n;i++)
        {
            scanf("%d",&a[i]);
            sum+=a[i];
        }
        sort(a+1,a+n+1,cmp);
        las[n]=n;
        for(int i=n-1;i>=1;i--)
        {
            if(a[i]==a[i+1]) las[i]=las[i+1];
            else las[i]=i;
        }
        bool fl=0;
        for(len=a[1];!fl&&len<=sum/2;len++)
        {
            if(sum%len) continue;
            aimn=sum/len;
            we[1]=1;
            if(dfs(1,1,len-a[1])) fl=1;
            we[1]=0;
        }
        if(!fl) printf("%d\n",sum);
    }

    return 0;
}


活动打卡代码 AcWing 166. 数独

ZTEG
18天前
#include<bits/stdc++.h>

using namespace std;

const int amou=110,N=9;

char s[amou];
int row[amou],col[amou],group[6][6];
int ones[1<<N],g[1<<N];

void init(){
    for(int i=1;i<=9;i++) row[i]=col[i]=(1<<9)-1;
    for(int i=1;i<=3;i++)
        for(int j=1;j<=3;j++)
            group[i][j]=(1<<9)-1;
}

int lowbit(int x){
    return x&-x;
}

int get(int i,int j){
    return row[i]&col[j]&group[(i-1)/3+1][(j-1)/3+1];
}

bool dfs(int rem){
    if(!rem) return true;
    int temp=0x3f3f3f3f,sti=0,stj=0;
    for(int i=1;i<=9;i++)
    {
        for(int j=1;j<=9;j++)
        {
            int pos=(i-1)*9+j-1;
            if(s[pos]!='.') continue;
            int t=ones[get(i,j)];
            if(t<temp) temp=t,sti=i,stj=j;
        }
    }
    for(int i=get(sti,stj);i;i-=lowbit(i))
    {
        int lowb=lowbit(i);
        row[sti]-=lowb;
        col[stj]-=lowb;
        int pos=(sti-1)*9+stj-1;
        s[pos]=g[lowb]+'0';
        group[((sti-1)/3)+1][(stj-1)/3+1]-=lowb;
        if(dfs(rem-1)) return true;
        row[sti]+=lowb;
        col[stj]+=lowb;
        s[pos]='.';
        group[((sti-1)/3)+1][(stj-1)/3+1]+=lowb;
    }
    return false;
}

int main(){
    for(int i=0;i<9;i++)
    {
        g[1<<i]=i+1;
    }
    for(int i=1;i<(1<<9);i++)
    {
        int s=0;
        for(int j=i;j;j-=lowbit(j))
            s++;
        ones[i]=s;
    }
    while(cin>>s,strcmp(s,"end"))
    {
        int goal=0;
        init();
        for(int i=0;i<strlen(s);i++)
        {
            if(s[i]=='.')
                goal++;
            else
            {
                int t=s[i]-'1';
                int x=i/9+1,y=i%9+1;
                row[x]-=(1<<t);
                col[y]-=(1<<t);
                group[(x-1)/3+1][(y-1)/3+1]-=(1<<t);
            }
        }
        dfs(goal);
        cout<<s<<endl;
    }

    return 0;
}