題目描述：

K 理事長は占いが好きで，いつも様々な占いをしている．今日は，表の面に ‘I’ が，裏の面に ‘O’ が書か れたカードを使って今年の IOI での日本選手団の出來を占うことにした． 占いの方法は次のようなものである．

1. まず，正の整數 A, B,C, D, E を決める．

2. A + B + C + D + E 枚のカードを橫 1 列に並べる．このとき，左から A 枚は表，続く B 枚は裏，続く C 枚は表，続く D 枚は裏，続く E 枚は表にして並べる．このように並べると，左から順に ‘I’ が A 個，‘O’ が B 個，‘I’ が C 個，‘O’ が D 個，‘I’ が E 個並ぶことになる．

3. あらかじめ決められた N 種類の操作の中から 1 つ以上の操作を選び，好きな順番で行う．このとき， 同じ種類の操作を 2 回以上行っても良い．i (1 ≦ i ≦ N) 種類目の操作は「左から Li 枚目から Ri 枚目 までのカードの表裏をすべてひっくり返す」というものである．1 枚のカードをひっくり返すのに 1 秒かかる．したがって，i 種類目の操作を行うには，Ri ? Li + 1 秒かかる． 4. 操作が終わった後，すべてのカードが表になっていれば占いは成功となる． K 理事長は必要以上にカードをひっくり返すことを避けるために，カードを実際に使って占う前にまず， 占いを成功させることが可能なのかどうかを求めることにした．さらに，もし占いを成功させることが可 能な場合は，占いを成功させるためにかかる時間の最小値を求めることにした．

課題 カードの並べ方の情報と，あらかじめ決められた操作の情報が與えられる．占いを成功させることが可 能かどうかを求め，可能である場合は占いを成功させるためにかかる時間の最小値を求めるプログラムを 作成せよ．

?

K理事長很喜歡占卜，經常用各種各樣的方式進行占卜。今天，他準備使用正面寫著”I”，反面寫著”O”的卡片為今年IOI的日本代表隊占卜最終的成績。

占卜的方法如下所示：

1.首先，選擇5個正整數A,B,C,D,E。

2.將A+B+C+D+E張IOI卡片排成一行，最左側的A張卡片正面朝上，接下來B張反面朝上，接下來C張卡片正面朝上，接下來D張反面朝上，最后E張正面朝上。如此排列的話，從左側開始順次為A張“I”，B張“O”，C張“I”，D張“O”，E張“I”。

3.在預先決定的N種操作中選出至少1種，然后按照任意順序執行。(注：同種操作執行多次也是可以的。)這里，第i種操作(1<=i<=N)為【將從左數第Li張卡片到第Ri張卡片全部翻轉】。翻轉一張卡片需要1秒的時間，因此第i種操作耗時Ri-Li+1秒。

4.操作結束后，如果所有卡片都是正面朝上則占卜成功。

K理事長不想翻多余的牌，因此在實際使用卡片占卜之前會先計算出是否存在占卜成功的可能性。進一步，如果占卜可能成功，他會計算出能使占卜成功所消耗的時間的最小值。

現在給出卡片的排列信息和預先決定的操作信息，請你寫一個程序，計算出占卜能否成功，如果能成功，輸出消耗時間的最小值。

【Input】

第一行5個空格分隔的整數A,B,C,D,E，表示占卜初始時，從最左端開始依次是A枚正面朝上，接下來B枚背面朝上，接下來C枚正面朝上，接下來D枚背面朝上，最后E枚正面朝上。

接下來一行一個正整數N，表示預先決定的操作種類數。

接下來N行，第i行(1<=i<=N)兩個空格分隔的正整數Li，Ri，表示第i種操作為【將從左數第Li張卡片到第Ri張卡片全部翻轉】。

【Output】

如果占卜能夠成功，輸出消耗時間的最小值，否則輸出-1。

【Sample Input】

1 2 3 4 5

3

2 3

2 6

4 10

?

【Sample Output】

12

?

【HINT】

?

初始的卡片序列為IOOIIIOOOOIIIII。

?

執行第2種操作后得到IIIOOOOOOOIIIII，耗時5秒。

?

接下來執行第3中操作，得到IIIIIIIIIIIIIII，占卜成功，耗時7秒。

?

耗時12秒完成占卜，這是耗時的最小值，故輸出12。

?

【Data Constraint】

對于15%的數據，N<=10

對于另外50%的數據，1<=A,B,C,D,E<=50

對于100%的數據：

1<=A,B,C,D,E,N<=10^5

1<=Li<=Ri<=A+B+C+D+E (1<=i<=N)

洛谷題目

乍一看感覺題目沒有什么頭緒，但仔細思考，好像你只需要讓反面朝上的卡牌翻動奇數次，讓正面朝上的卡牌翻動偶數次即可。（一句廢話）

那么，對于01交界處一定有翻動，因為兩側翻動次數一定不相同。

如果一個區間不夠長，那么我們考慮接下去：

　　比如說，像這樣，一個區間(我們稱之區間A)的左端點[i1]正好在[a+1]處而它的右端點小于[a+b]，那么它一定不能完成整個區間(就是從a+1到a+b)的翻轉。考慮接下去，如果這時恰好有一個區間(我們稱之區間B)的左端點就是A的右端點，那么就是說：它可以這么一直接下去直到到達[a+b+1]。

當然這只是最理想的情況，事實上，這其實給我們提供了一個思路:你看啊，怎么實現區間的拼接呢，有沒有想到一個叫做圖論的東西：比如說我們把一個區間的兩端作為點，而邊權就是這個區間反轉的長度，正好是這個區間右端點的值減去左端點的。

而翻轉奇數次的點一定在起始點區間內

神奇不是嗎

那么我們就要考慮一下了，如果已經建好了邊，邊權還是反轉的次數，而題目問的是最少翻轉次數，

那這不就是最短路嗎

是不是很神奇

好了，那么，怎么構造呢

無非就是這三種情況：

?

嗯，那就是這樣了

/代碼具體實現如下

1 #include<queue> 2 #include<cstdio> 3 #include<cstring> 4 #include<algorithm> 5 using namespace std; 6 typedef long long lnt; 7 struct pnt{ 8 int hd; 9 int no; 10 lnt dis; 11 bool vis; 12 bool friend operator < (pnt x,pnt y) 13 { 14 return x.dis>y.dis; 15 } 16 }p[500005]; 17 struct ent{ 18 int twd; 19 int lst; 20 lnt vls; 21 }e[200005]; 22 int a,b,c,d,jdr; 23 int n,m; 24 int piq[10000]; 25 int cnt; 26 lnt ans1,ans2,ans3; 27 priority_queue<pnt>Q; 28 void ade(int f,int t,lnt v) 29 { 30 cnt++; 31 e[cnt].twd=t; 32 e[cnt].vls=v; 33 e[cnt].lst=p[f].hd; 34 p[f].hd=cnt; 35 } 36 int main() 37 { 38 scanf("%d%d%d%d%d%d",&a,&b,&c,&d,&jdr,&n); 39 m=a+b+c+d+jdr; 40 for(int i=1;i<=n;i++) 41 { 42 int l,r; 43 scanf("%d%d",&l,&r); 44 ade(l,r+1,(lnt)(r-l+1)); 45 ade(r+1,l,(lnt)(r-l+1)); 46 } 47 for(int i=1;i<=m+1;i++) 48 { 49 p[i].dis=0x3f3f3f3f3f3f3f3fll; 50 p[i].vis=0; 51 p[i].no=i; 52 } 53 p[a+1].dis=0; 54 Q.push(p[a+1]); 55 while(!Q.empty()) 56 { 57 int x=Q.top().no; 58 Q.pop(); 59 if(p[x].vis)continue; 60 p[x].vis=1; 61 for(int i=p[x].hd;i;i=e[i].lst) 62 { 63 int to=e[i].twd; 64 if(p[to].dis>p[x].dis+e[i].vls) 65 { 66 p[to].dis=p[x].dis+e[i].vls; 67 Q.push(p[to]); 68 } 69 } 70 } 71 ans1+=(lnt)p[a+b+1].dis; 72 ans2+=(lnt)p[a+b+c+1].dis; 73 ans3+=(lnt)p[a+b+c+d+1].dis; 74 for(int i=1;i<=m+1;i++) 75 { 76 p[i].dis=0x3f3f3f3f3f3f3f3fll; 77 p[i].vis=0; 78 p[i].no=i; 79 } 80 p[a+b+1].dis=0; 81 Q.push(p[a+b+1]); 82 while(!Q.empty()) 83 { 84 int x=Q.top().no; 85 Q.pop(); 86 if(p[x].vis)continue; 87 p[x].vis=1; 88 for(int i=p[x].hd;i;i=e[i].lst) 89 { 90 int to=e[i].twd; 91 if(p[to].dis>p[x].dis+e[i].vls) 92 { 93 p[to].dis=p[x].dis+e[i].vls; 94 Q.push(p[to]); 95 } 96 } 97 } 98 ans2+=(lnt)p[a+b+c+d+1].dis; 99 ans3+=(lnt)p[a+b+c+1].dis; 100 for(int i=1;i<=m+1;i++) 101 { 102 p[i].dis=0x3f3f3f3f3f3f3f3fll; 103 p[i].vis=0; 104 p[i].no=i; 105 } 106 p[a+b+c+1].dis=0; 107 Q.push(p[a+b+c+1]); 108 while(!Q.empty()) 109 { 110 int x=Q.top().no; 111 Q.pop(); 112 if(p[x].vis)continue; 113 p[x].vis=1; 114 for(int i=p[x].hd;i;i=e[i].lst) 115 { 116 int to=e[i].twd; 117 if(p[to].dis>p[x].dis+e[i].vls) 118 { 119 p[to].dis=p[x].dis+e[i].vls; 120 Q.push(p[to]); 121 } 122 } 123 } 124 ans1+=(lnt)p[a+b+c+d+1].dis; 125 lnt ans=min(ans1,min(ans2,ans3)); 126 if(ans>=0x3f3f3f3f3f3f3f3fll) 127 printf("-1\n"); 128 else 129 printf("%lld\n",ans); 130 return 0; 131 }

?

轉載于:https://www.cnblogs.com/blog-Dr-J/p/9389487.html

總結

以上是生活随笔為你收集整理的IOIOI卡片占卜(Atcoder-IOIOI カード占い)（最短路）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。