寒假训练营2
D
这道题的题意很简单，有k张技能牌，每张技能牌可以把前\(a_i\)张牌放到最下边，消耗\(b_i\)的花费，现在我们需要的牌在从下往上的第k张，要变到第一张，花费最小的方式。建图的思路就有了，边权就是花费，也就是最短路问题，但是边很灵活，每个点都能建出m条边。
点击查看代码
void solve(long long kk) {
priority_queue<PII,vector<PII>,greater<PII>>q;
int n,m,k;
cin>>n>>m>>k;
for(int i=1;i<=m;i++){
cin>>a[i]>>b[i];
}
for(int i=1;i<=n;i++){
dist[i]=LLONG_MAX;
}
dist[k]=0;
q.push({0,k});
while(q.size()){
auto [dis,dian]=q.top();
q.pop();
if(dist[dian]<dis)
continue;
for(int i=1;i<=m;i++){
int jl=a[i],hf=b[i];
jl+=dian;
jl%=n;
if(jl==0)
jl=n;
if(dist[jl]>hf+dis){
dist[jl]=hf+dis;
q.push({dist[jl],jl});
}
}
}
if(dist[n]==LLONG_MAX)
cout<<-1<<endl;
else
cout<<dist[n]<<endl;
return ;
}
codeforces 933 (Div.3)
E
F
天梯1
7-6
这题巨简单，但是问题出在了vector的size函数，这个函数的返回值不是int类型，所以要注意可能会出现x<ve.size()-1和x<=ve.size()两个公式不等价的情况。
7-11
这道题大一就做过，当时就没认真补题，现在遇到还是没思路，其实很简单，根据题意可知，这一定是树，也就是跑完树上的几个点之后不用返回起点，那想要最短路就是遍历所有路径之后减去最长的那条路。找最深的结点就是个dfs，那怎么计算出跑完所有点的路径和呢，那就是返回到当前点回到根节点的路径还有多少路径是没有走过的（因为之前的点可能被其他的点走过了，那就不用重复走了）。
点击查看代码
int fa[100010];
int vis[100010];
vector<int>g[100010];
int dp[100010];
void dfs(int x){
for(auto e:g[x]){
dp[e]=dp[x]+1;
dfs(e);
}
}
void solve(long long kk) {
int n,m;
cin>>n>>m;
int root;
for(int i=1;i<=n;i++){
cin>>fa[i];
if(fa[i]==-1){
root=i;
}
else
g[fa[i]].push_back(i);
}
dp[root]=0;
dfs(root);
int max1=0;
int sum=0;
for(int i=1;i<=m;i++){
int x;
cin>>x;
max1=max(max1,dp[x]);
while(vis[x]==0&&x!=root){
vis[x]=1;
sum+=2;
x=fa[x];
}
cout<<sum-max1<<endl;
}
return ;
}
7-12
这个题其实不难，就是一直不停的套map，因为这个明显也是树，但是可以优化的点是那些老人一定为叶子结点，那我们直接将一个管理机构下的老人数记作这个点的权值，在老人更换机构时就不用考虑边的问题了，直接更换双方的权值即可，求一个管理机构下的老人总数，就是以它为根节点的dfs搜索，权值求和就好，但是有一个段错误，不太懂问题在哪。
点击查看代码
map<pair<string,string>,int>d;
map<string,string>fa;
map<string,vector<string>>ve;
map<string ,int>xx;
int dfs(string s){
int ans=xx[s];
for(auto e:ve[s]){
ans+=dfs(e);
//cout<<e<<" "<<s<<" "<<ans<<endl;
}
return ans;
}
void solve(long long kk) {
int n,m;
cin>>n>>m;
for(int i=1;i<=m;i++){
string s1,s2;
cin>>s1>>s2;
fa[s1]=s2;
ve[s2].push_back(s1);
if(s1[0]>='0'&&s1[0]<='9')
xx[s2]++;
// cout<<i<<" "<<s2<<" "<<xx[s2]<<endl;
// for(auto e:ve[s2]){
// cout<<e<<" ";
// }
// cout<<"-----\n";
//fa[s1]=s2;
}
while(1){
string s1;
cin>>s1;
if(s1=="E"){
break;
}
if(s1=="T"){
string s2,s3;
cin>>s2>>s3;
string ss=fa[s2];
xx[ss]--;
//cout<<ss<<" "<<s2<<" "<<s3<<endl;
ve[s3].push_back(s2);
fa[s2]=s3;
xx[s3]++;
}
else if(s1=="Q"){
string s2;
cin>>s2;
int ans=0;
ans=dfs(s2);
cout<<ans<<endl;
}
}
return ;
}