头像

lixiaoqian_qwq

SH OIer




离线:15小时前


最近来访(1146)
用户头像
理塘丁真_
用户头像
CCC_5
用户头像
星光璀璨
用户头像
太雪菜
用户头像
Vodka编程菜菜
用户头像
超级无敌霸王龙
用户头像
陌上花开Charlie
用户头像
acwing_gza
用户头像
这道题有点难耶
用户头像
锦木千束
用户头像
Shift.
用户头像
芒果黄桃冰
用户头像
大魔王001
用户头像
用户头像
cjlworld
用户头像
林慢慢
用户头像
湖北卒.
用户头像
Aigrl
用户头像
芒叉味阿米
用户头像
垫底抽風

活动打卡代码 AcWing 348. 沙漠之王

AcWing 348. 沙漠之王

#include <cstdio>
#include <cmath>
#include <algorithm>
#include <cstring>
#define sq(x) ((x)*(x))
using namespace std ;
const int N=1010,M=N*N ;
const double eps=1e-6 ;
int x[N],y[N],h[N] ;
double v[N][N],c[N][N] ;
double dis[N] ;
bool vis[N] ;
int n ;
inline bool check(double x)
{
    memset(dis,0xc2,sizeof dis) ;
    memset(vis,0,sizeof vis) ;
    dis[1]=0 ;
    double ans=0 ;
    for(int i=1;i<n;i++)
    {
        int t=0 ;
        for(int j=1;j<=n;j++) if(!vis[j]&&(!t||dis[t]<dis[j])) t=j ;
        vis[t]=true ;
        for(int j=1;j<=n;j++) if(!vis[j]) dis[j]=max(dis[j],c[j][t]-x*v[j][t]) ;
    }
    for(int i=2;i<=n;i++) ans+=dis[i] ;
    return ans>=0 ;
}
int main()
{
    while(~scanf("%d",&n),n)
    {
        for(int i=1;i<=n;i++) scanf("%d%d%d",&x[i],&y[i],&h[i]) ;
        double r=1e8 ;
        for(int i=1;i<=n;i++)
            for(int j=1;j<i;j++)
            {
                v[i][j]=v[j][i]=abs(h[i]-h[j]) ;
                c[i][j]=c[j][i]=sqrt(sq(x[i]-x[j])+sq(y[i]-y[j])) ;
                // r=max(r,c[i][j]/v[i][j]) ;
            }
        double l=0 ;
        while(r-l>eps)
        {
            double mid=(l+r)/2 ;
            if(check(mid)) l=mid ;
            else r=mid ;
        }
        printf("%.3lf\n",1/l) ;
    }
    return 0 ;
}


活动打卡代码 AcWing 346. 走廊泼水节

AcWing 346. 走廊泼水节

#include <iostream>
#include <algorithm>
using namespace std ;
const int N=6010 ;
int p[N],s[N] ;
struct edge
{
    int a,b,w ;
    bool operator<(edge &k)
    {
        return w<k.w ;
    }
}edges[N] ;
int find(int x)
{
    return p[x]==x?x:p[x]=find(p[x]) ; 
}
int main()
{
    int t ;
    scanf("%d",&t) ;
    while(t--)
    {
        int n ;
        scanf("%d",&n) ;
        for(int i=1;i<n;i++)
        {
            int a,b,w ;
            scanf("%d%d%d",&a,&b,&w) ;
            edges[i]={a,b,w} ;
        }
        sort(edges+1,edges+n) ;
        for(int i=1;i<=n;i++)
        {
            p[i]=i ;
            s[i]=1 ;
        }
        int res=0 ;
        for(int i=1;i<n;i++)
        {
            int a=edges[i].a ;
            int b=edges[i].b ;
            int w=edges[i].w ;
            a=find(a),b=find(b) ;
            if(a!=b)
            {
                res+=(s[a]*s[b]-1)*(w+1) ;
                p[a]=b ;
                s[b]+=s[a] ;
            }
        }
        printf("%d\n",res) ;
    }
    return 0 ;
}


活动打卡代码 AcWing 345. 牛站

AcWing 345. 牛站

#include <iostream>
#include <algorithm>
#include <cstring>
#include <unordered_map>
using namespace std ;
const int N=210 ;
int res[N][N] ;
int g[N][N] ;
int n,t,s,e ;
int cnt ;
unordered_map<int,int> id ;
void mul(int a[][N],int b[][N])
{
    int tmp[N][N] ;
    memset(tmp,0x3f,sizeof tmp) ;
    for(int k=1;k<=cnt;k++)
        for(int i=1;i<=cnt;i++)
            for(int j=1;j<=cnt;j++)
                tmp[i][j]=min(tmp[i][j],a[i][k]+b[k][j]) ;
    memcpy(a,tmp,sizeof tmp) ;
}
void qmi()
{
    memset(res,0x3f,sizeof res) ;
    for(int i=1;i<=cnt;i++)
        res[i][i]=0 ;
    while(n)
    {
        if(n&1) mul(res,g) ;
        mul(g,g) ;
        n>>=1 ;
    }
}
int main()
{
    scanf("%d%d%d%d",&n,&t,&s,&e) ;
    memset(g,0x3f,sizeof g) ;
    if(!id.count(s)) id[s]=++cnt ;
    if(!id.count(e)) id[e]=++cnt ;
    s=id[s],e=id[e] ;
    while(t--)
    {
        int a,b,c ;
        scanf("%d%d%d",&c,&a,&b) ;
        if(!id.count(a)) id[a]=++cnt ;
        if(!id.count(b)) id[b]=++cnt ;
        a=id[a],b=id[b] ;
        g[a][b]=g[b][a]=min(g[a][b],c) ;
    }
    qmi() ;
    printf("%d",res[s][e]) ;
    return 0 ;
}


活动打卡代码 AcWing 344. 观光之旅

AcWing 344. 观光之旅

#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std ;
const int N=110,INF=0x3f3f3f3f ;
int n,m ;
int g[N][N],d[N][N] ;
int pos[N][N] ;
int path[N],cnt ;
void get_path(int i,int j)
{
    int k=pos[i][j] ;
    if(!k) return ;
    get_path(i,k) ;
    path[cnt++]=k ;
    get_path(k,j) ;
}
int main()
{
    scanf("%d%d",&n,&m) ;
    memset(g,0x3f,sizeof g) ;
    for(int i=1;i<=n;i++)
        g[i][i]=0 ;
    while(m--)
    {
        int a,b,c ;
        scanf("%d%d%d",&a,&b,&c) ;
        g[a][b]=g[b][a]=min(g[a][b],c) ;
    }
    memcpy(d,g,sizeof g) ;
    int res=INF ;
    for(int k=1;k<=n;k++)
    {
        for(int i=1;i<k;i++)
            for(int j=1;j<i;j++)
                if((long long)d[i][j]+g[j][k]+g[k][i]<res)
                {
                    res=d[i][j]+g[j][k]+g[k][i] ;
                    cnt=0 ;
                    path[cnt++]=i ;
                    get_path(i,j) ;
                    path[cnt++]=j ;
                    path[cnt++]=k ;
                }
        for(int i=1;i<=n;i++)   
            for(int j=1;j<=n;j++)
                if(d[i][j]>d[i][k]+d[k][j])
                {
                    d[i][j]=d[i][k]+d[k][j] ;
                    pos[i][j]=k ;
                }
    }
    if(res==INF) puts("No solution.") ;
    else for(int i=0;i<cnt;i++) printf("%d ",path[i]) ;
    return 0 ;
}


活动打卡代码 AcWing 343. 排序

AcWing 343. 排序

#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std ;
const int N=26 ;
int n,m ;
bool d[N][N] ;
bool st[N] ;
void floyd(int a,int b)
{
    for(int i=0;i<n;i++)
        for(int j=0;j<n;j++)
        {
            if(d[i][a]) d[i][b]=true ;
            if(d[b][j]) d[a][j]=true ;
            if(d[i][a]&&d[b][j]) d[i][j]=true ;
        }
}
int tp()
{
    for(int i=0;i<n;i++)
        if(d[i][i]) return 1 ;
    for(int i=0;i<n;i++)
        for(int j=0;j<i;j++)
            if((!d[i][j])&&(!d[j][i])) return 0 ;
    return 2 ;
}
char get_min()
{
    for(int i=0;i<n;i++)
        if(!st[i])
        {
            bool flag=true ;
            for(int j=0;j<n;j++)
                if((!st[j])&&d[j][i])
                {
                    flag=false ;
                    break ;
                }
            if(flag)
            {
                st[i]=true ;
                return 'A'+i ;
            }
        }
    return 'x' ;
}
int main()
{
    while(~scanf("%d%d",&n,&m),n||m)
    {
        int type=0 ;
        int t ;
        memset(d,false,sizeof d) ;
        for(int i=1;i<=m;i++)
        {
            string str ;
            cin >> str ;
            int a=str[0]-'A',b=str[2]-'A' ;
            if(!type)
            {
                d[a][b]=true ;
                floyd(a,b) ;
                type=tp() ;
                if(type) t=i ;
            }
        }
        if(!type) puts("Sorted sequence cannot be determined.") ;
        else if(type==1) printf("Inconsistency found after %d relations.\n",t) ;
        else
        {
            printf("Sorted sequence determined after %d relations: ",t) ;
            memset(st,false,sizeof st) ;
            for(int i=0;i<n;i++)
                printf("%c",get_min()) ;
            puts(".") ;
        }
    }
    return 0 ;
}


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

AcWing 342. 道路与航线

#include <bits/stdc++.h>
using namespace std ;
const int N=300010 ;
int e[N],ne[N],h[N],w[N],idx ;
queue<int> q ;
vector<int> blocks[N] ;
int bcnt ;
int in[N],dis[N],blk[N] ;
int n,mr,mp,s ;
void dfs(int u,int bcnt)
{
    blk[u]=bcnt ;
    blocks[bcnt].push_back(u) ;
    for(int i=h[u];~i;i=ne[i])
        if(!blk[e[i]]) dfs(e[i],bcnt) ;
}
void add(int a,int b,int c)
{
    e[idx]=b,w[idx]=c,ne[idx]=h[a],h[a]=idx++ ;
}
void dijk(int b)
{
    priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>> heap ;
    for(auto i:blocks[b]) heap.push({dis[i],i}) ;
    static bool st[N] ;
    memset(st,false,sizeof st) ;
    while(heap.size())
    {
        auto t_=heap.top() ;
        heap.pop() ;
        int t=t_.second ;
        if(st[t]) continue ;
        st[t]=true ;
        for(int i=h[t];~i;i=ne[i])
        {
            int j=e[i] ;
            if(blk[j]!=blk[t]&&!(--in[blk[j]])) q.push(blk[j]) ;
            if(dis[t]+w[i]<dis[j])
            {
                dis[j]=dis[t]+w[i] ;
                if(blk[j]==blk[t]) heap.push({dis[j],j}) ;
            }
        }
    }
}
void topdijk()
{
    memset(dis,0x3f,sizeof dis) ;
    dis[s]=0 ;
    for(int i=1;i<=bcnt;i++)
        if(!in[i]) q.push(i) ;
    while(q.size())
    {
        int t=q.front() ;
        q.pop() ;
        dijk(t) ;
    }
}
int main()
{
    cin >> n >> mr >> mp >> s ;
    memset(h,-1,sizeof h) ;
    while(mr--)
    {
        int a,b,c ;
        cin >> a >> b >> c ;
        add(a,b,c),add(b,a,c) ;
    }
    for(int i=1;i<=n;i++)
        if(!blk[i]) dfs(i,++bcnt) ;
    while(mp--)
    {
        int a,b,c ;
        cin >> a >> b >> c ;
        in[blk[b]]++ ;
        add(a,b,c) ;
    }
    topdijk() ;
    for(int i=1;i<=n;i++)
        if(dis[i]>1e9) puts("NO PATH") ;
        else printf("%d\n",dis[i]) ;
    return 0 ;
}


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

AcWing 341. 最优贸易

#include <iostream>
#include <queue>
#include <cstring>
#include <algorithm>
using namespace std ;
const int N=100010,M=2000010 ;
int n,m ;
int price[N] ;
int hs[N],ht[N],e[M],ne[M],idx ;
int dmin[N],dmax[N] ;
bool st[N] ;
void add(int *h,int a,int b)
{
    e[idx]=b ;
    ne[idx]=h[a] ;
    h[a]=idx++ ;
}
void spfa(int *h,int *dis,bool mode)
{
    queue<int> q ;
    if(mode)
    {
        memset(dis,0x3f,sizeof dmin) ;
        dis[1]=price[1] ;
        q.push(1) ;
    }
    else
    {
        memset(dis,-0x3f,sizeof dmax) ;
        dis[n]=price[n] ;
        q.push(n) ;
    }
    while(q.size())
    {
        int t=q.front() ;
        q.pop() ;
        st[t]=false ;
        for(int i=h[t];~i;i=ne[i])
        {
            int j=e[i] ;
            if((dis[j]>min(dis[t],price[j])&&mode)||((dis[j]<max(dis[t],price[j]))&&!mode))
            {
                if(mode) dis[j]=min(dis[t],price[j]) ;
                else dis[j]=max(dis[t],price[j]) ;
                if(!st[j])
                {
                    st[j]=true ;
                    q.push(j) ;
                }
            }
        }
    }
}
int main()
{
    scanf("%d%d",&n,&m) ;
    for(int i=1;i<=n;i++)
        scanf("%d",&price[i]) ;
    memset(hs,-1,sizeof hs) ;
    memset(ht,-1,sizeof ht) ;
    while(m--)
    {
        int a,b,c ;
        scanf("%d%d%d",&a,&b,&c) ;
        add(hs,a,b) ;
        add(ht,b,a) ;
        if(c==2) 
        {
            add(hs,b,a) ;
            add(ht,a,b) ;
        }
    }
    spfa(hs,dmin,true) ;
    spfa(ht,dmax,false) ;
    int res=0 ;
    for(int i=1;i<=n;i++)
        res=max(res,dmax[i]-dmin[i]) ;
    printf("%d",res) ;
    return 0 ;
}


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

AcWing 340. 通信线路

#include <iostream>
#include <deque>
#include <cstring>
#include <algorithm>
using namespace std ;
const int N=1010,M=20010 ;
int n,p,k ;
int h[N],e[M],ne[M],w[M],idx ;
int dis[N] ;
deque<int> q ;
bool st[N] ;
void add(int a,int b,int c)
{
    e[idx]=b ;
    w[idx]=c ;
    ne[idx]=h[a] ;
    h[a]=idx++ ;
}
bool check(int bound)
{
    memset(st,false,sizeof st) ;
    memset(dis,0x3f,sizeof dis) ;
    dis[1]=0 ;
    q.push_back(1) ;
    while(q.size())
    {
        int t=q.front() ;
        q.pop_front() ;
        if(st[t]) continue ;
        st[t]=true ;
        for(int i=h[t];~i;i=ne[i])
        {
            int j=e[i] ;
            bool v=w[i]>bound ;
            if(dis[j]>dis[t]+v)
            {
                dis[j]=dis[t]+v ;
                if(!v) q.push_front(j) ;
                else q.push_back(j) ;
            }
        }
    }
    return dis[n]<=k ;
}
int main()
{
    scanf("%d%d%d",&n,&p,&k) ;
    memset(h,-1,sizeof h) ;
    while(p--)
    {
        int a,b,c ;
        scanf("%d%d%d",&a,&b,&c) ;
        add(a,b,c) ;
        add(b,a,c) ;
    }
    int l=0,r=1e6+1 ;
    while(l<r)
    {
        int mid=l+r>>1 ;
        if(check(mid)) r=mid ;
        else l=mid+1 ;
    }
    if(r==1e6+1) r=-1 ;
    printf("%d",r) ;
    return 0 ;
}


活动打卡代码 AcWing 297. 赤壁之战

AcWing 297. 赤壁之战

#include <cstdio>
#include <cstring>
#include <algorithm>
#define lowbit(i) (i&(-i))
using namespace std ;
const int N=1010 ;
const int mod=1e9+7 ;
struct node { int val,idx ; bool operator < (node &x) const { return val<x.val ; } } arr[N] ;
int a[N] ;
int f[N][N] ;
int tr[N] ;
int n,m ;
inline void add(int x,int v)
{
    for(int i=x;i<=n;i+=lowbit(i)) (tr[i]+=v)%=mod ;
}
inline int query(int x)
{
    int ans=0 ;
    for(int i=x;i;i-=lowbit(i)) (ans+=tr[i])%=mod ;
    return ans ;
}
// f[j][k] 严格单调递增数量为j 上一个结尾为arr[k] 求方案数
int main()
{
    int t ;
    scanf("%d",&t) ;
    for(int cs=1;cs<=t;cs++)
    {
        scanf("%d%d",&n,&m) ;
        for(int i=1;i<=n;i++) scanf("%d",&arr[i].val),arr[i].idx=i ;
        sort(arr+1,arr+n+1) ;
        for(int i=1,cnt=1;i<=n;i++)
        {
            a[arr[i].idx]=cnt ;
            if(arr[i].val<arr[i+1].val) cnt++ ;
        }
        memset(f,0,sizeof f) ;
        for(int i=1;i<=n;i++) f[1][i]=1 ;
        for(int j=2;j<=m;j++)
        {
            memset(tr,0,sizeof tr) ;
            for(int i=1;i<=n;i++)
            {
                f[j][i]=query(a[i]-1) ;
                add(a[i],f[j-1][i]) ;
            }
        }
        int ans=0 ;
        for(int i=1;i<=n;i++) (ans+=f[m][i])%=mod ;
        printf("Case #%d: %d\n",cs,ans) ;
    }
    return 0 ;
}


活动打卡代码 AcWing 296. 清理班次2

AcWing 296. 清理班次2

#include <cstdio>
#include <cstring>
#include <queue>
#define int long long
using namespace std ;
const int N=100010 ;
int e[N],ne[N],h[N],w[N],idx ;
int dis[N] ;
bool st[N] ;
int n,m,E ;
inline void add(int a,int b,int c) { /*printf("%d %d\n",a,b),*/e[idx]=b,ne[idx]=h[a],w[idx]=c,h[a]=idx++ ; }
inline int spfa(int start,int ed)
{
    memset(dis,0x3f,sizeof dis) ;
    dis[start]=0 ;
    queue<int> q ;
    q.push(start) ;
    while(q.size())
    {
        int t=q.front() ;
        q.pop() ;
        st[t]=false ;
        for(int i=h[t];~i;i=ne[i])
        {
            int j=e[i] ;
            if(dis[j]>dis[t]+w[i])
            {
                dis[j]=dis[t]+w[i] ;
                if(!st[j]) q.push(j),st[j]=true ;
            }
        }
    }
    return dis[ed]>1e18?-1:dis[ed] ;
}
signed main()
{
    scanf("%lld%lld%lld",&n,&m,&E),E-=m ;
    memset(h,-1,sizeof h) ;
    for(int i=1;i<=n;i++)
    {
        int x,y,z ;
        scanf("%lld%lld%lld",&x,&y,&z) ;
        if(x>m+E||y<m) continue ;
        add(max(x-m,0ll),min(y-m,E)+1,z) ;
    }
    for(int i=0;i<=E;i++) add(i+1,i,0) ;
    printf("%lld",spfa(0,E+1)) ;
    return 0 ;
}