专栏文章

3.11错题总结

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

文章操作

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

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

T2(P1049 [NOIP 2001 普及组] 装箱问题)

考试思路：把能装出来的都标记，然后找n行中最大的标记的，然后输出

时间复杂度：O(nm)

考试代码：
CPP
#include<bits/stdc++.h>
using namespace std;
int dp[35][20005],w[35],n,m; 
int main()
{
	cin>>m>>n;
	for(int i=1;i<=n;i++)
		cin>>w[i];
	dp[0][0]=1;
	for(int i=1;i<=n;i++)
	{
		dp[i][w[i]]=1;
		for(int j=w[i]+1;j<=m;j++)
			dp[i][j]=max(dp[i-1][j],dp[i-1][j-w[i]]);
	}
	for(int j=m;j>=1;j--)
	{
		if(dp[n][j]==1)
		{
			cout<<m-j;
			return 0;
		}
	}
	cout<<m;
	return 0;
}
错误原因：脑子宕机了，写错了

正确思路：存容量为i的背包最多能装多少东西，然后输出

时间复杂度：O(nm)

正确代码：
CPP
#include<bits/stdc++.h>
using namespace std;
int v,n,dp[100005],c[100005];
int main()
{
    cin>>v>>n;
    for(int i=1;i<=n;i++)
        cin>>c[i];
    for(int i=1;i<=n;i++)
        for(int j=v;j>=c[i];j--)
            dp[j]=max(dp[j],dp[j-c[i]]+c[i]);
    cout<<v-dp[v];	
    return 0;
}

T3(U542235 查找二叉树)

考试思路;骗分

时间复杂度：O(1)

考试代码：
CPP
#include<bits/stdc++.h>
using namespace std;
int a[105];
int main()
{
	int n,x;
	cin>>n>>x;
	for(int i=1;i<=n;i++)
	{
		int ls,rs;
		cin>>a[i]>>ls>>rs;
		if(a[i]==x)
		{
			cout<<i<<'\n';
			return 0;
		}
	}
	return 0;
}
错误原因：没时间写

T4(P3916 图的遍历)

考试思路：遍历一次就把遍历到的数都标记成能到达的数，最后输出

时间复杂度：O(n2n^2)

考试代码：
CPP
#include<bits/stdc++.h>
using namespace std;
vector<int>e[100005],s,l;
bool vis[100005];
int d[100005],cnt;
void dfs(int u)
{
	vis[u]=1;
	l.push_back(u);
	if(cnt<u)
	{
		s.clear();
		for(int i=0;i<l.size();i++)
			s.push_back(l[i]);
	}
	cnt=max(cnt,u);
	for(int i=0;i<e[u].size();i++)
		if(vis[e[u][i]]==0)
			dfs(e[u][i]);
	l.pop_back(); 
	vis[u]=1;
}
int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	int n,m;
	cin>>n>>m;
	while(m--)
	{
		int u,v;
		cin>>u>>v;
		e[u].push_back(v);
	}
	for(int i=1;i<=n;i++)
	{
		if(d[i]!=0)
			continue;
		cnt=0;
		dfs(i);
		while(s.size()>0)
		{
			d[s[s.size()-1]]=max(d[s[s.size()-1]],cnt);
			s.pop_back();
		}
	}
	for(int i=1;i<=n;i++)
		cout<<d[i]<<' ';
	return 0;
}
错误原因：回溯了个寂寞
CPP
	l.pop_back(); 
	vis[u]=1;

正确思路：边扫边记录

时间复杂度：O(n)

正确代码：
CPP
#include <bits/stdc++.h>
using namespace std;
int a[100005];
int f[100005];
vector<int>y[100005];
int maxn=-1e9;
void dfs(int sx,int u)
{
	if(f[u])
		return ;
	f[u]=sx;
	int len=y[u].size();
	for(int i=0;i<y[u].size();i++)
	{
		int v=y[u][i];
		dfs(sx,v);
	}
}
signed main()
{
	int n,m;
	cin>>n>>m;
	for(int i=1;i<=m;i++)
	{
		int x,k;
		cin>>x>>k;
		y[k].push_back(x);
	}
	for(int i=n;i>=1;i--)
		if(!f[i])
			dfs(i,i);
	for(int i=1;i<=n;i++)
		cout<<f[i]<<' ';
	return 0;
}

T5(B3856 [语言月赛 202309] 椰奶国)

考试思路：分几种情况，哪种情况就按那种情况模拟

时间复杂度：O(?)

考试代码：
CPP
#include<bits/stdc++.h>
using namespace std;
void solve()
{
	long long n,A,B,C,D,E,F,cnt=0;
	bool flag=0;
	cin>>n>>A>>B>>C>>D>>E>>F;
	if(D-A==0)
	{
		int z=E-B-1;
		if(z==-1)
			cnt=F-C;
		else if(z==0)
			cnt=B*10+1-C+F;
		else
		{
			cnt=B*10+1-C+F;
			int s=B+1,t=E-1;
			if(s==t)
				cnt+=s*10+1;
			else
				cnt+=(s*10+2+t*10)/(E-B-1)*2;
		}
	}
	else
		cnt=8;
	cout<<cnt<<'\n';
}
int main()
{
	int t;
	cin>>t;
	while(t--)
		solve();
	return 0;
}
错误原因：没写完上厕所去了

正确思路：把两个时间对应的秒数求出来如果是同一天就直接相减，如果不是就加上一天的时间在减去第一天加上第二天，最后输出

时间复杂度：O(nt)

正确代码：
CPP
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=10005;
int T,n,h1,m1,s1,h2,m2,s2;
signed main()
{
    cin>>T;
    while(T--)
	{
        cin>>n>>h1>>m1>>s1>>h2>>m2>>s2;
        int tot=0;
        for(int i=0;i<=n-1;i++)
			tot+=(1+i*10+1)*(i+1)/2;
		int res1=0;
        for(int i=0;i<=h1-1;i++)
		    res1+=(1+i*10+1)*(i+1)/2;
		res1+=(1+(m1-1)*10+1)*m1/2;
		res1+=s1+1;
	    int res2=0;
		for(int i=0;i<=h2-1;i++)
			res2+=(1+i*10+1)*(i+1)/2;
		res2+=(1+(m2-1)*10+1)*m2/2;
		res2+=s2+1; 
        if(res2>=res1)
			cout<<res2-res1<<endl;
		else
			cout<<res2+tot-res1<<endl;
	}
    return 0;
}

T6(P2383 狗哥玩木棒)

考试思路：骗分

时间复杂度：O(nt)

考试代码：
CPP
#include<bits/stdc++.h>
using namespace std;
int a[25];
void solve()
{
	int n,cnt=0,mx=-1e9;
	cin>>n;
	for(int i=1;i<=n;i++)
	{
		cin>>a[i];
		cnt+=a[i];
		mx=max(mx,a[i]);
	}
	if(cnt%n!=0||n%4!=0||cnt/4<mx)
		cout<<"no\n";
	else
		cout<<"yes\n";
}
int main()
{
	int t;
	cin>>t;
	while(t--)
		solve();
	return 0;
}
错误原因：不会写，也没时间写

正确思路：这题和小猫爬山很像，只是小猫爬山不要求坐满，这题要求坐满，改一下即可

时间复杂度：O(tn2tn^2)

正确代码：
CPP
#include<bits/stdc++.h>
using namespace std;
int a[25],box[25],n,tot;
bool flag;
bool cmp(int x,int y)
{
	return x>y;
}
void dfs(int step)
{
	if(flag)
		return ;
	if(step>n)
	{
		flag=1;
		return ;
	}
	for(int i=1;i<=4;i++)
	{
		if(box[i]-a[step]>=0)
		{
			box[i]-=a[step];
			dfs(step+1);
			box[i]+=a[step];
		}
	}
	return ;
}
void solve()
{
	flag=0;
	tot=0;
	memset(box,0,sizeof box);
	cin>>n;
	for(int i=1;i<=n;i++)
		cin>>a[i],tot+=a[i];
	if(tot%4!=0)
	{
		cout<<"no\n";
		return ;
	}
	for(int i=1;i<=4;i++)
		box[i]=tot/4;
	sort(a+1,a+n+1,cmp);
	dfs(1);
	if(flag)
		cout<<"yes\n";
	else
		cout<<"no\n";
	return ;
}
int main()
{
	int t;
	cin>>t;
	while(t--)
		solve();
	return 0;
}

评论

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

正在加载评论...