这道题首先先把所有的 关键词用map读入 然后用vector 去存string 和出现的次数 cnt 进行排序
之后读入目标字符串 用stl string自带的查找判断前缀 如果是前缀那么必为0
#include <bits/stdc++.h>
using namespace std;
struct node{
string s;
int cnt;
bool operator<(const node& A){
if(cnt!=A.cnt)
return cnt>A.cnt;// 从大到小排序！！
else return s<A.s;
}
};
vector<node> ve;
map<string,int> mp;
int n;
int main()
{
cin>>n;
for(int i=1;i<=n;i++)
{
string s1;
cin>>s1;
mp[s1]++;
}
for(auto [x,y]:mp)
{
ve.push_back({x,y});
}
sort(ve.begin(),ve.end());
int t;
cin>>t;
while(t--)
{
string s1;
cin>>s1;
int o=5;
for(int i=0;i<ve.size();i++)
{
if(ve[i].s.find(s1)==0)//因为是前缀！！
{
cout<<ve[i].s<<'\n';
o--;
}
if(o==0) break;
}
if(o==5) cout<<"-"<<'\n';
cout<<'\n';
}
}
这道题就是课上讲过的字符串哈希中的数组哈希 用一个vector去存数组然后把这个数组的哈希值存入map里面去然后进行判断即可 大水题
#include <bits/stdc++.h>
using namespace std;
int n,k;
unsigned long long p=99999999971;
int base=137;
unsigned long long hash1(const vector<unsigned long long> &s)
{
unsigned long long res=0;
// for(int i=0;i<k;i++)
// res=(res*base+(s[i])%p);
for(auto x:s)
{
res=(res*base+(x)%p);
}
return res;
}
int main()
{
map<unsigned long long,int> a;
cin>>n>>k;
vector<unsigned long long> v(k);
for(int i=1;i<=n;i++)
{
for(int i=0;i<k;i++)
{
cin>>v[i];
}
sort(v.begin(),v.end());
a[hash1(v)]++;
}
int ans=0;
for(auto [x,y]:a)
{
ans=max(y,ans);
}
cout<<ans;
}
这道题有意思这个是一个记忆化搜索 可仔细想想先去遍历 经过x,y的所有路径若之后的东西又经过x,y 那么，可由x,y行进的所有路径都被遍历了一遍那么就无了！
#include <bits/stdc++.h>
using namespace std;
int n,m;
int x11,y11,x22,y22;
long long f[1001][1001];
int st[1001][1001];
int fx[3],fy[3];
int mod=998244353;
long long dfs(int x,int y)
{
if(f[x][y]!=-1)
return f[x][y];
f[x][y]=0;//第一次遍历到赋值为0,由这个去往下走之后所有由它经过的路径都是可以的
if(x==x22&&y==y22)
return f[x][y]=1;//由终点不可能往下继续走了
for(int i=1;i<=2;i++)
{
int a=x+fx[i];
int b=y+fy[i];
if(a<=n&&a>=1&&b<=m&&b>=1&&st[a][b])
{
f[x][y]=(f[x][y]+dfs(a,b))%mod;
}
}
return f[x][y];
}
int main()
{
cin>>n>>m;
cin>>x11>>y11>>x22>>y22;
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
cin>>st[i][j];
}
}
if(x11<x22)
{
fx[1]=1,fy[1]=0;
}else fx[1]=-1,fy[1]=0;
if(y11<y22)
{
fx[2]=0,fy[2]=1;
}else fx[2]=0,fy[2]=-1;
memset(f,-1,sizeof(f));
dfs(x11,y11);
cout<<f[x11][y11];
}
这道题主要就是注意main也是一个函数在函数中开大数组会爆栈的！！所以得开到外面去或用vector 自动默认为堆
#include <bits/stdc++.h>
using namespace std;
int t,n;
int dist[100005];
struct node{
int y,v;
node(int a,int b)
{
y=a,v=b;
}
};
int dijkstra(int s,int t,int dist[],vector<node> edge[])
{
set<pair<int,int>>q;
for(int i=1;i<=t;i++)
{
dist[i]=1<<30;
}
dist[s]=0;
q.clear();
for(int i=1;i<=t;i++)
q.insert({dist[i],i});
while(!q.empty())
{
int x=q.begin()->second;
if(x==t||dist[x]>1<<30)
break;
q.erase(q.begin());
for(auto i:edge[x])
{
if(dist[x]+i.v<dist[i.y])
{
q.erase({dist[i.y],i.y});
dist[i.y]=dist[x]+i.v;
q.insert({dist[i.y],i.y});
}
}
}
return dist[t];
}
void solve()
{
cin>>n;
vector<node> edge[n+1];
for(int i=1;i<n;i++)
{
int x;
cin>>x;
edge[i].push_back({x,2});
edge[i].push_back({i+1,1});
}
cout<<dijkstra(1,n,dist,edge)<<'\n';
}
int main()
{
cin>>t;
while(t--)
{
solve();
}
}
注意如何改写即可