【NOIP2015模拟11.3】IOIOI卡片占蔔

Description

就像你看到的題目一樣，現在有A個I,接着B個O,再接着C個I,再接着D個O,再接着E個I，排成一排。你現在有N種操作，第i種操作吧從第li個字元到第ri個字元這個區間内的字元，I變成O，O變成I，時間為ri-li+1。求把所有字元都變成I的最小時間。若無解輸出-1。

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

Solution

神奇的一道題。

先%%出題人，這種思路誰想得到嘛~

Japanese…

首先，我們建立一個新的序列b,bi=ai^ai+1

這樣子，b中有了一堆0，中間有4個1。

那麼一次操作相當于什麼呢？

相當于把bl-1和br取反！（自己想想為什麼）

那麼，我們可以從l-1向r連一條長度為r-l+1的邊。

而我們的任務就變成了把b序列變成0.（雖然原序列全為0，b序列也全為0，但這是不可能的，自己想想為什麼）

那麼對于兩個1，把它們同時變為0的最小花費為，這兩個1中間的最短路！（自己想想為什麼）

那麼，我們隻需要打一個spfa/迪傑斯特拉就好了。

不過經過棟爺的測試，迪傑斯特拉好像過不了。

Code

#include<cstdio>
#include<cstring>
#include<algorithm>
#define fo(i,a,b) for(int i=a;i<=b;i++)
#define rep(i,a) for(int i=last[a];i;i=next[i])
#define N 500005
#define ll long long
using namespace std;
int n,tot,g[][]={,,,,,,,,,,,};
int t[N*],next[N*],last[N],a[],d[N*];
ll dis[N],v[N*],ans,l,r;
bool bz[N];
void add(int x,int y,ll z){
    t[++tot]=y;v[tot]=z;next[tot]=last[x];last[x]=tot;
}
ll spfa(int S,int T) {
    memset(dis,,sizeof(dis));
    ll mx=dis[S];dis[S]=;
    memset(bz,,sizeof(bz));bz[S]=;
    int i=,j=;d[]=S;
    while (i<j) {
        rep(k,d[++i]) if (dis[t[k]]>dis[d[i]]+v[k]) {
            dis[t[k]]=dis[d[i]]+v[k];
            if (!bz[t[k]]) bz[t[k]]=,d[++j]=t[k];
        }
        bz[d[i]]=;
    }
    if (dis[T]==mx) return -;else return dis[T];
} 
int main() {
    freopen("card.in","r",stdin);
    freopen("card.out","w",stdout);
    fo(i,,) scanf("%d",&a[i]),a[i]+=a[i-];
    scanf("%d",&n);ans=;
    fo(i,,n) scanf("%lld%lld",&l,&r),add(l-,r,r-l+),add(r,l-,r-l+);
    fo(i,,) {
        ll x=spfa(a[g[i][]],a[g[i][]]),y=spfa(a[g[i][]],a[g[i][]]);
        if (x==-||y==-) continue;
        ans=min(ans,x+y);
    }
    if (ans==) printf("-1");else printf("%lld",ans);
}