BZOJ1092 : [SCOI2003]蜘蛛难题

时间:2021-08-02 08:32:41

按时间一步一步模拟。

每一次,首先将所有没有水但是可以被灌到水的管子标记为有水,然后求出有水的管子里水面高度的最小值。

如果$a$号管有水且最小值为$b$,那么说明此时蜘蛛碰到了水。

如果有管子溢出且最小值就是它,那么说明此时无论如何水面都不会再上涨,即无解。

然后往所有高度等于最小值的管子里灌上一高度的水即可。

#include<cstdio>
const int N=25,M=110;
int n,m,i,j,x,y,z,A,B,T,g[N],v[M],w[M],nxt[M],ed;
struct P{int x,y,h,v;}a[N];
int getid(int x){for(int i=1;i<=n;i++)if(a[i].x==x)return i;}
void add(int x,int y,int z){
v[++ed]=y;w[ed]=z;nxt[ed]=g[x];g[x]=ed;
v[++ed]=x;w[ed]=z;nxt[ed]=g[y];g[y]=ed;
}
int main(){
scanf("%d",&n);
for(i=1;i<=n;i++)scanf("%d%d%d",&a[i].x,&a[i].y,&a[i].h),a[i].h+=a[i].y,a[i].v=i==1;
scanf("%d",&m);
while(m--)scanf("%d%d%d",&x,&y,&z),add(getid(x-1),getid(x+z),y);
scanf("%d%d",&A,&B);
while(1){
for(x=1;x;)for(x=0,i=1;i<=n;i++)if(a[i].v)
for(j=g[i];j;j=nxt[j])if(a[i].h<=w[j]&&!a[v[j]].v)a[v[j]].v=x=1;
for(m=0,i=1;i<=n;i++)if(a[i].v&&a[i].h>m)m=a[i].h;
if(a[A].v&&m==B)return printf("%d",T),0;
for(i=1;i<=n;i++)if(a[i].v&&a[i].y==a[i].h&&a[i].y==m)return puts("-1"),0;
for(i=1;i<=n;i++)if(a[i].v&&a[i].h==m)a[i].h--,T++;
}
}

  

BZOJ1092 : [SCOI2003]蜘蛛难题的更多相关文章

  1. 【SCOI2003】【BZOJ1092】蜘蛛难题

    有一堆管道,还有一个蜘蛛Willy,如下图所示.所有管道的是上端开口,下端封底,直径都是1cm,连接两个管道的连接容量无限,但体积可以忽略不计. 在第一个管道上方有一个水源,从中有水不断往下流,速度为 ...

  2. &lbrack;SCOI2003&rsqb;蜘蛛难题

    题目 对于当年来说似乎是神题?? 做法 对于联通注水来说,我们考虑把所有能平分到水的桶同时加高度,然后暴力判断 My complete code copy来的代码 #include <cstdi ...

  3. bzoj AC倒序

    Search GO 说明:输入题号直接进入相应题目,如需搜索含数字的题目,请在关键词前加单引号 Problem ID Title Source AC Submit Y 1000 A+B Problem ...

  4. 探讨webapp的SEO难题(上)

    前言 网络蜘蛛无法解析javascript,至少百度是不能的,神马搜索差的更远,而我们的webapp的渲染展示完全由javascript驱动 所以蜘蛛访问webapp页面会得到一个白页面,比如,我们期 ...

  5. c&num;蜘蛛

    C#写一个采集器 using System; using System.Collections.Generic; using System.Text; using System.Net; using ...

  6. 深入super,看Python如何解决钻石继承难题 【转】

    原文地址 http://www.cnblogs.com/testview/p/4651198.html 1.   Python的继承以及调用父类成员 python子类调用父类成员有2种方法,分别是普通 ...

  7. 判断来防ip是否为蜘蛛

    判断网站来防IP是否为蜘蛛,用命令查询 :     一.在windows平台 蜘蛛反查命令:nslookup IP 点击"开始"-"运行"-"cmd& ...

  8. BZOJ1090&colon; &lbrack;SCOI2003&rsqb;字符串折叠

    区间dp. 一种是分段dp[i][j]=min(dp[i][j],dp[i][k]+dp[k+1][j]); 一种是这一段可以缩写dp[i][j]=min(dp[i][j],dp[i][l]+2+ca ...

  9. 一起来做webgame,《Javascript蜘蛛纸牌》

    不得不说,做游戏是会上瘾的,这次带来的是win系统上的经典游戏<蜘蛛纸牌>,不能完美,但求一玩 移牌 0 次 Javascript game_蜘蛛纸牌 正在努力加载... // &quot ...

随机推荐

  1. WebApi防重复提交方案

    使用Redis锁机制. 偽代碼: void post { var key = GetKey(); var value = Redis.Incre(key); if(value == 1) { var ...

  2. 别误用IsDigit与IsNumber函数&lpar;转&rpar;

    1.起因 最近发现程序中有一段控制TextBox数字输入的代码,相信大家都不会太陌生,如下: void int_KeyPress(object sender, KeyPressEventArgs e) ...

  3. MVC路由探寻&comma;涉及路由的惯例、自定义片段变量、约束、生成链接和URL等

    引子 在了解MVC路由之前,必须了解的概念是"片段".片段是指除主机名和查询字符串以外的.以"/"分隔的各个部分.比如,在http://site.com/Hom ...

  4. 2&period;mybatis入门实例 连接数据库进行查询

    1.新建项目,添加mybatis和mysql的jar包 2.在mysql中新建表user[id,name,age] CREATE TABLE `users` ( `id` ) NOT NULL aut ...

  5. 图的最短路算法 Bellman-Ford

    BF求图的最短路径的时间复杂度是O(MN),这样的时间复杂度并不比迪杰斯特拉算法好,但是BF算法支持图中存在负权的情况,但图中不能存在负圈,因为如果存在负圈,最短路是不存在的,因此BF算法的另一个重要 ...

  6. css动画集合地址

    CSS3 UI Lib库是由腾讯AlloyTeam前端开发团队建立,主要收集国内外友好体验和创意的界面组件Demo. 它除了使用CSS3技术外,还使用了HTML5,JS,JX,jQuery等技术,来达 ...

  7. &lbrack;Node&period;js&rsqb; Web Scraping with Pagination and Advanced Selectors

    When web scraping, you'll often want to get more than just one page of data. Xray supports paginatio ...

  8. sql server DateTime相关内置函数总结

    本文部分内容参考msdn帮助文档和博客园!汇总备忘 1.获取当前日期      getdate()函数以datetime数据类型的格式返回当前SQLServer服务器所在计算机的日期和时间.其语法格式 ...

  9. python gui 之 tkinter库

    http://blog.csdn.net/jcodeer?viewmode=contents http://tieba.baidu.com/p/3082739560 http://blog.sina. ...

  10. 斯坦福大学公开课机器学习:Neural network-model representation(神经网络模型及神经单元的理解)

    神经网络是在模仿大脑中的神经元或者神经网络时发明的.因此,要解释如何表示模型假设,我们先来看单个神经元在大脑中是什么样的.如下图,我们的大脑中充满了神经元,神经元是大脑中的细胞,其中有两点值得我们注意 ...