Featured

2019 ICPC Asia Taipei Hsinchu Regional Contest Solution (Chinese)

SCNU & CCNU 两校第一次联合训练,勉强签到成功。这里要膜一波 SLF 和 LWH

#=PenaltyABCDEFGHIJKLM
9 (40)6449  +
00:27
+
00:12
+2
03:01
  +
01:29
 +
01:19
+
00:21
-7 
Official Final Standings

A. Rush Hour Puzzle

最后开的题,码了快一个小时,始终没法过样例。据说用 BFS 做的人都写疯了。

#include <bits/stdc++.h>
using namespace std;

struct Point
{
    int x;
    int y;
    Point(int _x, int _y) : x(_x), y(_y) {}
};

struct Car
{
    vector<Point> p;
    int val;
    int up;
};

struct Node
{
    int graph[6][6];
    vector<Car> car;
    int step;

    void init(int gg[6][6], vector<Car> c, int s)
    {
        memcpy(graph, gg, sizeof(graph));
        car.clear();
        for (int i = 0; i < c.size(); ++i)
        {
            car.push_back(c[i]);
        }
        step = s;
    }
};

int upx[] = {-1, 1};
int lry[] = {-1, 1};

Car start;
Point endP(2, 5);
int in[6][6];
int vis[6][6];
queue<Node> q;
map<string, int> mg;

string toString(int g[6][6])
{
    string s = "";
    for (int i = 0; i < 6; ++i)
    {
        for (int j = 0; j < 6; ++j)
        {
            char c = '0' + g[i][j];
            s.push_back(c);
        }
    }
    return s;
}

bool checkSide(int i, int j)
{
    if (i >= 0 && i < 6 && j >= 0 && j < 6)
    {
        return true;
    }
    return false;
}

void printG(Node n)
{

    for (int i = 0; i < 6; ++i)
    {
        for (int j = 0; j < 6; ++j)
        {
            cout << n.graph[i][j] << " ";
        }
        cout << endl;
    }

    for (int i = 0; i < n.car.size(); ++i)
    {
        for (int j = 0; j < n.car[i].p.size(); ++j)
        {
            cout << "car " << i << ": " << n.car[i].p[j].x << " " << n.car[i].p[j].y << endl;
        }
    }
    cout << "===============" << endl;
}

int bfs()
{
    while (!q.empty())
    {
        Node p = q.front();
        q.pop();

        //printG(p);

        for (int i = 0; i < p.car.size(); ++i)
        {
            Node n;
            int l = 0;
            int r = p.car[i].p.size() - 1;
            int val = p.car[i].val;
            if (val == 1)
            {
                if (p.car[i].p[r].x == endP.x && p.car[i].p[r].y == endP.y && p.step + 2 <= 10)
                {
                    return p.step + 2;
                }
            }

            //cout << "ffff" << endl;
            // 左右
            if (p.car[i].up == 0)
            {
                l = 0;
                r = p.car[i].p.size() - 1;
                //cout << l << " -- " << r << endl;
                val = p.car[i].val;
                // 左移
                Point left = p.car[i].p[l];
                Point right = p.car[i].p[r];
                left.y -= 1;
                if (checkSide(left.x, left.y))
                {

                    if (p.graph[left.x][left.y] == 0)
                    {

                        //cout << "==============" << endl;
                        n.init(p.graph, p.car, p.step + 1);
                        //cout << "lllll" << endl;

                        n.graph[left.x][left.y] = val;
                        n.graph[right.x][right.y] = 0;
                        string ss = toString(n.graph);
                        if (mg.count(ss) == 0 && p.step + 1 <= 10)
                        {
                            for (int j = 0; j < n.car[i].p.size(); ++j)
                            {
                                n.car[i].p[j].y -= 1;
                            }
                            mg[ss] = 1;
                            q.push(n);
                        }
                    }
                }
                //cout << "11111111" << endl;
                // 右移
                left = p.car[i].p[l];
                right = p.car[i].p[r];
                right.y += 1;
                if (checkSide(right.x, right.y))
                {

                    if (p.graph[right.x][right.y] == 0)
                    {

                        n.init(p.graph, p.car, p.step + 1);
                        n.graph[left.x][left.y] = 0;
                        n.graph[right.x][right.y] = val;
                        string ss = toString(n.graph);
                        if (mg.count(ss) == 0 && p.step + 1 <= 10)
                        {
                            for (int j = 0; j < n.car[i].p.size(); ++j)
                            {
                                n.car[i].p[j].y += 1;
                            }
                            mg[ss] = 1;
                            q.push(n);
                        }
                    }
                }
                //cout << "222222" << endl;
            }
            else
            {
                //上移
                //cout << "up" << endl;
                int u = 0;
                int d = p.car[i].p.size() - 1;
                int val = p.car[i].val;
                Point up = p.car[i].p[u];
                Point down = p.car[i].p[d];
                up.x -= 1;
                if (checkSide(up.x, up.y))
                {
                    if (p.graph[up.x][up.y] == 0)
                    {

                        //cout << "up 1" << endl;
                        n.init(p.graph, p.car, p.step + 1);
                        //cout << "up 2" << endl;
                        n.graph[up.x][up.y] = val;
                        n.graph[down.x][down.y] = 0;
                        string ss = toString(n.graph);
                        if (mg.count(ss) == 0 && p.step + 1 <= 10)
                        {
                            for (int j = 0; j < n.car[i].p.size(); ++j)
                            {
                                n.car[i].p[j].x -= 1;
                            }
                            mg[ss] = 1;
                            q.push(n);
                        }
                    }
                }

                up = p.car[i].p[u];
                down = p.car[i].p[d];
                down.x += 1;
                if (checkSide(down.x, down.y))
                {

                    if (p.graph[down.x][down.y] == 0)
                    {

                        n.init(p.graph, p.car, p.step + 1);

                        n.graph[up.x][up.y] = 0;
                        n.graph[down.x][down.y] = val;
                        string ss = toString(n.graph);
                        if (mg.count(ss) == 0 && p.step + 1 <= 10)
                        {
                            for (int j = 0; j < n.car[i].p.size(); ++j)
                            {
                                n.car[i].p[j].x += 1;
                            }
                            mg[ss] = 1;
                            q.push(n);
                        }
                    }
                }
            }
        }
    }
    return -1;
}

void search_car(int x, int y, Car &c)
{
    int xx, yy;
    c.p.push_back(Point(x, y));
    vis[x][y] = 1;
    for (int i = 0; i < 2; ++i)
    {
        // 上下
        yy = y;
        xx = x + upx[i];
        if (checkSide(xx, yy) && in[x][y] == in[xx][yy])
        {
            while (checkSide(xx, yy) && in[x][y] == in[xx][yy])
            {
                c.up = 1;
                c.p.push_back(Point(xx, yy));
                vis[xx][yy] = 1;
                yy = yy;
                xx = xx + upx[i];
            }
            return;
        }

        // 左右
        xx = x;
        yy = y + lry[i];
        if (checkSide(xx, yy) && in[x][y] == in[xx][yy])
        {
            while (checkSide(xx, yy) && in[x][y] == in[xx][yy])
            {
                c.up = 0;
                c.p.push_back(Point(xx, yy));
                vis[xx][yy] = 1;
                xx = x;
                yy = yy + lry[i];
            }
            return;
        }
    }

    return;
}

bool init()
{
    mg.clear();
    while (!q.empty())
        q.pop();
    memset(vis, 0, sizeof(vis));
    Node st;
    memcpy(st.graph, in, sizeof(in));
    st.step = 0;
    for (int i = 0; i < 6; ++i)
    {
        for (int j = 0; j < 6; ++j)
        {
            if (in[i][j] != 0 && !vis[i][j])
            {
                Car c;
                c.val = in[i][j];
                search_car(i, j, c);
                st.car.push_back(c);
                if (in[i][j] == 1)
                {
                    if (i != endP.x)
                    {
                        return false;
                    }

                    else if (c.up != 0)
                    {
                        return false;
                    }
                    start = c;
                }
            }
        }
    }

    q.push(st);
    mg[toString(in)] = 1;
    return true;
}

int main()
{
    for (int i = 0; i < 6; ++i)
    {
        for (int j = 0; j < 6; ++j)
        {
            cin >> in[i][j];
        }
    }

    if (!init())
    {
        cout << "-1" << endl;
    }
    else
    {
        cout << bfs() << endl;
    }

    return 0;
}
Continue reading “2019 ICPC Asia Taipei Hsinchu Regional Contest Solution (Chinese)”
Featured

2020 Nowcoder Basic Algorithm Training Camp Solution (Chinese)

颓废了一个寒假,Codeforces 打来打去都是 Specialist,菜的一批。POJ 又刷到怀疑人生。后来被 Kaidora 神犇安排了这个集训营。当时已经是第四场要开始了,还是去了。果然,哪怕都是自闭五小时每小时过一题,氪了金感觉就是不一样。

点击下方的页码查看相应场次的记录,第 \(i\) 页对应的是第 \(i-1\) 场比赛。

SCNUSE 2020 GPLT Tryouts Level 2-3 Solution (Chinese)

2-1

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 200010;
int f[MAXN];
int find_father(int x) { return f[x] == x ? x : f[x] = find_father(f[x]); }
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    int flag[110];
    memset(flag, 0, sizeof(flag));
    int n;
    cin >> n;
    for (int i = 1; i <= n; ++i)
    {
        f[i] = i;
        string str;
        cin >> str;
        for (int j = 0; j < str.size(); ++j)
        {
            int t = str[j] - 'a';
            if (!flag[t])
            {
                flag[t] = i;
            }
            else
            {
                int tx = find_father(flag[t]);
                int ty = find_father(i);
                if (tx != ty)
                {
                    f[tx] = ty;
                }
            }
        }
    }
    int res = 0;
    for (int i = 1; i <= n; ++i)
    {
        if (i == find_father(i))
            res++;
    }
    cout << res;
    return 0;
}
Continue reading “SCNUSE 2020 GPLT Tryouts Level 2-3 Solution (Chinese)”

Porting Calamares to Arch Linux ISO Images

This article is for reference ONLY.

Calamares is a distribution-independent installer framework. As distributions like Arch Linux don’t provide graphical installer, we can try to adapt Calamares to them. To make things easier, we simply start by trying to provide a pacstrap part for Calamares, which allow users to install a minimal Arch Linux system, then we add the Calamares installer to our Archiso.

Getting Started

Make sure that you have Git installed, fetch the source code by cloning the Calamares repository, to speed up, add --depth=1 option:

git clone https://github.com/calamares/calamares.git --depth=1

Entering the repository, you will find lots of files and directories, don’t panic! All you have to focus on are three files/directories: settings.conf, src/branding/ and src/modules/. Let’s try to deal with them one by one.

Continue reading “Porting Calamares to Arch Linux ISO Images”

Install and Configure WordPress on Fedora Server Edition

Hi everyone! I am trying to i18n my website, so this post will be the first one which is written in English. Hope you will like it! 🙂

First things first

You should get a IP address after buying VPS, such as 123.123.123.123. Open your favourite terminal and enter:

Replace 123.123.123.123 with your actual IP address.

ssh [email protected]

Enter your password to login. Perform a full upgrade on your system:

dnf upgrade
Continue reading “Install and Configure WordPress on Fedora Server Edition”

NixOS Installation Guide (Chinese)

这篇文章是我没有启用本 WordPress 站点前输出的为数不多的长文之一,将格式转换了一下就放了上来。由于是本人的早期作品,而且我现在也不用 NixOS 了,所以里面的内容仅供参考。

NixOS 是独立开发的 GNU/Linux 发行,它旨在改进系统配置管理的现状。本文将指导如何用官方安装镜像启动的 Live 系统安装并配置 NixOS。

在 NixOS 中,整个操作系统,包括内核、应用程序、系统软件包、配置文件,统统都由 Nix 包管理器来创建。Nix 将所有软件包以彼此分离的方式进行存储,因此就不存在 /bin/sbin/lib/usr 之类的目录;相反,所有软件包都保存在 /nix/store 中。NixOS 的其他创新特色包括可靠升级、回滚、可重现的系统配置、二进制代码基于源文件的管理模型、多用户包管理。尽管 NixOS 是一份研究性项目,它是一份功能性的及可用的操作系统,能进行硬件检测,使用 KDE Plasma 作为缺省桌面,并采用 systemd 进行系统服务管理。

Continue reading “NixOS Installation Guide (Chinese)”