3个月前
#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;
}


3个月前

//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;
}



3个月前
#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;
}



3个月前
#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);
}


3个月前
#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;
}


3个月前
#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;
{
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);
}
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;
}


3个月前
关键是要想到将整数转化为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;
}


3个月前
#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;
}


3个月前

# 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;
}

3个月前

### 题目描述

#### 样例

输入样例：
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;
}