5.27错题总结
wangyichenawm · · 个人记录
T1(P1151 子数整数)
考试思路：直接模拟
考试代码：
#include<bits/stdc++.h>
using namespace std;
int k;
bool pd(int i)
{
int sub1=i%1000;
i/=10;
int sub2=i%1000;
i/=10;
int sub3=i;
if(sub1%k==0&&sub2%k==0&&sub3%k==0)
return 1;
return 0;
}
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin>>k;
for(int i=10000;i<=30000;i++)
if(pd(i)==1)
cout<<i<<'\n';
return 0;
}错误原因：没看到无解就输出No
正确思路：模拟，如果没有解就输出No
正确代码：
#include<bits/stdc++.h>
using namespace std;
int k;
bool flag;
bool pd(int i)
{
int sub1=i%1000;
i/=10;
int sub2=i%1000;
i/=10;
int sub3=i;
if(sub1%k==0&&sub2%k==0&&sub3%k==0)
return 1;
return 0;
}
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin>>k;
for(int i=10000;i<=30000;i++)
if(pd(i)==1)
cout<<i<<'\n',flag=1;
if(!flag)
cout<<"No\n";
return 0;
}T2(P1376 [USACO05MAR] Yogurt factory 机器工厂)
考试思路：骗分
考试代码：
#include<bits/stdc++.h>
using namespace std;
int main()
{
cout<<"126900\n";
return 0;
}错误原因：没时间了
正确思路：加油站问题，每一次可以从之前买过来或者就在这里买
正确代码：
#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,s,v[10005],w[10005];
signed main()
{
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin>>n>>s;
for(int i=1; i<=n;i++)
cin>>v[i]>>w[i];
int ans=v[1]*w[1],num=v[1];
for(int i=2;i<=n;i++)
{
num=min(v[i],num+s);
ans+=w[i]*num;
}
cout<<ans;
return 0;
}T3(P6365 [传智杯 #2 初赛] 众数出现的次数)
考试思路：一个一个比较
考试代码：
#include<bits/stdc++.h>
using namespace std;
int n,a[1000005],b[1000005];
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];
b[i]^=a[i];
}
int ans=0,sum=0;
for(int i=1;i<=n;i++)
{
int z=0,z1=0;
for(int j=1;j<=n;j++)
{
if(a[j]==a[i]||b[j]==a[i])
z++;
if(a[j]==b[i]||b[j]==b[i])
z1++;
}
if(z==z1)
{
sum=z;
ans=min(a[i],b[i]);
}
if(z>sum)
{
ans=a[i];
sum=z;
}
if(z1>sum)
{
ans=b[i];
sum=z;
}
}
cout<<ans;
return 0;
}错误原因：TLE
正确思路：把a[i]和b[i]存map里，如果b[i]==a[i]，就只加一个a[i]，然后找最大值
正确思路：
#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,a[1000005],b[1000005];
map<int,int>cnt;
int maxi,ans;
signed 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];
b[i]=a[i]^b[i];
cnt[a[i]]++;
if(a[i]!=b[i])
cnt[b[i]]++;
}
for(int i=1;i<=n;i++)
{
if(maxi<cnt[a[i]])
{
maxi=cnt[a[i]];
ans=a[i];
}
if(maxi<cnt[b[i]])
{
maxi=cnt[b[i]];
ans=b[i];
}
}
cout<<ans;
return 0;
}T4(U225113 连接格点)
考试思路：因为横着连比竖着连贵，所以每列之间只连一次横着的
考试代码：
#include<bits/stdc++.h>
using namespace std;
int m,n,jl,jh;
bool vis[1005][1005];
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin>>m>>n;
int x1,y1,x2,y2;
while(cin>>x1>>y1>>x2>>y2)
{
if(abs(x2-x1)==1)
{
if(vis[max(x2,x1)][y1]==0)
jh++;
vis[max(x2,x1)][y1]=1;
}
else
{
if(vis[x2][max(y1,y2)]==0)
jl++;
vis[x2][max(y1,y2)]=1;
}
}
int ans=2*(n-1-jl)+(m-1)*n-jh;
cout<<ans;
return 0;
}错误原因：有多种情况没考虑
正确思路：最小生成树模版，可以把这个矩阵转换成一条线，以此来存数组
正确代码：
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e6+5;
int n,m,x,y,k,ans;
int x1,yy,x2,y2;
int fa[N];
int find(int x)
{
if(fa[x]==x)
return fa[x];
return fa[x]=find(fa[x]);
}
signed main()
{
cin>>n>>m;
for(int i=1;i<=n*m;i++)
fa[i]=i;
while(scanf("%d %d %d %d",&x1,&yy,&x2,&y2)==4)
{
x=(x1 - 1)*m+yy;
y=(x2 - 1)*m+y2;
x=find(x);
y=find(y);
if(x!=y)
{
fa[y]=x;
k++;
}
}
for (int j=1;j<=m;j++)
for (int i=1;i<n;i++)
{
x=find((i-1)*m+j);
y=find(i*m+j);
if(x!=y)
{
fa[y]=x;
k++;
ans++;
}
}
for(int i=1;i<=n;i++)
for(int j=1;j<m;j++)
{
x=find((i-1)*m+j);
y=find((i-1)*m+j+1);
if(x!=y)
{
fa[y]=x;
k++;
ans+=2;
}
}
cout<<ans;
return 0;
}T5(B3851 [GESP202306 四级] 图像压缩)
考试思路：模拟
考试代码：
#include<bits/stdc++.h>
using namespace std;
map<string,int>mp;
int n,m,ss[3][35];
struct N
{
int zh,id;
}a[305];
string s[305]={"00","01","02","03","04","05","06","07","08","09","0A","0B","0C","0D","0E","0F","10","11","12","13","14","15","16","17","18","19","1A","1B","1C","1D","1E","1F","20","21","22","23","24","25","26","27","28","29","2A","2B","2C","2D","2E","2F","30","31","32","33","34","35","36","37","38","39","3A","3B","3C","3D","3E","3F","40","41","42","43","44","45","46","47","48","49","4A","4B","4C","4D","4E","4F","50","51","52","53","54","55","56","57","58","59","5A","5B","5C","5D","5E","5F","60","61","62","63","64","65","66","67","68","69","6A","6B","6C","6D","6E","6F","70","71","72","73","74","75","76","77","78","79","7A","7B","7C","7D","7E","7F","80","81","82","83","84","85","86","87","88","89","8A","8B","8C","8D","8E","8F","90","91","92","93","94","95","96","97","98","99","9A","9B","9C","9D","9E","9F","A0","A1","A2","A3","A4","A5","A6","A7","A8","A9","AA","AB","AC","AD","AE","AF","B0","B1","B2","B3","B4","B5","B6","B7","B8","B9","BA","BB","BC","BD","BE","BF","C0","C1","C2","C3","C4","C5","C6","C7","C8","C9","CA","CB","CC","CD","CE","CF","D0","D1","D2","D3","D4","D5","D6","D7","D8","D9","DA","DB","DC","DD","DE","DF","E0","E1","E2","E3","E4","E5","E6","E7","E8","E9","EA","EB","EC","ED","EE","EF","F0","F1","F2","F3","F4","F5","F6","F7","F8","F9","FA","FB","FC","FD","FE","FF"};
string s2[25];
bool cmp(N x,N y)
{
if(x.zh!=y.zh)
return x.zh>y.zh;
return s[x.id]<s[y.id];
}
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin>>n;
for(int i=0;i<=255;i++)
mp[s[i]]=i;
for(int i=1;i<=n;i++)
{
cin>>s2[i];
m=s2[i].size();
for(int j=0;j<s2[i].size();j+=2)
{
string s1;
s1=s2[i][j];
s1+=s2[i][j+1];
a[mp[s1]].zh++;
a[mp[s1]].id=mp[s1];
}
}
sort(a,a+256,cmp);
for(int i=0;i<=15;i++)
{
cout<<s[a[i].id];
if(s[a[i].id][0]>9)
ss[1][i]=s[a[i].id][0]-'A'+10;
else
ss[1][i]=s[a[i].id][0]-'0';
if(s[a[i].id][1]>9)
ss[2][i]=s[a[i].id][1]-'A'+10;
else
ss[2][i]=s[a[i].id][1]-'0';
}
cout<<'\n';
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m/2;j++)
{
int mn=1e9,i1=0;
for(int z=0;z<=15;z++)
{
int xx1,xx2;
if(s2[i][2*j]>9)
xx1=s2[i][2*j]-'A'+10;
else
xx1=s2[i][2*j]-'0';
if(s2[i][2*j+1]>9)
xx2=s2[i][2*j+1]-'A'+10;
else
xx2=s2[i][2*j+1]-'0';
int f=xx1*10+xx2,f1=ss[1][z]*10+ss[2][z];
if(mn>abs(f-f1))
{
mn=abs(f-f1);
i1=z;
}
}
if(i1<=9)
cout<<i1;
else
{
char z=(i1+'A'-10);
cout<<z;
}
}
cout<<"\n";
}
return 0;
}错误原因：大模拟，太费时间，没写完
正确思路：模拟
正确思路：
#include<bits/stdc++.h>
using namespace std;
int toint(char c)
{
if (c>='A'&&c<='F')
return c-'A'+10;
return c-'0';
}
int a[25][25];
struct node
{
int hd;
int sl;
}c[300];
void myprint(int x)
{
char c;
if (x>9)
c='A'+x-10;
else
c=x+'0';
cout<<c;
}
bool cmp(node x,node y)
{
if (x.sl==y.sl) return x.hd<y.hd;
return x.sl>y.sl;
}
int main()
{
int n;
cin>>n;
string s;
for(int i=1;i<=n;i++)
{
cin>>s;
int t;
for(int j=0;j<s.size();j+=2)
{
t=toint(s[j])*16+toint(s[j+1]);
a[i][j/2+1]=t;
c[t].sl++;
}
}
for (int i=1;i<=255;i++)
c[i].hd=i;
sort(c,c+256,cmp);
for (int i=0;i<16;i++)
{
myprint(c[i].hd/16);
myprint(c[i].hd%16);
}
cout<<endl;
int len=s.length()/2;
for(int i=1;i<=n;i++)
{
for (int j=1;j<=len;j++)
{
int cha=256;
int p=0;
for (int k=0;k<=15;k++)
{
if (abs(c[k].hd-a[i][j])<cha)
{
cha=abs(c[k].hd-a[i][j]);
p=k;
}
}
myprint(p);
}
cout<<endl;
}
return 0;
}