完整代码:https://github.com/abmcar/ACM/tree/master/OpenjudgeNow/Codeforces/Codeforces%20Round%20%23765%20(Div.%202)

A. Ancient Civilization

在这里插入图片描述
题目大意:
给你n个二进制下长度小于k的数,让你求一个数,使它和其余数的二进制上的不同的个数最少
思路:
一道不怎么简单的A题,统计所有数每一位的个数,判断某一位的0多还是1多来构造答案
代码:

string intToString(int x)
{
    string ans = "";
    while (x)
    {
        ans = ans + (char)(x % 2 + '0');
        x = x / 2;
    }
    return ans;
}

void work()
{
    cin >> n >> m;
    map<int, int> M;
    for (int i = 1; i <= n; i++)
    {
        int temp;
        cin >> temp;
        string nowString;
        nowString = intToString(temp);
        for (int j = 0; j < nowString.size(); j++)
            if (nowString[j] == '1')
                M[j]++;
    }
    ll nowNum = 0;
    for (int i = 0; i < m; i++)
        if (M[i] * 2 > n)
            nowNum += (1 << i);
    cout << nowNum << endl;
}

B. Elementary Particles

在这里插入图片描述
题目大意:给你一个长度为n的数组,让你求两个最长的子区间使得其中有一位相同
思路:
从相同的位入手,我们发现如果要使得子区间长度最长,那这两个区间应该是尽可能重叠的,也就是说他们再相同的哪一位上是相邻的,比如相同位的数是1,那么这两个1中间没有另一个1,否则我们可以构造出一个更长的子区间,因此,我们记录所有相同的数出现的位置遍历找最长,时间复杂度On
代码:

void work()
{
    cin >> n;
    vector<int> nums(n + 1);
    for (int i = 1; i <= n; i++)
        cin >> nums[i];
    map<int, vector<int>> M;
    for (int i = 1; i <= n; i++)
        M[nums[i]].push_back(i);
    int ans = 0;
    for (auto it : M)
    {
        for (int j = 0; j + 1 < it.second.size(); j++)
        {
            int nowPos = it.second[j] + 1;
            int nextPos = it.second[j + 1] + 1;
            ans = max(ans, min(nowPos, nextPos) + min(n - nowPos, n - nextPos));
        }
    }
    if (ans == 0)
        ans = -1;
    cout << ans << endl;
}

C. Road Optimization

在这里插入图片描述

在这里插入图片描述
题目大意:
给你一段路,路上有n个路牌限速,限速后每公里要花ai分钟,给你这段路的总长度m,以及你可以去掉k个路牌,问最小通过这段路的时间
思路:
简化一下模型,想不想一个取个不去的01背包,只是这个问题里还有当前速度这个因素,有点像那种分层图,
因此我们用dp[i][j][k]表示在第i个路牌已经去掉j个限速时当前速度为k的最小花费时间
i j的范围都是500,而k我们知道虽然可能很大,但实际非常少,因此我们用map来保存
对于每一个状态dp[i][j][k],它可以转移到dp[i+1][j][k],这种情况下不去掉这个路牌
如果当前限速比新路牌小,我们可以选择去掉路牌,转移到dpi+1][j+1][v[i]]
值得注意的是这种写法需要给定一个初值,
而且最后也要判断一下最后的一段距离
代码:

int n, m, k;
vector<int> d, v;
map<int, int> dp[616][616];

signed main()
{
    Buff;
#ifdef Debug
    freopen("temp.in", "r", stdin);
    freopen("temp.out", "w", stdout);
#endif
    cin >> n >> m >> k;
    d.resize(n + 2);
    v.resize(n + 2);
    for (int i = 1; i <= n; i++)
        cin >> d[i];
    for (int i = 1; i <= n; i++)
        cin >> v[i];
    dp[1][0][v[1]] = 0;
    for (int i = 2; i <= n; i++)
    {
        for (int j = 0; j <= k; j++)
        {
            for (auto it : dp[i - 1][j])
            {
                dp[i][j][v[i]] = min(dp[i][j][v[i]], dp[i - 1][j][it.first] + it.first * (d[i] - d[i - 1]));
                if (dp[i][j][v[i]] == 0)
                    dp[i][j][v[i]] = dp[i - 1][j][it.first] + it.first * (d[i] - d[i - 1]);
                if (it.first < v[i])
                {
                    dp[i][j + 1][it.first] = min(dp[i][j + 1][it.first], dp[i - 1][j][it.first] + it.first * (d[i] - d[i - 1]));
                    if (dp[i][j + 1][it.first] == 0)
                        dp[i][j + 1][it.first] = dp[i - 1][j][it.first] + it.first * (d[i] - d[i - 1]);
                }
            }
        }
    }
    int ans = 1e12;
    for (int j = 0; j <= k; j++)
        for (auto it : dp[n][j])
        {
            // cout << j << " " << it.first << " " << it.second << endl;
            ans = min(ans, it.second + it.first * (m - d[n]));
        }
    cout << ans << endl;
    return 0;
}

Q.E.D.