NOIP2018提高组题解

[mathjax]

请注意发布时间，以免引起不必要的麻烦。

Day1

T1

五年前提高组原题，差分后将正数累加即可，复杂度\(O(n)\)

read(n);
for (int i = 1; i <= n; i++) {
    read(a);
    if (a > cur)
        ans += a - cur;
    cur = a;
}

fprintf(out, "%lld\n", ans);

T2

对于每一种货币做一次完全背包，最后统计不能被其他货币所表示的货币种类数量即为答案。复杂度\(O(Tna_{max})\)

int n, int a[MaxN], cnt[MaxA];
int t;

read(t);
while (t--) {
    read(n);
    memset(cnt, 0, sizeof(cnt));
    int maxa = 0;
    for (int i = 1; i <= n; i++) {
        read(a[i]);
        maxa = max(maxa, a[i]);
        cnt[a[i]]++;
    }
    for (int i = 1; i <= n; i++)
        for (int j = a[i]; j <= maxa; j++)
            cnt[j] += cnt[j - a[i]];
    int ans = 0;
    for (int i = 1; i <= n; i++)
        if (cnt[a[i]] == 1)
            ans++;
    fprintf(out, "%d\n", ans);
}

T3

这道题比较复杂，可以看到有许多的部分分

\(m=1\)：两遍DFS求树的直径即可

namespace diameter {
    typedef pair<int, int> pii;
    int ans = 0;
    int cur;

    // pair<length, maxnodeid>
    pii dfs1(int u, int from) {
        int maxlen = 0, maxlenid = u;
        for (node* p = h[u]; p; p = p->next) {
            int v = p->v;
            if (v != from) {
                pii val = dfs1(v, u);
                if (val.first + p->len > maxlen) {
                    maxlen = val.first + p->len;
                    maxlenid = val.second;
                }
            }
        }
        return make_pair(maxlen, maxlenid);
    }

    int run() {
        pii ans0 = dfs1(1, 0);
        DEBUG("dfs maxlen from 1: node: %d, length: %d\n", ans0.second, ans0.first);
        pii ans1 = dfs1(ans0.second, 0);
        DEBUG("2nd dfs maxlen from %d: node: %d, length: %d\n", ans0.second, ans1.second, ans1.first);
        return ans1.first;
    }
}

\(a_i =1\)（菊花图）：首先二分答案，check中把所有的边按长度排序，对于每一个当前最长的边，贪心地选取一个最短的相加满足要求的边和他组成一份贡献，two pointers搞一搞即可。由于并不需要向上传回一个没用过的最大值，所以不需要考虑把配对大值往左挪

namespace flower {
    int val[MaxN];

    void prepare() {
        for (int i = 2; i <= n; i++) {
            for (node* p = h[i]; p; p = p->next) {
                if (p->v == 1)
                    val[i - 1] = p->len;
            }
        }
        DEBUG("unsorted array:\n");
        PRINTARR("%d", val, 1, n);
        sort(val + 1, val + n);
    }

    bool check(int limit) {
        DEBUG("checking limit %d...", limit);
        int cur = 0, cnt = 0;
        int l = 1, r = n - 1;
        while (l < r) {
            if (val[r] >= limit) {
                r--;
                cnt++;
            } else {
                while (l < r&&val[l] + val[r] < limit)
                    l++;
                if (l >= r)
                    break;
                l++;
                r--;
                cnt++;
            }
            if (cnt >= m)
                break;
        }
        DEBUG(" cnt=%d, %s\n", cnt, cnt >= m ? "success" : "failed");
        return cnt >= m;
    }

    int run() {
        prepare();
        int l = 1, r = 6e8;
        while (l < r - 1) {
            int mid = (l + r) / 2;
            if (check(mid))
                l = mid;
            else
                r = mid;
        }
        if (check(r))
            return r;
        else
            return l;
    }
}

\(b_i =a_i +1\)（退化为链）：还是二分答案，然后每次check时从头到尾贪心地扩展当前的一条链，若长度大于等于要求则记作一份贡献，同时重新开一条链

namespace chain {
    int val[MaxN];

    void prepare() {
        for (int i = 1; i < n; i++) {
            for (node* p = h[i]; p; p = p->next) {
                if (p->v == i + 1) {
                    val[i] = p->len;
                }
            }
        }
    }

    bool check(int limit) {
        DEBUG("checking limit %d...", limit);
        int cur = 0, cnt = 0;
        for (int i = 1; i <= n - 1; i++) {
            cur += val[i];
            if (cur >= limit) {
                cnt++;
                cur = 0;
            }
            if (cnt >= m)
                break;
        }
        DEBUG(" cnt=%d, %s\n", cnt, cnt >= m ? "success" : "failed");
        return cnt >= m;
    }

    int run() {
        prepare();
        PRINTARR("%d", val, 1, n);
        int l = 1, r = 6e8;
        while (l < r - 1) {
            int mid = (l + r) / 2;
            if (check(mid))
                l = mid;
            else
                r = mid;
        }
        if (check(r))
            return r;
        else
            return l;
    }
}

以上是我在考场上做出的部分，拿到55分，以下是主函数

int main(int argc, char* argv[]) {
#ifdef LOCAL
    in = stdin;
    out = stdout;
#else
    in = fopen(FILENAME ".in", "rb");
    out = fopen(FILENAME ".out", "wb");
#endif

    bool chainflag = true, flowerflag = true;

    read(n); read(m);
    for (int i = 1; i <= n - 1; i++) {
        read(u); read(v); read(l);
        addedge(u, v, l);
        if (v - u != 1)
            chainflag = false;
        if (u != 1)
            flowerflag = false;
    }

    if (m == 1) {
        DEBUG("diameter mode\n");
        fprintf(out, "%d\n", diameter::run());
    } else if (chainflag) {
        DEBUG("chain mode\n");
        fprintf(out, "%d\n", chain::run());
    } else if (flowerflag) {
        DEBUG("flower mode\n");
        fprintf(out, "%d\n", flower::run());
    } else {
        DEBUG("QAQ mode\n");
        fputs("QAQAQAQAQAQAQAQ\n", out);
    }

    return 0;
}

分叉不大于3：二分答案，对于每一个点最多有两个子节点，传上来的最长链相加或单独如果达到要求值则贪心地选为一份贡献，然后选一个最长的没有组成贡献的链（或是0）传上去，结合以上可以拿到80分的好成绩

namespace binary{
    int cnt = 0;

    int dfs(int u, int from, int limit) {
        int a[2];
        int scnt = 0;
        for(node* p = h[u]; p; p = p->next) {
            int v = p->v;
            if(v != from)
                a[scnt++] = dfs(v, u, limit) + p->len;
        }
        if(scnt == 2) {
            if(a[0] >= limit) {
                cnt++;
                a[0] = 0;
            }
            if(a[1] >= limit) {
                cnt++;
                a[1] = 0;
            }
            if(a[0] + a[1] >= limit) {
                cnt++;
                return 0;
            } else
                return max(a[0], a[1]);
        } else if(scnt == 1) {
            if(a[0] >= limit) {
                cnt++;
                a[0] = 0;
            }
            return a[0];
        } else
            return 0;
    }

    bool check(int limit) {
        DEBUG("checking limit %d...", limit);
        cnt=0;
        dfs(1, 0, limit);
        DEBUG(" cnt=%d, %s\n", cnt, cnt >= m ? "success" : "failed");
        return cnt >= m;
    }

    int run() {
        int l = 1, r = 6e8;
        while(l < r - 1) {
            int mid = (l + r) / 2;
            if(check(mid))
                l = mid;
            else
                r = mid;
        }
        if(check(r))
            return r;
        else
            return l;
    }
}

正解其实就是综上所述

首先二分答案，然后check时对于每一个点，他的子节点给他传上来一些可用的链长，先把这些链长贪心地配对组成尽可能多的贡献，然后再把剩下中最长的传上去

注意配对时要先two pointers扫一遍配对，然后再从左到右对于每一个选了的大数判断他左边的那个比他小一些的数能不能和与他配对的那个数配对。注意肯定只会往左挪一步，否则他左边的两个数肯定能够配成一对

namespace solution{
    int cnt=0;

    vector<int> as[MaxN];
    vector<int> bs[MaxN];

    int dfs(int u,int from,int limit,int layer){
        //DEBUG("%sdfs at node %d, from %d, limit=%d, current cnt=%d\n",string(layer*4,' ').c_str(),u,from,limit,cnt);
        vector<int>& a=as[u];
        a.clear();
        vector<int>& used=bs[u];
        used.clear();
        for(node* p=h[u];p;p=p->next){
            int v=p->v;
            if(v!=from){
                a.push_back(dfs(v,u,limit,layer+1)+p->len);
                used.push_back(-1);
            }
        }
        sort(a.begin(),a.end());
        int l=0,r=a.size()-1;
        while(r>=0&&a[r]>=limit){
            used.at(r)=true;
            r--;
            cnt++;
        }
        /*if(l==r&&a[r]>=limit){
            used.at(r)=true;
            r--;
            cnt++;
        }*/
        while(l<r){
            if(a[r]>=limit){
                cnt++;
                used[r]=a.size();
                r--;
            }else if(a[l]+a[r]>=limit){
                cnt++;
                used.at(l)=r;
                used.at(r)=l;
                l++;
                r--;
            }else
                l++;
        }
        for(int i=1;i<a.size();i++){
            if(used[i]<i-1&&used[i-1]<0&&a[i-1]+a[used[i]]>=limit){
                used[i-1]=used[i];
                used[i]=-1;
            }
        }
        int ret=0;
        for(int i=a.size()-1;i>=0;i--)
            if(used.at(i)<0){
                ret=a[i];
                break;
            }
        //DEBUG("%sdfs at node %d: cnt is now %d, returning %d\n",string(layer*4,' ').c_str(),u,cnt,ret);
        //DEBUG(", returned: %d\n",ret);
        return ret;
    }

    bool check(int limit){
        DEBUG("checking limit %d...\n",limit);
        cnt=0;
        dfs(1,0,limit,1);
        DEBUG(" cnt=%d, %s\n",cnt,cnt>=m?"success":"failed");
        return cnt>=m;
    }

    int run(){
        int l=1,r=6e8;
        while(l<r-1){
            int mid=(l+r)/2;
            if(check(mid))
                l=mid;
            else
                r=mid;
        }
        if(check(r))
            return r;
        else
            return l;
    }
}

Day2

T1

直接dfs搜出环，然后枚举换上的一条断边，从最小的1点开始搜索，每次把接下来的点从小到大遍历，最后在所有的序列中取最大的即可，\(O(nm)\)

stack<int> S;
bool inS[MaxN];
bool ringok;
vector<int> ring;
void dfs1(int u,int from){
    if(inS[u]){
        ringok=true;
        int cur=S.top();
        do{
            cur=S.top();
            S.pop();
            ring.push_back(cur);
        }while(cur!=u);
        return;
    }
    S.push(u);
    inS[u]=true;

    for(node* p=h[u];p;p=p->next){
        int v=p->v;
        if(v!=from)
            dfs1(v,u);
        if(ringok)
            return;
    }

    inS[u]=false;
    S.pop();
}

//  min(u,v),max(u,v)
int disableu,disablev;

void dfs2(int u,int from,vector<int>& trace){
    trace.push_back(u);
    vector<int> nodes;
    for(node* p=h[u];p;p=p->next){
        if(p->v!=from&&!(min(u,p->v)==disableu&&max(u,p->v)==disablev))
            nodes.push_back(p->v);
    }
    sort(nodes.begin(),nodes.end());
    for(int i=0;i<nodes.size();i++){
        dfs2(nodes[i],u,trace);
    }
}

vector<int> trace,ans;

int main(int argc, char* argv[]){
    read(n);read(m);
    for(int i=1;i<=m;i++){
        read(u);read(v);
        addedge(u,v);
    }

    trace.reserve(MaxN);
    ans.resize(n,n+1);

    if(m==n-1){
        dfs2(1,0,trace);
        for(int i=0;i<trace.size();i++){
            if(i==0)
                fprintf(out,"%d",trace[i]);
            else
                fprintf(out," %d",trace[i]);
        }
        fputc('\n',out);
    }else{
        dfs1(1,0);
        for(int i=0;i<ring.size();i++){
            disableu=min(ring[i],ring[(i+1)%ring.size()]);
            disablev=max(ring[i],ring[(i+1)%ring.size()]);
            trace.clear();
            dfs2(1,0,trace);
            bool updateans=false;
            for(int i=0;i<trace.size();i++){
                if(trace[i]!=ans[i]){
                    if(trace[i]<ans[i])
                        updateans=true;
                    break;
                }
            }
            if(updateans){
                for(int i=0;i<trace.size();i++){
                    ans[i]=trace[i];
                }
            }
        }
        
        for(int i=0;i<ans.size();i++){
            if(i==0)
                fprintf(out,"%d",ans[i]);
            else
                fprintf(out," %d",ans[i]);
        }
        fputc('\n',out);
    }

    return 0;
}

T2

神仙题，我也不知道我是怎么骗到15分的

T3

44分好拿，剩下的神仙动态dp