「NOIP 2017」解题报告

整体来说 … 这次考试还是很 NOIP 的 …

D1

T3

wyj 在写最短路计数的时候还写挂了。
所以我们来复习一发最短路计数。

Luogu P1144 最短路计数
（无权图最短路计数，对于重边和自环我们无需处理
（无法到达的点，那么在 bfs 的时候就不会访问所以就一直是 num[] 的初始值。所以当题目要求我们在点无法到达的点输出什么我们把起初值赋成什么

#include <bits/stdc++.h>

using namespace std;
const int N = 1e6 + 5, mod = 1e5 + 3;

struct Edge {
    int to, next;
}e[N << 2];

int cnt = 0;
int head[N];
void add(int x, int y) {
    e[++ cnt].to = y;
    e[cnt].next = head[x];
    head[x] = cnt;
}

int d[N], num[N]; // d[] 是最短路径长度，num[] 是最短路径条数 
queue<int> q;

int main() {
    memset(head, 0, sizeof(head));
    memset(num, 0, sizeof(num));
    memset(d, 0x7f, sizeof(d)); // 一定要初始设为最大值 
    int n, m;
    scanf("%d%d", &n, &m);
    for(int i = 1; i <= m; i ++) {
        int x, y;
        scanf("%d%d", &x, &y);
        add(x, y), add(y, x);
    }
    q.push(1);
    d[1] = 1, num[1] = 1;
    while(!q.empty()) {
        int u = q.front(); q.pop();
        for(int i = head[u]; i; i = e[i].next) {
            int v = e[i].to;
            if(d[v] < d[u]) continue; // 不往自己父亲走避免死循环 
            if(num[v] == 0) {
                d[v] = d[u] + 1;
                num[v] = num[u];
                q.push(v);
            } else if(d[v] == d[u] + 1) {
                num[v] += num[u];
                num[v] %= mod;
            }
        }
    }
    for(int i = 1; i <= n; i ++)
        printf("%d\n", num[i]);
    return 0;
}

Luogu P1608 路径统计
（有权图最短路计数

Luogu P3953 逛公园

#include <bits/stdc++.h>

using namespace std;
const int N = 1e5 + 5, inf = 1 << 30;

inline int read() {
    int ret = 0; char gc = getchar();
    while(gc < '0' || gc > '9') gc = getchar();
    while(gc >= '0' && gc <= '9') ret = ret * 10 + gc - '0', gc = getchar();
    return ret;
}

int n, m, K, p;

struct Edge {
    int to, next, w;
}e1[N << 1], e2[N << 1];

struct point {
    int id, val;
    point(int id, int val): id(id), val(val){}
    bool operator < (const point &x) const {
        return val > x.val;
    }
};

int cnt;
int head1[N], dis1[N], vis1[N], head2[N], dis2[N], vis2[N];

void add(int x, int y, int z) {
    e1[++ cnt].to = y; e1[cnt].next = head1[x]; e1[cnt].w = z; head1[x] = cnt;
    e2[cnt].to = x; e2[cnt].next = head2[y]; e2[cnt].w = z; head2[y] = cnt; 
}

priority_queue <point> q1;
void dijkstra1(int s) {
    for(int i = 1; i <= n; i ++) dis1[i] = inf;

    q1.push(point(s, 0));
    dis1[s] = 0;
    while(!q1.empty()) {
        int cur1 = q1.top().id; q1.pop();

        if(vis1[cur1]) continue;
        vis1[cur1] = 1;

        for(int i = head1[cur1]; i != - 1; i = e1[i].next) {
            int temp1 = e1[i].to;
            if(dis1[cur1] + e1[i].w < dis1[temp1]) {
                dis1[temp1] = dis1[cur1] + e1[i].w;
                q1.push(point(temp1, dis1[temp1]));
            }
        }
    }
}

priority_queue <point> q2;
void dijkstra2(int s) {
    for(int i = 1; i <= n; i ++) dis2[i] = inf;

    q2.push(point(s, 0));
    dis2[s] = 0;
    while(!q2.empty()) {
        int cur2 = q2.top().id; q2.pop();

        if(vis2[cur2]) continue;
        vis2[cur2] = 1;

        for(int i = head2[cur2]; i != - 1; i = e2[i].next) {
            int temp2 = e2[i].to;
            if(dis2[cur2] + e2[i].w < dis2[temp2]) {
                dis2[temp2] = dis2[cur2] + e2[i].w;
                if(dis2[temp2] <= K)
                    q2.push(point(temp2, dis2[temp2]));
            }
        }
    }
}

int tot;
int d[N], que[N << 1];

inline int check() {
    for(int i = 1; i <= n; i ++)
        for(int j = head1[i]; j != - 1; j = e1[j].next) {
            int v = e1[j].to;
            e1[j].w = dis1[i] + e1[j].w - dis1[v];
            if(e1[j].w == 0) d[v] ++;
        }
    for(int i = 1; i <= n; i ++)
        if(!d[i]) que[++ tot] = i;
    for(int i = 1; i <= tot; i ++) {
        int u = que[i];
        for(int j = head1[u]; j != -1; j = e1[j].next) {
            int v = e1[j].to;
            if(e1[j].w == 0) {      
                d[v] --;
                if(!d[v]) que[++ tot] = v;
            }
        }
    }
    for(int i = 1; i <= n; i ++)
        if(d[i] && dis1[i] + dis2[i] <= dis1[n] + K)
            {printf("-1\n"); return false;}
    return true;
}

int f[N][55];

void dp() {
    memset(f, 0, sizeof(f));
    f[1][0] = 1;
    for(int k = 0; k <= K; k ++) {
        for(int i = 1; i <= tot; i ++) {
            int u = que[i];
            for(int j = head1[u]; j != -1; j = e1[j].next) {
                int v = e1[j].to;
                if(e1[j].w == 0) f[v][k] = (f[v][k] + f[u][k]) % p;
            }
        }
        for(int i = 1; i <= n; i ++) {
            for(int j = head1[i]; j != -1; j = e1[j].next) {
                int v = e1[j].to;
                if(e1[j].w != 0 && k + e1[j].w <= K)
                    f[v][k + e1[j].w] = (f[v][k + e1[j].w] + f[i][k]) % p;
            }
        }
    }
}

void mem() {
    tot = 0;
    cnt = 0;
    memset(head1, -1, sizeof(head1)); memset(head2, -1, sizeof(head2));
    memset(vis1, 0, sizeof(vis1)); memset(vis2, 0, sizeof(vis2));
    memset(d, 0, sizeof(d));
}

void work() {
    n = read(), m = read(), K = read(), p = read();
    for(int i = 1; i <= m; i ++) {
        int a, b, c;
        a = read(), b = read(), c = read();
        add(a, b, c);
    }
    dijkstra1(1), dijkstra2(n);
    if(check() == 0) return ;
    dp();
    int ans = 0;
    for(int i = 0; i <= K; i ++)
        ans = (ans + f[n][i]) % p;
    printf("%d\n", ans);
}

int main() {
    int T;
    T = read();
    while(T --) mem(), work();
    return 0;
}

---

D2

T2

Luogu P3959 宝藏

预备知识：枚举子集的二进制写法

// 枚举 i 的子集
for (int j = i & (i - 1); j; j = i & (j - 1))

这样做就是每次不断 - 1 来枚举所有子集，它不是忽略了 i 中的 0，而是在 & i 的过程中将 0 消去了。

分析：

我们发现每层的边对应的权值都不一样，所以可以按层考虑状压 dp。

我们定义：如果状态 s 的第 k 个位置访问过，则第 k 个位置为 1。
令 f[i][s] 表示第 i 层，到状态 s 的最小花费。
接着枚举 s 子集的补集 s’，作为第 i + 1 层的点，对于 s’ 中每个点，都选择一条连向 s 中最小的边。
可以预处理出 u 到任意集合 s 中的最小的边，所以我们可以按 s 从小带大 dp。
时间复杂度为 O(3n∗n)。

#include <bits/stdc++.h>
 #define ll long long

 using namespace std;
 const int N = 1005, s = (1 << 12) + 5, inf = 0x7fffffff;

 int a[N][N], f[N][s], w[N][s];
// f[i][s] 表示第 i 层，到状态 s 的最小花费 
// w[i][s] 表示 s 集合到 i 点的最短边
// 如果状态 s 的第 k 个位置访问过，则第 k 个位置为 1 

 int main() {
    int n, m;
    scanf("%d%d", &n, &m);
    for(int i  = 1; i <= n; i ++)
        for(int j = 1; j <= n; j ++)
            a[i][j] = inf;
    for(int i = 1; i <= m; i ++) {
        int x, y, z;
        scanf("%d%d%d", &x, &y, &z);
        if(z < a[x][y]) a[x][y] = a[y][x] = z;
    }
    int sn = (1 << n) - 1;
    for(int i = 1; i <= n; i ++)
        for(int j = 1; j <= sn; j ++) {
            w[i][j] = inf;
            for(int k = 1; k <= n; k ++) if(1 << (k - 1) & j) w[i][j] = min(w[i][j], a[i][k]);
        }
    for(int i = 1; i <= sn; i ++) {
        if(!(i & (i - 1))) continue;
        for(int j = 0; j <= n; j ++) f[j][i] = inf;
        for(int j = i & (i - 1); j; j = i & (j - 1)) {
            ll z = 0;
            for(int k = 1; k <= n; k ++) if(1 << (k - 1) & j) z += w[k][i - j];
            // i - j 是 i 的子集 j 的补集  
            // z 是子集的补集连向子集中所有点的最短边的和 
            for(int k = 1; k <= n; k ++) f[k][i] = min((ll)f[k][i], f[k - 1][i - j] + z * k);
            // f[k - 1][i - j] 是状态为子集的补集的花费，z * k 是状态为子集的花费，和起来就是状态 i 的花费 
        }
    }
    int ans = inf;
    for(int i = 1; i <= n; i ++) ans = min(ans, f[i][sn]);
    printf("%d\n", ans);
    return 0;
 }

T3

Luogu P3960 列队

我们可以用 n + 1 个 Treap 来维护。
用一个 Treap 维护最后一列的位置 treap[0]，其他 n 个 Treap 分别维护每行除最后一列剩余的位置。

然后我们发现维护每一个 Treap 只需要维护他的 root 就好了。
维护 Treap 的时候是在维护他的 root，而对于 Treap 内的每个节点 root 是在维护一个区间。

每次插入就会将根节点的区间分成
如果 k 小于等于左子树大小，左边就完全在左子树里
如果 k 大于等于 左子树大小 + 当前节点大小，那自己和左子树就都在左边
这两种情况之外，就是，v 自己，的一半在 k 左边，一半在 k 右边

还有注意因为节点维护的是一个区间，所以注意一个节点的大小不是 1 了，而是他维护的区间大小 r - l + 1

#include <bits/stdc++.h>

#define ll long long

using namespace std;
const int N = 3e5 + 5;

int n, m, q;

struct Treap {
    struct Node {
        Node *lc, *rc;
        int size, key;
        ll l, r;

        Node(ll l, ll r) : lc(NULL), rc(NULL), size(r - l + 1), l(l), r(r), key(rand()) {}

        inline void maintain() { size = (lc ? lc->size : 0) + (rc ? rc->size : 0) + r - l + 1; }

        inline int lSize() { return lc ? lc->size : 0; }

        inline long long len() {
            return r - l + 1;
        }
    } *root;

    Node *merge(Node *a, Node *b) {
        if (!a && !b) return NULL;
        if (!a) { b->maintain(); return b; }
        if (!b) { a->maintain(); return a; }

        if (a->key > b->key) {
            a->rc = merge(a->rc, b);
            a->maintain();
            return a;
        } else {
            b->lc = merge(a, b->lc);
            b->maintain();
            return b;
        }
    }

    static inline void split(Node *v, int k, Node *&l, Node *&r) {
        if (!v) { l = r = NULL; return; }

        int s = v->lSize();
        if (k <= s) {
            split(v->lc, k, l, r);
            v->lc = r;
            r = v;  
        } else if (k >= s + v->len()) {
            split(v->rc, k - s - v->len(), l, r);
            v->rc = l;
            l = v;
        } else {
            int t = k - s; // 把这个点代表的前 t 个点分裂出来 

            l = new Node(v->l, v->l + t - 1);
            r = new Node(v->l + t, v->r);

            l->lc = v->lc;
            r->rc = v->rc;

            l->maintain();
            r->maintain();

            delete v;

            return ;
        }

        v->maintain();
    }

    Node *erase(int pos) {
        Node *pred, *tmp;
        split(root, pos - 1, pred, tmp);

        Node *target, *succ;
        split(tmp, 1, target, succ);

        root = merge(pred, succ);

        return target;
    }

    void append(Node *v) {
        root = merge(root, v);
    }

} treap[N + 1];

inline void init() {
    Treap::Node *v;
    for (int i = 1; i <= n; i ++)  {
        v = new Treap::Node((long long)(i - 1) * m + 1, (long long)i * m - 1);
        treap[i].root = v;
    }

    v = new Treap::Node(m, m);
    treap[0].root = v;
    for (int i = 2; i <= n; i ++) {
        v = new Treap::Node((long long)i * m, (long long)i * m);
        treap[0].root = treap[0].merge(treap[0].root, v);
    }
}

inline long long solve(int a, int b) {
    long long ans;
    if (b == m) {
        Treap::Node *v = treap[0].erase(a);
        ans = v->l;
        treap[0].append(v);
    } else {
        Treap::Node *v = treap[a].erase(b);
        ans = v->l;
        treap[0].append(v);

        // 最右边一列的第 a 行的点要向前移动   
        Treap::Node *u = treap[0].erase(a);
        treap[a].append(u);
    }

    return ans;

    /*之前的错误写法，删最后一列的时候还要记得合并到这一行前面的 Treap 里 
    Treap::Node *pos, *pos1;

    if (b != m) pos = treap[a].erase(b);   
    pos1 = treap[0].erase(a);    
    if (b == m) pos = pos1;  
    printf("%lld\n", pos->l); // RE
    treap[0].root = treap[0].merge(treap[0].root, pos);
    */
}

int main() {
    scanf("%d%d%d", &n, &m, &q);
    init();
    for (int i = 1; i <= q; i ++) {
        int a, b;
        scanf("%d%d", &a, &b);
        printf("%lld\n", solve(a, b));
    }
    return 0;   
}