「JOISC 2015 Day1」IOIOI 卡片占卜

· · 题解

原版题解移步这里。

Overview

Subtask 1

通过观察，可以发现操作顺序对于最后结果没有影响。重要的是各个位置被反转几次。同一个操作的使用不会多于一次，因为翻两次就回到原来状态了。

于是可以想到一个朴素的暴搜，先用 \mathcal{O}(2^N) 的时间决定使用哪些操作，然后检查操作后的卡片序列是否符合要求，这样记 S=A+B+C+D+E，于是朴素暴力的复杂度是 \mathcal{O}(S\times 2^N) 的，过不去。

我们知道，I 要翻偶数次，O 要翻奇数次，因此判断一下我们选出的操作区间是不是覆盖了偶数次 I 区间，奇数次 O 区间即可。对于这个问题，原题解提出：「压缩区间」，将复杂度降为 \mathcal{O}(2^N\times N\log N)，可以通过第一个子任务。

不知道 Chtholly Tree 能不能做……

Subtask 2,3

当然我们还需要优化，这里引入差分序列。

这里构造的差分序列是：从第二位起，这一位与之前一位相同，则写 0，否则写 1。观察可知，只有四个位置为 1，其余位置均为 0。

可以发现，一次翻转只改变两个位置的值，即 l 和 r+1。取反即可。

于是我们只需要把差分序列中 A+1,A+B+1,A+B+C+1,A+B+C+D+1 这 4 个位置的值经过操作后变为 0 即可。

把差分序列中每一个元素看成一个点，A+1,A+B+1,A+B+C+1,A+B+C+D+1 两两看成起点和终点，把每次修改看成两点之间的一条边，边权为修改的代价，每次修改意味着将通过的边相连的两个点取反。可以发现只有起点和终点经过一次，其余经过点都经过两次，于是其余点与之前的点相同关系不变，只有起点和终点变了，而且只能变成相同，对于这个图，求其最短路即为最小代价。

对于原序列的第一个位置，可以不用考虑，因为第一个位置确定为 I,并且算法中并不需要原序列第一个元素与其前一个元素的差分值。

对于 Subtask 2，用 Floyd 求最短路，时间复杂度为 \mathcal{O}(S^3)。

用堆优化的 Dijkstra 算法可以通过全部测试数据，我们发现差分序列中最多只有 2N 个点对于我们有用，因此时间复杂度为 \mathcal{O}(N\log N)。

代码如下

#include <queue>
#include <cstdio>
#include <vector>
#include <cstring>
#include <algorithm>
#define MAXM 100005
#define MAXN 500005
#define pi pair<long long,int>
#define mp make_pair
using namespace std;

const long long inf=0x3f3f3f3f3f3f3f3fLL;

struct link
{
    int to;long long val;int nxt;
};

link e[MAXM<<1];
int head[MAXN],cnt;
int A,B,C,D,E,T,n,l,r;
priority_queue <pi,vector <pi >,greater<pi > > q;
long long dis[MAXN],ans=inf;

inline long long mymin(long long a,long long b){return a<b?a:b;}

inline void add(int u,int v,long long w)
{
    e[cnt]=(link){v,w,head[u]};head[u]=cnt++;
    e[cnt]=(link){u,w,head[v]};head[v]=cnt++;
}

inline long long Dijkstra(int S,int T)
{
    memset(dis,0x3f,sizeof dis);q.push(mp(0LL,S));dis[S]=0LL;
    while (!q.empty())
    {
        int x=q.top().second;q.pop();
        for (int i=head[x];~i;i=e[i].nxt)
            if (dis[e[i].to]>dis[x]+e[i].val)
            {
                dis[e[i].to]=dis[x]+e[i].val;
                q.push(mp(dis[e[i].to],e[i].to));
            }
    }
    return dis[T];
}

inline void read(int &x)
{
    x=0;char ch=getchar();
    while (ch<'0'||ch>'9') ch=getchar();
    while (ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+ch-'0',ch=getchar();
    return ;
}

int main()
{
    memset(head,-1,sizeof head);
    read(A);read(B);read(C);read(D);read(E);
    B+=A;C+=B;D+=C;E+=D;++A;++B;++C;++D;
    read(n);
    for (int i=1;i<=n;i++)
        read(l),read(r),add(l,r+1,r-l+1);
    ans=mymin(ans,Dijkstra(A,B)+Dijkstra(C,D));
    ans=mymin(ans,Dijkstra(A,C)+Dijkstra(B,D));
    ans=mymin(ans,Dijkstra(A,D)+Dijkstra(B,C));
    if (ans==inf) puts("-1");
    else printf("%lld\n",ans);
    return 0;
}