3.25错题总结
wangyichenawm · · 个人记录
T1(P1051 [NOIP 2005 提高组] 谁拿了最多奖学金)
考试思路：一个个枚举，再比大小
时间复杂度：O(n)
考试代码：
#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)
正确代码：
#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)
考试代码：
#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)
正确代码：
#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)
考试代码：
#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(n^2 )
正确代码：
#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(n^2 )
考试代码：
#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)
正确代码：
#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(n^3 )
考试代码：
#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)
正确代码：
#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)
考试代码：
#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)
正确代码：
#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;
}