头像

王子涵


访客:7587

离线:6小时前



王子涵
25天前
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;

int a[3010][3010],d[3010],n,m,ans;
bool v[3010];
const int INF = 0x3f3f3f3f;
bool prim()
{
    memset(d,INF,sizeof d);
    memset(v,0,sizeof v);
    d[1]=0;
    for(int i=1;i<n;i++)
    {
        int x = 0;
        for(int j = 1 ; j <= n ; j++)
        {
            if(!v[j]&&(x==0||d[j]<d[x]))
            {
                x=j;
            }
        }
        v[x]=1;
        if(i&&d[x] == INF)
        return false;
        for(int j =1; j <= n ; j++)
        {
            if(!v[j])d[j] = min(d[j],a[x][j]);
        }
    }
    return true;
}

int main()
{
    cin >> n >>m;
    memset(a,INF,sizeof a);
    for(int i=1;i<=n;i++)a[i][i]=0;
    for(int i=1;i<=m;i++)
    {
        int x,y,z;
        cin>> x >> y >> z;
        a[x][y] = a[y][x] = min(a[x][y],z);
    }
    bool p = prim();
    if(!p){
        cout<<"impossible"<<endl;
        return 0;
    }
    for(int i = 1 ;i <= n; i++)ans+=d[i];
    cout<< ans <<endl;
    return 0;
}



王子涵
25天前

//Kruskal 算法
//O(m log m)
#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;

struct rec {
    int x,y;
    int val;
}edge[500010];
int fa[100010],n,m,ans=0;

bool operator <(rec a, rec b)
{
    return a.val<b.val;
}
int get(int x)
{
    if(x == fa[x])return x;
    return fa[x] = get(fa[x]);
}

int main()
{
    cin >> n >> m;
    for(int i =0 ;i< m ; i++)
    {
        scanf("%d%d%d",&edge[i].x,&edge[i].y,&edge[i].val);
    }
    sort(edge,edge+m);
    for(int i=1;i<=n;i++)fa[i]=i;
    int num =0;//记录最小生成树的边数
    for(int i=0;i<m;i++)
    {
        int x= get(edge[i].x);
        int y = get(edge[i].y);
        if(x==y)continue;
        else{
                num++;
            fa[x]=y;
            ans += edge[i].val;
        }
    }
    if(num<n-1)//当边数小于点数减一,则构不成连通图也就成不了树
    {
        cout<<"impossible"<<endl;
        return 0;
    }
    cout<< ans <<endl;
    return 0;
}



活动打卡代码 AcWing 844. 走迷宫

王子涵
1个月前
#include <bits/stdc++.h>

using namespace std;

int mp[150][150];
struct node{
    int x,y,num;
};
int n,m;
queue<node>q;
int bfs()
{
    q.push(node{1,1,0});
    while(!q.empty())
    {
        node u = q.front(); 
        q.pop();
        //cout<<u.x<<" "<<u.y<<endl;
        if(u.x==n&&u.y==m)
        {
           // cout<<u.num<<endl;
            return u.num;
        }
        if(u.x+1<=n&&mp[u.x+1][u.y]==0)
        {
            node v = node{u.x+1,u.y,u.num+1};
            q.push(v);
              mp[u.x+1][u.y]=1;
        }
        if(u.y+1<=m&&mp[u.x][u.y+1]==0)
        {
             node v = node{u.x,u.y+1,u.num+1};
              q.push(v);
                mp[u.x][u.y+1]=1;
        }
        if(u.x-1>0&&mp[u.x-1][u.y]==0)
        {
             node v = node{u.x-1,u.y,u.num+1};
              q.push(v);
                mp[u.x-1][u.y]=1;
        }

        if(u.y-1>0&&mp[u.x][u.y-1]==0)
        {
            node v = node{u.x,u.y-1,u.num+1};
             q.push(v);
             mp[u.x][u.y-1]=1;
        }
    }
}
int main()
{
    cin >> n >>m;
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            scanf("%d",&mp[i][j]);
        }
    }
    int t = bfs();
    cout<<t<<endl;
}



活动打卡代码 AcWing 843. n-皇后问题

王子涵
1个月前
#include <bits/stdc++.h>

using namespace std;

int r[150];
int n;
bool check(int ans)
{
   for(int i=1;i<ans;i++)
   {
       if(r[i]==r[ans])return false;
       if(abs(r[ans]-r[i])== abs(ans-i))return false;
   }
   return true;
}
void dfs(int ans)
{
    if(ans>n)
    {
        for(int i=1;i<=n;i++)
        {
            for(int j=1;j<=n;j++)
            {
                if(r[i]==j)
                {
                    cout<<"Q";
                }
                else{
                    cout<<'.';
                }
            }
            cout<<endl;
        }
        cout<<endl;
    }
    for(int i=1;i<=n;i++)
    {
        r[ans]=i;
        if(check(ans))
        {
            dfs(ans+1);
            r[ans]=0;
        }
    }
    return ;
}
int main()
{
    cin >> n;
    dfs(1);
}


活动打卡代码 AcWing 842. 排列数字

王子涵
1个月前
#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
int num[150];
int vis[150];
int n;
void dfs(int x)
{
    if(x>n)
    {
        for(int i=1;i<n;i++)
        {
            cout<<num[i]<<" ";
        }
        cout<<num[n]<<endl;
        return ;
    }
    for(int i=1;i<=n;i++)
    {
        if(vis[i]==0)
        {
            num[x]=i;
            vis[i]=1;
           dfs(x+1);
           vis[i]=0;
        }
    }
}
int main()
{
    cin >> n;
    dfs(1);
    return 0;
}



王子涵
1个月前
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;
const int N = 100000,M= 3000010;
int h[N] ,c[N<<1],e[N<<1],ne[N<<1],cnt=0;
typedef long long ll;
int a[N];
int son[M][2],idx =0;
void add(int u,int v,int w)
{
    e[cnt] = v, c[cnt] = w, ne[cnt] = h[u], h[u] = cnt++; 
}
void dfs(int u,int fa,int sum)
{
    a[u] = sum;
    for(int i = h[u] ; ~i; i = ne[i])
    {
        if(e[i] != fa)
        dfs(e[i],u,sum^c[i]);
        else break;
    }
}
void insert(int x)
{
    int p = 0;
    for(int i = 30;~i;i--)
    {
        int &s = son[p][x>>i&1];
        if(!s)s=++idx;
        p = s;
    }
}
int query(int x)
{
    int p=0;
    int res=0;
    for(int i=30;~i;i--)
    {
        int s = x >> i & 1;
        if(son[p][!s])
        {
            res+=1<<i;
            p = son[p][!s];
        }
        else
        p = son[p][s];
    }
    return res;
}
int main()
{
    int n;
    cin >> n;
    memset(h,-1,sizeof(h));
    for(int i=1;i<n;i++)
    {
        int u,v,w;
        scanf("%d%d%d",&u,&v,&w);
        add(u,v,w);
        add(v,u,w);
    }
    dfs(0,-1,0);
    for(int i=0;i<n;i++)insert(a[i]);
    int res =0;
    for(int i=0;i<n;i++)
    {
        res = max(res,query(a[i]));
    }
    cout<<res<<endl;
    return 0;
}


活动打卡代码 AcWing 143. 最大异或对

王子涵
1个月前
关键是要想到将整数转化为32位二进制数,在构造trie
#include <iostream>

using namespace std;

const int N = 1e5+10;
const int M = 3e6+30;
int son[M][2],cnt[N];
int idx =0;
void insert(int x)
{
    int p=0;
    for(int i = 30; ~i; i--)
    {
        int &s = son[p][ x >> i & 1];
        if(!s){
            s = ++idx;
        }
        p = s;
    }
}
int query(int x)
{
    int p = 0;
    int res =0 ;
    for(int i = 30;~i;i--)
    {
        int s = x >> i & 1;
        if(son[p][!s]){
            res+=1<<i;
            p = son[p][!s];
        }
        else{
            p = son[p][s];
        }
    }
    return res;
}
int main()
{
    int n;
    cin >> n;
    for(int i = 1 ; i <= n ; i++)
    {
        scanf("%d",&cnt[i]);
        insert(cnt[i]);
    }
    int res=0;

    for(int i = 1; i <= n; i ++)
    {
        res = max(res,query(cnt[i]));
    }
    cout << res <<endl;
    return 0;
}


活动打卡代码 AcWing 143. 最大异或对

王子涵
1个月前
#include <iostream>

using namespace std;

const int N = 1e5+10;
const int M = 3e6+30;
int son[M][2],cnt[N];
int idx =0;
void insert(int x)
{
    int p=0;
    for(int i = 30; ~i; i--)
    {
        int &s = son[p][ x >> i & 1];
        if(!s){
            s = ++idx;
        }
        p = s;
    }
}
int query(int x)
{
    int p = 0;
    int res =0 ;
    for(int i = 30;~i;i--)
    {
        int s = x >> i & 1;
        if(son[p][!s]){
            res+=1<<i;
            p = son[p][!s];
        }
        else{
            p = son[p][s];
        }
    }
    return res;
}
int main()
{
    int n;
    cin >> n;
    for(int i = 1 ; i <= n ; i++)
    {
        scanf("%d",&cnt[i]);
        insert(cnt[i]);
    }
    int res=0;

    for(int i = 1; i <= n; i ++)
    {
        res = max(res,query(cnt[i]));
    }
    cout << res <<endl;
    return 0;
}


活动打卡代码 AcWing 142. 前缀统计

王子涵
1个月前

include [HTML_REMOVED]

include [HTML_REMOVED]

include [HTML_REMOVED]

include [HTML_REMOVED]

include [HTML_REMOVED]

include [HTML_REMOVED]

using namespace std;
typedef long long ll;
const int N = 1e6+10;
int son[N][26],cnt[N];
int idx=0;
char str[N];
void insert()
{
int p=0;
for(int i=0;str[i];i)
{
int &s = son[p][str[i]-‘a’];
if(!s)
{
s=
idx;
}
p=s;
}
cnt[p];
}
int search()
{
int p=0,res=0;
for(int i=0;str[i];i
)
{
int &s = son[p][str[i]-‘a’];
if(!s)break;
p=s;
res+=cnt[p];
}
return res;
}
int main()
{
int n , m ;
cin >> n >> m;
for(int i=1;i<=n;i++)
{
scanf(“%s”,str);
insert();
}
while(m–)
{
scanf(“%s”,str);
printf(“%d\n”, search());
}
return 0;
}




王子涵
1个月前

题目描述

给定N个字符串S1,S2…SN,接下来进行M次询问,每次询问给定一个字符串T,求S1~SN中有多少个字符串是T的前缀。

输入字符串的总长度不超过106,仅包含小写字母。

输入格式
第一行输入两个整数N,M。

接下来N行每行输入一个字符串Si。

接下来M行每行一个字符串T用以询问。

输出格式
对于每个询问,输出一个整数表示答案。

每个答案占一行。

样例

输入样例:
3 2
ab
bc
abc
abc
efg

输出样例:
2
0


#include <iostream>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <cstring>
#include <string>

using namespace std;
typedef long long ll;
const int N = 1e6+10;
int son[N][26],cnt[N];
int idx=0;
char str[N];
void insert()
{
    int p=0;
    for(int i=0;str[i];i++)
    {
        int &s = son[p][str[i]-'a'];//这里引用,节省空间时间
        if(!s)
        {
            s=++idx;//对应的son值也更新
        }
        p=s;
    }
    cnt[p]++;
}
int search()
{
    int p=0,res=0;
    for(int i=0;str[i];i++)
    {
        int &s = son[p][str[i]-'a'];
        if(!s)break;
        p=s;
        res+=cnt[p];
    }
    return res;
}
int main()
{
    int n , m ;
    cin >> n >> m;
    for(int i=1;i<=n;i++)
    {
        scanf("%s",str);
        insert();
    }
    while(m--)
    {
        scanf("%s",str);
       printf("%d\n", search());
    }
    return 0;
}