4.15错题总结
wangyichenawm · · 个人记录
T3(P2126 Mzc家中的男家丁)
考试思路：从Mzc开始遍历，把每种可能都试一遍，并用mn取最小值
考试代码：
#include<bits/stdc++.h>
using namespace std;
int n,m,mn=1e9;
vector<int>e[2305],h[2305];
bool vis[2305];
void dfs(int u,int rs,int cnt)
{
if(rs==n)
{
if(mn>cnt)
mn=cnt;
return ;
}
vis[u]=1;
for(int i=0;i<e[u].size();i++)
if(vis[e[u][i]]==0)
dfs(e[u][i],rs+1,cnt+h[u][i]);
vis[u]=0;
}
int main()
{
cin>>n>>m;
while(m--)
{
int u,v,w;
cin>>u>>v>>w;
e[u].push_back(v);
e[v].push_back(u);
h[u].push_back(w);
h[v].push_back(w);
}
dfs(0,0,0);
cout<<mn;
return 0;
}错误原因：没时间，外加脑子瓦特
正确思路：最小生成树模板，区别是有n+1个人
正确代码：
#include<bits/stdc++.h>
using namespace std;
#define int long long
struct N
{
int x,y,w;
}a[400005];
int fa[400005];
int find(int x)
{
if(fa[x]==x)
return x;
return fa[x]=find(fa[x]);
}
bool cmp(N a,N b)
{
return a.w<b.w;
}
signed main()
{
int n,m;
cin>>n>>m;
for(int i=1;i<=m;i++)
cin>>a[i].x>>a[i].y>>a[i].w;
for(int i=1;i<=n;i++)
fa[i]=i;
sort(a+1,a+m+1,cmp);
int sum=0;
for(int i=1;i<=m;i++)
{
if(find(a[i].x)!=find(a[i].y))
{
fa[find(a[i].y)]=find(a[i].x);
sum+=a[i].w;
}
}
cout<<sum;
return 0;
}T4(P1806 跑步)
考试思路：打表
考试代码：
#include<bits/stdc++.h>
using namespace std;
int n;
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin>>n;
if(n==5)
cout<<2<<endl;
else if(n==6)
cout<<3<<endl;
else if(n==7)
cout<<4<<endl;
else if(n==8)
cout<<5<<endl;
else if(n==9)
cout<<7<<endl;
…………
else if(n==209)
cout<<834194699<<endl;
else if(n==210)
cout<<884987528<<endl;
else if(n==212)
cout<<995645335<<endl;
return 0;
}错误原因：写的不是正解
正确思路：背包dp
正确代码：
#include<bits/stdc++.h>
using namespace std;
long long dp[505];
int main()
{
dp[0]=1;
for(int i=1;i<=500;i++)
for(int j=500;j>=i;j--)
dp[j]=dp[j-i]+dp[j];
long long n;
cin>>n;
cout<<dp[n]-1<<"\n";
return 0;
}T5(P1702 突击考试)
考试思路：直接暴力枚举
考试代码：
#include<bits/stdc++.h>
using namespace std;
int n,a[100005],b[100005];
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin>>n;
for(int i=1;i<=n;i++)
cin>>a[i]>>b[i];
int l=0,k=1e9;
for(int i=1;i<=n;i++)
{
int ans=1,i1=i+1;
while((a[i]==a[i1]||a[i]==b[i1])&&i1<n)
i1++,ans++;
if(l<ans)
{
l=ans;
k=a[i];
}
else if(l==ans&&k>a[i])
k=a[i];
ans=1,i1=i+1;
while((b[i]==a[i1]||b[i]==b[i1])&&i1<n)
i1++,ans++;
if(l<ans)
{
l=ans;
k=b[i];
}
else if(l==ans&&k>b[i])
k=b[i];
}
cout<<l<<' '<<k;
return 0;
}错误原因：没有写正解
正确思路：这道题目的数在1~5之间，可以直接用一层循环来枚举，需要枚举五遍n，用来判断是否连续
正确代码：
#include<bits/stdc++.h>
using namespace std;
int a[100005][5];
int main()
{
int n,maxn=0;
cin>>n;
for(int i=1;i<=n;i++)
for(int j=1;j<=2;j++)
cin>>a[i][j];
int ans=0,ak;
for(int i=1;i<=5;i++)
{
int lst=1;
for(int j=1;j<=n;j++)
{
if(a[j][1]==i||a[j][2]==i)
{
if(j-lst+1>ans)
{
ans=j-lst+1;
ak=i;
}
}
else
lst=j+1;
}
}
cout<<ans<<' '<<ak;
return 0;
}T6(P11005 [蓝桥杯 2024 省 Python B] 缴纳过路费)
考试思路：把每个起点和终点都枚举一遍，最后输出符合要求的数量
考试代码：
#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,m,l,r,ans,flag;
vector<int>e[100005],h[100005];
bool vis[100005];
void dfs(int u,int v,int cnt)
{
if(u==v)
{
if(cnt>=l&&cnt<=r)
flag=1;
return ;
}
if(flag==1)
return ;
vis[u]=1;
for(int i=0;i<e[u].size();i++)
if(vis[e[u][i]]==0)
dfs(e[u][i],v,max(cnt,h[u][i]));
vis[u]=0;
}
signed main()
{
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin>>n>>m>>l>>r;
while(m--)
{
int u,v,w;
cin>>u>>v>>w;
e[u].push_back(v);
e[v].push_back(u);
h[u].push_back(w);
h[v].push_back(w);
}
for(int i=1;i<=n;i++)
{
for(int j=i+1;j<=n;j++)
{
flag=0;
dfs(i,j,0);
ans+=flag;
}
}
cout<<ans<<'\n';
return 0;
}错误原因：闹子瓦特
正确思路：最小生成树
正确代码：
#include<bits/stdc++.h>
using namespace std;
const int N=1e6+1;
int ans,fa[N],s[N];
struct node
{
int x,y,w;
}a[N];
bool comp(node a1,node a2)
{
return a1.w<a2.w;
}
int Father(int x)
{
if(fa[x]!=x)
return fa[x]=Father(fa[x]);
return x;
}
void unionn(int x,int y)
{
if (x!=y)
fa[x]=y,s[y]+=s[x];
}
int main()
{
int n,m,l,r;
cin>>n>>m>>l>>r;
for(int i=1;i<=n;i++)
fa[i]=i,s[i]=1;
for(int i=1;i<=m;i++)
cin>>a[i].x>>a[i].y>>a[i].w;
sort(a+1,a+1+m,comp);
for(int i=1;i<=m;i++)
{
if(a[i].w>r)
break;
int x=Father(a[i].x),y=Father(a[i].y);
if(x==y)
continue;
if(a[i].w>=l)
ans+=s[x]*s[y];
unionn(x,y);
}
cout<<ans;
return 0;
}