A – 道路铺设

这道题考场上神智不清，敲了个线段树拿了满分（当然不用这么复杂）。以下是考场代码。

// road.cpp
// NOIp rp++;
#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
const int maxn= 100200;
const int INF = 1e9 + 1e8;
// segment tree;
int arr[maxn],tree[maxn*4],treeid[maxn*4],n;

void build(int l, int r, int node)
{
	if(l == r)
	{
		tree[node] = arr[l];
		treeid[node] = l;
		return;
	}
	int mid = (l+r)>>1;
	if(l<=mid)
		build(l,mid,2*node);
	if(mid<r)
		build(mid+1,r,2*node+1);
	if(tree[2*node]<tree[2*node+1])
		treeid[node] = treeid[2*node];
	else
		treeid[node] = treeid[2*node+1];
	tree[node] = min(tree[2*node], tree[2*node+1]);
}

void update(int ql, int qr, int l, int r, int node, int c)
{
	if(l == r)
	{
		tree[node] += c;
		treeid[node] = l;
		return;
	}
	int mid = (l+r)>>1;
	if(ql<=mid)
		update(ql,qr,l,mid,2*node,c);
	if(mid<qr)
		update(ql,qr,mid+1,r,2*node+1,c);
	if(tree[2*node]<tree[2*node+1])
		treeid[node] = treeid[2*node];
	else
		treeid[node] = treeid[2*node+1];
	tree[node] = min(tree[2*node], tree[2*node+1]);
}
struct result
{
	int val,id;
	result(){
	}
	result(int v, int i)
	{
		val = v;
		id = i;
	}
	bool operator<(const result& t)const
	{
		return val<t.val;
	}
};
result getMin(int ql, int qr, int l, int r, int node)
{
	if(ql<=l && r<=qr)
		return result(tree[node],treeid[node]);
	int mid = (l+r)>>1;
	result val = result(INF,0);
	if(ql<=mid)
		val = min(val, getMin(ql,qr,l,mid,2*node));
	if(mid<qr)
		val = min(val, getMin(ql,qr,mid+1,r,2*node+1));
	return val;
}

long long ans = 0;

void solve(int l, int r)
{
	result minres = getMin(l,r,1,n,1);
	int min_val = minres.val;
	ans += min_val;
	if(min_val!=0)
		update(l,r,1,n,1,-min_val);
	if(l == r && min_val == 0)
		return;
	int mid = minres.id;
	if(l<mid)
		solve(l,mid-1);
	if(mid<r)
		solve(mid+1,r);
}

// segment tree OK!
int main()
{
	scanf("%d", &n); 
	for(int i = 1;i<=n;i++)
		scanf("%d",&arr[i]);
	build(1,n,1);
	solve(1,n);
	printf("%lld",ans);
	return 0;
}

B – 货币系统

sb 背包，先排序保证用小的换大的。

// P5020.cpp
#include <bits/stdc++.h>

using namespace std;

const int MAX_N = 110, MAX_DOM = 25010;

int T, n, ai[MAX_N];
bool dp[MAX_DOM];

int main()
{
    scanf("%d", &T);
    while (T--)
    {
        scanf("%d", &n);
        for (int i = 1; i <= n; i++)
            scanf("%d", &ai[i]);
        sort(ai + 1, ai + 1 + n);
        memset(dp, false, sizeof(dp)), dp[0] = true;
        int cnt = 0;
        for (int i = 1; i <= n; i++)
        {
            if (dp[ai[i]] == true)
                continue;
            cnt++;
            for (int j = 0; j < MAX_DOM; j++)
                if (j >= ai[i])
                    dp[j] |= dp[j - ai[i]];
        }
        printf("%d\n", cnt);
    }
    return 0;
}

C – 赛道修建

其实大概的思路是可以想到的：二分出一个基准长度，然后利用这个长度去找最多有多少个链，大概就是贪心地从下面抽点，然后把不足的链拼在一起。拼的时候也要用二分，所以这个复杂度带两个\(\log\)。数据范围大概就是这样的。

// P5021.cpp
#include <bits/stdc++.h>
typedef long long ll;

using namespace std;

const int MAX_N = 50500;

int head[MAX_N], current, n, prod[MAX_N], m;
ll dist[MAX_N];
vector<ll> sons[MAX_N];

struct edge
{
    int to, nxt, weight;
} edges[MAX_N << 1];

void addpath(int src, int dst, int weight)
{
    edges[current].to = dst, edges[current].nxt = head[src];
    edges[current].weight = weight, head[src] = current++;
}

int getPairs(int u, int mid, int tot, ll limit)
{
    int ret = 0;
    for (int r = tot - 1, l = 0; r >= 1; r--)
    {
        r -= (r == mid);
        while (l < r && sons[u][l] + sons[u][r] < limit)
            l++;
        l += (l == mid);
        if (l >= r)
            break;
        ret++, l++;
    }
    return ret;
}

void dfs(int u, int fa, ll limit)
{
    dist[u] = prod[u] = 0;
    sons[u].clear();
    for (int i = head[u]; i != -1; i = edges[i].nxt)
        if (edges[i].to != fa)
        {
            dfs(edges[i].to, u, limit);
            dist[edges[i].to] += edges[i].weight;
            if (dist[edges[i].to] >= limit)
                prod[u]++;
            else
                sons[u].push_back(dist[edges[i].to]);
        }
    int siz = sons[u].size();
    sort(sons[u].begin(), sons[u].end());
    int res = 0;
    for (int r = siz - 1, l = 0; r >= 1; r--)
    {
        while (l < r && sons[u][l] + sons[u][r] < limit)
            l++;
        if (l >= r)
            break;
        res++, l++;
    }
    prod[u] += res;
    if ((res << 1) == siz)
        return;
    int l = 0, r = siz - 1, ret;
    while (l <= r)
    {
        int mid = (l + r) >> 1;
        if (getPairs(u, mid, siz, limit) == res)
            ret = mid, l = mid + 1;
        else
            r = mid - 1;
    }
    dist[u] = sons[u][ret];
}

bool check(ll limit)
{
    int lane_tot = 0;
    dfs(1, 0, limit);
    for (int i = 1; i <= n; i++)
        lane_tot += prod[i];
    return lane_tot >= m;
}

int main()
{
    memset(head, -1, sizeof(head));
    ll l = 0, r = 0, ans = 0;
    scanf("%d%d", &n, &m);
    for (int i = 1, u, v, w; i <= n - 1; i++)
        scanf("%d%d%d", &u, &v, &w), addpath(u, v, w), addpath(v, u, w), r += w;
    r /= 1LL * m;
    while (l <= r)
    {
        int mid = (l + r) >> 1;
        if (check(mid))
            ans = mid, l = mid + 1;
        else
            r = mid - 1;
    }
    printf("%lld", ans);
    return 0;
}

D – 旅行

sb \(O(n^2)\)随便拆边进行 DFS。太水了。

// P5022.cpp
#include <bits/stdc++.h>

using namespace std;

const int MAX_N = 5050;

int n, m, deg[MAX_N], ST, ED;
vector<int> ans, now, G[MAX_N];

void dfs(int u, int fa)
{
    now.push_back(u);
    for (int i = 0, siz = G[u].size(); i < siz; i++)
    {
        if ((ST == u && ED == G[u][i]) || (ST == G[u][i] && ED == u) || fa == G[u][i])
            continue;
        dfs(G[u][i], u);
    }
}

bool compare()
{
    if (ans.empty())
        return true;
    for (int i = 0; i < n; i++)
        if (now[i] < ans[i])
            return true;
        else if (now[i] > ans[i])
            return false;
    return false;
}

void toposort()
{
    queue<int> q;
    for (int i = 1; i <= n; i++)
        if (deg[i] == 1)
            q.push(i);
    while (!q.empty())
    {
        int u = q.front();
        q.pop();
        for (int i = 0, siz = G[u].size(); i < siz; i++)
            if (--deg[G[u][i]] == 1)
                q.push(G[u][i]);
    }
}

int main()
{
    /*
    freopen("travel.in", "r", stdin);
    freopen("travel.out", "w", stdout);
    */
    scanf("%d%d", &n, &m);
    for (int i = 1, u, v; i <= m; i++)
        scanf("%d%d", &u, &v), deg[u]++, deg[v]++, G[u].push_back(v), G[v].push_back(u);
    for (int i = 1; i <= n; i++)
        sort(G[i].begin(), G[i].end());
    if (m == n - 1)
    {
        dfs(1, 0);
        for (int i = 0, siz = now.size(); i < siz; i++)
            printf("%d ", now[i]);
        return 0;
    }
    else
    {
        toposort();
        for (int u = 1; u <= n; u++)
            for (int i = 0, siz = G[u].size(); i < siz; i++)
                if (u < G[u][i] && deg[u] > 1 && deg[G[u][i]] > 1)
                {
                    ST = u, ED = G[u][i];
                    now.clear();
                    dfs(1, 0);
                    if (compare())
                        swap(ans, now);
                }
        for (int i = 0, siz = ans.size(); i < siz; i++)
            printf("%d ", ans[i]);
    }

    return 0;
}

E – 填数游戏

写得心好痛，因为如果今年 NOIp 真考这样的神经题，真的就送掉了。我只写几个情况的：

• \(n = 1\)时，显然答案等于\(2^m\)（随便填）。
• \(n = 2\)时，答案等于\(4 \cdot 3^{m – 1} \)，因为初始状态就有\(4\)种，再加上对角线不增这个性质就可以想到。
• \(n = 3\)时，找一下规律就发现等于\(122 \times 3^{m – 3}\)。

所以这道题 50 分还是比较好拿的。剩下的分基本上告辞任命。

// P5023.cpp
#include <bits/stdc++.h>
#define ll long long
using namespace std;

const int mod = 1e9 + 7;

int quick_pow(int bas, int tim)
{
    int ans = 1;
    while (tim)
    {
        if (tim & 1)
            ans = 1LL * ans * bas % mod;
        bas = 1LL * bas * bas % mod;
        tim >>= 1;
    }
    return ans;
}

int main()
{
    int n, m;
    scanf("%d%d", &n, &m);
    if (n > m)
        swap(n, m);
    if (n == 1)
        printf("%d", quick_pow(2, m));
    else if (n == 2)
        // decending sequence order makes it 3 options;
        printf("%lld", 4LL * quick_pow(3, m - 1) % mod);
    else if (n == 3)
        // What the fuck.
        printf("%lld", 112LL * quick_pow(3, m - 3) % mod);
    else
    {
        if (n == m)
            printf("%lld", (83LL * quick_pow(8, n) % mod + 5LL * quick_pow(2, n + 7) % mod) * quick_pow(384, mod - 2) % mod);
        else
            printf("%lld", (83LL * quick_pow(8, n) % mod + quick_pow(2, n + 8) % mod) % mod * quick_pow(128, mod - 2) % mod * quick_pow(3, m - n - 1) % mod);
    }
    return 0;
}

F – 保卫王国

倍增 DP 的好题。50 分随便送，\(O(nm)\)搞定，剩下的分就需要对询问进行分析：考虑每次都是对链的限制，所以可以考虑额外考虑一种 DP，设状态\(f[0/1][0/1][u][v]\)表示\(u\)选不选、\(v\)选不选的情况的答案。因为这种 DP 的信息可以合并，我们不妨用倍增压缩下，然后在对两条单链进行合并（分类讨论中间的 LCA 是否选）。大概是这样，代码其实表达的也比较自然，所以就不过多解释。

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

using namespace std;

const int MAX_N = 1e5 + 200;
const ll INF = 0x3f3f3f3f3f3f3f3f;

int head[MAX_N], current, n, q, val[MAX_N], dep[MAX_N], fa[20][MAX_N], m;
ll f[2][2][20][MAX_N], dp[MAX_N][2];
char typ[10];

struct edge
{
    int to, nxt;
} edges[MAX_N << 1];

void addpath(int src, int dst)
{
    edges[current].to = dst, edges[current].nxt = head[src];
    head[src] = current++;
}

// checked;
// at predfs(int);
void predfs(int u)
{
    dep[u] = dep[fa[0][u]] + 1, dp[u][1] = val[u], f[0][0][0][u] = INF;
    for (int i = 1; i <= 19; i++)
        fa[i][u] = fa[i - 1][fa[i - 1][u]];
    for (int i = head[u]; i != -1; i = edges[i].nxt)
        if (edges[i].to != fa[0][u])
        {
            fa[0][edges[i].to] = u;
            predfs(edges[i].to);
            dp[u][0] += dp[edges[i].to][1];
            dp[u][1] += min(dp[edges[i].to][0], dp[edges[i].to][1]);
        }
}

void dfs(int u)
{
    // not selecting the node u but the father node;
    f[1][0][0][u] = dp[fa[0][u]][0] - dp[u][1];
    f[0][1][0][u] = f[1][1][0][u] = dp[fa[0][u]][1] - min(dp[u][0], dp[u][1]);
    // to process the chains bypassing the LCA:
    for (int i = 1; (1 << i) < dep[u]; i++)
    {
        // merging two chains from 2 situations: mid point chosen or not;
        int mid_point = fa[i - 1][u];
        f[0][0][i][u] = min(f[0][0][i - 1][u] + f[0][0][i - 1][mid_point], f[0][1][i - 1][u] + f[1][0][i - 1][mid_point]);
        f[0][1][i][u] = min(f[0][0][i - 1][u] + f[0][1][i - 1][mid_point], f[0][1][i - 1][u] + f[1][1][i - 1][mid_point]);
        f[1][0][i][u] = min(f[1][0][i - 1][u] + f[0][0][i - 1][mid_point], f[1][1][i - 1][u] + f[1][0][i - 1][mid_point]);
        f[1][1][i][u] = min(f[1][0][i - 1][u] + f[0][1][i - 1][mid_point], f[1][1][i - 1][u] + f[1][1][i - 1][mid_point]);
    }

    for (int i = head[u]; i != -1; i = edges[i].nxt)
        if (edges[i].to != fa[0][u])
            dfs(edges[i].to);
}

ll query(int x, int y, bool togA, bool togB)
{
    if (dep[x] < dep[y])
        swap(x, y), swap(togA, togB);
    ll x_enable = INF, y_enable = INF;
    ll x_disable = INF, y_disable = INF, answer;
    ll ans0 = INF, ans1 = INF;
    int lca;

    if (togA)
        x_enable = dp[x][1];
    else
        x_disable = dp[x][0];

    if (togB)
        y_enable = dp[y][1];
    else
        y_disable = dp[y][0];

    for (int i = 19; i >= 0; i--)
        if (dep[fa[i][x]] >= dep[y])
        {
            ll xdis = x_disable, xen = x_enable;
            x_disable = min(xdis + f[0][0][i][x], xen + f[1][0][i][x]);
            x_enable = min(xdis + f[0][1][i][x], xen + f[1][1][i][x]);
            x = fa[i][x];
        }
    if (x == y)
        lca = x, togB ? ans1 = x_enable : ans0 = x_disable;
    else
    {
        for (int i = 19; i >= 0; i--)
            if (fa[i][x] != fa[i][y])
            {
                ll xdis = x_disable, xen = x_enable;
                ll ydis = y_disable, yen = y_enable;
                x_disable = min(xdis + f[0][0][i][x], xen + f[1][0][i][x]);
                x_enable = min(xdis + f[0][1][i][x], xen + f[1][1][i][x]);
                y_disable = min(ydis + f[0][0][i][y], yen + f[1][0][i][y]);
                y_enable = min(ydis + f[0][1][i][y], yen + f[1][1][i][y]);
                x = fa[i][x], y = fa[i][y];
            }
        lca = fa[0][x];
        ans0 = dp[lca][0] - dp[x][1] - dp[y][1] + x_enable + y_enable;
        ans1 = dp[lca][1] - min(dp[x][1], dp[x][0]) - min(dp[y][0], dp[y][1]) + min(x_enable, x_disable) + min(y_enable, y_disable);
    }
    if (lca == 1)
        answer = min(ans1, ans0);
    else
    {
        for (int i = 19; i >= 0; i--)
            if (dep[lca] - (1 << i) > 1)
            {
                ll tmp0 = ans0, tmp1 = ans1;
                ans0 = min(tmp0 + f[0][0][i][lca], tmp1 + f[1][0][i][lca]);
                ans1 = min(tmp0 + f[0][1][i][lca], tmp1 + f[1][1][i][lca]);
                lca = fa[i][lca];
            }
        answer = min(dp[1][0] - dp[lca][1] + ans1, dp[1][1] - min(dp[lca][0], dp[lca][1]) + min(ans1, ans0));
    }
    return answer >= INF ? -1 : answer;
}

int main()
{
    memset(head, -1, sizeof(head));
    scanf("%d%d%s", &n, &m, typ + 1);
    for (int i = 1; i <= n; i++)
        scanf("%d", &val[i]);
    for (int i = 1, u, v; i <= n - 1; i++)
        scanf("%d%d", &u, &v), addpath(u, v), addpath(v, u);

    predfs(1), dfs(1);
    while (m--)
    {
        int u, v, x, y;
        scanf("%d%d%d%d", &u, &x, &v, &y);
        printf("%lld\n", query(u, v, x, y));
    }
    return 0;
}