5.13错题总结

wangyichenawm · 2025-05-15 08:56:34 · 个人记录

T5(P3910 纪念邮票)

考试思路：双指针暴力

考试代码：

#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

正确思路：双指针暴力

正确代码：

#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] 部落划分)

考试思路：骗分

考试代码：

#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;
}

错误原因：没想出来

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

正确代码：

#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;
}