我用 set<pair<int,int>> 来存药水的位置，使用药水后 erase 即可。
#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,m,h,k;
string s;
set<pair<int,int> > se;
signed main(){
cin>>n>>m>>h>>k;
cin>>s;
for(int i=1;i<=m;++i){
int x,y;
cin>>x>>y;
se.insert(make_pair(x,y));
}
pair<int,int> now;
now.first=now.second=0;
for(char c:s){
if(c=='R'){
now.first++;
}
if(c=='L'){
now.first--;
}
if(c=='U'){
now.second++;
}
if(c=='D'){
now.second--;
}
h--;
if(h<0){
cout<<"No\n";
return 0;
}
if(h<k){
if(se.find(now)!=se.end()){
h=k;
se.erase(now);
}
}
}
cout<<"Yes\n";
return 0;
}
表示打完第 个字符后，大写锁状态为 的最小花费。
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=3e5+10;
int x,y,z;
string s;
int f[N][2];
signed main(){
cin>>x>>y>>z;
cin>>s;
f[0][0]=0;
f[0][1]=z;
for(int i=1;i<=s.size();++i){
if(s[i-1]=='A'){
f[i][0]=min(min(f[i-1][1]+x+z,f[i-1][1]+z+y),
min(f[i-1][0]+y,f[i-1][0]+z+x+z));
f[i][1]=min(min(f[i-1][1]+x,f[i-1][1]+z+y+z),
min(f[i-1][0]+y+z,f[i-1][0]+z+x));
}
else{
f[i][0]=min(min(f[i-1][1]+y+z,f[i-1][1]+z+x),
min(f[i-1][0]+x,f[i-1][0]+z+y+z));
f[i][1]=min(min(f[i-1][1]+y,f[i-1][1]+z+x+z),
min(f[i-1][0]+x+z,f[i-1][0]+z+y));
}
}
cout<<min(f[s.size()][0],f[s.size()][1])<<"\n";
return 0;
}
按照题目的构建方法，是一棵树，所以可以用 直接判断每个点是中心点还是星星图的边缘。
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=2e5+10;
int n;
vector<int> e[N];
bool vis[N];
int ans[N];
vector<int> v;
void dfs(int u,int f){
bool f1=false,f2=true;
for(auto v:e[u]){
if(v==f) continue;
dfs(v,u);
f1=f1 || (ans[v]>0);
f2=f2 && vis[v];
}
if(f1){
vis[u]=true;
}
else if(f2){
vis[u]=false;
}
else{
vis[u]=true;
ans[u]=e[u].size();
}
}
signed main(){
cin>>n;
for(int i=1;i<n;++i){
int u,v;
cin>>u>>v;
e[u].push_back(v);
e[v].push_back(u);
}
dfs(1,0);
for(int i=1;i<=n;++i){
if(ans[i]) v.push_back(ans[i]);
}
sort(v.begin(),v.end());
for(auto i:v){
cout<<i<<" ";
}
cout<<"\n";
return 0;
}