Category Archives

418 Articles

OI

P1351:联合权值题解

Posted by kal0rona on

思路

这道题本来用爆搜来写的(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%%%

OI

P1141:01迷宫题解

Posted by kal0rona on

思路

在我思考了很久之后(其实是理解题解),我解决了这道题的做法。主要就是并查集的一个扩展和预处理。我们在读取01迷宫时,就检测左边的点和右边的点是否连通。如果是连通的话,在并查集中合并,并且在并查集中把连通块个数相加即可

还有一个主要的思想就是映射。在并查集中我们的数组是一维的(mem[]),我们只需要一个计算函数把(x,y)转换成数字即可。(具体的:ret = x*n + y;)

代码

// P1141_ufs.cpp
#include <iostream>

using namespace std;

const int maxm = 10000000;
const int maxn = 1010;
char map[maxn][maxn];
int n, m;

struct UFS
{
    int mem[maxm];
    int mem_h[maxm];

    UFS()
    {
        for (int i = 0; i < maxm; i++)
            mem[i] = i, mem_h[i] = 1;
        for (int i = maxm; i < maxn; i++)
            mem_h[i] = 1;
    }

    int Find(int a)
    {
        if (mem[a] == a)
            return a;
        return mem[a] = Find(mem[a]);
    }

    void Unite(int a, int b)
    {
        if (Find(a) != Find(b))
            mem_h[Find(a)] += mem_h[Find(b)], mem[Find(b)] = Find(a);
    }
} u;

int hashcode(int a, int b)
{
    return a * n + b;
}

int main()
{
    ios::sync_with_stdio(false);
    cin >> n >> m;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++)
        {
            cin >> map[i][j];
            // left;
            if (j != 1 && map[i][j - 1] != map[i][j])
                u.Unite(hashcode(i, j), hashcode(i, j - 1));
            // up;
            if (i != 1 && map[i - 1][j] != map[i][j])
                u.Unite(hashcode(i, j), hashcode(i - 1, j));
        }
    for (int i = 0; i < m; i++)
    {
        int a, b;
        cin >> a >> b;
        cout << u.mem_h[u.Find(hashcode(a, b))] << endl;
    }
    return 0;
}

代码我喜欢强格式化(vscode)所以行数可能比较多。

OI

Dilworth定理和拦截导弹问题

Posted by kal0rona on

这道题目是我思考了很久的一道题目,可能是因为我太弱了吧。我们先来分析题目。

第一问

这一问是求一套系统能最大拦截的导弹数量。抽象化后,我们可以得出,其实这一问就是让我们求这个序列中最长的不上升序列。我们先来分析样例输入。

389 207 155 300 299 170 158 65

显然,对于这个序列,他的最长不上升序列是{389,300,299,170,158,65}。那么,我们如何用最佳的算法求出此子序列呢?

贪心策略

我们先设定一个指向变量cursor = 0,这个变量记录当前算法在序列S中的位置。我们再设定一个pos = 0的变量,记录我们子序列H的尾部位置。

如果S[cursor]>H[pos],我们可以直接把S[cursor]置于H的尾部,即H[++pos] = S[cursor]。而如果不是这样,我们则可以在H[0:pos],即0到pos这段区间内,总可以找到第一个小于S[cursor]的的量(事实上,我们可以使用二分搜索来查找这个量,因为序列H是拍好了顺序的),我们就让H[bias] = S[cursor]。反复如此。

为什么要把第一个在序列H中小于S[cursor]的赋为S[cursor]?因为当我们把这个值赋入后,我们后续需要插入数据的时候,便会更容易地加入数字(因为在相同位置下,值越大,后续加入的数字的限制也会缩小),也就会使这个子序列最长。

而如果我们要追求O(n log n)的做法时,便需要二分查找。接下来我来介绍两个函数。

lower_bound(start, end, key, [cmp])

该函数调用后会返回一个有序序列中第一个大于等于(如果有cmp函数传入,那就是另外一回事)key的元素地址。

upper_bound(start, end, key, [cmp])

该函数调用后会返回一个有序序列中第一个大于(如果有cmp函数传入,那就是另外一回事)key的元素地址。

奇怪的是,这两个函数跟字面上的完全不同,upper_bound和lower_bound在没有cmp参数传入的情况下,默认的序列排序情况是一致的。搭配之后,便可以获得O(n log n)的神奇速度。

第二问

Dilworth定理

在一个数字序列中,最大不上升子序列的个数为最大上升子序列的长度。亦而反之。

对于我这种蒟蒻而言,Dilworth定理能帮助到我的只是这句话。我曾经翻阅过很多博客,也翻阅过《组合数学》,我并没有找到易于理解的语句。而在我翻阅到一篇绝世神作之后,我便把我的理解归于这一句话。对于OIer而言,Dilworth最有力的部分便是这句话了。

解题思路

第二问的疑问是求出导弹防御系统的套数,根据Dilworth定理,套数应该等于最大不下降子序列的长度。所以,按照第一问的贪心思路,我们很容易类比出本题求最大不上升子序列的贪心策略。所以,在这里,我便不再赘述。