PTA练习题

L1-101 别再来这么多猫娘了！（字符串查找-替换）

主要考察字符串函数的运用，当然也可以自己暴力写

先用一个短的字符串替换，输出时再替换为长的。

string s[150];
void solve()
{int n,k,c=0;string a,b;cin>>n;cin.ignore();for(int i=1;i<=n;i++)getline(cin,s[i]);cin>>k;cin.ignore();getline(cin,a);for(int i=1;i<=n;i++){while(a.find(s[i])!=-1ll){int it=a.find(s[i]);a.replace(it,s[i].size(),"*+*");c++;}}if(c>=k) cout<<c<<'\n'<<"He Xie Ni Quan Jia!\n";else{while(a.find("*+*")!=-1ll){int it=a.find("*+*");a.replace(it,3,"<censored>");}cout<<a<<'\n';	}
}

L2-049 鱼与熊掌（set/暴力/vector）

• 不能直接用哈希，会爆内存
• set 插入x,y ，size没变,说明存在
• vector,find查找

vector<int> v[N];
void solve()
{int n,m;cin>>n>>m;fir(i,1,n){int x,y;cin>>x;while(x--){cin>>y;v[i].push_back(y);}}int q;cin>>q;while(q--){int x,y,c=0;cin>>x>>y;fir(i,1,n){if(find(ALL(v[i]),x)!=v[i].end() && find(ALL(v[i]),y)!=v[i].end())c++;}cout<<c<<'\n';}}

L2-050 懂蛇语（字符串匹配）

两个坑：

• 不一定以字母开头
• 字典中可能有重复的句子，所以用vector，或者multimap

multimap 没法下标索引，用insert

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define IOS ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
#define fir(i,a,b) for(int i=a;i<=b;i++)
#define fir_(i,a,b) for(int i=a;i>=b;i--)
#define ALL(x) x.begin(),x.end()
#define lowbit(x) (x&(-x))
#define PII pair<int,int> 
#define fi first
#define se second
#define tup tuple<int,int,int>
const int N=1e5+10;
map<string, multimap<string,int> > mp;
string s[N];
void solve()
{int n,m;cin>>n;cin.ignore();fir(i,1,n){getline(cin,s[i]);string a;for(int j=0;j<s[i].size();j++){if((s[i][j-1]==' '||j==0)&&s[i][j]!=' ')a+=s[i][j];}// mp[a][s[i]]=1;mp[a].insert({s[i],1});}cin>>m;cin.ignore();fir(i,1,m){string b,c;getline(cin,b);for(int j=0;j<b.size();j++)if((b[j-1]==' '||j==0)&&b[j]!=' ')c+=b[j];int f=0;for(auto x:mp[c]){string it=x.fi;if(f==1)cout<<'|';cout<<it;f=1;}if(f==0) cout<<b;cout<<'\n';}}
signed main()
{IOSint t=1;//cin>>t;while(t--)solve();return 0;
}

L2-051 满树的遍历(前序)

vector<int> g[150000];
int r=0;
void qianxu(int x)
{if(x==r)cout<<x;elsecout<<' '<<x;for(auto it:g[x]){qianxu(it); }}
signed main()
{int n,f=0;cin>>n;for(int i=1;i<=n;i++){int x;cin>>x;g[x].push_back(i);if(x==0) r=i;}queue<int> q;q.push(0);int c=g[r].size();while(q.size()){int x=q.front();q.pop();for(auto it: g[x]){if(g[it].size()!=0&&g[it].size()!=c){f=1;c=max(c,(long long)g[it].size());  	}q.push(it);}}  cout<<c<<" ";if(f==0)cout<<"yes\n";elsecout<<"no\n";qianxu(r);
}

L2-001 紧急救援（最短路）

vector<pair<int,int> > g[500100];
int n,m,s,e,a[550],d[550],v[550],f[550],sum[550],ans[550],cnt[550];
priority_queue<PII,vector<PII>,greater<PII> > q;
void dij()
{q.push({0,s});while(q.size()){int x=q.top().first,y=q.top().second;q.pop();if(v[y]==1)continue;v[y]=1;for(auto it: g[y]){if(d[y]+it.second<d[it.first]){d[it.first]=d[y]+it.second;f[it.first]=y;sum[it.first]=sum[y]+a[it.first];q.push({d[it.first],it.first});cnt[it.first]=cnt[y];//!!!}else if(d[y]+it.second==d[it.first]){if(sum[y]+a[it.first]>sum[it.first]){f[it.first]=y;sum[it.first]= sum[y]+a[it.first];}cnt[it.first]+=cnt[y];//!!//q.push({d[it.first],it.first});}}}
}
signed main()
{cin>>n>>m>>s>>e;for(int i=0;i<n;i++)cin>>a[i];for(int i=1;i<=m;i++){int u,v,w;cin>>u>>v>>w;g[u].push_back({v,w});g[v].push_back({u,w});}memset(d,127,sizeof(d));d[s]=0;sum[s]=a[s];cnt[s]=1;dij();int k=e,i=1;while(k!=s){ans[i++]=k;k=f[k];}cout<<cnt[e]<<' '<<sum[e]<<'\n'<<s;for(int j=i-1;j>0;j--)cout<<' '<<ans[j];}