专栏文章

3.25错题总结

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

文章操作

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

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

T1(P1051 [NOIP 2005 提高组] 谁拿了最多奖学金)

考试思路：一个个枚举，再比大小

时间复杂度：O(n)

考试代码：
CPP
#include<bits/stdc++.h>
using namespace std;
int n;
struct N
{
	string s;
	int pj,py;
	char gb,sf;
	int lw;
}a[105];
int main()
{
	cin>>n;
	for(int i=1;i<=n;i++)
		cin>>a[i].s>>a[i].pj>>a[i].py>>a[i].gb>>a[i].sf>>a[i].lw;
	int mx=-1e9,i1,zs=0;
	for(int i=1;i<=n;i++)
	{
		int jj=0;
		if(a[i].pj>80&&a[i].lw>=1)
			jj+=8000;
		if(a[i].pj>85&&a[i].py>80)
			jj+=4000;
		if(a[i].pj>90)
			jj+=2000;
		if(a[i].pj>85&&a[i].sf=='Y')
			jj+=1000;
		if(a[i].pj>80&&a[i].gb=='Y')
			jj+=850;
		if(jj>mx)
		{
			mx=jj;
			i1=i;
		}
		zs+=jj; 
	}
	cout<<a[i1].s<<'\n'<<mx<<'\n'<<zs;
	return 0;
}

错误原因：把py打成了pj

正确思路：一个个枚举，在比大小

时间复杂度：O(n)

正确代码：
CPP
#include<bits/stdc++.h>
using namespace std;
int n;
struct N
{
	string s;
	int pj,py;
	char gb,sf;
	int lw;
}a[105];
int main()
{
	cin>>n;
	for(int i=1;i<=n;i++)
		cin>>a[i].s>>a[i].pj>>a[i].py>>a[i].gb>>a[i].sf>>a[i].lw;
	int mx=-1e9,i1,zs=0;
	for(int i=1;i<=n;i++)
	{
		int jj=0;
		if(a[i].pj>80&&a[i].lw>=1)
			jj+=8000;
		if(a[i].pj>85&&a[i].py>80)
			jj+=4000;
		if(a[i].pj>90)
			jj+=2000;
		if(a[i].pj>85&&a[i].sf=='Y')
			jj+=1000;
		if(a[i].py>80&&a[i].gb=='Y')
			jj+=850;
		zs+=jj;
		if(mx<jj)
		{
			i1=i;
			mx=jj;
		}
	}
	cout<<a[i1].s<<'\n'<<mx<<'\n'<<zs;
	return 0;
}

T2(B4006 [GESP202406 四级] 宝箱)

考试思路：桶装价值，然后从一开始依次把价值为i到i+k的总和求出来比大小

时间复杂度：O(nk)

考试代码：
CPP
#include<bits/stdc++.h>
using namespace std;
int n,k,a[1005],vis[1005];
int main()
{
	cin>>n>>k;
	for(int i=1;i<=n;i++)
		cin>>a[i],vis[a[i]]++;
	int mx=-1e9;
	for(int i=1;i<=1000;i++)
	{
		if(vis[i]==0)
			continue;
		int ans=0;
		for(int j=i;j<=i+k;j++)
			ans+=vis[j]*j;
		mx=max(mx,ans);
	}
	cout<<mx<<'\n';
	return 0;
}

错误原因：数组越界了

正确思路：桶装价值，然后从一开始依次把价值为i到i+k的总和求出来比大小

时间复杂度：O(nk)

正确代码：
CPP
#include<bits/stdc++.h>
using namespace std;
int n,k,a[1005],vis[1005];
int main()
{
	cin>>n>>k;
	for(int i=1;i<=n;i++)
		cin>>a[i],vis[a[i]]++;
	int mx=-1e9;
	for(int i=1;i<=1000;i++)
	{
		if(vis[i]==0)
			continue;
		int ans=0;
		for(int j=i;j<=i+k&&j<=1000;j++)
			ans+=vis[j]*j;
		mx=max(mx,ans);
	}
	cout<<mx<<'\n';
	return 0;
}

T3(P1832 A+B Problem（再升级）)

考试思路：打表

时间复杂度：O(1)

考试代码：
CPP
#include<bits/stdc++.h>
using namespace std;
long long n;
int main()
{
	int n;
	cin>>n;
	if(n==1)
    cout<<0<<endl;
	if(n==2)
	    cout<<1<<endl;
	if(n==3)
	    cout<<1<<endl;
	if(n==4)
	    cout<<1<<endl;
	if(n==5)
	    cout<<2<<endl;
	if(n==6)
	    cout<<2<<endl;
	if(n==7)
	    cout<<3<<endl;
	if(n==8)
	    cout<<3<<endl;
	if(n==9)
	    cout<<4<<endl;
	if(n==10)
	    cout<<5<<endl;
	if(n==11)
	    cout<<6<<endl;
	if(n==12)
	    cout<<7<<endl;
略…………
	if(n==255)
	    cout<<107807529<<endl;
	if(n==256)
	    cout<<112302573<<endl;
	if(n==257)
	    cout<<116975172<<endl;
	if(n==258)
	    cout<<121831963<<endl;
	if(n==259)
	    cout<<126879839<<endl;
	if(n==260)
	    cout<<132125912<<endl;
	return 0;
}

错误原因：不是正解

正确思路：完全背包dp

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

正确代码：
CPP
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e3+5;
int a[N],dp[N];
bool zs(int x)
{
	for(int i=2;i<=sqrt(x);i++)
		if(x%i==0)
			return false;
	return true;
}
signed main()
{
	int n,cnt=0;
	cin>>n;
	for(int i=2;i<=n;i++)
		if(zs(i)==true)
			a[++cnt]=i;
	dp[0]=1;
	for(int i=1;i<=cnt;i++)
		for(int j=a[i];j<=n;j++)
			dp[j]=dp[j]+dp[j-a[i]];
	cout<<dp[n]<<endl;
	return 0;
}

T4(P1692 部落卫队)

考试思路：把图都遍历一遍，用vector数组存遍历路线

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

考试代码：
CPP
#include<bits/stdc++.h>
using namespace std;
int n,m,mx=-1e9;
bool vis[105][105],f[105];
vector<int>da,l;
void dfs(int step,int sum)
{
	if(step>n)
	{
		if(sum>mx)
		{
			da.clear();
			for(int i=0;i<n;i++)
				da.push_back(l[i]);
			mx=sum;
		}
		return ;
	}
	bool flag=0;
	for(int i=1;i<=n;i++)
	{
		if(f[i]==1)
		{
			if(vis[step][i]==1)
			{
				flag=1;
				break;
			}
		}
	}
	if(flag==0)
	{
		l.push_back(1);
		f[step]=1;
		dfs(step+1,sum+1);
		l.pop_back();
		f[step]=0;
	}
	l.push_back(0);
	dfs(step+1,sum);
	l.pop_back();
}
int main()
{
	cin>>n>>m;
	for(int i=1;i<=m;i++)
	{
		int u,v;
		cin>>u>>v;
		vis[u][v]=1;
		vis[v][u]=1;
	}
	for(int i=1;i<=n;i++)
		dfs(i,0);
	cout<<mx<<'\n';
	for(int i=0;i<n;i++)
		cout<<da[i]<<' ';
	cout<<'\n';
	return 0;
}

错误原因：暴力超时

正确思路：只搜一遍，从小往大搜

时间复杂度：O(nlogn)

正确代码：
CPP
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=105;
int T,n,m,e[N][N],ans;
bool vis[N],f[N];
void dfs(int u,int sum)
{
	if(u>n)
	{
		if(sum>ans)
		{
			ans=sum;
			for(int i=1;i<=n;i++)
				f[i]=vis[i];
		}
		return ;
	}
	bool flag=0;
	for(int v=1;v<u;v++)
	{
		if(e[u][v]&&vis[v])
		{
			flag=1;
			break;
		}
	}
	if(flag==0)
	{
		vis[u]=1;
		dfs(u+1,sum+1);
		vis[u]=0;
	}
	dfs(u+1,sum);
	return ;
}
signed main()
{
	cin>>n>>m;
	while(m--)
	{
		int u,v;
		cin>>u>>v;
		e[u][v]=e[v][u]=1;
	}
	dfs(1,0);
	cout<<ans<<'\n';
	for(int i=1;i<=n;i++)
		cout<<f[i]<<' ';
	return 0;
}

T5(P7965 [COCI 2021/2022 #2] Kutije)

考试思路：拿部分分，暴力拿取，剩下的骗分

时间复杂度：O(n3n^3)

考试代码：
CPP
#include<bits/stdc++.h>
using namespace std;
int n,m,q,a[1005],c[1005],b[1005][1005],ans;
int main()
{
	cin>>n>>m>>q;
	for(int i=1;i<=m;i++)
	{
		for(int j=1;j<=n;j++)
		{
			cin>>b[i][j];
			if(b[i][j]!=j)
				ans++;
		}
	}
	if(m==1)
	{
		while(q--)
		{
			int x,y;
			cin>>x>>y;
			for(int i=1;i<=n;i++)
				a[i]=i;
			for(int z=1;z<=ans;z++)
			{
				for(int i=1;i<=n;i++)
					c[b[1][i]]=a[i];
				if(c[y]==x)
				{
					cout<<"DA\n";
					break;
				}
				for(int i=1;i<=n;i++)
					c[b[1][i]]=a[i];
			}
			if(c[y]!=x)
				cout<<"NE\n";
		}
	}
	else
	{
		for(int i=1;i<=q;i++)
		{
			if(i%2==1)
				cout<<"DA\n";
			else
				cout<<"NE\n";
		}
	}
	return 0;
}

错误原因：TLE

正确思路：并查集板子题

时间复杂度：O(nm)

正确代码：
CPP
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=10005;
int Q,n,m,ans,fa[N];
int getf(int x)
{
	if(fa[x]==x)
		return x;
	return fa[x]=getf(fa[x]);
}
signed main()
{
	cin>>n>>m>>Q;
	for(int i=1;i<=n;i++)
		fa[i]=i;
	while(m--)
	{
		for(int i=1;i<=n;i++)
		{
			int x;
			cin>>x;
			int t1=getf(i),t2=getf(x);
			fa[t1]=t2;
		}
	}
	while(Q--)
	{
		int u,v;
		cin>>u>>v;
		int t1=getf(u),t2=getf(v);
		if(t1==t2)
			cout<<"DA\n";
		else
			cout<<"NE\n"; 
	}
	return 0;
}

T6(P2655 2038年问题)

考试思路：按照时间进制模拟个大概

时间复杂度：O(t)

考试代码：
CPP
#include<bits/stdc++.h>
#define int long long
using namespace std;
void solve()
{
	int ws,n,y,r,s,f,m;
	cin>>ws>>n>>y>>r>>s>>f>>m;
	int ms=pow(2,ws-1)-1;
	m+=ms;
	int m1=m/60;
	m=m%60;
	f+=m1;
	int f1=f/60;
	f=f%60;
	s+=f1;
	int s1=s/24;
	s=s%24;
	r+=s1;
	while(1)
	{
		if(r<32)
		{
			if(y==2)
			{
				if((n%4==0&&n%100!=0)||n%400==0)
				{
					if(r<=29)
						break;
				}
				else if(r<=28)
					break;
			}
			else if(y==1||y==3||y==5||y==7||y==8||y==10||y==12)
			{
				if(r<=31)
					break;
			}
			else if(r<=30)
				break;
		}
		if(y==2)
		{
			if(n%4==0&&n%100!=0)
			{
				r-=29;
				y++;
			}
			else if(n%400==9)
			{
				r-=29;
				y++;
			}
			else
			{
				r-=28;
				y++;
			}
		}
		else if(y==1||y==3||y==5||y==7||y==8||y==10||y==12)
		{
			r-=31;
			y++;
		}
		else
		{
			r-=30;
			y++;
		}
		if(y>12)
		{
			y=1;
			n++;
		}
	}
	cout<<n<<' '<<y<<' '<<r<<' '<<s<<' '<<f<<' '<<m<<'\n';
	return ;
}
signed main()
{
	ios::sync_with_stdio(0);
	int t;
	cin>>t;
	while(t--)
		solve();
	return 0;
}

错误原因：因为是直接除以所以有不准确性

正确思路：根据时间模拟，时分秒都可以直接除，后面的要按照年月日的进制方式，来推

时间复杂度：O(t)

正确代码：
CPP
#include<bits/stdc++.h>
using namespace std;
long long T,jz,ye,mo,da,ho,mi,se;
int month[13]={0,31,28,31,30,31,30,31,31,30,31,30,31};
void change()
{
	if(ye%400==0)
		month[2]=29;
	else if(ye%100!=0 && ye%4==0)
		month[2]=29;
	else
		month[2]=28;
}
int main()
{
	cin>>T;
	while(T--)
	{
		cin>>jz>>ye>>mo>>da>>ho>>mi>>se;
		long long tot=(1<<(jz-1))-1;
		se+=tot;
		mi+=se/60, se%=60;
		ho+=mi/60, mi%=60;
		da+=ho/24, ho%=24;
		if(mo==2)
			change();
		while(da>month[mo])
		{
			da-=month[mo];
			mo++;
			if(mo>12)
				ye++,mo=1;
			if(mo==2)
				change();
		}
		printf("%lld %lld %lld %lld %lld %lld\n",ye,mo,da,ho,mi,se);
	}
	return 0;
}

评论

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

正在加载评论...