首页 > 其他分享 >8.22 [CSP-S 2021] 交通规划 题解

8.22 [CSP-S 2021] 交通规划 题解

时间:2023-08-22 20:45:28浏览次数:67  
标签:int 题解 hed ++ 2021 8.22 cst col dis

#include <bits/stdc++.h>
using namespace std;
using pii = pair<int, int>;

constexpr int N = 3e5 + 5, S = 2e3 + 5, K = 1e2 + 5, INF = 0x3f3f3f3f;
int n, m, T, poi[N];
int hed[N], nxt[N << 2], rch[N << 2], val[N << 2], idx;
void link(int u, int v, int w)
{
    nxt[++idx] = hed[u], hed[u] = idx, rch[idx] = v, val[idx] = w;
    nxt[++idx] = hed[v], hed[v] = idx, rch[idx] = u, val[idx] = w;
}

int trs(int i, int j) { return (m + 1) * i + j; }
signed main()
{
    ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
    cin >> n >> m >> T;
    for (int i = 1, w, p; i < n; i++)
        for (int j = 1; j <= m; j++)
            p = trs(i, j - 1), cin >> w, link(p, p + 1, w);
    for (int i = 1, w, p; i <= n; i++)
        for (int j = 1; j < m; j++)
            p = trs(i - 1, j), cin >> w, link(p, p + m + 1, w);
    for (int i = 1; i <= (n + m) << 1; i++)
        if (i <= m)
            poi[i] = trs(0, i - 1);
        else if (i <= m + n)
            poi[i] = trs(i - m - 1, m);
        else if (i <= 2 * m + n)
            poi[i] = trs(n, 2 * m + n + 1 - i);
        else
            poi[i] = trs(2 * m + 2 * n + 1 - i, 0);
    const int ori = idx;

    while (T--)
    {
        for (int i = 0; i < (n + 1) * (m + 1); i++)
            while (hed[i] > ori)
                hed[i] = nxt[hed[i]];
        idx = ori;

        static int col[S], cst[S], k;
        memset(col, -1, sizeof(col)), memset(cst, 0, sizeof(cst)), cin >> k;
        for (int i = 1, w, p, c; i <= k; i++)
            cin >> w >> p >> c, col[p] = c, cst[p] = w;
        for (int i = 1; i <= (n + m) << 1; i++)
            if (i <= m)
                link(poi[i], poi[i] + 1, cst[i]);
            else if (i <= m + n)
                link(poi[i], poi[i] + m + 1, cst[i]);
            else if (i <= 2 * m + n)
                link(poi[i], poi[i] - 1, cst[i]);
            else
                link(poi[i], poi[i] - m - 1, cst[i]);

        vector<vector<int>> outer;
        int fir = 0, lst = 0;
        for (int i = 1; i <= (n + m) << 1; i++)
        {
            if (col[i] == -1)
                continue;
            if (!fir)
                fir = i;
            else if (col[lst] != col[i])
            {
                vector<int> inner;
                for (int j = lst + 1; j <= i; j++)
                    inner.emplace_back(poi[j]);
                outer.emplace_back(inner);
            }
            lst = i;
        }
        if (col[lst] != col[fir])
        {
            vector<int> inner;
            for (int i = lst + 1; i <= (n + m) << 1; i++)
                inner.emplace_back(poi[i]);
            for (int i = 1; i <= fir; i++)
                inner.emplace_back(poi[i]);
            outer.emplace_back(inner);
        }
        if (outer.empty())
        {
            cout << "0\n";
            continue;
        }

        static int w[K][K], f[K][K];
        memset(w, 0x3f, sizeof(w)), memset(f, 0x3f, sizeof(f)), k = outer.size();
        for (int i = 0; i < k; i += 2)
        {
            static int dis[N];
            memset(dis, 0x3f, sizeof(dis));
            priority_queue<pii, vector<pii>, greater<>> q;
            for (int u : outer[i])
                q.emplace(dis[u] = 0, u);
            while (!q.empty())
            {
                int pre = q.top().first, u = q.top().second;
                q.pop();
                if (pre != dis[u]) continue;
                for (int e = hed[u]; e; e = nxt[e])
                {
                    int v = rch[e], cur = pre + val[e];
                    if (dis[v] > cur) q.emplace(dis[v] = cur, v);
                }
            }
            for (int j = 0; j < k; j++)
            {
                for (int u : outer[j])
                    w[i][j] = min(w[i][j], dis[u]);
                w[j][i] = w[i][j];
            }
        }
        for (int i = 0; i < k; i++)
            for (int j = 0; j < k; j++)
                w[i + k][j] = w[i][j + k] = w[i + k][j + k] = w[i][j];
        for (int i = 1; i <= k << 1; i++)
            f[i][i - 1] = 0;
        for (int i = 2; i <= k; i++)
            for (int l = 1; l <= (k << 1) - i + 1; l++)
            {
                int r = l + i - 1;
                f[l][r] = f[l + 1][r - 1] + w[l][r];
                for (int x = l + 1; x < r; x += 2)
                    f[l][r] = min(f[l][r], f[l][x] + f[x + 1][r]);
            }
        int ans = INF;
        for (int i = 0; i < k; i++)
            ans = min(ans, f[i][i + k - 1]);
        cout << ans << '\n';
    }
    return 0;
}

标签:int,题解,hed,++,2021,8.22,cst,col,dis
From: https://www.cnblogs.com/bingxin-ly/p/17649634.html

相关文章

  • P3089 题解
    P3089令\(f_1[i][j]\)表示向右跳,从\(j\)跳到\(i\)的最大总得分,有状态转移方程:\[f_1[i][j]=\displaystyle\max_{k<j<i,x_j-x_k\lex_i-x_j}\{f_1[j][k]+s_i\}\]将\(s_i\)看作定值,整理得\(f_1[i][j]=\displaystyle\max_{k<j<i,x_j-x_k\lex_i-x_j}\{f_1[j][......
  • P2572 序列操作 题解
    link。对平衡树的懒标记的应用题,其实和线段树也差不多。如果不考虑取反操作,那维护操作\(5\)就需要知道当前区间答案,当前区间前缀和后缀,因为在push_up时我们当前区间的答案肯定等于左区间的答案,右区间的答案以及左区间的后缀加上右区间的前缀这三者间的最大值。但与线段树不......
  • AGC032 A-D题解
    A最后一次插入的数的值与位置一定相同考虑倒着做每次从左往右扫一遍当遇到a[i]==i时将此数删除并跳出B当n为5时构造出的图如下(图形编辑器(csacademy.com))那么我们猜想当n为奇数时将n与其他点连边i与除了n-i的其他点连边证明:n的邻接点的编号之和为(n......
  • 8.22练习总结
    模拟3分数:期望100+100+20+20,实际90+90+15+0总体上:思路还是不错的,但是细节地方没有处理到,详情见后面T1/T2/T3/T4的反思。多多少少总是有点毛病。个体上:第一题:连续三个已经想到了,但是我选择了修改最后一个而不是中间。当时贪心的想法是:如果能通过改变最后一个让后面的不合......
  • iOS开发之--获取验证码倒计时及闪烁问题解决方案
    大家在做验证码的时候一般都会用到倒计时,基本上大家实现的方式都差不多,先贴出一些代码来..-(void)startTime{__blockinttimeout=59;//倒计时时间dispatch_queue_tqueue=dispatch_get_global_queue(DISPATCH_QUEUE_PRIORITY_DEFAULT,0);dispatch_source......
  • 国标GB28181视频平台EasyGBS国标平台激活码授权提示“授权失败”的问题解决方案
    EasyGBS平台是基于国标GB28181协议的视频云服务平台,支持多路设备接入,并对多平台、多终端分发出RTSP、RTMP、FLV、HLS、WebRTC等多种格式的视频流。平台可为大数据等综合性监管平台提供极强的视频能力,既能作为能力平台为业务层提供接口调用,也可作为业务平台使用。有用户反馈,现场Easy......
  • 2023.8.22
    有点超模了。签完到跑路。记下做法。T2有字符串\(S\),\(T\),且\(|S|=n\),\(|T|=m\),均由小写字母构成。一个匹配指\(T\)作为子序列在\(S\)中出现,记匹配位置为\(pos_1,pos_2,\dots,pos_m\),该匹配的权值为\(\displaystyle\sum_{i=1}^{m}A_{pos_i}\).每次问\(S[l:r]\)与\(......
  • [CSP-J 2021] 网络连接 题解
    传送门早期题解,转自博客QwQ本蒟蒻为数不多过了的黄题,祝贺!!!题面[CSP-J2021]网络连接题目描述TCP/IP协议是网络通信领域的一项重要协议。今天你的任务,就是尝试利用这个协议,还原一个简化后的网络连接场景。在本问题中,计算机分为两大类:服务机(Server)和客户机(Client)。服务机......
  • 「JLOI2014」松鼠的新家 题解
    「JLOI2014」松鼠的新家前言这道题倒也不是很难,只是有一些小坑需要避一下,可以看作半个LCA树上差分裸题。解析考虑维护一个树,点\(u\)表示每个房间需要的糖果数\(s_u\),而维尼在参观房间时从\(a\)到\(b\)就需要在\((a,\tob)\)的路径上的每个房间都摆上一个糖果,这时直......
  • [ABC098D] Xor Sum 2 题解
    题解传送门题目大意给出一个序列\(A\),求\(A_l\oplusA_{l+1}\oplus\dots\oplusA_r=A_l+A_{l+1}+\dots+A_r\)(\(\oplus\)即为\(xor\)异或)解析众所周知,异或是位运算中的一种不进位加法,即为如果两个\(bit\)相等返回\(0\),反之返回\(1\)。为什么说是不......