头像

一只野生彩色铅笔

梓瑟正确的:$\href{http://www.colopen-blog.com}{Colopen's \ blog}$




离线:20天前


最近来访(7627)
用户头像
Mark1St
用户头像
一只小丑人
用户头像
种花家的兔兔
用户头像
顺然
用户头像
旭日临窗
用户头像
TheForsaking
用户头像
灰原哀
用户头像
刘春山
用户头像
郭华峰
用户头像
何必在乎太多
用户头像
狂气电波
用户头像
ねずこ
用户头像
DP真的难
用户头像
OnLine_Set
用户头像
mmk-
用户头像
从前
用户头像
OI
用户头像
ephemeral.
用户头像
Epimenides
用户头像
plank_black

活动打卡代码 AcWing 179. 八数码

#include <iostream>
#include <queue>
#include <unordered_map>
#include <algorithm>
using namespace std;

typedef pair<int, string> PIS;

int f(string state)
{
    int res = 0;
    for (int i = 0; i < 9; ++i)
    {
        if (state[i] != 'x')
        {
            int t = state[i] - '1';
            res += abs(t / 3 - i / 3) + abs(t % 3 - i % 3);
        }
    }
    return res;
}
string astar(string start, string end)
{
    char op[5] = {"udlr"};
    int dx[] = {-1, 1, 0, 0};
    int dy[] = {0, 0, -1, 1};
    unordered_map<string, int> dist;
    unordered_map<string, pair<char, string>> prev;
    priority_queue<PIS, vector<PIS>, greater<PIS>> heap;
    heap.push({f(start), start});

    while (!heap.empty())
    {
        PIS t = heap.top();
        heap.pop();

        string state = t.second;

        if (state == end) break;
        int x, y;
        for (int i = 0; i < 9; ++i)
        {
            if (state[i] == 'x')
            {
                x = i / 3, y = i % 3;
                break;
            }
        }

        for (int i = 0; i < 4; ++i)
        {
            int a = x + dx[i], b = y + dy[i];
            if (a < 0 || a >= 3 || b < 0 || b >= 3) continue;

            string temp = state;
            swap(temp[a * 3 + b], temp[x * 3 + y]);

            int d = dist[state] + 1;
            if (!dist.count(temp) || dist[temp] > d)
            {
                dist[temp] = d;
                prev[temp] = {op[i], state};
                heap.push({dist[temp] + f(temp), temp});
            }
        }
    }
    string path;
    while (start != end)
    {
        path += prev[end].first;
        end = prev[end].second;
    }
    reverse(path.begin(), path.end());
    return path;
}
int main()
{
    string start, x, seq;
    while (cin >> x)
    {
        start += x;
        if (x != "x") seq += x;
    }
    string end = "12345678x";
    int t = 0;
    for (int i = 0; i < 8; ++i)
        for (int j = i + 1; j < 8; ++j)
            if (seq[i] < seq[j])
                ++t;
    if (t & 1) puts("unsolvable");
    else cout << astar(start, end) << endl;
    return 0;
}


活动打卡代码 AcWing 178. 第K短路

易知,当点 $x$ 第 $k$ 次从优先队列队头取出时,求得的就是从起点到点 $x$ 的第 $k$ 短路代价

直接用优先队列做的时间复杂度为 $O(K(N + M) \log (N + M))$

考虑设计估价函数 f(x)x 到点 T 的最短路距离

这样在第 K 短路中,点x 到点T的估计距离f(x)小于实际距离,估价函数设计成立

#include <iostream>
#include <cstring>
#include <algorithm>
#include <queue>

#define x first
#define y second

using namespace std;

typedef pair<int, int> PII;
typedef pair<int, PII> PIII;

const int N = 1010, M = 20010;

int S, T, K, n, m;
int hp[N], hn[N], e[M], w[M], ne[M], idx;
int cnt[N], dist[N];
bool st[N];

void add(int h[], int a, int b, int c)
{
    e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx ++ ;
}
void dijkstra()
{
    memset(st, 0, sizeof st);
    memset(dist, 0x3f, sizeof dist);
    priority_queue<PII, vector<PII>, greater<PII>> heap;
    dist[T] = 0;
    heap.push({0, T});
    while (heap.size())
    {
        PII t = heap.top(); heap.pop();

        if (st[t.y]) continue;
        st[t.y] = true;

        for (int i = hn[t.y]; ~i; i = ne[i])
        {
            int j = e[i];
            if (dist[j] > dist[t.y] + w[i])
            {
                dist[j] = dist[t.y] + w[i];
                heap.push({dist[j], j});
            }
        }
    }
}
int f(int id)
{
    return dist[id];
}
int astar()
{
    memset(cnt, 0, sizeof cnt);
    priority_queue<PIII, vector<PIII>, greater<PIII>> heap;
    heap.push({f(S), {0, S}});
    while (heap.size())
    {
        PIII t = heap.top(); heap.pop();

        int ver = t.y.y, d = t.y.x;
        cnt[ver] ++ ;
        if (cnt[T] == K) return d;

        for (int i = hp[ver]; ~i; i = ne[i])
        {
            int j = e[i];
            if (cnt[j] < K)
                heap.push({d + w[i] + f(j), {d + w[i], j}});
        }
    }
    return -1;
}
int main()
{
    cin >> n >> m;
    memset(hp, -1, sizeof hp);
    memset(hn, -1, sizeof hn);
    while (m -- )
    {
        int a, b, c;
        cin >> a >> b >> c;
        add(hp, a, b, c);
        add(hn, b, a, c);
    }
    cin >> S >> T >> K;
    if (S == T) K ++ ;

    dijkstra();
    cout << astar() << endl;
    return 0;
}


活动打卡代码 AcWing 177. 噩梦

#include <iostream>
#include <algorithm>
#include <cstring>
#include <queue>

#define x first
#define y second

using namespace std;

typedef pair<int, int> PII;

const int N = 810;

int n, m;
char g[N][N];
int st[N][N];
PII boy, girl, ghost[2];
int dx[] = {1, 0, -1, 0};
int dy[] = {0, 1, 0, -1};

bool check(int a, int b, int t)
{
    if (a < 0 || a >= n || b < 0 || b >= m || g[a][b] == 'X') return false;
    for (int i = 0; i < 2; i ++ )
        if (abs(ghost[i].x - a) + abs(ghost[i].y - b) <= 2 * t)
            return false;
    return true;
}
int solve()
{
    memset(st, 0, sizeof st);
    cin >> n >> m;
    for (int i = 0; i < n; i ++ ) cin >> g[i];
    int cnt = 0;
    for (int i = 0; i < n; i ++ )
        for (int j = 0; j < m; j ++ )
            if (g[i][j] == 'M') boy = {i, j};
            else if (g[i][j] == 'G') girl = {i, j};
            else if (g[i][j] == 'Z') ghost[cnt ++ ] = {i, j};

    queue<PII> qb, qg;
    qb.push(boy);
    qg.push(girl);

    int step = 0;
    while (qb.size() || qg.size())
    {
        step ++ ;
        for (int i = 0; i < 3; i ++ )
        {
            for (int j = 0, siz = qb.size(); j < siz; j ++ )
            {
                PII t = qb.front(); qb.pop();
                int x = t.x, y = t.y;
                if (!check(x, y, step)) continue;
                for (int k = 0; k < 4; k ++ )
                {
                    int a = x + dx[k], b = y + dy[k];
                    if (check(a, b, step))
                    {
                        if (st[a][b] == 2) return step;
                        if (!st[a][b])
                        {
                            st[a][b] = 1;
                            qb.push({a, b});
                        }
                    }
                }
            }
        }
        for (int i = 0; i < 1; i ++ )
        {
            for (int j = 0, siz = qg.size(); j < siz; j ++ )
            {
                PII t = qg.front(); qg.pop();
                int x = t.x, y = t.y;
                if (!check(x, y, step)) continue;
                for (int k = 0; k < 4; k ++ )
                {
                    int a = x + dx[k], b = y + dy[k];
                    if (check(a, b, step))
                    {
                        if (st[a][b] == 1) return step;
                        if (!st[a][b])
                        {
                            st[a][b] = 2;
                            qg.push({a, b});
                        }
                    }
                }
            }
        }
    }
    return -1;
}
int main()
{
    int T;
    cin >> T;
    while (T -- ) cout << solve() << endl;
    return 0;
}


活动打卡代码 AcWing 176. 装满的油箱

直接拆点,以二元组 {city, fuel} 作为一个点,进行建图,然后做一遍最短路即可

每一次扩展有两种选择:

  1. 当前油箱未满,且加一升油后 {city, fuel} + price[city] < {city, fuel + 1} 那么就在当前城市加一升油,并扩展出去
  2. 当前油量可以抵达下一个城市且 cost < {next, fuel - dist} 那就扩展出去
#include <iostream>
#include <algorithm>
#include <cstring>
#include <queue>

#define x first
#define y second

using namespace std;

typedef pair<int, int> PII;
typedef pair<int, PII> PIII;

const int INF = 0x3f3f3f3f;

int n, m, q;
int C, S, E;
int h[1010], e[20010], w[20010], ne[20010], idx;
int p[1010];
int dist[1010][110];
bool st[1010][110];

void add(int a, int b, int c)
{
    e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx ++ ;
}
int dijkstra()
{
    memset(st, 0, sizeof st);
    memset(dist, 0x3f, sizeof dist);
    priority_queue<PIII, vector<PIII>, greater<PIII>> heap;
    dist[S][0] = 0;
    heap.push({0, {S, 0}});
    while (heap.size())
    {
        auto t = heap.top(); heap.pop();
        int cost = t.x, ver = t.y.x, fuel = t.y.y;

        if (st[ver][fuel]) continue;
        st[ver][fuel] = true;
        if (ver == E) return cost;

        if (fuel < C && dist[ver][fuel + 1] > cost + p[ver])
        {
            dist[ver][fuel + 1] = cost + p[ver];
            heap.push({cost + p[ver], {ver, fuel + 1}});
        }
        for (int i = h[ver]; ~i; i = ne[i])
        {
            int j = e[i], d = w[i];
            if (fuel >= d && dist[j][fuel - d] > cost)
            {
                dist[j][fuel - d] = cost;
                heap.push({cost, {j, fuel - d}});
            }
        }
    }
    return -1;
}
int main()
{
    memset(h, -1, sizeof h);
    cin >> n >> m;
    for (int i = 0; i < n; i ++ ) cin >> p[i];
    for (int i = 0; i < m; i ++ )
    {
        int u, v, d;
        cin >> u >> v >> d;
        add(u, v, d), add(v, u, d);
    }
    cin >> q;
    while (q -- )
    {
        cin >> C >> S >> E;
        int t = dijkstra();
        if (~t) cout << t << endl;
        else puts("impossible");
    }
    return 0;
}


活动打卡代码 AcWing 175. 电路维修

#include <iostream>
#include <cstring>
#include <algorithm>
#include <deque>

#define x first
#define y second

using namespace std;

typedef pair<int,int> PII;

const int N = 510;

int T, n, m;
char g[N][N];
int dist[N][N];
bool st[N][N];

void solve()
{
    memset(st, 0, sizeof st);
    memset(dist, 0x3f, sizeof dist);
    dist[0][0] = 0;
    deque<PII> deq;
    deq.push_back({0, 0});

    char state[] = {"\\/\\/"};
    int dx[] = {1, 1, -1, -1}, dy[] = {1, -1, -1, 1};
    int ix[] = {0, 0, -1, -1}, iy[] = {0, -1, -1, 0};

    while (deq.size())
    {
        PII t = deq.front();
        deq.pop_front();
        if (st[t.x][t.y]) continue;
        if (t.x == n && t.y == m) break;
        st[t.x][t.y] = true;

        for (int i = 0; i < 4; i ++ )
        {
            int a = t.x + dx[i], b = t.y + dy[i];
            if (a < 0 || a > n || b < 0 || b > m) continue;
            int w = g[t.x + ix[i]][t.y + iy[i]] != state[i];
            int d = w + dist[t.x][t.y];

            if (d < dist[a][b])
            {
                dist[a][b] = d;
                if (w) deq.push_back({a, b});
                else deq.push_front({a, b});
            }
        }
    }
    cout << dist[n][m] << endl;
}
int main()
{
    cin >> T;
    while (T -- )
    {
        cin >> n >> m;
        for (int i = 0; i < n; i ++ ) cin >> g[i];
        if ((n + m) & 1) puts("NO SOLUTION");
        else solve();
    }
    return 0;
}


新鲜事 原文

上岸 沙坡村皇家男子职业技术学院 有考研相关的问题可以找我免费咨询


活动打卡代码 工程课 Web-1.10. homework_10

工程课 Web-1.10. homework_10

编写一个完整的 HTML 页面。

页面中包含一行如下内容:

©<Web>版权所有
&copy;&lt;Web&gt;版权所有


活动打卡代码 工程课 Web-1.9. homework_9

工程课 Web-1.9. homework_9

编写一个完整的 HTML 页面。

内容包括四个部分:

  • header区:
    • 包含 <h3> 标题,内容为:我的收藏夹
  • section区:
    • 包含 <h4> 标题,内容为:图片
    • 第一个 <figure>,包含一个 <img>src/images/logo.png,宽度为 100px<figcaption> 的文本为:logo
    • 第二个 <figure>,包含一个 <img>src/images/mountain.jpg,宽度为 100px<figcaption> 的文本为:
  • section
    • 包含 <h4> 标题,内容为:古诗
    • 第一个 <article>,包含一个 <h5> 标题,内容为:春晓,之后包含一个段落,内容为:春眠不觉晓,处处闻啼鸟。夜来风雨声,花落知多少。
    • 第二个 <article>,包含一个 <h5> 标题,内容为:咏柳,之后包含一个段落,内容为:碧玉妆成一树高,万条垂下绿丝绦。不知细叶谁裁出,二月春风似剪刀。
  • footer
    • 包含一行文本:©2018-2022 Me 版权所有
<header>
    <h3>我的收藏夹</h3>
</header>

<section>
    <h4>图片</h4>
    <figure>
        <img src="/images/logo.png" width="100" alt="logo">
        <figcaption>logo</figcaption>
    </figure>
    <figure>
        <img src="/images/mountain.jpg" width="100" alt="山">
        <figcaption>山</figcaption>
    </figure>
</section>

<section>
    <h4>古诗</h4>
    <article>
        <h5>春晓</h5>
        <p>
            春眠不觉晓,处处闻啼鸟。夜来风雨声,花落知多少。
        </p>
    </article>
    <article>
        <h5>咏柳</h5>
        <p>
            碧玉妆成一树高,万条垂下绿丝绦。不知细叶谁裁出,二月春风似剪刀。
        </p>
    </article>
</section>

<footer>
    &copy;2018-2022 Me 版权所有
</footer>


活动打卡代码 工程课 Web-1.8. homework_8

工程课 Web-1.8. homework_8

编写一个完整的 HTML 页面。

页面中包含一个表格,要求:

表格的 标题 为:成绩单
表格的 内容 为:

姓名 数学 语文 英语
Alice 100 99 98
Bob 99 98 97
Tom 98 97 96
<table>
    <caption>成绩单</caption>
    <thead>
        <tr>
            <th>姓名</th>
            <th>数学</th>
            <th>语文</th>
            <th>英语</th>
        </tr>
    </thead>
    <tr>
        <td>Alice</td>
        <td>100</td>
        <td>99</td>
        <td>98</td>
    </tr>
    <tr>
        <td>Bob</td>
        <td>99</td>
        <td>98</td>
        <td>97</td>
    </tr>
    <tr>
        <td>Tom</td>
        <td>98</td>
        <td>97</td>
        <td>96</td>
    </tr>
</table>


活动打卡代码 工程课 Web-1.7. homework_7

工程课 Web-1.7. homework_7

编写一个完整的 HTML 页面。

页面中包含一个有序列表:

  • 列表第一项只包含一个文本,内容为:第一讲
  • 列表第二项包含:
    • 一个文本,内容为:第二讲
    • 一个无序列表,包含3项,均为文本,内容分别为:第一小节第二小节第三小节
  • 列表第三项包含:
    • 一个文本,内容为:第三讲
    • 一个有序列表,包含3想,均为文本,内容分别为:第一小节第二小节第三小节
<ol>
    <li>第一讲</li>
    <li>
        第二讲
        <ul>
            <li>第一小节</li>
            <li>第二小节</li>
            <li>第三小节</li>
        </ul>
    </li>
    <li>
        第三讲
        <ol>
            <li>第一小节</li>
            <li>第二小节</li>
            <li>第三小节</li>
        </ol>
    </li>
</ol>