最近文章

P2279:[HNOI2003]消防局的设立题解

思路

题面中给出的数据结构很显然是一棵树,我们需要求能覆盖整棵树的最少的消防局数量。我们先按照要求输入,决定根节点(我这里是1号)之后按深度排序,从深度最深的节点开始检测。如果一个节点没有被覆盖,那么就覆盖他的爷爷节点,这样可以使覆盖面积最大,在覆盖时向两个方向扩散设置vis[i]标记。被标记过的点则跳过,没有被标记的点则把消防局设在爷爷处。由于我们的设置过程是按照深度由深到浅渐进,所以不会存在潜在的问题。

代码

// P2279.cpp
#include <iostream>
#include <stack>
#include <queue>
using namespace std;

const int maxn = 4040;

struct edge
{
    int to, next;
} edges[maxn];
int head[maxn];
int F[maxn];
stack<int> st;
bool vis[maxn];
int current = 0;
int n;

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

void BFS()
{
    queue<int> q;
    q.push(1);
    st.push(1);
    while (!q.empty())
    {
        int curt = q.front();
        q.pop();
        for (int i = head[curt]; i != -1; i = edges[i].next)
            if (edges[i].to != F[curt])
                st.push(edges[i].to), q.push(edges[i].to);
    }
}

void DFS(int p, int dep)
{
    if (dep > 2)
        return;
    vis[p] = true;
    for (int i = head[p]; i != -1; i = edges[i].next)
        DFS(edges[i].to, dep + 1);
}

int main()
{
    cin >> n;
    fill(head, head + maxn, -1);
    fill(vis, vis + maxn, false);
    int num = -1;
    for (int i = 2; i <= n; i++)
    {
        cin >> num;
        F[i] = num;
        addpath(num, i), addpath(i, num);
    }
    // going to solve;
    BFS();
    int ans = 0;
    while (!st.empty())
    {
        int curt = st.top();
        st.pop();
        if (!vis[curt] && ++ans)
            DFS(F[F[curt]], 0);
    }
    cout << ans;
    return 0;
}

 

P1137:旅行计划题解

思路

好久没有写拓扑排序了。今天看到这题看了半天,由题解可知是拓扑序DP。原理根据拓扑序来进行DP。由于每个点在DAG是不会回路的,所以我们只需一头往下走就好,用dp[x]记录点x可到达的地方。使用拓扑排序就会让DP时不会出现影响其他已计算过的节点。

代码

// P1137.cpp
#include <iostream>
#include <cstring>
#include <queue>

using namespace std;

const int maxn = 100010;
int points[maxn];
int to[2 * maxn];
int next[2 * maxn];
int indeg[maxn];
int res[maxn];
int dp[maxn];
int tot = 0;
int current = 0;
int n, m;

void add_edge(int a, int b)
{
    to[current] = b;
    next[current] = points[a];
    points[a] = current++;
}

void toposort()
{
    queue<int> waiting;
    for (int i = 1; i <= n; i++)
        if (indeg[i] == 0)
            waiting.push(i), res[tot++] = i;
    while (!waiting.empty())
    {
        int curt = waiting.front();
        waiting.pop();
        for (int edge = points[curt]; edge != -1; edge = next[edge])
        {
            indeg[to[edge]]--;
            if (indeg[to[edge]] == 0)
                waiting.push(to[edge]), res[tot++] = to[edge];
        }
    }
}

void DP()
{
    for (int i = 1; i <= n; i++)
        dp[i] = 1;
    for (int i = 0; i < n; i++)
        for (int edge = points[res[i]]; edge != -1; edge = next[edge])
            dp[to[edge]] = max(dp[to[edge]], dp[res[i]] + 1);
}

int main()
{
    memset(points, -1, sizeof(points));
    memset(to, -1, sizeof(to));
    memset(indeg, 0, sizeof(indeg));
    cin >> n >> m;
    int a, b;
    for (int i = 0; i < m; i++)
    {
        cin >> a >> b, add_edge(a, b);
        indeg[b] += 1;
    }
    toposort();
    DP();
    for (int i = 1; i <= n; i++)
        cout << dp[i] << endl;
    return 0;
}

P1122:最大子树和题解

思路

设一个F[n+1]为树形DP的数组。在点i上,对于每一个子节点j,都有F[j] = dis[i] + max(0, F[j])。其中dis是美丽指数。

代码

// P1122.cpp
#include <iostream>
#include <algorithm>

using namespace std;
// the tree;
const int maxn = 160010;
int n;
int dis[maxn];
int to[maxn];
int next[maxn];
int point[maxn];
int current = 0;
int F[maxn];
int ans = 0;

void add_edge(int src, int dst)
{
    next[current] = point[src];
    to[current] = dst;
    point[src] = current;
    current++;
}
// core code: search subtrees and add them up to F[curt],
// in the meanwhile, get the ans;
void DFS(int curt, int fat)
{
    F[curt] = dis[curt];
    for (int i = point[curt]; i != -1; i = next[i])
    {
        int dst = to[i];
        if (dst == fat)
            continue;
        DFS(dst, curt);
        F[curt] += max(0, F[dst]);
    }
    ans = max(ans, F[curt]);
}
// initialize;
int main()
{
    cin >> n;
    for (int i = 1; i <= n; i++)
        cin >> dis[i];
    fill(point, point + n + 1, -1);
    fill(next, next + n + 1, -1);
    fill(F, F + n + 1, 0);
    int a, b;
    for (int i = 0; i < n - 1; i++)
    {
        cin >> a >> b;
        add_edge(a, b), add_edge(b, a);
    }
    DFS(1, 0);
    cout << ans;
    return 0;
}

P2678:跳石头题解&二分答案原理

暑假和小学神仙们集训的时候发过这道题,一直不知道如何去解决。一个月前crazydave大佬给我简述过二分答案的原理,而蒟蒻我今天才搞定这些。

我们先来看例题:洛谷P2678

这是一道NOIP提高组的简单题(我太菜了),主要是通过枚举答案,在每次枚举时检测能不能符合要求即可。先看代码:

// P2678.cpp
#include <iostream>

using namespace std;

const int maxn = 500020;
int L, N, M;
int D[maxn];

bool check(int num)
{
    int last = 0;
    int cnt = 0;
    for (int i = 0; i <= N; i++)
        if (D[i] - last < num)
            cnt++;
        else
            last = D[i];
    if (cnt > M)
        return false;
    return true;
}

void solve()
{
    int left = 0;
    int right = L;
    int ans = 0;
    while (left <= right)
    {
        int mid = (left + right) / 2;
        if (check(mid))
            left = mid + 1, ans = mid;
        else
            right = mid - 1;
    }
    cout << ans;
}

int main()
{
    cin >> L >> N >> M;
    for (int i = 0; i < N; i++)
        cin >> D[i];
    D[N] = L;
    solve();
    return 0;
}

check函数就是验证答案num(也就是我们枚举出来的答案)是否符合要求,在这里便是检测当最小距离为num时,移走的石子会不会超过限制。如果超过了,返回false,二分便会把区间调为[left,mid-1],以降低最大值来试探限制;没有超过,则返回true,二分把区间调整为[mid+1,right],以追求更大的最大值。

抽象化分析结果

准备枚举一道题答案之前,请考虑二分答案。如果可以二分答案,那么时间复杂度会极度降低,从O(n^2)转变为O(n log n)。二分答案的结构就是二分代码和检验答案正确性代码。如果能通过正确性检查,那么追求更大(小)的答案并重新枚举;如果无法通过,则把区间调整,在较小(大)区间内追求更大(小)的答案。亦复如此。

糟透了的十月

这个月,我经历了很多糟糕的事情。

十一长假的补作业之旅,NOIP2018初赛的烂成绩,面临考验的TOEFL考试,学习速度如乌龟般的OI,文化课一坨屎的成绩令我几乎呕吐。我曾经是一个很重视文化课成绩的人,而现在身为一个OIer,在一定时间内没有转变想法,依旧对文化课成绩十分敏感。可能我就是那种全方位的蒟蒻吧,晚自习在机房学的东西也甚少,退宿回家也增加了家长的疲惫之感。

计算机带所给我的

我太热爱计算机了,甚至有时夜不能寐,思考计算机能带来的东西。一切坏的东西碰上了计算机这个使我充满热情的东西,都会被我所忽略。我在机房的时光应该是这两个月我在滨江最棒的记忆,大佬们教我倍增、DP、神奇的O(n)解法,我也在以微小的努力学习OI。我热爱OI。

失败的恐惧

我每天睡觉前都在思考我如果OI失败后我如何面对面临着滨江垫底的文化课成绩。我很难想象,没有好的大学教育我将如何继续做我想做的事情 。人工智能、生物与计算机这些东西都会在我文化课高考后与我分别。我知道要努力,但是当我最近把心思放在OI上时,文化课成绩相继爆炸,我就像溺死在海里的水手一般。

希望好运。

P1351:联合权值题解

思路

这道题本来用爆搜来写的(DFS),然而TLE了3个点。我只好去向机房巨佬lornd求教。在他神奇的操作之下这道题从\(O(n^3)\)变成了\(O(n)\)的时间复杂度。

我们先来解析一下我们的流程。在存图之后,我们需要遍历n个点,然后获取与点n相连的点。这些点之间的距离必定为2。接下来我们来处理。

第一问

我们在遍历的时候记录下第一大和第二大的数,在处理完这些点之后,我们便把第一大、第二大的数相乘,可以得到这些有序对之中最大的联合权值,与ans变量取最大值便可解决第一问。

第二问

我们先来写一个公式:\[(\sum^{n}_{i=0}{a_i})^2 = \sum^{n}_{i=0}{a^2_i} + 2(\sum^{m}_{i=0,j=0}{a_i a_j})\]

第二问其实问的就是这个式子中的第三项:\[2(\sum^{m}_{i=0,j=0}{a_i a_j})\]

即\(2ab + 2cd + 2ef + \dots \)所以我们如果要求,我们便可以在代码中把第一项和第二项算出,相减即可出答案。

代码

// P1351.cpp
#include <iostream>
#include <algorithm>
#include <cstring>
#include <queue>

using namespace std;

#define ull unsigned long long
const int maxn = 2000000;
int n;
ull W[maxn];
// The graph data structure;
int to[maxn];
int point[maxn];
int next[maxn];
bool vis[maxn];
int current = 0;
// answers;
ull ans_max = 0;
ull ans_tot = 0;
// initialize to make the graph up;
void init()
{
    memset(to, -1, sizeof(to));
    memset(point, -1, sizeof(point));
    memset(next, -1, sizeof(next));
    memset(vis, false, sizeof(vis));
    cin >> n;

    for (int i = 0; i < n - 1; i++)
    {
        int x, y;
        cin >> x >> y;
        next[current] = point[x];
        to[current] = y;
        point[x] = current;
        current++;
        next[current] = point[y];
        to[current] = x;
        point[y] = current;
        current++;
    }
    for (int i = 1; i <= n; i++)
        cin >> W[i];
}
// calculate the n^2;
ull secondary(ull a)
{
    return a * a;
}
// solve;
void solve()
{
    for (int i = 1; i <= n; i++)
    {
        // get the maximum and the second one;
        ull firmax = 0;
        ull secmax = 0;
        // the term1 and the term2;
        ull tmp1 = 0;
        ull tmp2 = 0;
        for (int j = point[i]; j != -1; j = next[j])
        {
            int jto = to[j];
            if (W[jto] > firmax)
                secmax = firmax, firmax = W[jto];
            else if (W[jto] > secmax)
                secmax = W[jto];
            tmp1 += W[jto];
            tmp2 += secondary(W[jto]);
        }
        // add them up;
        ans_tot += (secondary(tmp1) - tmp2) % 10007;
        ans_tot %= 10007;
        ans_max = max(ans_max, firmax * secmax);
    }
}
// just solve it;
int main()
{
    init();
    solve();
    cout << ans_max << " " << ans_tot;
    return 0;
}

lornd tql%%%