AWC赛后题解
2026-08-26 21:25:43
发布于：浙江
3阅读
0回复
0点赞
rt.
A - 最小框架
思路：找到所有 # 的最上、最下、最左、最右边界，最小矩形就是这四个边界围成的矩形，周长 (高 + 宽)。如果没有 #，输出 ，挺水的，感觉不难。
#include<bits/stdc++.h>
using namespace std;
int main(){
int h,w;
cin>>h>>w;
int minx=h+1,maxx=0,miny=w+1,maxy=0;
for(int i=1;i<=h;i++){
string s;
cin>>s;
for(int j=1;j<=w;j++){
if(s[j-1]=='#'){
minx=min(minx,i);
maxx=max(maxx,i);
miny=min(miny,j);
maxy=max(maxy,j);
}
}
}
if(maxx==0){
cout<<0<<"\n";
return 0;
}
cout<<2*((maxx-minx+1)+(maxy-miny+1))<<"\n";
return 0;
}
B - Point Earning Campaign
思路：贪心，选点数最大的前 个产品即可。排序后累加。
#include<bits/stdc++.h>
using namespace std;
int main(){
int n,k;
cin>>n>>k;
vector<long long> p(n);
for(int i=0;i<n;i++) cin>>p[i];
sort(p.begin(),p.end(),greater<long long>());
long long ans=0;
for(int i=0;i<min(n,k);i++) ans+=p[i];
cout<<ans<<"\n";
return 0;
}
C - Cave Exploration
思路：模拟，维护当前房间的出边指针 ，按优先级遍历。遇到已访问或同色跳过，异色则访问并入栈记录父节点。无路可走时回溯到栈顶房间继续。
#include<bits/stdc++.h>
using namespace std;
int n,m;
int c[200005];
vector<int> e[200005];
int vis[200005],idx[200005];
stack<int> st;
void dfs(int x){
while(idx[x] < (int)e[x].size()){
int y = e[x][idx[x]];
idx[x]++;
if(vis[y]) continue;
if(c[y] == c[x]) continue;
vis[y] = 1;
st.push(x);
dfs(y);
return;
}
if(st.empty()) return;
int fa = st.top();
st.pop();
dfs(fa);
}
int main(){
cin>>n>>m;
for(int i=1;i<=n;i++) cin>>c[i];
for(int i=0;i<m;i++){
int u,v;
cin>>u>>v;
e[u].push_back(v);
}
vis[1]=1;
dfs(1);
bool flag=true;
for(int i=1;i<=n;i++){
if(!vis[i]){
flag=false;
cout<<i<<" ";
}
}
if(flag) cout<<"COMPLETE";
cout<<"\n";
return 0;
}
这里空空如也
有帮助，赞一个