讨论
ABC305 CDE 题解 -fangyanli
ABC305 CDE 题解 -fangyanli
fangyanli
2023-08-17 10:50:02
4
C题
题意:有一个由 构成的矩阵,问哪里少了一块
思路:如果该位置不是 并且它四周有两个及以上的 则一定是该位置
代码
#include<bits/stdc++.h>
using namespace std;
int n,m,x[10],y[10],f;
string s[10001];
signed main(){
ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
cin>>n>>m;
for(int i=1;i<=n;i++){
string ss;
cin>>ss;
s[i]=" ";
s[i]+=ss;
}
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
if(s[i][j]=='.'){
int sum=0;
if(s[i][j-1]=='#') sum++;
if(s[i-1][j]=='#') sum++;
if(s[i][j+1]=='#') sum++;
if(s[i+1][j]=='#') sum++;
if(sum>=2){
cout<<i<<" "<<j;
return 0;
}
}
}
}
}
D题
题意:有个数，下标为奇数, 则代表高桥君从这个时间点停止睡觉；下标为偶数, 则代表高桥君从这个时间点开始睡觉。
次询问，每次有,两数,问在这段时间内高桥君睡觉时间的总和是多少；
思路:前缀和然后lower_bound一下，把左边少的加上，右边多的减去
代码
#include<bits/stdc++.h>
using namespace std;
int n,a[200001],sum[200001],m;
signed main(){
ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
cin>>n;
for(int i=1;i<=n;i++){
cin>>a[i];
if(i%2==0) sum[i]=sum[i-1];
else sum[i]=sum[i-1]+a[i]-a[i-1];
}
cin>>m;
while(m--){
int l,r;
cin>>l>>r;
int x=lower_bound(a+1,a+n+1,l)-a;
int y=lower_bound(a+1,a+n+1,r)-a;
int ans=sum[y]-sum[x];
if(x%2==1) ans+=(a[x]-l);
if(y%2==1) ans+=(r-a[y]);
cout<<ans<<"\n";
}
}
E题
题意:一个点个边的无向图有个起点，每个起点有和两个属性，表示起点为并且能走条边，每到一个点就可以染色；
问最后有几个点被染色并从小到大输出编号
思路:用bfs和优先队列，每次找到一个点就继续找,并且把,当为零就换下一个继续
代码
#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,m,k,v[200001],ans;
vector<int> g[200001];
priority_queue<pair<int,int> > q;
signed main(){
ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
cin>>n>>m>>k;
for(int i=1;i<=m;i++){
int x,y;
cin>>x>>y;
g[x].push_back(y);
g[y].push_back(x);
}
for(int i=1;i<=k;i++){
int x,y;
cin>>x>>y;
q.push({y,x});
}
while(q.size()){
int dis=q.top().first,s=q.top().second;
q.pop();
if(!v[s]){
v[s]=1;
if(dis)
for(auto y:g[s]){
if(!v[y]){
q.push({dis-1,y});
}
}
}
}
for(int i=1;i<=n;i++){
if(v[i]){
ans++;
}
}
cout<<ans<<"\n";
for(int i=1;i<=n;i++){
if(v[i]){
cout<<i<<" ";
}
}
}
{{ vote && vote.total.up }}
