Skip to content
This repository was archived by the owner on Jul 24, 2022. It is now read-only.

Latest commit

 

History

History
466 lines (405 loc) · 12.4 KB

5-3.md

File metadata and controls

466 lines (405 loc) · 12.4 KB

4.20-5.3 Learning Notes

Huawei Sofeware Competition

First Round

成功水进复赛
5-3-2020-05-01-12-58-52

思路：

  • 三邻域剪枝
  • 6+1
  • 向量改数组

感谢：

code

#include <iostream>
#include <algorithm>
#include <string>
#include <cstring>
#include <array>
#include <chrono>
#include <cmath>
using namespace std;

auto time_start = chrono::steady_clock::now();

// #define LINUXOUTPUT
#define OUTPUT
#define TEST

string input_path = "/data/test_data.txt";
string output_path = "/projects/student/result.txt";
#ifdef TEST
string test_scale = "1004812";
string test_input_path_s = "./data/" + test_scale + "/test_data.txt";
string test_output_path_s = test_input_path_s.substr(0, test_input_path_s.rfind('/')) + "/output.txt";
#endif

const int INF = 280005;
typedef long long ll;

int GUV[INF][51];
int GVU[INF][51];

bool visited[INF];
int flag[INF];

typedef array<int, 8> ans_t;
int ans_size;
ans_t ans[4000005];

int u_max;
namespace IO
{
const int MAXSIZE = 1 << 20;
char buf[MAXSIZE], *p1, *p2;
#define gc() (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, MAXSIZE, stdin), p1 == p2) ? EOF : *p1++)
inline int rd()
{
    int x = 0;
    int16_t c = gc();
    while (!isdigit(c))
    {
        if (c == EOF)
            return c;
        c = gc();
    }
    while (isdigit(c))
        x = x * 10 + (c ^ 48), c = gc();
    return x;
}
inline void rd_to_line_end()
{
    int16_t c = gc();
    while (c != '\n')
        c = gc();
}
char pbuf[MAXSIZE], *pp = pbuf;
inline void push(const char &c)
{
    if (pp - pbuf == MAXSIZE)
        fwrite(pbuf, 1, MAXSIZE, stdout), pp = pbuf;
    *pp++ = c;
}
inline void write(int x)
{
    static int sta[35];
    int top = 0;
    do
    {
        sta[top++] = x % 10, x /= 10;
    } while (x);
    while (top)
        push(sta[--top] + '0');
}
} // namespace IO

inline void read_data()
{
    freopen(test_input_path_s.c_str(), "r", stdin);
    int u, v;
    int ch;
    register int i;
    while (1)
    {
        u = IO::rd();
        if (u == EOF)
            break;
        v = IO::rd();
        IO::rd_to_line_end();
        GUV[u][++GUV[u][0]] = v;
        GVU[v][++GVU[v][0]] = u;
        u_max = max(u_max, u);
    }
#ifdef TEST
    auto input_time_end = chrono::steady_clock::now();
    auto input_time_diff = input_time_end - time_start;
    cout << "prehandle cost: " << chrono::duration<double, milli>(input_time_diff).count() / 1000 << "s" << endl;
#endif
}
inline bool cmp(ans_t &x, ans_t &y)
{
    int now = 0;
    while (x[now] == y[now])
        ++now;
    return x[now] < y[now];
}
void flag_reverse_dfs(int u, int depth, int target)
{
    register int i;
    int v;
    for (i = 1; i <= GVU[u][0]; i++)
    {
        v = GVU[u][i];
        if (!visited[v] && v > target)
        {
            visited[v] = 1;
            flag[v] = target;
            if (depth <= 2)
                flag_reverse_dfs(v, depth + 1, target);
            visited[v] = 0;
        }
    }
}
void dfs(int u, int depth, ans_t &path, int target)
{
    register int i;
    int v;
    for (i = 1; i <= GUV[u][0]; i++)
    {
        v = GUV[u][i];
        if (v <= target)
            continue;
        if (flag[v] == -target && visited[v] == 0)
        {
            if (depth >= 2)
            {
                path[0] = depth + 1;
                path[depth + 1] = v;
                ans[++ans_size] = path;
            }
        }
        if (flag[v] != target && flag[v] != -target && depth >= 4)
            continue;
        if (!visited[v] && depth <= 5)
        {
            visited[v] = 1;
            path[depth + 1] = v;
            dfs(v, depth + 1, path, target);
            visited[v] = 0;
        }
    }
}
inline void work()
{
    ans_t path;
    register int i, j;
    int target;
    for (i = 1; i <= u_max; i++)
    {
        if (GUV[i][0] == 0)
            continue;
        flag_reverse_dfs(i, 1, i);
        for (j = 1; j <= GVU[i][0]; j++)
            flag[GVU[i][j]] = -i;
        path[1] = i;
        dfs(i, 1, path, i);
    }
}
inline void output_data()
{
    register int i, j;
    freopen(test_output_path_s.c_str(), "w", stdout);
    sort(ans + 1, ans + ans_size + 1, cmp);
#ifdef TEST
    auto output_time_start = chrono::steady_clock::now();
#endif
    printf("%d\n", ans_size);
    for (i = 1; i <= ans_size; i++)
    {
        for (j = 1; j < ans[i][0]; j++)
        {
            IO::write(ans[i][j]);
            IO::push(',');
        }
        IO::write(ans[i][ans[i][0]]);
        IO::push('\n');
    }
    fwrite(IO::pbuf, 1, IO::pp - IO::pbuf, stdout);
#ifdef LINUXOUTPUT
    freopen("/dev/tty", "w", stdout);
#else
    freopen("CON", "w", stdout);
#endif
#ifdef TEST
    auto output_time_end = chrono::steady_clock::now();
    auto output_time_diff = output_time_end - output_time_start;
    cout << "output cost: " << chrono::duration<double, milli>(output_time_diff).count() / 1000 << "s" << endl;
#endif
    return;
}
int main()
{
    read_data();
    work();
    output_data();
#ifdef TEST
    auto time_end = chrono::steady_clock::now();
    auto diff = time_end - time_start;
#ifdef LINUXOUTPUT
    freopen("/dev/tty", "w", stdout);
#else
    freopen("CON", "w", stdout);
#endif
    printf("ans size is %d\n", ans_size);
    cout << "The program's speed: " << chrono::duration<double, milli>(diff).count() / 1000 << "s" << endl;
#endif
    fclose(stdin);
    fclose(stdout);
    return 0;
}

总结

  • 多看群信息
  • 多上网找别人的思路
  • 钻规则漏洞：开小号/探测数据（误）

面向数据编程

Level 1: 计分数据只有一组

以下设 answer 表示找到的环数。

  • 加入如下代码：

    assert(answer > 2500000);

    提交后返回 Runtime Error。断定：线上存在环数不大于 2500000 的数据。

  • 加入如下代码：

    if (answer <= 2500000) {
    sleep(100);
}

    提交后分数不变。断定：环数不大于 2500000 的数据不计分。

  • 加入如下代码：

    if (answer > 2500000) {
    if (rand() & 1) sleep(100);
}

    多次提交，每次分数都不变。断定：对于一组数据，运行了多次，取最快的一次作为分数。

  • 加入如下代码：

    if (answer > 2500000) {
    sleep((answer - 2500000) / 1000);
}

    提交后返回 414。断定：某一组数据的答案除以 1000 为 2914。

  • 加入如下代码：

    if (answer / 1000 == 2914) {
    sleep(answer % 1000);
}

    提交后返回 186。断定：上述数据的答案为 2914186。

  • 加入如下代码：

    if (answer > 2500000) {
    assert(answer == 2914186);
}

    提交后正常返回。断定：线上计分的数据只有一组，且答案为 2914186。

Level 2: 计分数据分布极不规律

以下设 src[i] 表示以 i 为起点的环数。

  • 加入如下代码：

    if (answer == 2914186) {
    int max_src = 0;
    for (int i = 0; i <= n; i++) {
        max_src = max(max_src, src[i]);
    }
    sleep(max_src * 100 / answer);
}

    提交后返回 26。表明存在一个点，以其为起点的环不少于 2914186 * 0.26 = 757688 个。

  • 加入如下代码：

    if (answer == 2914186) {
    vector<int> vec;
    for (int i = 0; i <= n; i++) {
        if (src[i]) vec.push_back(src[i]);
    }
    sort(vec.begin(), vec.end());
    sleep(vec[(int)vec.size() - 2] * 100 / answer);
}

    提交后返回 13。表明存在另外一个点，以其为起点的环不少于 2914186 * 0.13 = 378844 个。

  • 使用类似的方法，可以得出还有另外一个点，以其为起点的环也不少于 378844 个。

Level 3: 根据数据特点进行优化

  • 使用 Level 1 中介绍的方法，可以得出如下信息：线上的点数为 20W，其中出现在答案里的点数为 4.2W，出现在答案里的点的最大值为 49999。所以优化策略如下：读入时，直接忽略 >= 5W 的节点。

  • 使用 Level 2 中介绍的方法，得出：以 6000, 10000, 10001, 25123 这四个点为起点的环非常多，在给线程分配任务时可以特殊处理。

  • 加入如下代码：

    if (answer == 2914186) {
    int max_src_i = 0;
    for (int i = 0; i <= n; i++) {
        if (src[i]) max_src_i = i;
    }
    sleep(max_src_i / 1000);
}

    提交后返回 43。表明不存在满足“环中的最小值大于 44000”的环，所以枚举起点时只需要枚举到 44000。

Level 4: 猜测数据生成规则

下述 K12, K13 分别表示 12 个点、13 个点的有向完全图。容易知道，对于 K_n，其中长度为 m(3<=m<=n) 的环数为 C(n,m) * (m-1)!。

  • 使用 Level 2 中介绍的方法，得出：以 10000 为起点的环大约为 757688 个；以 6000, 10001 为起点的环大约为 378844 个。

  • 观察到：设 1, 2, 3, ..., 13 这 13 个点组成一个 K13，那么以 1 为起点的长度介于三和七之间的环的个数为 773652 个，这个数字和 757688 十分接近。同时可以发现，以 2 为起点的长度介于三和七之间的环的个数为 397100，这个数字和 378844 十分接近。由此猜测：10000, 10001, ..., 10012 这 13 个点组成了一个 K13。经验证果然如此！

  • 使用相同的做法可以发现，6000, 6001, ..., 6011 这 12 个点组成了一个 K12，25123, 25124, ..., 25134 这 12 个点也组成了一个 K12。

  • 结合 Level 3 中的结论 “答案中最大的点为 49999”，猜测：大于等于 50000 的点连成一个 DAG 森林，没有环出现。

  • 对于 K13，其中长度介于三和七之间的环的个数为 1477190。对于 K12，其中长度介于三和七之间的环的个数为 703538。所以仅仅这三个团的环数已经有 2884266 个，而总环数只有 2914186 个，也就是说除了这三个团，只有 29920 个环。这些环是很容易生成的，推测是使用了某种随机算法。

综上：10000, 10001, ..., 10012 这 13 个点组成了一个 K13，6000, 6001, ..., 6011 这 12 个点组成了一个 K12，25123, 25124, ..., 25134 这 12 个点也组成了一个 K12。其余的小于 50000 的点随机连边。大于等于 50000 的点连成 DAG 森林。

Leetcode

滑动窗口+map/multiset

只有滑动窗口的代码

思路：
若maxn-minx>limit，将滑动窗口左端点右移
否则扩大窗口，将右端点右移
答案就是最大的滑动窗口大小

class Solution
{
public:
    int longestSubarray(vector<int> &nums, int limit)
    {
        int ans = 1;
        int len = 0;
        int minx = 1 << 30;
        int maxn = 0;
        for (int j = 0; j < nums.size(); j++)
        {
            len = 1;
            minx = nums[j];
            maxn = nums[j];
            for (int i = j + 1; i < nums.size(); i++)
            {
                maxn = max(maxn, nums[i]);
                minx = min(minx, nums[i]);
                if (maxn - minx > limit)
                {
                    ans = max(len, ans);
                    break;
                }
                else
                {
                    ++len;
                }
            }
            ans = max(len, ans);
        }
        return ans;
    }
};

+map/multiset

上面的程序在每次滑动窗口右移的时候，都要重新计算滑动窗口中的最大值和最小值。
所以可以用map（红黑树）来维护滑动窗口中的最大值和最小值，右移的时候就删掉窗口左端点的值，扩大窗口的时候就插入右端点的值

class Solution
{
public:
    int longestSubarray(vector<int> &nums, int limit)
    {
        map<int,int> m;
        int ans = 1;
        int j=0;
        for (int i=0;i<nums.size();i++)
        {
            // insert
            ++m[nums[i]];
            // maxn-minx>limit
            if (m.rbegin()->first-m.begin()->first>limit) 
            {
                // window right shift
                --m[nums[j]];
                if (m[nums[j]]==0)
                    m.erase(nums[j]);
                ++j;
            }
            else
            {
                // calculate window's size
                ans=max(ans,i-j+1);
            }
        }
        return ans;
    }
};