NOIP2018 题解

RT

D1

T1 积木大赛

排序,从大到小并查集维护。

顺便,我在考场上虽然觉得像某原题,但事实上我已经完全忘记了原题,所以直到考试的最后我都认为今天出的蛮难的,因此打完暴力就满足了(

复杂度:$O(n\log n)$

T2 货币系统

类似拟阵贪心+背包

当时很有线性基的既视感,事实上我只要把数组改大我其实能A掉...

不多bb了

复杂度:$O(n \log n + nV)$

T3 赛道修建

首先二分答案很明显 考虑菊花,维护一个双指针,先把$\geq lim$的排除,然后看看最小的能不能和最大的匹配,如果可以就匹配(使浪费最小),如果不行那么小的肯定不行了,就可以把小的扔掉。

顺便我直到考试最后都以为这个是什么神仙dp,所以打完菊花的贪心就暴力滚粗了。

考虑正解。维护一个从下往上贪心合并的过程,发现与菊花的情况非常类似,只是我们需要把能传的最大的没合并的路径合并上去。

然而菊花的做法只能告诉我们最多能合并多少个,而并不能告诉我们没合并的最大的路径。

所以可以先用菊花的做法求出最多能合并多少个,然后再二分求一下能上传的最大路径。

当然也有个更方便的做法,那就是从小到大枚举路径,然后把能合并的最小的路径与这条路径合并。这个可以用平衡树(multiset)实现。这样我们可以在保证尽可能合并最多的情况下,使留下来的路径尽量大。我就写后一种了(

这样的贪心在上次CF那道leaf sets有一些既视感。

复杂度:约$O(n \log^2 n)$

multiset常数过大不开O2会被卡掉菊花,将就看看吧(

// Code by ajcxsu
// Problem: running way

#include<bits/stdc++.h>
using namespace std;

const int N=5e4+10, M=1e5+10;
int h[N], to[M], nexp[M], W[M], p=1;
inline void ins(int a, int b, int w) { nexp[p]=h[a], h[a]=p, to[p]=b, W[p]=w, p++; }

int m, cnt, lim;

int dfs(int x, int fr) {
    multiset<int> s;
    int na;
    for(int u=h[x];u;u=nexp[u]) if(to[u]!=fr) {
        na=dfs(to[u], x)+W[u];
        if(na>=lim) cnt++;
        else s.insert(na);
    }
    int ret=0;
    while(s.size()>=2) {
        auto it=s.lower_bound(lim-*s.begin());
        if(it!=s.end()) s.erase(it), s.erase(s.begin()), cnt++;
        else ret=max(ret, *s.begin()), s.erase(s.begin());
    }
    return max(ret, s.size()?*s.rend():0);
}

bool check(int x) {
    cnt=0, lim=x;
    cnt+=dfs(1, 0)>=lim;
    return cnt>=m;
}

int main() {
    ios::sync_with_stdio(false), cin.tie(0);
    int n, u, v, w;
    cin>>n>>m;
    for(int i=1;i<n;i++) cin>>u>>v>>w, ins(u, v, w), ins(v, u, w);
    int l=0, r=5e8, mid, ans=0;
    while(l<=r) {
        mid=(l+r)>>1;
        if(check(mid)) l=mid+1, ans=mid;
        else r=mid-1;
    }
    printf("%d\n", ans);
    return 0;
}

D2

T1 旅行

找环,断环边,贪心。

顺便,考场上找环写错了,感谢CCF的88pts。

#include<bits/stdc++.h>
#define CLR(x, y) memset(x, y, sizeof(x))
#define INF (0x3f3f3f3f)
using namespace std;
typedef long long ll;

template<typename T> inline void gn (T &x) {
    char ch=getchar(), pl=0; x=0;
    while(ch<'0' || ch>'9') pl=ch=='-', ch=getchar();
    while(ch>='0' && ch<='9') x=x*10+ch-'0', ch=getchar();
    x*=pl?-1:1;
}

const int N=5010;
vector<int> to[N];
typedef vector<int>::iterator ite;
int ans[N];
int nans[N], nap;

void check() {
    for(int i=0;i<nap;i++) if(nans[i]<ans[i]) {
        memcpy(ans, nans, sizeof(nans));
        break;
    }
    else if(nans[i]>ans[i]) break;
}

int fa[N];
char cir[N], vis[N];
struct edge { int u, v; } deled[N];
int p, np;
void dfs(int x, int fr) {
    for(ite it=to[x].begin(); it!=to[x].end(); it++) if(*it!=fr) {
        if(fa[*it]) {
            fa[*it]=x;
            int na=x;
            do {
                cir[na]=1; na=fa[na];
                deled[p].u=na, deled[p].v=fa[na], p++;
            } while(x!=na);
        }
        else fa[*it]=x, dfs(*it, x);
    }
}

int lim;
bool check2(int u, int v) {
    return (u==deled[np].u && v==deled[np].v) || (v==deled[np].u && u==deled[np].v);
}
void dfs2(int x, int fr) {
    nans[nap++]=x;
    for(ite it=to[x].begin(); it!=to[x].end(); it++) if(*it!=fr && !check2(x, *it)) 
        dfs2(*it, x);
}

int main() {
    CLR(ans, 0x3f);
    int n, m;
    gn(n), gn(m);
    int u, v;
    for(int i=1;i<=m;i++) gn(u), gn(v), to[u].push_back(v), to[v].push_back(u);
    for(int i=1;i<=n;i++) sort(to[i].begin(), to[i].end());
    dfs(1, 0);
    if(!p) dfs2(1, 0), check();
    else {
        for(np=0; np<p; np++) {
            nap=0;
            dfs2(1, 0);
            check();
        }
    }
    for(int i=0;i<n;i++) printf("%d ", ans[i]);
    putchar('\n');
    return 0;
}

T2 填数游戏

不是很想改
看情况吧

T3 保卫王国

于是去把ddp学了(

最小独立集=全集-最大独立集

注意点细节就好了

#include<bits/stdc++.h>
#define INF (1ll<<60)
using namespace std;
typedef long long ll;
template<typename T> inline void gn(T &x) {
    char ch=getchar(), pl=0; x=0;
    while(ch<'0'||ch>'9') pl=ch=='-', ch=getchar();
    while(ch>='0'&&ch<='9') x=x*10+ch-'0', ch=getchar(); x*=pl?-1:1;
}
const int N=1e5+10;
int h[N], to[N<<1], nexp[N<<1], p=1;
ll v[N];
inline void ins(int a, int b) { nexp[p]=h[a], h[a]=p, to[p]=b, p++; }

struct matrix {
    static const int M=2;
    ll a[M][M];
    matrix() { memset(a, -0x3f, sizeof(a)); }
    ll * operator [] (int x) { return a[x]; }
    matrix operator * (matrix b) {
        matrix c;
        for(int i=0;i<M;i++)
        for(int k=0;k<M;k++)
        for(int j=0;j<M;j++)
            c[i][j]=max(c[i][j], a[i][k]+b[k][j]);
        return c;
    }
} s[N<<2];

#define ls x<<1
#define rs x<<1|1

int dfn[N], dep[N], top[N], son[N], siz[N], fa[N], bot[N], idx, ref[N];
ll dp[N][2], ddp[N][2];

void build(int x, int l, int r) {
    if(l==r) { s[x][0][0]=s[x][0][1]=ddp[ref[l]][0], s[x][1][0]=ddp[ref[l]][1]; return; }
    int mid=(l+r)>>1;
    build(ls, l, mid), build(rs, mid+1, r);
    s[x]=s[ls]*s[rs];
}
void updata(int x, int l, int r, int d) {
    if(l==r) { s[x][0][0]=s[x][0][1]=ddp[ref[l]][0], s[x][1][0]=ddp[ref[l]][1]; return; }
    int mid=(l+r)>>1;
    if(d<=mid) updata(ls, l, mid, d);
    else updata(rs, mid+1, r, d);
    s[x]=s[ls]*s[rs];
}
matrix query(int x, int l, int r, int xl, int xr) {
    if(xl<=l && r<=xr) return s[x];
    int mid=(l+r)>>1;
    if(xr<=mid) return query(ls, l, mid, xl, xr);
    else if(xl>mid) return query(rs, mid+1, r, xl, xr);
    else return query(ls, l, mid, xl, xr)*query(rs, mid+1, r, xl, xr);
}

void dfs1(int x, int k) {
    dep[x]=k, siz[x]=1;
    for(int u=h[x];u;u=nexp[u]) {
        if(!dep[to[u]]) {
            dfs1(to[u], k+1), siz[x]+=siz[to[u]], fa[to[u]]=x;
            if(siz[to[u]]>siz[son[x]]) son[x]=to[u];
        }
    }
}
void dfs2(int x, int t) {
    dfn[x]=++idx, ref[idx]=x, top[x]=t;
    if(!son[x]) bot[x]=x;
    else dfs2(son[x], t), bot[x]=bot[son[x]];
    for(int u=h[x];u;u=nexp[u])
        if(!dfn[to[u]]) {
            dfs2(to[u], to[u]);
            ddp[x][0]+=max(dp[to[u]][0], dp[to[u]][1]);
            ddp[x][1]+=dp[to[u]][0];
        }
    ddp[x][1]+=v[x];
    dp[x][0]=ddp[x][0]+max(dp[son[x]][0], dp[son[x]][1]);
    dp[x][1]=ddp[x][1]+dp[son[x]][0];
}

int n;
void modify(int x, ll w) {
    ddp[x][1]+=-v[x]+w;
    v[x]=w;
    matrix bef;
    int k;
    while(k=fa[top[x]]) {
        bef=query(1, 1, n, dfn[top[x]], dfn[bot[x]]);
        ddp[k][0]-=max(bef[0][0], bef[1][0]);
        ddp[k][1]-=bef[0][0];
        updata(1, 1, n, dfn[x]);
        bef=query(1, 1, n, dfn[top[x]], dfn[bot[x]]);
        ddp[k][0]+=max(bef[0][0], bef[1][0]);
        ddp[k][1]+=bef[0][0];
        x=k;
    }
    updata(1, 1, n, dfn[x]);
}

ll deal(int x, int y) {
    if(y) {
        modify(x, -INF);
        return 0;
    }
    else {
        ll ret=-INF+v[x];
        modify(x, INF);
        return ret;
    }
}

int main() {
    srand(time(NULL));
    int m;
    char str[4];
    gn(n), gn(m), scanf("%s", str);
    ll asl=0;
    for(int i=1;i<=n;i++) gn(v[i]), asl+=v[i];
    int u, v;
    for(int i=0;i<n-1;i++) gn(u), gn(v), ins(u, v), ins(v, u);
    int rt=1;
    dfs1(rt, 1), dfs2(rt, rt);
    build(1, 1, n);
    matrix ans;
    int lst=0;
    int a, b, rwa, rwb;
    ll tot;
    while(m--) {
        gn(u), gn(a), gn(v), gn(b);
        rwa=::v[u], rwb=::v[v];
        tot=deal(u, a)+deal(v, b);
        ans=query(1, 1, n, dfn[top[rt]], dfn[bot[rt]]);
        if(tot+max(ans[0][0], ans[1][0])<0) puts("-1");
        else printf("%lld\n", asl-(tot+max(ans[0][0], ans[1][0])));
        modify(u, rwa), modify(v, rwb);
    }
    return 0;
}

本文链接:https://acxblog.site/archives/sol-noip2018.html
文章采用知识共享署名-非商业性使用 4.0 国际许可协议进行许可。