NOIP 2013 day2
2024-08-27 18:09:05
tags:
- 模拟
- 贪心
- 搜索
- 动态规划
categories: - 信息学竞赛
- 总结
积木大赛
Solution
发现如果一段先单调上升然后在单调下降, 那么这一块的代价是最高的减去前面已经铺好的, 例如
6 5 6 7 8 9 8 7 6 5
需要先先铺6 5
代价是6
, 然后铺67898765
, 代价是9-5
.
根据这个这个就是记录一个已经铺好的最大值, 然后如果比已经铺好的大就加入答案并且更新已经铺好的.
Code
#include<cstdio>
int main(){
int n,h,l,a;
scanf("%d",&n);
for(int i=0,l=a=0;i<n;++i){
scanf("%d",&h);
if(h>l)a+=h-l;
l=h;
}
printf("%d",a);
return 0;
}
花匠
Solution
发现实际上是求最长波动子序列, 然后实际上可以用dp做, 但是不如找一下其他的性质, 会发现数列可以表示成下面的形式.
\[\nearrow \searrow \nearrow \searrow \nearrow \searrow \nearrow \searrow \cdots
\]
\]
然后只需要取连续下降子序列中的最大值和连续上升子序列中的最小值.写的非常草率.
Code
#include<cstdio>
#include<stack>
std::stack<int>que;
int main(){
int n,h,l;
scanf("%d",&n);
for(int i=0;i<n;++i){
scanf("%d",&h);
if(que.size()&&h==que.top())continue;
if(que.empty())que.push(h);
else if(que.size()==1){
if(h==que.top())continue;
l=h>que.top();que.push(h);
}
else if(l){
if(h>que.top())
que.pop(), que.push(h);
else
que.push(h),l^=1;
}
else {
if(h<que.top())
que.pop(),que.push(h);
else
que.push(h),l^=1;
}
}
printf("%d\n",que.size());
return 0;
}
华容道
Solution
- bfs, 用空格的位置和目标棋子的位置当状态, 可以得到70分.
- bfs出空白格子到每个格子各个方向的路程, 求出最短路.
Code
70分做法
#include<cstring>
#include<cstdio>
#include<queue>
#include<map>
#define N 35
#include<iostream>
using namespace std;
struct Graph{
int sx,ox,sy,oy;
Graph(){};
Graph(int s){scanf("%d%d%d%d",&ox,&oy,&sx,&sy);}
Graph(int a,int b,int c,int d){
sx=a,sy=b,ox=c,oy=d;
}
void print(){
printf("Graph: %d %d %d %d\n",sx,sy,ox,oy);
}
};
int dx[9]={0,0,1,-1};
int dy[9]={1,-1,0,0};
int vis[N][N][N][N];
int ti[N][N][N][N];
int n,m,q,ans;
int G[N][N];
Graph start;
int tx,ty;
int tot;
bool check(int x,int y){
if(!G[x][y])return false;
if(x<1||x>n||y<1||y>m)return false;return true;
}
int main(){
int x,y,xx,yy;
scanf("%d%d%d",&n,&m,&q);
for(int i=1;i<=n;++i)
for(int j=1;j<=m;++j)
scanf("%d",&G[i][j]);
while(q--){
memset(vis,false,sizeof(vis));
start=Graph(true);
scanf("%d%d",&tx,&ty);
if(start.sx==tx&&start.sy==ty){
printf("0\n");
continue;
}
ti[start.sx][start.sy][start.ox][start.oy]=0;
std::queue<Graph>que;
que.push(start);bool flag=false;
while(!que.empty()){
Graph now=que.front(),nxt;que.pop();
for(int i=0;i<4;++i){
nxt=now,xx=now.ox+dx[i],yy=now.oy+dy[i];
if(!check(xx,yy))continue;
x=now.sx,y=now.sy;
if(xx==x&&yy==y)x=now.ox,y=now.oy;
if(vis[x][y][xx][yy])continue;
nxt=(Graph){x,y,xx,yy};
// nxt.print();
ti[x][y][xx][yy]=ti[now.sx][now.sy][now.ox][now.oy]+1;
if(x==tx&&y==ty){
flag=true,ans=ti[x][y][xx][yy];
break;
}
vis[x][y][xx][yy]=true;
que.push(nxt);
}
if(flag)break;
}
if(flag)printf("%d\n",ans);
else printf("-1\n");
}
return 0;
}
最新文章
- Codeforces Round #352 (Div. 2) ABCD
- this上下文,以及通过call 、apply 实现继承
- spring 注解
- 关于AJAX中status中12030与12031的错误
- Nginx + CGI/FastCGI + C/Cpp
- Windows Server 安装 BitLocker
- EnumHelper枚举常用操作类
- BZOJ 1452 Count
- [Raobin] Ext.net在页面中以窗体的形式打开另外的页面
- IOS 在IOS6中设置navigationBar背景图片 会有一条 黑色阴影 --- 解决方案
- HDU 1548 A strange lift(Dijkstra,简单BFS)
- C++内存管理学习笔记(6)
- win7/win8通过媒体流(DLNA技术)共享音乐照片和视频
- Func常用模块及API
- splinter
- php取余运算(%) 注意事项
- PHP-循环结构-数组
- bzoj 2460 [BeiJing2011]元素 (线性基)
- db2系统表相应功能
- 大杂烩 -- 四种生成和解析XML文档的方法详解
热门文章
- BZOJ1458 士兵占领 【带上下界网络流】
- HDOJ(HDU).2546 饭卡(DP 01背包)
- [zhuan]Android程序的真正入口Application
- HDU 5640
- git--------------bug修复流程
- Maven命令行窗口指定settings.xml
- [LeetCode] 6. ZigZag Conversion ☆☆☆
- Spring @Async的异常处理
- 快速搭建rabbitmq单节点并配置使用
- [BZOJ2440]完全平方数解题报告|莫比乌斯函数的应用