专栏文章

abc305解题报告

ttang2hao4zhe2
个人记录参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@miql1l26
此快照首次捕获于
2025/12/04 06:32
3 个月前
此快照最后确认于
2025/12/04 06:32
3 个月前
查看原文

A

solution

枚举0,5,10,...,1000,5,10,...,100即可

code

CPP
#include<bits/stdc++.h>
using namespace std;
#define int long long
signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	
	int n;cin>>n;
	int ans=0;
	for(int i=0;i<=100;i+=5){
		if(abs(n-i)<abs(n-ans)) ans=i;
	}
	cout<<ans<<endl;
	return 0;
}

B

solution

用常量数组将字符转化为数字

code

CPP
#include<bits/stdc++.h>
using namespace std;
#define int long long
int a[]={0,3,4,8,9,14,23};
signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	
	char x,y;cin>>x>>y;
	cout<<abs(a[x-'A']-a[y-'A'])<<endl;
	return 0;
}

C

solution

找出唯一的全#矩形中被挖掉的那个
可以先算出这个矩形的四个边界

code

CPP
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=505;
char a[N][N];
signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	
	int l=1e18,r=-1e18,u=1e18,d=-1e18;
	int n,m;cin>>n>>m;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			cin>>a[i][j];
			if(a[i][j]=='#'){
				l=min(l,j);
				r=max(r,j);
				u=min(u,i);
				d=max(d,i);
			}
		}
	}
	for(int i=u;i<=d;i++){
		for(int j=l;j<=r;j++){
			if(a[i][j]=='.'){
				cout<<i<<' '<<j<<endl;
				return 0;
			}
		}
	}
	return 0;
}

D

solution

整个时间可以分成n−1n-1段，我们设ll在第xx段，rr在第yy段
则答案分三段计算：
1、x+1x+1到y−1y-1，这个可以用稍加讨论的前缀和
2、ll到xx
3、yy到rr

code

CPP
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=2e5+5;
int a[N],sum[N];
signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	
	int n;cin>>n;
	for(int i=1;i<=n;i++) cin>>a[i];
	for(int i=2;i<=n;i++){
		if(i%2==0) sum[i]=sum[i-1];
		else sum[i]=sum[i-1]+a[i]-a[i-1];
	}
	int q;cin>>q;
	while(q--){
		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;
		if(l>a[x]) x++;
		if(r<a[y]) y--;
		int ans=sum[y]-sum[x];
		if(x%2==1) ans+=a[x]-l;
		if(y%2==0) ans+=r-a[y];
		cout<<ans<<endl;
		//cout<<x<<' '<<y<<endl;
	}
	return 0;
}

E

solution

我们会先扩展剩余次数多的节点，因此，我们使用优先队列bfsbfs

code

CPP
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int N=2e5+5;
vector<int> G[N];
void addedge(int u,int v){
	G[u].push_back(v);
}
struct node{
	int u,d;
	bool operator<(const node& o)const{
		return d<o.d;
	}
};
priority_queue<node> pq;
int vis[N];
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	
	int n,m,k;cin>>n>>m>>k;
	for(int i=1;i<=m;i++){
		int u,v;cin>>u>>v;
		addedge(u,v);
		addedge(v,u);
	}
	for(int i=1;i<=k;i++){
		int p,h;cin>>p>>h;
		pq.push((node){p,h});
	}
	while(!pq.empty()){
		node t=pq.top();
		pq.pop();
		int u=t.u,d=t.d;
		vis[u]=1;
		if(d==0) continue;
		for(int v:G[u]){
			if(vis[v]) continue;
			vis[v]=1;
			pq.push((node){v,d-1});
		}
	}
	int tot=0;
	for(int i=1;i<=n;i++) if(vis[i]) tot++;
	cout<<tot<<endl;
	for(int i=1;i<=n;i++) if(vis[i]) cout<<i<<' ';
	cout<<endl;
	return 0;
}

F

solution

直接dfsdfs即可，考虑最坏情况，每个点被遍历到两次，次数为2n2n，满足题意

code

CPP
#include<bits/stdc++.h>
using namespace std;
#define int long long
int n,m,k,pos,path[105];
vector<int> v[105];
bool on[105];
void explore(int x){
	cout<<x<<endl;
	if(x==n) exit(0);
}
void read(int x){
	cin>>k;
	on[x]=1,v[x].resize(k);
	for(int i=0;i<v[x].size();i++) cin>>v[x][i];
	for(int i:v[x]) if(!on[i]){
		path[i]=x;pos=i;
		return;
	}
	pos=path[x];
}
signed main(){
	cin>>n>>m;
	pos=1;
	while(1) read(pos),explore(pos);
	return 0;
}

G

我不会矩阵加速，看以后会不会写

H

这玩意就是fyc都不会做吧

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...