【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);
}