第二届“传智杯”全国大学生IT技能大赛（决赛）

七海

题解

发布于：2020年4月18日

次浏览

按照惯例还是先挂出来一些链接。

比赛地址：https://www.luogu.com.cn/contest/29004

官方题解：https://www.zhihu.com/question/388180965/answer/1163540927

但是已经不能在上面的比赛链接里上交题目了，所有的题目已经加入公共题库了，所以你可以搜索题目的名字然后在公共题库中找到它们；好像直接点进去就会自动切到公共题库，还行。

两个黄题没有做出来，这不太行啊。

A - 暴力模拟

暴力模拟，语言题。但是数据范围给的有些歧义。

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

using namespace std;
using longs = long long;
using longd = long double;
using ulongs = unsigned long long;

const int inf = 0x3f3f3f3f;
const longs INF = 0x3f3f3f3f3f3f3f3f;
const double eps = 1e-8;

const char graph[100][100] =
        {
                R"(...........................,]]OOO@@@@OOO]`........)",
                R"(....................,]OO@@@@@@@@@@@@@@@@@@@@O`....)",
                R"(................./O@@@@@@@@@@@@@@@@@@@@@@@@@@@@^..)",
                R"(............../O@@@@@@@@@@@@@@@OOOOOOO@@@@@@@@@@@.)",
                R"(..........,/@@@@@@@@@@@@O/[.............[O@@@@@@@\)",
                R"(........,O@@@@@@@@@@O/`..................,O@@@@@@O)",
                R"(.......O@@@@@@@@@O`......]OO@@@O\`........O@@@@@@@)",
                R"(.....,O@@@@@@@@/`.....]O@@@@@@@@@@^.......O@@@@@@@)",
                R"(...,/@@@@@@@O/...../@@@@@@@@@@@@@@O....../@@@@@@@0)",
                R"(..=@@@@@@@O`...../@@@@@@@@@@@@@@@@^.....O@@@@@@@O.)",
                R"(./@@@@@@@/......O@@@@@@@@@@@@@@@O`..../@@@@@@@@O..)",
                R"(=@@@@@@@O......O@@@@@@@@@@@@@@@^....O@@@@@@@@@O...)",
                R"(O@@@@@@@^.....=@@@@@@@@@@@@@O[..../@@@@@@@@@O`....)",
                R"(@@@@@@@O.......\@@@@@@@@O[...../O@@@@@@@@@O`......)",
                R"(@@@@@@@@^.........[`.......]OO@@@@@@@@@@O`........)",
                R"(O@@@@@@@@O\............]/@@@@@@@@@@@@O/...........)",
                R"(=@@@@@@@OOOoo`........O@@@@@@@@@@@@/`.............)",
                R"(..\OOOOO*,`*..........O@@@@@@@@@O`................)",
                R"(.....,[[..............O@@@@@@O`...................)",
                R"(......................O@@@@@@O....................)"
        };

char campus[2060][2060];

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, h, w;
    int x, y, r;

    auto initfill = [&]
    {
        for (int i = 0; i < h; ++ i)
        {
            for (int j = 0; j < w; ++ j)
                campus[i][j] = '.';
            campus[i][w] = '\0';
        }
    };

    auto paint = [&](int x, int y)
    {
        for (int i = x, ii = 0; i < h; ++ i, ++ ii)
        {
            if (ii >= 20) break;
            if (i < 0) continue;
            for (int j = y, jj = 0; j < w; ++ j, ++ jj)
            {
                if (jj >= 50) break;
                if (graph[ii][jj] == '.') continue;
                if (j < 0) continue;
                campus[i][j] = graph[ii][jj];
            }
        }
    };

    auto paint180 = [&](int x, int y)
    {
        for (int i = x, ii = 19; i < h; ++ i, -- ii)
        {
            if (ii < 0) break;
            if (i < 0) continue;
            for (int j = y, jj = 49; j < w; ++ j, -- jj)
            {
                if (jj < 0) break;
                if (graph[ii][jj] == '.') continue;
                if (j < 0) continue;
                campus[i][j] = graph[ii][jj];
            }
        }
    };

    cin >> n >> h >> w;
    initfill();
    while (n --)
    {
        cin >> x >> y >> r;
        if (r) paint180(x,y);
        else paint(x,y);
    }

    for (int i = 0; i < h; ++ i)
        cout << campus[i] << endl;

    return 0;
}

或者说是贴标赞助题好一些？

B - 屑游戏

脑筋急转弯。考虑为0的边界情况之后，防御塔留一手给英雄，要是能鲨咯那就完事。

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

using namespace std;
using longs = long long;
using longd = long double;
using ulongs = unsigned long long;

const int inf = 0x3f3f3f3f;
const longs INF = 0x3f3f3f3f3f3f3f3f;
const double eps = 1e-8;

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int t; cin >> t;
    longs h, x, y;
    while (t --)
    {
        cin >> h >> x >> y;
        if (!y) {cout << "No" << endl; continue;}
        else if (!x) {cout << "Yes" << endl; continue;}
        longs tt = h / x + 1;
        longs mm = h % x;
        if (!mm) mm += x, -- tt;
        if (mm / y + bool(mm % y) <= tt) cout << "Yes" << endl;
        else cout << "No" << endl;
    }

    return 0;
}

记得开long long。

C - 加大范围

比赛时候的数据只要暴力模拟就行了，但是需要使用更优的算法：最优的算法是O(n³)的

朴素的想法：枚举重心的高度和所在坐标，然后判断每个位置是否可行，这是跑不满的五次方算法；如果把遍历获得所需操作数的行为使用二维前缀和/差分优化的话就可以压到四次方；如果使用二维RMQ问题的解决方法，判断一个方形区域是否都大于某个值，就可以压到最优复杂度。

D - 迫真最短路

又是一个暴力。传送门问题往往是先最短路，然后枚举传送门的位置。这个题目只不过就是题面有些吓人，但是数据范围是小的可怜的100，就算是四次方算法也是可以接受的（

因为要求出所有的最短路之和，所以要用Floyd；然后再加上暴力枚举传送门位置，暴力枚举求出题目说的和，维护它的最小值即可。

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

using namespace std;
using longs = long long;
using longd = long double;
using ulongs = unsigned long long;

const int inf = 0x3f3f3f3f;
const longs INF = 0x3f3f3f3f3f3f3f3f;
const double eps = 1e-8;

longs dis[105][105], ans = INF;
int n, m;

inline void floyd()
{
    for (int k = 1; k <= n; ++ k)       // Floyd：中转点要写在外面
        for (int i = 1; i <= n; ++ i)
            for (int j = 1; j <= n; ++ j)
                dis[i][j] = min(dis[i][j], dis[i][k] + dis[k][j]);
}

longs sum(int ii, int jj)
{
    longs tmp = 0;
    for (int i = 1; i <= n; ++ i)
        for (int j = i+1; j <= n; ++ j)
            tmp += min(
                dis[i][j], 
                min(
                    dis[i][ii] + dis[jj][j],
                    dis[i][jj] + dis[ii][j]
                ));
    return tmp;        
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n >> m;
    memset(dis, 0x3f, sizeof dis);
    while (m --)
    {
        int u, v, w;
        cin >> u >> v >> w;
        dis[u][v] = dis[v][u] = w;
    }
    for (int i = 1; i <= n; ++ i)
        dis[i][i] = 0;
    floyd(); 
    for (int i = 1; i <= n; ++ i)
        for (int j = i+1; j <= n; ++ j)
        {
            longs tmp = sum(i, j);
            ans = min(tmp, ans);
        }
    cout << ans << endl;

    return 0;
}

Floyd算法三重循环的中转点在最外层！

E - 上课

本　次　比　赛　唯　一　的　一　个　绿　题

做法很多。我是找到所有连续的课程作为断点，然后对于每个连续的区间扫描一遍，记录扫描过的区域不同课出现的次数，然后加算贡献的。有点像是在乱搞，复杂度O(n)。

事实上这个题还可以DP，也可以莫队（？），还可以反向思维：也就是先算出所有大于l的点对，在用双指针法减掉各种不太行的情况，时间复杂度都是O(n)的。

贴的代码不是DP的，是比赛时乱搞的版本。

#include <iostream>
#include <vector>
#include <map>
#include <cstring>
#include <algorithm>

using namespace std;
using longs = long long;
using longd = long double;
using ulongs = unsigned long long;

const int inf = 0x3f3f3f3f;
const longs INF = 0x3f3f3f3f3f3f3f3f;
const double eps = 1e-8;

const int N = 5e5+5;
int n, l, a[N], c[N];
vector<pair<int,int>> vv;
map<int,int> mm;

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int t; cin >> t;

    auto jump = [&]
    {
        int s = 1, t = 0;
        for (int i = 1; i < n; ++ i)
        {
            if (c[i] != c[i+1])
            {
                a[i] = i+1;
                t = i;
            }
            else
            {
                if (s != t) vv.emplace_back(s, i);
                int j = i+1;
                while (c[++ j] == c[i]);
                for (int k = i; k < j; ++ k)
                    a[k] = j;
                i = j - 1; s = t = j - 1;
            }
        }
        if (s != n) vv.emplace_back(s, n);
        a[n] = 0;
    };

    while (t --)
    {
        vv.clear();
        cin >> n >> l;
        for (int i = 1; i <= n; ++ i)
            cin >> c[i];
        if (n == 1 || n < l) cout << 0 << endl;
        else
        {
            jump();
            longs ans = 0;
            for (auto ii : vv)
            {
                if (ii.second - ii.first + 1 < l) continue;
                int lim = ii.second - l + 1, noko = 0;
                for (int xx = ii.first + l - 1; xx <= ii.second; ++ xx)
                {
                    ++ mm[c[xx]];
                    ++ noko;
                }
                for (int xx = ii.first; xx <= lim; ++ xx)
                {
                    ans += noko - mm[c[xx]];
                    -- noko;
                    -- mm[c[xx + l - 1]];
                }
                mm.clear();
            }
            cout << ans << endl;
        }
    }

    return 0;
}

然后就是DP版本：

写了半天，我紫菜（

后记

kkksc03：什么嘛，我的洛谷比赛系统还挺好用的嘛。

但是非专业性质的比赛打成这样，属实不太行。引人深思。

更新于：2020年4月18日

算法

ACM

Luogu

“Shopee杯” e起来编程暨武汉大学2020年大学生程序设计大赛（决赛）题解

“科大讯飞杯”第18届上海大学程序设计联赛春季赛暨高校网络友谊赛

科大讯飞冠名的上海大学校赛网络赛。一共五个小时，十二个题目。前六个题是简单题，后六个题是麻烦一点的题目；本来还想着能不能挑战一下A七个，然后……然后我就签到完六个题目光荣下岗（ A2B28BE...