专栏文章

5.13错题总结

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

文章操作

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

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

T5(P3910 纪念邮票)

考试思路:双指针暴力

考试代码:
CPP
#include<bits/stdc++.h>
using namespace std;
int n,m;
int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin>>n>>m;
	int l=1,cnt=0;
	for(int r=1;r<=n;r++)
	{
		cnt+=r;
		if(cnt>=m)
		{
			while(cnt>m&&l<r)
			{
				cnt-=l;
				l++;
			}
			if(cnt==m)
				cout<<"["<<l<<","<<r<<"]\n";
		}
	}
	return 0;
}

错误原因:不需要判断l<r,因为l>r后就肯定小于0了,不会加1

正确思路:双指针暴力

正确代码:
CPP
#include<bits/stdc++.h>
using namespace std;
int n,m;
int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin>>n>>m;
	int l=1,cnt=0;
	for(int r=1;r<=n;r++)
	{
		cnt+=r;
		if(cnt>=m)
		{
			while(cnt>m)
			{
				cnt-=l;
				l++;
			}
			if(cnt==m)
				cout<<"["<<l<<","<<r<<"]\n";
		}
	}
	return 0;
}

T6(P4047 [JSOI2010] 部落划分)

考试思路:骗分

考试代码:
CPP
#include<bits/stdc++.h>
using namespace std;
int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cout<<"1.00";
	return 0;
}

错误原因:没想出来

正确思路:最小生成树+欧几里得距离:

正确代码:
CPP
#include<bits/stdc++.h>
using namespace std;
const int N=1e4+5,M=1e6+5;
int fa[N];
int n,m,k;
int x[N],y[N];
struct node 
{    
	int u,v;
    double w; 
}a[M];
bool cmp(node q,node h) 
{    
	return q.w<h.w; 
}
int find(int x)
{
	if(fa[x]==x)
		return x;
	return fa[x]=find(fa[x]);
}
signed main()
{
	cin>>n>>k;
	for(int i=1;i<=n;i++)
		cin>>x[i]>>y[i];
	for(int u=1;u<n;u++)
	{
		for(int v=u+1;v<=n;v++)
		{
			double w=sqrt((x[u]-x[v])*(x[u]-x[v])+(y[u]-y[v])*(y[u]-y[v]));            
			a[++m]={u,v,w}; 
		}
	}
	sort(a+1,a+m+1,cmp);
	for(int i=1;i<=n;i++)
		fa[i]=i;
	int cnt=0,sum=0;
	for(int i=1;i<=m;i++) 
	{
	 	int t1=find(a[i].u);        
		int t2=find(a[i].v); 
		if(t1!=t2)
		{
			cnt++;
			fa[t2]=t1;
			sum+=a[i].w;
		}
		if(cnt==n-k+1)
		{
			printf("%.2lf",a[i].w);
			return 0;
		}
	}
 	return 0;
}

评论

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

正在加载评论...