「JOISC 2015 Day 1」卡片占卜

题目描述

K 理事长是占卜好手,他精通各种形式的占卜。今天,他要用正面写着 I ,背面写着 O 的卡片占卜一下日本 IOI 国家队的选手选择情况。

占卜的方法如下:

  1. 首先,选取五个正整数 A,B,C,D,EA,B,C,D,EA,B,C,D,E;
  2. 然后,拿出 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
  3. 再从预先确定的 NNN 种操作中选择 111 种以上,然后按照自己喜欢的顺序进行操作,同样的操作可以进行 111 次及以上。第 iii 种操作是「把从左到右第 LiL_iLi​ 张卡片到第 RiR_iRi​ 张卡片(包括两端)翻过来」,因为需要用手操作,所以翻 111 张牌需要花费 111 秒,完成一次操作需要花费 Ri−Li+1R_i-L_i+1Ri​−Li​+1 秒;
  4. 操作后,如果所有牌都是正面朝上的,占卜就结束了。

因为这种占卜比较费时,所以 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

「JOISC 2015 Day 1」卡片占卜
 1 #include<cstdio>
 2 #include<iostream>
 3 #include<cstdlib>
 4 #include<cstring>
 5 #include<algorithm>
 6 #include<cmath>
 7 #include<queue>
 8 #define maxn 500005
 9 #define inf 1e15
10 #define ll long long
11 using namespace std;
12 int n,m,head[maxn],A,B,C,D,E,tot,flag[maxn];
13 ll d[maxn],dis[5][5];
14 struct node{
15     int v,nex;
16 }e[maxn];
17 void lj(int t1,int t2){
18     e[++tot].v=t2;e[tot].nex=head[t1];head[t1]=tot;
19 }
20 struct no{
21     int x;ll dist;
22 };
23 bool operator <(no a,no b){
24     return a.dist>b.dist;
25 }
26 void dij(int S){
27     priority_queue<no>q;
28     q.push((no){S,0});
29     for(int i=0;i<=n;i++)d[i]=inf,flag[i]=0;d[S]=0;
30     while(!q.empty()){
31         no k=q.top();q.pop();
32         if(flag[k.x])continue;
33         flag[k.x]=1;
34         for(int i=head[k.x];i;i=e[i].nex){
35             if(d[e[i].v]>d[k.x]+abs(k.x-e[i].v)){
36                 d[e[i].v]=d[k.x]+abs(k.x-e[i].v);
37                 q.push((no){e[i].v,d[e[i].v]});
38             }
39         }
40     }
41 }
42 int main()
43 {
44     scanf("%d%d%d%d%d",&A,&B,&C,&D,&E);
45     n=A+B+C+D+E;
46     cin>>m;
47     for(int i=1,t1,t2;i<=m;i++){
48         scanf("%d%d",&t1,&t2);t1--;
49         lj(t1,t2);lj(t2,t1);
50     }
51     dij(A);
52     dis[1][1]=d[A];dis[1][2]=d[A+B];dis[1][3]=d[A+B+C];dis[1][4]=d[A+B+C+D];
53     dij(A+B);
54     dis[2][1]=d[A];dis[2][2]=d[A+B];dis[2][3]=d[A+B+C];dis[2][4]=d[A+B+C+D];
55     dij(A+B+C);
56     dis[3][1]=d[A];dis[3][2]=d[A+B];dis[3][3]=d[A+B+C];dis[3][4]=d[A+B+C+D];
57     dij(A+B+C+D);
58     dis[4][1]=d[A];dis[4][2]=d[A+B];dis[4][3]=d[A+B+C];dis[4][4]=d[A+B+C+D];
59     ll ans=min(dis[1][2]+dis[3][4],min(dis[1][3]+dis[2][4],dis[1][4]+dis[2][3]));
60     if(ans>=inf)puts("-1");
61     else cout<<ans<<endl;
62     return 0;
63 }
View Code

 

上一篇:VUE使用QRcode或者vue-qr生成二维码


下一篇:Javascript生成二维码(QR)