专栏文章

8.23错题总结

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

文章操作

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

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

T1(B3702 [语言月赛202301] 华小科的旅行开始了)

考试思路：直接按照数组给的路线模拟，并输出

考试代码：
CPP
#include<bits/stdc++.h>
using namespace std;
int n,m,sx,sy;
struct N
{
	int x,y;
}a[1005][1005];
int main()
{
	cin>>n>>m>>sx>>sy;
	for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++)
			cin>>a[i][j].x>>a[i][j].y;
	while(a[sx][sy].x!=0&&a[sx][sy].y!=0)
	{
		cout<<sx<<' '<<sy<<'\n';
		int j=sx;
		sx=a[sx][sy].x;
		sy=a[j][sy].y;
	}
	cout<<sx<<' '<<sy<<'\n';
	return 0;
}

正确思路：直接按照数组给的路线模拟，并输出，注意先输入m再输入n，不要搞反了

正确代码：
CPP
#include<bits/stdc++.h>
using namespace std;
int n,m,sx,sy;
struct N
{
	int x,y;
}a[1005][1005];
int main()
{
	cin>>m>>n>>sx>>sy;
	for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++)
			cin>>a[i][j].x>>a[i][j].y;
	while(a[sx][sy].x!=0&&a[sx][sy].y!=0)
	{
		cout<<sx<<' '<<sy<<'\n';
		int j=sx;
		sx=a[sx][sy].x;
		sy=a[j][sy].y;
	}
	cout<<sx<<' '<<sy<<'\n';
	return 0;
}

T3(T658802 突击考试)

考试思路：因为a[i]和b[i]只有5，所以我就用了前缀和记录，再跑5遍双指针

考试代码：
CPP
#include<bits/stdc++.h>
using namespace std;
int sum[15][100005],ans,k,a[100005],b[100005];
int main()
{
	int n;
	cin>>n;
	for(int i=1;i<=n;i++)
	{
		cin>>a[i]>>b[i];
		sum[a[i]][i]=1;
		if(a[i]==b[i])
			continue;
		sum[b[i]][i]=1;
	}
	for(int j=1;j<=5;j++)
		for(int i=1;i<=n;i++)
			sum[j][i]+=sum[j][i-1];
	for(int i=1;i<=5;i++)
	{
		int l=1,cnt=0;
		for(int r=1;r<=n;r++)
		{
			int z=sum[i][r]-sum[i][l-1];
			while(sum[i][r]-sum[i][l]>=z&&l<=r)
				l++;
			if(l>r)
				l--;
			if(sum[i][r]-sum[i][l-1]>=r-l+1)
				cnt=max(cnt,r-l+1);
		}
		if(ans<cnt)
		{
			ans=cnt;
			k=i;
		}
	}
	cout<<ans<<' '<<k;
	return 0;
}

正确思路：直接硬搜我竟然没想出来

正确代码：
CPP
#include<bits/stdc++.h>
using namespace std;
int n,K=100,ans,cnt,a[100005],b[100005];
int main()
{
	cin>>n;
	for(int i=1;i<=n;i++)
		cin>>a[i]>>b[i];
	for(int k=1;k<=5;k++)
	{
		cnt=0;
		for(int i=1;i<=n;i++)
		{
			if(a[i]==k||b[i]==k)
				cnt++;
			else
				cnt=0;
			if(cnt>ans)
				ans=cnt,K=k;
		}
	}
	cout<<ans<<' '<<K;
	return 0;
}

T5(T658813 奶牛的羁绊)

考试思路：骗分

考试代码：
CPP
#include<bits/stdc++.h>
using namespace std;
int main()
{
	cout<<"0\n1\n0\n2\n1\n";
	return 0;
}

正确思路：树的父节点已经搜到了，那它的子节点一定会受影响。DFS序中，一个节点和它的子树一定是连在一起的。所以用DFS求出各个节点的子树大小和DFS序，因为要做区间修改，所以我们用树状数组维护差分数组，每次用get_sum求出单点的答案，然后再把它的子树全部加一，以便后面求值。

正确代码：
CPP
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e5+5, INF=1E9;
int n,m,a[N],c[N];
int idx,dfn[N],siz[N];
vector<int>e[N];
void dfs(int u,int father)
{
	dfn[u]=++idx;
	siz[u]=1;
	for(int i=0;i<e[u].size();i++)
	{
		int v=e[u][i];
		if(v==father)
			continue;
		dfs(v,u);
		siz[u]+=siz[v];
	}
	return;
}
int lowbit(int x)
{
	return x&-x;
}
int get_sum(int x)
{
	int res=0;
	while(x>0)
	{
		res+=c[x];
		x-=lowbit(x);
	}
	return res;
}
void modify(int x,int val)
{
	while(x<=n)
	{
		c[x]+=val;
		x+=lowbit(x);
	}
	return;
}
signed main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin>>n;
	for(int i=1;i<n;i++)
	{
		int u,v;
		cin>>u>>v;
		e[u].push_back(v);
		e[v].push_back(u);
	}
	dfs(1,-1);
	for(int i=1;i<=n;i++)
	{
		int x;
		cin>>x;
		int id=dfn[x];
		cout<<get_sum(id)<<'\n';
		modify(id+1,1);
		modify(id+siz[x]-1+1,-1);
	}
	return 0;
}

评论

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

正在加载评论...