头像

zmy


访客:744

离线:4小时前


活动打卡代码 AcWing 1081. 度的数量

zmy
7小时前

度的数量(数位DP)

#include<cstdio>
#include<vector>
#include<iostream>
#include<algorithm>
const int N = 35;
using namespace std;
int f[N][N];
int K,B;
void init()
{
    for(int i=0;i < N;i++)
    {
        for(int j = 0;j <= i;j++)
        {
            if(j == 0) f[i][j] = 1;
            else f[i][j] = f[i-1][j] + f[i-1][j-1];
        }
    }
}
int dp(int n)
{
    if(n == 0) return 0;
    vector<int> v;
    while(n){
        v.push_back(n % B);
        n /= B;
    }
    int last=0,res=0;
    for(int i=v.size()-1;i>=0;i--)
    {
        int x = v[i];
        if(x)
        {
            res+=f[i][K-last];
            if(x > 1){
                if(K - last - 1 >= 0) {
                    res += f[i][K - last - 1];
                    break;
                }
            }
            else{
                last++;
                if(last > K) break;
            }
        }
        if(!i&&last==K) res++;
    }
    return res;
}
int main()
{
    init();
    int x,y;
    cin >> x >> y >> K >> B;
    cout << dp(y) - dp(x-1) << endl;
    return 0;
}


活动打卡代码 AcWing 237. 程序自动分析

zmy
1天前

程序自动分析(并查集+离散化)

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<unordered_map>
using namespace std;
const int N = 1000010;
unordered_map<int,int> mp;
int n,t,s;
struct query{
    int x,y,type;
}q[N];
int p[N];
int find(int root)
{
    while(root!=p[root])
    {
        root=p[root]=p[p[root]];
    }
    return root;
}
int get(int x)
{
    if(mp.count(x)==0) mp[x] = ++s;
    return mp[x];
}
int main()
{
    scanf("%d",&t);
    while(t--)
    {
        s=0;
        mp.clear();
        scanf("%d",&n);

        for(int i=1;i<=n;i++)
        {
            int x,y,type;
            scanf("%d%d%d",&x,&y,&type);
            q[i]={get(x),get(y),type};
        }
        for(int i=1;i<=s;i++) p[i]=i;
        for(int i=1;i<=n;i++)
        {
            if(q[i].type==1)
            {
                int a=find(q[i].x),b=find(q[i].y);
                if(a!=b) p[a]=b;
            }
        }
        bool flag=false;
        for(int i=1;i<=n;i++)
        {
            if(q[i].type==0)
            {
                int a=find(q[i].x),b=find(q[i].y);
                if(a==b)
                {
                    flag=true;
                    break;
                }
            }
        }
        if(flag) puts("NO");
        else puts("YES");
    }
    return 0;
}


活动打卡代码 AcWing 1252. 搭配购买

zmy
1天前

搭配购买(并查集+01背包)

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
const int N = 10010;
int price[N],value[N];
int p[N];
int find(int root)
{
    while(root!=p[root])
    {
        root=p[root]=p[p[root]];
    }
    return root;
}
int dp[N];
int main()
{
    int n,m,w;
    scanf("%d%d%d",&n,&m,&w);
    for(int i=1;i<=n;i++) p[i]=i;
    for(int i=1;i<=n;i++) scanf("%d%d",&price[i],&value[i]);
    while(m--)
    {
        int a,b;
        scanf("%d%d",&a,&b);
        a=find(a),b=find(b);
        if(a!=b) {
            p[a]=b;
            price[b]+=price[a];
            value[b]+=value[a];
        }
    }
    for(int i=1;i<=n;i++)
    {
        if(p[i]==i)
        {
            for(int j=w;j>=price[i];j--)
            {
                dp[j]=max(dp[j],dp[j-price[i]]+value[i]);
            }
        }
    }
    cout<<dp[w]<<endl;
    return 0;
}


活动打卡代码 AcWing 1250. 格子游戏

zmy
1天前

格子游戏(并查集$+$坐标映射)

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
const int N = 40010;
int p[N];
int n,m;
int find(int root)
{
    while(root!=p[root])
    {
        root=p[root]=p[p[root]];
    }
    return root;
}
int get(int x,int y)
{
    return x*n+y+1;
}
int main()
{

    cin>>n>>m;
    for(int i=0;i<n*n;i++) p[i]=i;
    int ans=0;
    for(int i=1;i<=m;i++)
    {
        int x,y;
        char op;
        cin>>x>>y>>op;
        x--,y--;
        int a=get(x,y);
        int b;
        if(op=='D') b=get(x+1,y);
        else b=get(x,y+1);
        a=find(a);b=find(b);
        if(a==b)
        {
            ans=i;
            break;
        }
        else p[a]=b;
    }
    if(ans==0) puts("draw");
    else cout<<ans<<endl;
    return 0;
}


活动打卡代码 AcWing 1171. 距离

zmy
3天前

距离($tanjan$离线求$LCA$,另需$DFS$和并查集做辅助)

#include<vector>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
typedef pair<int,int> PII;
const int N = 10010,M = 20020;
int h[N],e[M],w[M],ne[M],idx;
int dist[N];
int p[N];
int st[N],ans[M];
vector<PII> query[N];
void add(int a,int b,int c)
{
    e[idx]=b; w[idx]=c; ne[idx]=h[a]; h[a]=idx++;
}
int find(int root)
{
    while(root!=p[root])
    {
        root=p[root]=p[p[root]];
    }
    return root;
}
void dfs(int u,int fa)
{
    for(int i=h[u];i!=-1;i=ne[i])
    {
        int j=e[i];
        if(j==fa) continue;
        dist[j]=dist[u]+w[i];
        dfs(j,u);
    }
}
void tarjan(int u)
{
    st[u]=1;
    for(int i=h[u];i!=-1;i=ne[i])
    {
        int j=e[i];
        if(!st[j])
        {
            tarjan(j);
            p[j]=u;
        }
    }
    for(auto item:query[u])
    {
        int x=item.first,y=item.second;
        if(st[x]==2)
        {
            int anc=find(x);
            ans[y]=dist[x]+dist[u]-2*dist[anc];
        }
    }
    st[u]=2;
}
int main()
{
    int n,m;
    scanf("%d%d",&n,&m);
    memset(h,-1,sizeof h);
    for(int i=1;i<=n-1;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<=m;i++)
    {
        int a,b;
        scanf("%d%d",&a,&b);
        if(a!=b){
            query[a].push_back({b,i});
            query[b].push_back({a,i});
        }
    }
    for(int i=1;i<=n;i++) p[i]=i;
    dfs(1,-1);
    tarjan(1);
    for(int i=1;i<=m;i++)
    {
        cout<<ans[i]<<endl;
    }
    return 0;
}



zmy
4天前

最长上升子序列(DP)

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
const int N = 1010;
int dp[N],a[N];
int main()
{
    int n;
    scanf("%d",&n);
    for(int i=1;i<=n;i++) scanf("%d",&a[i]),dp[i]=1;
    for(int i=1;i<=n;i++)
    {
        for(int j=i-1;j>=1;j--)
        {
            if(a[i]>a[j])
            {
                dp[i]=max(dp[i],dp[j]+1);
            }
        }
    }
    int ans=0;
    for(int i=1;i<=n;i++)
    {
        ans=max(ans,dp[i]);
    }
    cout<<ans<<endl;
    return 0;
}


活动打卡代码 AcWing 1172. 祖孙询问

zmy
4天前

祖孙询问(倍增在线求LCA)

#include<queue>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
const int N = 40010,M = 80020;
int h[N],e[M],ne[M],idx;
int depth[N];
int p[N][20];
void add(int a,int b)
{
    e[idx]=b; ne[idx]=h[a]; h[a]=idx++;
}
void bfs(int root)
{
    memset(depth,0x3f,sizeof depth);
    depth[0]=0,depth[root]=1;
    queue<int> q;
    q.push(root);
    while(q.size())
    {
        int t=q.front();q.pop();
        for(int i=h[t];i!=-1;i=ne[i])
        {
            int j=e[i];
            if(depth[j]>depth[t]+1)
            {
                depth[j]=depth[t]+1;
                q.push(j);
                p[j][0]=t;
                for(int k=1;k<=15;k++)
                {
                    p[j][k]=p[p[j][k-1]][k-1];
                }
            }
        }
    }
}
int lca(int a,int b)
{
    if(depth[a]<depth[b]) swap(a,b);
    for(int i=15;i>=0;i--)
    {
        if(depth[p[a][i]]>=depth[b])
        {
            a=p[a][i];
        }
    }
    if(a==b) return a;
    for(int i=15;i>=0;i--)
    {
        if(p[a][i]!=p[b][i])
        {
            a=p[a][i];
            b=p[b][i];
        }
    }
    return p[a][0];
}
int main()
{
    int n;
    scanf("%d",&n);
    memset(h,-1,sizeof h);
    int root=0;
    for(int i=1;i<=n;i++)
    {
        int a,b;
        scanf("%d%d",&a,&b);
        if(b==-1) root=a;
        else add(a,b),add(b,a);
    }
    bfs(root);
    int m;
    scanf("%d",&m);
    while(m--)
    {
        int a,b,p;
        scanf("%d%d",&a,&b);
        p=lca(a,b);
        if(p==a) puts("1");
        else if(p==b) puts("2");
        else puts("0");
    }
    return 0;
}



zmy
6天前

$Kruskal$算法求最小生成树

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
const int N=200010;
int p[N];
struct Edge{
    int x,y,w;
    bool operator < (const Edge& t)
    {
        return w < t.w;
    }
}e[N];
int find(int root)
{
    while(root!=p[root])
    {
        root=p[root]=p[p[root]];
    }
    return root;
}
int main()
{
    int n,m;
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++) p[i]=i;
    for(int i=1;i<=m;i++)
    {
        scanf("%d%d%d",&e[i].x,&e[i].y,&e[i].w);
    }
    sort(e+1,e+m+1);
    int cnt=0,res=0;
    for(int i=1;i<=m;i++)
    {
        int a=e[i].x,b=e[i].y,w=e[i].w;
        a=find(a);b=find(b);
        if(a!=b)
        {
            res+=w;
            p[a]=b;
            cnt++;
        }
    }
    if(cnt<n-1) cout<<"impossible"<<endl;
    else cout<<res<<endl;

}



zmy
7天前

$Dijkstra$求最短路(堆优化版)

#include<queue>
#include<cstdio>
#include<vector>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
const int N=150010;
typedef pair<int,int> PII;
int h[N],e[N],ne[N],w[N],idx,n,m;
int dist[N];
void add(int a,int b,int c)
{
    e[idx]=b; w[idx]=c; ne[idx]=h[a]; h[a]=idx++;
}
bool st[N];
int dijkstra()
{
    memset(dist,0x3f,sizeof dist);
    priority_queue<PII,vector<PII>,greater<PII> > q;
    dist[1]=0;
    q.push({0,1});
    while(q.size())
    {
        PII tmp=q.top();q.pop();
        int d=tmp.first,u=tmp.second;
        if(st[u]) continue;
        st[u]=true;
        for(int i=h[u];i!=-1;i=ne[i])
        {
            int j=e[i];
            if(dist[j]>d+w[i])
            {
                dist[j]=d+w[i];
                q.push({dist[j],j});
            }
        }
    }
    if(dist[n]==0x3f3f3f3f) return -1;
    else return dist[n];

}
int main()
{
    scanf("%d%d",&n,&m);
    memset(h,-1,sizeof h);
    while(m--)
    {
        int a,b,c;
        scanf("%d%d%d",&a,&b,&c);
        add(a,b,c);
    }
    cout<<dijkstra()<<endl;
    return 0;
}




zmy
7天前

$dijkstra$求最短路(朴素版)

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
const int N=510;
int g[N][N];//用邻接矩阵来存储边
int dist[N];//dist[i]表示i到1的最短距离
bool st[N];//标记当前的这个点到起点的距离是否确定
int n,m;
int dijkstra()
{
    memset(dist,0x3f,sizeof dist);
    dist[1]=0;
    for(int i=0;i<n;i++)
    {
        int t=-1;
        for(int j=1;j<=n;j++)
        {
            if(!st[j]&&(t==-1||dist[t]>dist[j]))
                t=j;
        }
        st[t]=true;
        for(int j=1;j<=n;j++)
        {
            dist[j]=min(dist[j],dist[t]+g[t][j]);
        }

    }
    if(dist[n]==0x3f3f3f3f) return -1;
    else return dist[n];
}
int main()
{
    cin>>n>>m;
    memset(g,0x3f,sizeof g);
    while(m--)
    {
        int x,y,z;
        scanf("%d%d%d",&x,&y,&z);
        g[x][y]=min(g[x][y],z);
    }
    cout<<dijkstra()<<endl;
    return 0;
}