「JOISC 2015 Day 1」卡片占卜
2024-09-04 17:56:37
题目描述
K 理事长是占卜好手,他精通各种形式的占卜。今天,他要用正面写着 I
,背面写着 O
的卡片占卜一下日本 IOI 国家队的选手选择情况。
占卜的方法如下:
- 首先,选取五个正整数 A,B,C,D,EA,B,C,D,EA,B,C,D,E;
- 然后,拿出 A+B+C+D+EA+B+C+D+EA+B+C+D+E 张卡片摆成一排,从左至右摆成 AAA 张正面,BBB 张反面,CCC 张正面,DDD 张反面,EEE 张正面的形式。也就是说,从左到右依次摆 AAA 张
I
,BBB 张O
,CCC 张I
,DDD 张O
,EEE 张I
; - 再从预先确定的 NNN 种操作中选择 111 种以上,然后按照自己喜欢的顺序进行操作,同样的操作可以进行 111 次及以上。第 iii 种操作是「把从左到右第 LiL_iLi 张卡片到第 RiR_iRi 张卡片(包括两端)翻过来」,因为需要用手操作,所以翻 111 张牌需要花费 111 秒,完成一次操作需要花费 Ri−Li+1R_i-L_i+1Ri−Li+1 秒;
- 操作后,如果所有牌都是正面朝上的,占卜就结束了。
因为这种占卜比较费时,所以 K 理事长在占卜之前想知道占卜能否结束,如果能结束,他想知道占卜的最小耗时。
输入格式
第一行,五个正整数 A,B,C,D,EA,B,C,D,EA,B,C,D,E,意义如题目描述;
第二行,一个正整数 NNN,意义如题目描述;
接下来 NNN 行描述操作,一行两个正整数 Li,RiL_i,R_iLi,Ri,意义如题目描述。
输出格式
输出一行,如果占卜能够结束,则输出一个正整数,表示占卜的最小耗时;如不能,输出 −1-1−1。
样例
样例输入 1
1 2 3 4 5
3
2 3
2 6
4 10
样例输出 1
12
样例说明 1
最初的卡片序列为 IOOIIIOOOOIIIII
;
先进行第二个操作,卡片序列变为 IIIOOOOOOOIIIII
,花费 555 秒;
再进行第三个操作,卡片序列变为 IIIIIIIIIIII
,这个操作花费 777 秒,一共花费 121212 秒。
可以证明,121212 秒为占卜的最小耗时,因此输出 121212。
样例输入 2
1 1 1 1 1
1
1 1
样例输出 2
-1
数据范围与提示
对于全部测试点,满足 1≤A,B,C,D,E,N≤105,1≤Li≤Ri≤A+B+C+D+E1\le A,B,C,D,E,N\le 10^5,1\le L_i\le R_i\le A+B+C+D+E1≤A,B,C,D,E,N≤105,1≤Li≤Ri≤A+B+C+D+E。
solution
我们把区间改成(l-1,r] ,这样子修改一段区间就相当于从l-1走到r。
有两个起点两个终点,那就枚举配对就行。
当时考场我居然不会把区间转化成左开右闭的,真的很菜。
有一点要注意:0也是一个合法的点,所以dist也得清inf
#include<cstdio>
#include<iostream>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<queue>
#define maxn 500005
#define inf 1e15
#define ll long long
using namespace std;
int n,m,head[maxn],A,B,C,D,E,tot,flag[maxn];
ll d[maxn],dis[][];
struct node{
int v,nex;
}e[maxn];
void lj(int t1,int t2){
e[++tot].v=t2;e[tot].nex=head[t1];head[t1]=tot;
}
struct no{
int x;ll dist;
};
bool operator <(no a,no b){
return a.dist>b.dist;
}
void dij(int S){
priority_queue<no>q;
q.push((no){S,});
for(int i=;i<=n;i++)d[i]=inf,flag[i]=;d[S]=;
while(!q.empty()){
no k=q.top();q.pop();
if(flag[k.x])continue;
flag[k.x]=;
for(int i=head[k.x];i;i=e[i].nex){
if(d[e[i].v]>d[k.x]+abs(k.x-e[i].v)){
d[e[i].v]=d[k.x]+abs(k.x-e[i].v);
q.push((no){e[i].v,d[e[i].v]});
}
}
}
}
int main()
{
scanf("%d%d%d%d%d",&A,&B,&C,&D,&E);
n=A+B+C+D+E;
cin>>m;
for(int i=,t1,t2;i<=m;i++){
scanf("%d%d",&t1,&t2);t1--;
lj(t1,t2);lj(t2,t1);
}
dij(A);
dis[][]=d[A];dis[][]=d[A+B];dis[][]=d[A+B+C];dis[][]=d[A+B+C+D];
dij(A+B);
dis[][]=d[A];dis[][]=d[A+B];dis[][]=d[A+B+C];dis[][]=d[A+B+C+D];
dij(A+B+C);
dis[][]=d[A];dis[][]=d[A+B];dis[][]=d[A+B+C];dis[][]=d[A+B+C+D];
dij(A+B+C+D);
dis[][]=d[A];dis[][]=d[A+B];dis[][]=d[A+B+C];dis[][]=d[A+B+C+D];
ll ans=min(dis[][]+dis[][],min(dis[][]+dis[][],dis[][]+dis[][]));
if(ans>=inf)puts("-1");
else cout<<ans<<endl;
return ;
}
最新文章
- HTML CSS 特殊字符表(转载)
- Hadoop单机模式安装-(2)安装Ubuntu虚拟机
- 由于 ASP.NET 进程标识对全局程序集缓存没有读权限,因此未能执行请求。错误: 0x80131902
- smartjs - DataManager 场景示例分析 - 数据懒加载
- <;<;Effective Java>;>;之善用组合而不是继承
- Linux操作系统常用命令
- DB天气app冲刺第十一天
- php计算最后一次,第一次字符串出现位置
- failure injection
- 小鱼提问1 类中嵌套public修饰的枚举,外部访问的时候却只能Class.Enum这样访问,这是为何?
- Redis数据结构底层知识总结
- Nginx负载均衡和反向代理的配置和优化
- 学习一下DOM中的cloneNode()与cloneNode(true)的基础知识
- js实现复制文本内容到剪切板
- Windows下安装配置MongoDB
- Servlet(3)—Servlet
- supervisor的安装部署及集群管理
- 在windows10上创建ASP.NET mvc5+Memcached服务
- Area---poj1265(皮克定理+多边形求面积)
- JVM内存模型及垃圾回收算法
热门文章
- Delphi7程序调用C#写的DLL解决办法(转)
- hdu_1452_Happy 2004 (乘法逆元
- linux数据库copy方法
- 【异常】The server time zone value &#39;&#214;&#208;&#185;&#250;&#177;&#234;&#215;&#188;&#202;&#177;&#188;&#228;&#39; is unrecognized or represents more than one time zone.
- 总结 Date 2017.09.23
- 为 dll (类库) 解决方案添加测试项目
- 如何将多个Eclipse项目导入IntelliJ IDEA
- Kafka消费分组和分区分配策略
- ElasticSearch学习笔记(四)-- 分布式
- css3 3D