8.3综合测试-错题分析和改正
赛时题目(只包含本人做错的)
-T639126 落落的去的数学问题2-
居然还能出续集😡
题目描述
对于正整数 $x, y$，定义 $f(x, y)$ 为“$(x+y)$ 除以 $10^8$ 的余数”。
给定一个长度为 $N$ 的正整数序列 $A=(A_1,\ldots,A_N)$。请计算下式的值：
$$ \sum_{i=1}^{N-1}\sum_{j=i+1}^N f(A_i, A_j) $$
错误原因
- 暴力 $20pts$。
错误代码
#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,a[300010],sum=0;
signed main()
{
cin>>n;
for(int i=1;i<=n;i++)
{
cin>>a[i];
}
for(int i=1;i<n;i++)
{
for(int j=i+1;j<=n;j++)
{
sum+=(a[i]+a[j])%100000000;
}
}
cout<<sum;
return 0;
}
正解
思路
- 因为任意两个数都要相加,就先把所有的 $2$ 个数都加上,这里只需要一层循环,然后用 $sum$(变量) 减去多余的部分。
- 多余部分:因为 $a_i<10^8,a_i+a_j<2 \times 10^8$,所以余数一定是 $a_i+a_j-10^8$。
代码
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int mod=1e8;
int n,a[300010],sum=0,ans=0;
signed main()
{
cin>>n;
for(int i=1;i<=n;i++)
{
cin>>a[i];
}
sort(a+1,a+n+1);
for(int i=1;i<=n;i++)
{
sum+=a[i];
int res=lower_bound(a+i+1,a+n+1,mod-a[i])-a;
res=n-res+1;
ans+=res;
}
cout<<sum*(n-1)-ans*mod;
return 0;
}
-T638485 第K小-
题目描述
落落的去又开始研究奇奇怪怪的问题，然后研究出来一个新问题，这个问题是这样子的，有 $n$ 种小球，每种小球都有一个值，每种小球都有无限个。每次可以拿若干个小球，可以重复拿某些种类小球，每次至少拿一个。我们的目标是找到第 $k$ 小值，注意可能存在拿不同的球的方案数但是值相同，这种只算一种值。
错误原因
- 未想出正解,代码只有框架,所以 $0pts$。
错误代码
不想说(其实根本没有)
正解
思路
-
先想暴力做法:
第 $1$ 小的数字 $k1$,是 $a$ 数组中最小的数;
第 $2$ 小的数字 $k2$, 先让 $k2$ 和 $a$ 数组中其他的数字相加,再从产生的所有数字中找出最小的数就是 $k2$;
第 $3$ 小的数字 $k3$, 先让 $k3$ 和 $a$ 数组中其他的数字相加,再从产生的所有数字中找出最小的数就是 $k3$;
以此类推$\dots$
代码
#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,k,a[10010],ans=0;
map<int,bool> mp;//map用于去重
void bfs()
{
priority_queue<int,vector<int>,greater<int> > q;
for(int i=1;i<=n;i++)
{
if(!mp[a[i]])
{
q.push(a[i]);
mp[a[i]]=true;
}
}
while(!q.empty())
{
ans++;
int f=q.top();
q.pop();
if(ans==k)
{
cout<<f;
return ;
}
for(int i=1;i<=n;i++)
{
if(!mp[f+a[i]])
{
mp[f+a[i]]=true;
q.push(f+a[i]);
}
}
}
cout<<"0";
}
signed main()
{
cin>>n>>k;
for(int i=1;i<=n;i++)
{
cin>>a[i];
}
bfs();
return 0;
}
-U591734 磁铁迷宫-
题目描述
有一个 $h$ 行 $w$ 列的格子，其中有若干个（也可能为 $0$ 个）格子上放置了磁铁。
格子的状态由 $h$ 个长度为 $w$ 的字符串 $S_1,S_2,\ldots,S_h$ 表示，$S_i$ 的第 $j$ 个字符为 # 时，表示从上往下第 $i$ 行、从左往右第 $j$ 列的格子上放置了磁铁，为 . 时表示该格子上没有放置任何东西。
落落的去穿着铁制盔甲，在某个格子时可以按如下方式移动：
- 如果当前格子的上下左右相邻的任意一个格子上放置了磁铁，则无法移动到任何地方。
- 否则，可以选择上下左右相邻的任意一个格子并移动到该格子。
但不能移动到格子外面。
对于没有放置磁铁的每个格子，定义该格子的自由度为“最初落落的去在该格子时，从该格子出发通过多次移动能够到达的格子的数量”。
请你求出所有没有放置磁铁的格子中，自由度的最大值。
需要注意的是，在自由度的定义中，“能够通过多次移动到达的格子”指的是，从最初所在的格子出发，通过若干次（也可以为 $0$ 次）移动能够到达的格子，不要求存在一种移动方式能够遍历所有这些格子。特别地，每个没有放置磁铁的格子本身总是包含在“能够到达的格子”之中。
错误原因
- 时间不足,来不及修改错误代码。
错误代码
#include<bits/stdc++.h>
#define int long long
using namespace std;
struct node
{
int x,y,step;
};
int dx[4]={0,1,0,-1};
int dy[4]={1,0,-1,0};
int n,m,ans=1;
char c[1010][1010];
bool vis[1010][1010];
queue<node> q;
bool check(int x,int y)
{
for(int i=1;i<=4;i++)
{
int nx,ny;
nx=x=dx[i];
ny=y=dy[i];
if(c[nx][ny]=='#')
{
return true;
}
}
return false;
}
void bfs(int x,int y)
{
vis[x][y]=true;
q.push({x,y,0});
while(!q.empty())
{
node f=q.front();
q.pop();
ans=max(ans,f.step);
for(int i=0;i<4;i++)
{
node nf;
nf.x=f.x=dx[i];
nf.y=f.y=dy[i];
nf.step=f.step+1;
if(nf.x>=1 && nf.x<=n && nf.y>=1 && nf.y<=m && !vis[nf.x][nf.y])
{
vis[nf.x][nf.y]=true;
q.push(nf);
}
}
}
}
signed main()
{
cin>>n>>m;
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
cin>>c[i][j];
}
}
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
if(check(i,j))
{
bfs(i,j);
memset(vis,false,sizeof(vis));
if(!q.empty())
{
q.pop();
}
}
}
}
cout<<ans;
return 0;
}
甚至没写完都有 $3pts$。
补药让我改这个错误代码啊aaa
正解
思路
-
我们可以定义一个 $a$ 数组来储存每个点的状态:
$a_{ij}=0:$ 本身不是磁铁且周围没有磁铁;
$a_{ij}=1:$ 本身就是磁铁;
$a_{ij}=2:$ 本身不是磁铁但周围有磁铁。 -
还需要定义一个 $int$ 类型的 $vis$ 数组,第 $color$ 次搜索就将搜过的位置赋值为 $color$,即 $vis_{ij}=color$。
提醒: $i$ 和 $j$ 均为下标。
代码
#include<bits/stdc++.h>
#define int long long
using namespace std;
int dx[4]={1,-1,0,0};
int dy[4]={0,0,1,-1};
int n,m,a[1010][1010];//网格数据，1表示障碍物，0表示普通区域，2表示边界区域
int ans=1;//记录最大连通块大小
int vis[1010][1010];//标记访问状态，存储连通块编号
int cnt,color;//cnt当前连通块大小，color连通块编号
void dfs(int x,int y)//深搜遍历所有连通块
{
for(int i=0;i<4;i++)//遍历
{
int nx,ny;
nx=x+dx[i];
ny=y+dy[i];//计算新坐标
//判断是否越界、已访问、或为障碍物
if(nx>=1 && nx<=n && ny>=1 && ny<=m && vis[nx][ny]!=color && a[nx][ny]!=1)
{
vis[nx][ny]=color;//标记为当前连通块
cnt++;//连通块大小加1
if(a[nx][ny]==2)
{
continue;//边界区域不再继续扩散
}
dfs(nx,ny);//递归遍历
}
}
}
signed main()
{
cin>>n>>m;//输入网格尺寸
for(int i=1;i<=n;i++)//读取网格数据
{
for(int j=1;j<=m;j++)
{
char c;
cin>>c;
if(c=='#')
{
a[i][j]=1;//'#'表示障碍物
}
else
{
a[i][j]=0;//其他为可通行区域
}
}
}
for(int i=1;i<=n;i++)//标记边界区域,即与障碍物相邻的可通行区域
{
for(int j=1;j<=m;j++)
{
if(a[i][j]==1)
{
continue;//跳过障碍物
}
if(a[i-1][j]==1||a[i+1][j]==1||a[i][j-1]==1||a[i][j+1]==1)//如果上下左右有障碍物
{
a[i][j]=2;//标记为边界
}
}
}
for(int i=1;i<=n;i++)//寻找最大的普通连通块,即非边界的可通行区域
{
for(int j=1;j<=m;j++)
{
if(vis[i][j]==0 && a[i][j]==0)//如果未访问且为普通区域
{
color++;//新连通块编号
cnt=1;//初始化大小为1(当前格子)
vis[i][j]=color;//标记当前格子
dfs(i,j);//遍历整个连通块
ans=max(ans,cnt);//更新最大值
}
}
}
cout<<ans;//输出结果
return 0;
}