程序员经验分享-hwhale

Luogu 2305 [NOI 2014] 购票

2023-05-16

          • 传送门
          • 思路
          • 别人家的题解
          • 弱化的传送门（Luogu 3994 高速公路）
            • 参考代码
          • 对于没有距离限制的 50 分
            • 参考代码
          • 对于 100 分的数据
          • 参考代码
          • Remarks

传送门
思路

唉，我太弱了，什么都不会，斜率优化也不会，唉，我太弱啦！

显然可以 O(n2) O ( n 2 ) DP，这样就得到了 30 分。考虑斜率优化。设我们正在计算 fi f i ，可能的决策点 j j 比可能的决策点 k 更深。若 j j 比 k 更优，我们有：

fj+(di−dj)pi+qi<fk+(di−dk)pi+qi f j + ( d i − d j ) p i + q i < f k + ( d i − d k ) p i + q i

化简得：

fj−fkdj−dk<pi f j − f k d j − d k < p i

由于 pi p i 并不单调，因此我们需要在凸壳上二分。但显然我的知识水平是不够的，因为题目还有一个 l l 的限制。下面我们来逐一解决……

别人家的题解

唉，我太弱了，别人的题解一句话就把这道题切了，我写两页都切不了，别人写的我又看不懂，根本没有学过那些黑科技，唉，我太弱啦！

别人家的题解写道：方法 1：线段树维护可持久化单调队列；方法 2：点分治

QAQ 全都不会啊。

不如我们先看一下这道题的弱化版。

弱化的传送门（Luogu 3994 高速公路）

哪里弱化了：没有距离限制 l，且 pi p i 是递增的。

做了弱化版的题有助于做这道题吗？当然不可能 QAQ

我们仍然有斜率优化的不等式：

fj−fkdj−dk<pi f j − f k d j − d k < p i

由于 pi p i 是递增的，因此，如果这棵树是一条链，那么这就是一个裸的单调队列斜率优化 DP。现在在树上，可以怎么做呢？

我们考虑可持久化。当然，这个可持久化是概念上的，我们还没有规定要用什么具体的数据结构。我们考虑直接用数组维护这个单调队列。观察发现，这个单调队列实际上可以看成一个单调栈（因为我们没有向队头插入元素，所以队头那一部分的数据是不受影响的），所以我们只需要考虑如何维护队尾就好了。当我们遍历到一个结点上时，我们会弹出一些元素，然后入队一个元素。弹出元素的操作可以通过修改队尾下标来实现，也就是说队列中的数据实际上还在。但是入队一个元素会导致一个数据被覆盖，我们记录一下这个被覆盖的数据是什么就好了。当我们需要得到父结点对应的版本时，我们恢复被覆盖的那个数据，将队头和队尾的下标还原即可。

但是这样做每个元素的出队次数不能使用均摊分析。考虑二分出队位置，这样我们就能在 O(nlogn) O ( n log ⁡ n ) 的时间复杂度内解决这个问题了。

参考代码
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>
#include <cassert>
#include <cctype>
#include <climits>
#include <ctime>
#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <stack>
#include <queue>
#include <deque>
#include <map>
#include <set>
#include <bitset>
#include <list>
#include <functional>
typedef long long LL;
typedef unsigned long long ULL;
using std::cin;
using std::cout;
using std::endl;
typedef LL INT_PUT;
INT_PUT readIn()
{
    INT_PUT a = 0; bool positive = true;
    char ch = getchar();
    while (!(ch == '-' || std::isdigit(ch))) ch = getchar();
    if (ch == '-') { positive = false; ch = getchar(); }
    while (std::isdigit(ch)) { a = a * 10 - (ch - '0'); ch = getchar(); }
    return positive ? -a : a;
}
void printOut(INT_PUT x)
{
    char buffer[20]; int length = 0;
    if (x < 0) putchar('-'); else x = -x;
    do buffer[length++] = -(x % 10) + '0'; while (x /= 10);
    do putchar(buffer[--length]); while (length);
    putchar('\n');
}

const int maxn = int(1e6) + 5;
int n;
int parent[maxn];
LL cost[maxn];
LL p[maxn], q[maxn];

struct Graph
{
    struct Edge
    {
        int to;
        LL cost;
        int next;
    } edges[maxn];
    int i;
    int head[maxn];
    Graph() : i() { memset(head, -1, sizeof(head)); }
    void addEdge(int from, int to, LL cost)
    {
        edges[i].to = to;
        edges[i].cost = cost;
        edges[i].next = head[from];
        head[from] = i;
        i++;
    }
#define idx(G) idx_##G
#define wander(G, node) for (int idx(G) = G.head[node]; ~idx(G); idx(G) = G.edges[idx(G)].next)
#define DEF(G) const Graph::Edge& e = G.edges[idx(G)]; int to = e.to; LL cost = e.cost
} G;

LL f[maxn];
LL depth[maxn];

int deque[maxn];
int head, tail;
double slope(int j, int k)
{
    return (double)(f[j] - f[k]) / (depth[j] - depth[k]);
}
LL DP(int i, int j)
{
    return f[j] + (depth[i] - depth[j]) * p[i] + q[i];
}
void DFS(int node)
{
    wander(G, node)
    {
        DEF(G);
        depth[to] = depth[node] + cost;
        int preHead = head; // 保存之前的队头和队尾
        int preTail = tail;
        if (tail - head > 1)
        {
            int k = 0;
            while (1 << k < (tail - head - 1)) k++;
            for (int i = k; ~i; i--) if (head + (1 << i) < tail)
            {
                if (slope(deque[head + (1 << i)],
                    deque[head + (1 << i) - 1]) < p[to])
                {
                    head += 1 << i;
                }
            }
        }
        f[to] = DP(to, deque[head]);

        if (tail - head > 1)
        {
            int k = 0;
            while (1 << k < (tail - head - 1)) k++;
            for (int i = k; ~i; i--) if (head + (1 << i) < tail)
            {
                if (slope(to, deque[tail - (1 << i)]) <
                    slope(deque[tail - (1 << i)], deque[tail - (1 << i) - 1]))
                {
                    tail -= 1 << i;
                }
            }
        }
        int pos = tail; // 保存被覆盖的数据
        int val = deque[pos];
        deque[tail++] = to;
        DFS(to);

        head = preHead; // 还原队头队尾以及被覆盖的数据
        tail = preTail;
        deque[pos] = val;
    }
}

void run()
{
    n = readIn();
    for (int i = 2; i <= n; i++)
    {
        parent[i] = readIn();
        cost[i] = readIn();
        p[i] = readIn();
        q[i] = readIn();
        G.addEdge(parent[i], i, cost[i]);
    }
    deque[tail++] = 1;
    DFS(1);
    for (int i = 2; i <= n; i++)
        printOut(f[i]);
}

int main()
{
    run();
    return 0;
}
对于没有距离限制的 50 分

我们可以将以上例题的单调队列改成单调栈。因为上面的单调队列实质上是一个可以忽略部分栈底内容的栈，所以要得到这 50 分还是很容易的。由于我从来没有写过这种单调栈类型的斜率优化，所以还是贴一份代码吧……

参考代码
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>
#include <cassert>
#include <cctype>
#include <climits>
#include <ctime>
#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <stack>
#include <queue>
#include <deque>
#include <map>
#include <set>
#include <bitset>
#include <list>
#include <functional>
typedef long long LL;
typedef unsigned long long ULL;
using std::cin;
using std::cout;
using std::endl;
typedef LL INT_PUT;
INT_PUT readIn()
{
    INT_PUT a = 0; bool positive = true;
    char ch = getchar();
    while (!(ch == '-' || std::isdigit(ch))) ch = getchar();
    if (ch == '-') { positive = false; ch = getchar(); }
    while (std::isdigit(ch)) { a = a * 10 - (ch - '0'); ch = getchar(); }
    return positive ? -a : a;
}
void printOut(INT_PUT x)
{
    char buffer[20]; int length = 0;
    if (x < 0) putchar('-'); else x = -x;
    do buffer[length++] = -(x % 10) + '0'; while (x /= 10);
    do putchar(buffer[--length]); while (length);
    putchar('\n');
}

const int maxn = int(1e6) + 5;
int n;
int parent[maxn];
LL cost[maxn];
LL p[maxn], q[maxn];

struct Graph
{
    struct Edge
    {
        int to;
        LL cost;
        int next;
    } edges[maxn];
    int i;
    int head[maxn];
    Graph() : i() { memset(head, -1, sizeof(head)); }
    void addEdge(int from, int to, LL cost)
    {
        edges[i].to = to;
        edges[i].cost = cost;
        edges[i].next = head[from];
        head[from] = i;
        i++;
    }
#define idx(G) idx_##G
#define wander(G, node) for (int idx(G) = G.head[node]; ~idx(G); idx(G) = G.edges[idx(G)].next)
#define DEF(G) const Graph::Edge& e = G.edges[idx(G)]; int to = e.to; LL cost = e.cost
} G;

LL f[maxn];
LL depth[maxn];

int stack[maxn];
int tail;
double slope(int j, int k)
{
    return (double)(f[j] - f[k]) / (depth[j] - depth[k]);
}
LL DP(int i, int j)
{
    return f[j] + (depth[i] - depth[j]) * p[i] + q[i];
}
void DFS(int node)
{
    wander(G, node)
    {
        DEF(G);
        depth[to] = depth[node] + cost;
        int preTail = tail;

        int k = 0;
        while (1 << k < (tail - 1)) k++;
        int cnt = 0;
        for (int i = k; ~i; i--) if (cnt + (1 << i) < tail)
        {
            if (slope(stack[cnt + (1 << i)],
                stack[cnt + (1 << i) - 1]) < p[to]) // note
            {
                cnt += 1 << i;
            }
        }
        f[to] = DP(to, stack[cnt]);

        if (tail > 1)
        {
            for (int i = k; ~i; i--) if ((1 << i) < tail)
            {
                if (slope(to, stack[tail - (1 << i)]) <
                    slope(stack[tail - (1 << i)], stack[tail - (1 << i) - 1]))
                {
                    tail -= 1 << i;
                }
            }
        }
        int pos = tail;
        int val = stack[pos];
        stack[tail++] = to;
        DFS(to);

        tail = preTail;
        stack[pos] = val;
    }
}

void run()
{
    n = readIn();
    if (readIn() > 1) throw; // 只能处理没有距离限制的情况
    for (int i = 2; i <= n; i++)
    {
        parent[i] = readIn();
        cost[i] = readIn();
        p[i] = readIn();
        q[i] = readIn();
        readIn(); // l
        G.addEdge(parent[i], i, cost[i]);
    }
    stack[tail++] = 1;
    DFS(1);
    for (int i = 2; i <= n; i++)
        printOut(f[i]);
}

int main()
{
    run();
    return 0;
}

需要注意的是，虽然在单调栈上的斜率优化可以理解成找到凸包的切线，但是如果这样想的话边界情况就很难理解。最好的理解方法是：抛弃所有斜率小于目标斜率的直线，即抛弃所有满足不等式的点，这样，我们的最终结果就是一个明确的点，而不会在边界情况出现歧义了。

对于 100 分的数据

先了解一下为什么不能将 50 分做法扩展到 100 分做法来：

示意图 1

我们考虑这么一个做法：还是用可持久化单调栈（弱化版题目用的那个），但是为当前链上的每一个元素都开一个单调栈。假设最远只能到达 j j ，那么我们找到 j 对应的那个单调栈，在上面二分，这样正确性就有了保证。

我们来分析一下时间复杂度。修改单个单调栈的时间复杂度是 O(logn) O ( log ⁡ n ) 的（不要忘了不能使用均摊分析），总共有 O(n) O ( n ) 个单调栈需要修改，因此整个算法的时间复杂度是 O(n2logn) O ( n 2 log ⁡ n ) 。

考虑优化，这里我就直接给出如何优化的，我们用线段树结构进行优化。具体地说，我们维护一棵线段树，线段树上的每个结点都对应一个单调栈，那么空间复杂度显然就是 O(nlogn) O ( n log ⁡ n ) 的。设线段树上的结点的左端点为 l l ，每个单调栈保存的内容为深度大于等于 l 的结点对应的单调栈。每次修改时，我们修改所有覆盖了待修改深度的结点，总共有 O(logn) O ( log ⁡ n ) 个，每个要花费 O(logn) O ( log ⁡ n ) 的时间去修改。查询时，我们查询可以到达的结点深度对应的区间，总共要查 O(logn) O ( log ⁡ n ) 次，每个要花费 O(logn) O ( log ⁡ n ) 的时间。深搜结束时，我们要花费 O(logn) O ( log ⁡ n ) 的时间复杂度还原。所以总时间复杂度为 O(nlog2n) O ( n log 2 ⁡ n ) 。

为什么可以像这样分成多个单调栈来查询呢？原因其实很简单。我们使用单调栈的目的是排除无用决策，显然的是，最终答案对应的决策点一定不会是无用决策，所以它在任何一个单调栈中都不会被排除。因此，最优决策点一定在 O(logn) O ( log ⁡ n ) 个单调栈中的一个里。

参考代码
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>
#include <cassert>
#include <cctype>
#include <climits>
#include <ctime>
#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <stack>
#include <queue>
#include <deque>
#include <map>
#include <set>
#include <bitset>
#include <list>
#include <functional>
typedef long long LL;
typedef unsigned long long ULL;
using std::cin;
using std::cout;
using std::endl;
typedef LL INT_PUT;
INT_PUT readIn()
{
    INT_PUT a = 0; bool positive = true;
    char ch = getchar();
    while (!(ch == '-' || std::isdigit(ch))) ch = getchar();
    if (ch == '-') { positive = false; ch = getchar(); }
    while (std::isdigit(ch)) { a = a * 10 - (ch - '0'); ch = getchar(); }
    return positive ? -a : a;
}
void printOut(INT_PUT x)
{
    char buffer[20]; int length = 0;
    if (x < 0) putchar('-'); else x = -x;
    do buffer[length++] = -(x % 10) + '0'; while (x /= 10);
    do putchar(buffer[--length]); while (length);
    putchar('\n');
}

const int maxn = int(2e5) + 5;
int n;
int logn;
int parent[19][maxn];
LL cost[maxn];
LL p[maxn], q[maxn], l[maxn];

struct Graph
{
    struct Edge
    {
        int to;
        LL cost;
        int next;
    } edges[maxn];
    int i;
    int head[maxn];
    Graph() : i() { memset(head, -1, sizeof(head)); }
    void addEdge(int from, int to, LL cost)
    {
        edges[i].to = to;
        edges[i].cost = cost;
        edges[i].next = head[from];
        head[from] = i;
        i++;
    }
#define idx(G) idx_##G
#define wander(G, node) for (int idx(G) = G.head[node]; ~idx(G); idx(G) = G.edges[idx(G)].next)
#define DEF(G) const Graph::Edge& e = G.edges[idx(G)]; int to = e.to; LL cost = e.cost
} G;

LL f[maxn];
int depth[maxn];
LL dis[19][maxn];
LL Depth[maxn];

int stack[maxn];
int tail;
double slope(int j, int k)
{
    return (double)(f[j] - f[k]) / (Depth[j] - Depth[k]);
}
LL DP(int i, int j)
{
    return f[j] + (Depth[i] - Depth[j]) * p[i] + q[i];
}
class SegTree
{
    int stack[maxn * 19];
    static inline int code(int l, int r)
    {
        return (l + r) | (l != r);
    }
    int size;
    int head[maxn * 2];
    int tail[maxn * 2];
    void build(int l, int r)
    {
        head[code(l, r)] = tail[code(l, r)] = size;
        size += r - l + 1;
        if (l == r)
            return;
        int mid = (l + r) >> 1;
        build(l, mid);
        build(mid + 1, r);
    }

    int g_Pos, g_Val;
    int g_L, g_R;

    struct RestoreRecord
    {
        int stackCode;
        int preTail;
        int prePos;
        int preVal;
        RestoreRecord() {}
        RestoreRecord(int sc, int pt, int pp, int pv) :
            stackCode(sc), preTail(pt), prePos(pp), preVal(pv) {}
    };
    std::vector<std::vector<RestoreRecord> > rr;
    std::vector<RestoreRecord> curRecord;

    void modify(int l, int r)
    {
        const int& h = head[code(l, r)];
        int& t = tail[code(l, r)];
        int step = 1;
        int cnt = t;
        if (t - h > 1)
        {
            while (step < t - h) step <<= 1;
            for (; step; step >>= 1) if (h + step < cnt)
            {
                if (slope(g_Val, stack[cnt - step]) <
                    slope(stack[cnt - step], stack[cnt - step - 1]))
                {
                    cnt -= step;
                }
            }
        }
        curRecord.push_back(RestoreRecord(code(l, r), t, cnt, stack[cnt]));
        t = cnt;
        stack[t++] = g_Val;

        if (l == r)
            return;
        int mid = (l + r) >> 1;
        if (g_Pos <= mid) modify(l, mid);
        if (g_Pos > mid) modify(mid + 1, r);
    }
    LL query_(int l, int r) const
    {
        if (g_L <= l && r <= g_R)
        {
            const int& h = head[code(l, r)];
            const int& t = tail[code(l, r)];
            int step = 1;
            while (step < t - h) step <<= 1;
            int cnt = h;
            if (t - h > 1)
            {
                for (; step; step >>= 1) if (cnt + step < t)
                {
                    if (slope(stack[cnt + step], stack[cnt + step - 1]) < p[g_Val])
                    {
                        cnt += step;
                    }
                }
            }
            return DP(g_Val, stack[cnt]);
        }
        int mid = (l + r) >> 1;
        LL ret = LLONG_MAX;
        if (g_L <= mid) ret = std::min(ret, query_(l, mid));
        if (g_R > mid) ret = std::min(ret, query_(mid + 1, r));
        return ret;
    }

public:
    void build()
    {
        build(1, n);
    }
    void push(int pos, int val)
    {
        g_Pos = pos;
        g_Val = val;
        modify(1, n);
        rr.push_back(std::move(curRecord));
    }
    void restore()
    {
        std::vector<RestoreRecord> r(std::move(rr.back()));
        rr.pop_back();
        for (const RestoreRecord& t : r)
        {
            stack[t.prePos] = t.preVal;
            tail[t.stackCode] = t.preTail;
        }
    }
    LL query(int l, int r, int val)
    {
        g_L = l;
        g_R = r;
        g_Val = val;
        return query_(1, n);
    }
} st;

void DFS(int node)
{
    wander(G, node)
    {
        DEF(G);
        depth[to] = depth[node] + 1;
        Depth[to] = Depth[node] + cost;
        dis[0][to] = cost;
        for (int i = 1; i <= logn; i++)
        {
            parent[i][to] = parent[i - 1][parent[i - 1][to]];
            dis[i][to] = dis[i - 1][to] + dis[i - 1][parent[i - 1][to]];
        }
        int cnt = to;
        LL remain = l[to];
        for (int i = logn; ~i; i--) if (parent[i][cnt])
        {
            if (remain < dis[i][cnt]) continue;
            remain -= dis[i][cnt];
            cnt = parent[i][cnt];
        }
        f[to] = st.query(depth[cnt], depth[node], to);

        st.push(depth[to], to);
        DFS(to);
        st.restore();
    }
}

void run()
{
    n = readIn();
    while (1 << logn < n) logn++;
    readIn();
    for (int i = 2; i <= n; i++)
    {
        parent[0][i] = readIn();
        cost[i] = readIn();
        p[i] = readIn();
        q[i] = readIn();
        l[i] = readIn();
        G.addEdge(parent[0][i], i, cost[i]);
    }
    st.build();
    st.push(1, 1);
    depth[1] = 1;
    Depth[1] = 0;
    DFS(1);
    for (int i = 2; i <= n; i++)
        printOut(f[i]);
}

int main()
{
    run();
    return 0;
}
Remarks

一群神仙，都是一句话就把题解写完了，还有不需要任何题解直接贴代码的超级神仙 Orz。还有觉得太简单直接叫看别人博客的神仙 Orz。太强啦！！！我太弱啦！！！

  1. 图片来源：http://www.cnblogs.com/Sakits/p/8215297.html ↩
本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)

luogu

2305

NOI

2014

Luogu 2305 [NOI 2014] 购票 的相关文章

  • 百度2014校园招聘研发工程师笔试题+答案

    一 xff0c 简答题 30分 1 xff0c 当前计算机系统一般会采用层次结构存储数据 xff0c 请介绍下典型计算机存储系统一般分为哪几个层次 xff0c 为什么采用分层存储数据能有效提高程序的执行效率 xff1f 10分 xff08

  • luogu P2078 朋友

    题目背景 小明在A公司工作 xff0c 小红在B公司工作 题目描述 这两个公司的员工有一个特点 xff1a 一个公司的员工都是同性 A公司有N名员工 xff0c 其中有P对朋友关系 B公司有M名员工 xff0c 其中有Q对朋友关系 朋友的朋

  • Luogu 1552 [APIO 2012] 派遣

    传送门思路参考代码 传送门 思路 唉 xff0c 我太弱了 xff0c 什么都不会 xff0c 题读错了两次 xff0c 一开始读成了一个一般的背包 xff0c 然后读成了一个价值和花费相同的背包 xff0c 最后才发现原来是一个价值为 1

  • Luogu 2168 [NOI 2015] 荷马史诗

    传送门思路参考代码 传送门 思路 唉 xff0c 我太弱了 xff0c 什么都不会 xff0c 连哈夫曼树都不会 这道题就是一个 k k 叉哈夫曼树 题目要求满足两个条件 一是代价最小 二是最长长度最小 最长长度最小很好解决 只需要优先合并

  • Luogu 1712 [NOI 2016] 区间

    传送门思路参考代码 传送门 思路 唉 xff0c 我太弱了 xff0c 什么都不会 xff0c 这么个傻逼题 xff0c 居然把离散化写错了 xff0c 唉 xff0c 我太弱啦 xff01 显然我们可以考虑枚举最短长度和最长长度 xff0

  • Luogu 3822 [NOI 2017] 整数

    传送门思路参考代码 传送门 思路 唉 xff0c 我太弱了 xff0c 什么都不会 xff0c 当年网同这道题还拿了 16 16 分 xff0c 现在一分都不会做了 xff0c 唉 xff0c 我太弱啦 xff01 这道题其实是很不错的 x

  • Luogu 2305 [NOI 2014] 购票

    传送门思路别人家的题解弱化的传送门 xff08 Luogu 3994 高速公路 xff09 参考代码 对于没有距离限制的 50 分 参考代码 对于 100 分的数据参考代码Remarks 传送门 思路 唉 xff0c 我太弱了 xff0c

  • 2014雅虎校招笔试题目

    今天去参加了雅虎的笔试题 xff0c 算是给自己留个记录吧 首先是8个选择题 xff0c 然后2个填空题 选择题不太难 xff0c 也记不大清楚了 填空题为2个概率题 xff0c 1个是2个人在下午2点 3点之间碰面 xff0c 他们出发时

  • 回望2014

    时光荏苒 xff0c 流光飞逝 xff0c 一转眼的时间又是一年 回望一下2014年 xff0c 这一年应该是成长的一年 xff0c 是温暖的一年 xff0c 也是丰收的一年 在这过去的一年里 xff0c 大概可以从工作和生活两方面说说吧

  • 2014——我们都任性过

    任性的岁月中 xff0c 所处在的每一个角落都可能像个自由的天堂 xff0c 我们每天都充满着任性的笑脸 xff0c 像脱了靶的子弹 xff0c 一任性似乎收不回来 xff01 似乎不变的是 xff0c 时间还是那种脚步声 xff0c 速度

  • 转身不带走一丝云彩--我的2014

    时间或许就是这样不管你愿意不愿意都会毫不犹疑的向前 xff0c 逼你成长 2014年得到了很多也失去了很多 xff0c 我对未来还是有诸多憧憬的 谨以此文献给过去的时光 xff0c 也希望对后来人能有所帮助 改变篇 相比于2013年 xff

  • 2014找工作总结-机会往往留给有准备的人

    好基友的文章必须转 xff0c 大神一枚 xff1a 出处 xff1a http blog csdn net xiajun07061225 article details 12844801 其实我的求职过程在十一之前就已经结束了 xff0c

  • 2014找工作----扎实的基础和开阔的视野是企业最看重的因素

    其实找工作之前一直很忐忑 xff0c 或者说不是很自信 xff0c 因为各种传言说 14 年就业难 实验室的项目逼的有些紧 xff0c 在四川做项目 xff0c 腾讯实习面试都错过了 4 月底回到学校给实验室申请不去实验室 xff0c 准备

  • 百度2014校园招聘笔试题武汉站三道算法设计题

    百度2014校园招聘笔试题武汉站三道算法设计题 1 给定任意一个整整数 求比这个数大且最小的不重复数 就是相邻两位不同 xff0c 例如1231 如1101就是重复数 解 xff1a 思路 xff1a 每次将给定的值加上1 xff0c 然后

  • 2014欢聚时代（YY）软件研发笔试题

    本文转载自 xff1a http blog csdn net arcsinsin article details 12714027

  • 2014暴风影音校招技术笔试题(长春站)

    转http www itmian4 com forum php mod 61 viewthread amp tid 61 3622 1 升序排列下列数值 xff1a 2 写出下列函数的返回值 int func int x 61 300 in

  • 2013&2014

    2013总结 2013 毕业了 xff0c 算是正式工作半年 xff0c 2013年7月开始 xff0c 算是我的生活 xff0c 工作之外的时间都是自己的 一 收获 1 压力测试 差不多算是一个月的时间 xff0c 疯狂的一个月 xff0

  • 2014年408专业算法题

    文章目录 0 结果1 题目2 思路附录 0 结果 1 题目 2 思路 二叉树的带权路径长度 xff08 WPL xff09 的计算方法有两种 xff1a 1 xff0c 定义 xff1a W P L 61

  • P1586 四方定理

    Powered by NEFU AB IN Link 文章目录 P1586 四方定理 题意 思路 代码 P1586 四方定理 题意 四方定理是众所周知的 任意一个正整数n 可以分解为不超过四个整数的平方和 给定的正整数n 编程统计它能分解的

  • [NOI 2015复习][BZOJ 1509][NOI 2003]逃学的小孩(树的直径)

    题目链接 http www lydsy com JudgeOnline problem php id 1509 题目大意 要从一棵树中找出三个点 X Y Z X Y Z 使得 min dis A C dis B C dis A B min

随机推荐

  • CF 963A Alternating Sum

    传送门思路参考代码 传送门 思路 唉 xff0c 我太弱了 xff0c 什么都不会 xff0c 好不容易做得来一道题 xff0c 还是 A 题 xff08 所以不要瞧不起 A 题 xff09 xff0c 结果还写错了 xff08 不知道为什

  • iOS中瀑布流布局详解

    前段时间在逛淘宝的时候发现淘宝的商品界面的布局是瀑布流 我记得明明之前不是瀑布流的 x1f611 刚好手上活忙完了 xff0c 写了一个瀑布流的布局 xff0c 简单的封装了下 xff0c 以便日后使用 x1f60f 其实说到底瀑布流也就是

  • Luogu 2146 [NOI 2015] 软件包管理器

    传送门思路参考代码 传送门 思路 唉 xff0c 我太弱了 xff0c 什么都不会 xff0c 好不容易遇到一道傻逼题 xff0c 又出了个傻逼错误 xff0c 爆得只剩 30 30 分了 唉 xff0c 我太弱啦 xff01 显然 xff

  • Luogu 2150 [NOI 2015] 寿司晚宴

    传送门思路对于 30 30 30 的数据对于 100 100 100 的数据参考代码 传送门 思路 唉 xff0c 我太弱了 xff0c 什么都不会 xff0c 完全做不来 xff0c 连暴力都打不来 主要好像是因为我从来没有做过以质因子为

  • Luogu 3649 [APIO 2014] 回文串

    传送门思路Manacher 算法 特殊字符回文半径算法与实现本质不同的回文串个数 正解参考代码总结 传送门 思路 唉 xff0c 我太弱了 xff0c 什么都不会 xff0c 这道题各路神仙都说是模板题 xff0c 但我觉得完全不可做 xf

  • Luogu 2168 [NOI 2015] 荷马史诗

    传送门思路参考代码 传送门 思路 唉 xff0c 我太弱了 xff0c 什么都不会 xff0c 连哈夫曼树都不会 这道题就是一个 k k 叉哈夫曼树 题目要求满足两个条件 一是代价最小 二是最长长度最小 最长长度最小很好解决 只需要优先合并

  • Luogu 2178 [NOI 2015] 品酒大会

    传送门思路参考代码 传送门 思路 唉 xff0c 我太弱了 xff0c 什么都不会 xff0c 做了两个星期的题 xff0c 自己做出来的才只有这一道 xff0c 唉 xff0c 我太弱啦 xff01 我们考虑第一问怎么做 题目中相似的概念

  • Luogu 1117 [NOI 2016] 优秀的拆分

    传送门思路利用后缀数组解决重复子串问题注意事项参考代码 传送门 思路 唉 xff0c 我太弱了 xff0c 什么都不会 xff0c 连暴力都想不到 xff0c 唉 xff0c 我太弱啦 xff01 考虑暴力法 xff0c 可以枚举一个中间点

  • Luogu 1712 [NOI 2016] 区间

    传送门思路参考代码 传送门 思路 唉 xff0c 我太弱了 xff0c 什么都不会 xff0c 这么个傻逼题 xff0c 居然把离散化写错了 xff0c 唉 xff0c 我太弱啦 xff01 显然我们可以考虑枚举最短长度和最长长度 xff0

  • CF 977F Consecutive Subsequence

    传送门思路参考代码 传送门 思路 CF 的第一场 div3 xff0c 在我提交了一份有错的代码后突然不能提交了 xff0c 在跑什么 System Testing xff0c 我就跟它杠上了 xff0c 直到它评测完 唉 xff0c 我太

  • CF 7D Palindrome Degree

    传送门思路参考代码 传送门 思路 不是马拉车加随便 DP 乱搞 xff1f 本来想复习一下马拉车的 xff0c 结果拉出了许多事端 xff08 修复了 OI Learner Judge 的严重 bug 一个害我调了两节课的 bug xff0

  • Luogu 3822 [NOI 2017] 整数

    传送门思路参考代码 传送门 思路 唉 xff0c 我太弱了 xff0c 什么都不会 xff0c 当年网同这道题还拿了 16 16 分 xff0c 现在一分都不会做了 xff0c 唉 xff0c 我太弱啦 xff01 这道题其实是很不错的 x

  • 【Go】go语言中切片的长度变化后容量的变化

    一 新增信息长度 43 当前长度 lt 61 当前容量 span class token keyword func span span class token function printSlice span span class toke

  • APIO 2018 Practice Session T1 Wedding cake

    没有传送门题目大意思路参考代码熟悉环境 没有传送门 题目大意 给你一个长度为 n n 的正整数序列 a i ai xff0c 要求构造出 n n 个小数 使得它们的和为 1 1 xff0c 且每个数小数点后恰好有

  • APIO 2018 Practice Session T3 / CF 936C Lock Puzzle

    传送门题目大意思路参考代码总结 传送门 题目大意 给你一个字符串 origin xff0c 一个字符串 target xff0c 长度均为 n n 要求在 3 n 3n xff08 5 2 n 5 2

  • APIO 2018 游记

    Day 0Day 1Day 2Day 3Day 4 Day 0 早上 4 4 点就上车去机场赶那 7 7 点的飞机 感觉很困 xff0c 所以在飞机上就这么睡过去了 北京是个好地方 xff0c 但是与我无关 下飞机后 xff0c 我们一行人

  • Luogu 2375 [NOI 2014] 动物园

    文章目录 传送门思路参考代码Review 传送门 思路 唉 xff0c 我太弱了 xff0c 什么都不会 xff0c 连 KMP 也不会 xff0c WA 飞了 xff0c 唉 xff0c 我太弱啦 xff01 首先 xff0c 原始的 K

  • Luogu 2114 [NOI 2014] 起床困难综合症

    传送门思路参考代码 传送门 思路 按位贪心 但是我太弱了 xff0c 明明可以 O n O n 预处理 xff0c 我却只会 O 32 n O

  • Luogu 2354 [NOI 2014] 随机数生成器

    传送门思路参考代码 传送门 思路 唉 xff0c 我太弱了 xff0c 什么都不会 xff0c 这么一个傻逼题 xff0c 我却看成了要你构造一种交换方案使得答案最小 xff0c 结果后面的额外交换是题目给定的 唉 xff0c 我太弱啦 x

  • Luogu 2305 [NOI 2014] 购票

    传送门思路别人家的题解弱化的传送门 xff08 Luogu 3994 高速公路 xff09 参考代码 对于没有距离限制的 50 分 参考代码 对于 100 分的数据参考代码Remarks 传送门 思路 唉 xff0c 我太弱了 xff0c

热门标签