蒟蒻的小窝

蒟蒻的小窝

题解 P6288 【[COCI2016-2017#1] Kralj】

posted on 2020-08-15 20:00:00 | under 题解 |

刚拿到题就有了40分的解法,田忌赛马嘛,但不能用 $n^2$的方法。

然后说说正解。将每个精灵放在小矮人的后面,这可以用 $vector$ +边表或者邻接表(推荐)来处理,然后对于每个小矮人,如果他后面有精灵,那就找他后面精灵中比他战斗力高的战斗力最低的精灵来处理,最大值中取最小,典型的二分,这里需要用集合加上 $upper$_ $bound$ 来处理。都处理好了,来枚举起点,我们从节点1开始,转一圈,将每个矮人后面的精灵都投影到后面的矮人身上,如果一个矮人身上没有精灵,那就假设这个矮人后面最近的一个身上有精灵的矮人为起点,转一圈后最后假设为起点的矮人就是起点!这样就ok了。

Code:

#include<bits/stdc++.h>
#define MAXN 500005
using namespace std;
int N,cnt,A[MAXN],P[MAXN],V[MAXN],w[MAXN],son[MAXN],nxt[MAXN],lnk[MAXN],hsh[MAXN];
set<int> S;
inline int read(){
    int ret=0;char ch=getchar();
    while (ch<'0'||ch>'9') ch=getchar();
    while (ch>='0'&&ch<='9') ret=ret*10+ch-'0',ch=getchar();
    return ret;
}
void add_e(int x,int y,int z){hsh[x]++;w[++cnt]=z;son[cnt]=y;nxt[cnt]=lnk[x];lnk[x]=cnt;}
int main() {
    N=read();
    for (int i=1;i<=N;i++) A[i]=read();
    for (int i=1;i<=N;i++) P[i]=read();
    for (int i=1;i<=N;i++) V[i]=read();
    for (int i=1;i<=N;i++) add_e(A[i],i,V[i]);
    int W=1,Sum=0;
    for (int i=1;i<=N;i++) {
        Sum+=hsh[i];
        if (--Sum<0) W=i%N+1,Sum=0;
    }
    int win=0;
    for (int i=1,j=W;i<=N;i++,j=j%N+1) {
        for (int k=lnk[j];k;k=nxt[k]) S.insert(w[son[k]]);
        if (*S.rbegin()<P[j]) S.erase(S.begin()); else S.erase(S.upper_bound(P[j])),win++;
    }
    printf("%d\n",win);
    return 0;
}