寒假集训一期总结(一)–––思维训练-创新互联
目录
创新互联专注为客户提供全方位的互联网综合服务,包含不限于成都网站建设、成都网站设计、渭城网络推广、成都小程序开发、渭城网络营销、渭城企业策划、渭城品牌公关、搜索引擎seo、人物专访、企业宣传片、企业代运营等,从售前售中售后,我们都将竭诚为您服务,您的肯定,是我们大的嘉奖;创新互联为所有大学生创业者提供渭城建站搭建服务,24小时服务热线:028-86922220,官方网址:www.cdcxhl.com思维训练
走方格
解题思路
参考代码
最短曼哈顿距离
编辑 解题思路
参考代码
酒厂选址
解题思路
参考代码
雪地足迹Tracks in the Snow
解题思路
参考代码
一个星期没有更博客了…这一个星期,去学校信竞集训的我收获颇丰,下面就是我的还加集训总结
思维训练下面是思维训练中比较重要的题目
走方格解题思路本题主要考查了动态规划;
我们用dp1[i][j]记录从(1,1)到(i,j)的大得分
我们用dp2[i][j]记录从(i,j)到(1,1)的大得分
由于要经过点(i,j),但是要去掉(i,j)的大得分
如下图:
从左侧绕开(i,j)的大得分
从上方绕开(i,j)的大得分
所以最多能获得的最小值为
参考代码#includeusing namespace std;
long long n,m,dp2[2005][2005];
long long dp1[2005][2005];
long long a[2005][2005];
long long x[2005][2005];
long long y[2005][2005];
long long minn=LONG_LONG_MAX;
int main(){
ios::sync_with_stdio(false);
cin>>n>>m;
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
cin>>a[i][j];
dp1[i][j]=max(dp1[i-1][j],dp1[i][j-1])+a[i][j];
}
}
for(int i=n;i>=1;i--){
for(int j=m;j>=1;j--){
dp2[i][j]=max(dp2[i+1][j],dp2[i][j+1])+a[i][j];
}
}
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
x[i][j]=max(x[i][j-1],dp1[i][j-1]+dp2[i+1][j-1]);
y[i][j]=max(y[i-1][j],dp1[i-1][j]+dp2[i-1][j+1]);
minn=min(minn,max(max(x[i][j],y[i][j]),dp1[i][j]+dp2[i][j]-a[i][j]*2));
}
}
cout<
最短曼哈顿距离解题思路题意是按照顺序一次去掉一个点后的最短曼哈顿距离,所以每个店需要记录其与相邻两个点的距离和离起点的距离,所以要定义二维数组,因为对于100%的数据满足3≤n≤100000,-1000≤xi,yi≤1000,所以储存所有点的坐标有一点浪费,于是我就用的滚动数组来存储最近三个点的坐标.就可以计算出每一个点的三种距离,滚动数组的下标用%3来区分每个点与之相邻两个点的坐标.
去掉某个点,需要修改新的总距离,例如去掉一号点,会有以下的改变.
参考代码#includeusing namespace std;
const int MAX=100005;
long long a[MAX][3],map1[3][2];
long long pos,n,sum,tot,tmp;
int f(int x,int y,int px,int py){
return fabs(x-px)+fabs(y-py);
}
int main(void){
ios::sync_with_stdio(false);
cin>>n>>map1[0][0]>>map1[0][1];
cin>>map1[1][0]>>map1[1][1];
a[1][0]=a[1][1]=a[1][2]=f(0,0,map1[1][0],map1[1][1]);
for(int i=2;i>map1[i%3][0]>>map1[i%3][1];
a[i][1]=f(map1[(i-1)%3][0],map1[(i-1)%3][1],map1[i%3][0],map1[i%3][1]);
a[i][2]=f(map1[(i-2)%3][0],map1[(i-2)%3][1],map1[i%3][0],map1[i%3][1]);
a[i][0]=a[i-1][0]+a[i][1];
}
sum=tot=a[n-1][0];
for(int i=1;i
酒厂选址解题思路本题主要考查了前缀和and枚举的思想.我用的d[i]记录从1号店到i号点的距离,sum来累加总距离,有余数据是一个单环,所以任意两点之间的距离有两种情况
或
选择较小的距离来计算运算成本.由于可能有多个消费相同大的城市,所以每一个点都要枚举讨论,在这个点修建酒厂是否代价最小.
参考代码#includeusing namespace std;
const int MAX=100005;
long long a[MAX],b[MAX],n;
long long tmp,ans,minn=LONG_LONG_MAX;
int main(){
ios::sync_with_stdio(false);
cin>>n;
for(int i=1;i<=n;i++){
cin>>a[i-1]>>b[i];
ans+=b[i];
b[i]=b[i]+b[i-1];
}
for(int i=0;ians/2){
if(j!=i){
tmp+=(ans-fabs(b[j]-b[i]))*a[j];
}
}
}
minn=min(minn,tmp);
}
cout<
雪地足迹Tracks in the Snow解题思路本题我主要是用deque(双端队列)做的,当搜索到不同的动物的时候,我就用pair来记录这个动物出现的下标,(1,1)坐标是最后一种动物,注意不会出现连续着相同的动物进入草坪,因为这样踩的脚印只能由第一个动物去完成.把当前位置的相邻动物入队:相同的动物放队头,不同的动物放队尾.并且记录目前已经出队的动物种类,如果队头对应的动物和之前的动物不同,说明就有新的动物出现,cnt+1;
参考代码#includeusing namespace std;
const int M=4005;
char mp[M][M];
int fx[4][2]={-1,0,0,1,1,0,0,-1};
int h,w,cnt;
char sum,last;
typedef pairpr;
dequeq;
int main(){
ios::sync_with_stdio(false);
scanf("%d%d",&h,&w);
for(int i=1;i<=h;i++)
scanf("%s",mp[i]+1);
last=char('R'+'F'-mp[1][1]);
q.push_front(pr(1,1));
while(!q.empty()){
pr now=q.front();
q.pop_front();
sum=mp[now.first][now.second];
if(sum==0)continue;
mp[now.first][now.second]=0;
if(sum!=last){
last=sum;
cnt++;
}
for(int i=0;i<4;i++){
pr pos=pr(now.first+fx[i][0],now.second+fx[i][1]);
char next=mp[pos.first][pos.second];
if(next==sum) q.push_front(pos);
else if(next+sum=='R'+'F') q.push_back(pos);
}
}
printf("%d\n",cnt);
return 0;
}
这个是寒假集训总结的第一篇文章,所有的文章都在我的专栏里面保存着的.
你是否还在寻找稳定的海外服务器提供商?创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源,准确流量调度确保服务器高可用性,企业级服务器适合批量采购,新人活动首月15元起,快前往官网查看详情吧
分享题目:寒假集训一期总结(一)–––思维训练-创新互联
新闻来源:http://myzitong.com/article/deisjh.html