首页 > 其他分享 >Codeforces Round #839 (Div. 3)题解

Codeforces Round #839 (Div. 3)题解

时间:2023-01-05 12:13:18浏览次数:47  
标签:le int 题解 839 矩阵 数组 染色 Div 拷贝

C. Different Differences(贪心)

题意

​ 给定 \(k\), \(n\) \((2 \le k \le n \le 40)\)。从\([1 - n]\)中不重复地任选\(k\)个数组成一个数组,使这个数组的差分数组中不同的数最多。

思路

​ 易知最佳的数组应该是这样的:1 2 4 7 11 16 22 29 37。我们可以得到第一个小于等于 \(n\) 且出现在上面数组中的数字,然后先组成一个最优的数组,设长度为 \(m\) ,剩下的\(k - m\)个数,就从 \(n\) 开始,向下选没出现过的补进去。为什么是从最大开始?假设现在从大开始填,28 - 37之间可以填8个数,使不同的数减少了1;从小到大填8个数,不同的数减少了远大于1。

代码

int n, k;
int a[10] = {1, 2, 4, 7, 11, 16, 22, 29, 37, 46};

void solve()
{
    cin >> k >> n;
    vector<int> vis(41, 0); // 呃呃一开始开的40wa了
    if (n == k)
    {
        for (int i = 1; i <= n; i++)
            cout << i << ' ';
        cout << '\n';
    }
    else // k < n
    {
        int v = 1;
        for (int i = 0;; i++)
        {
            if (a[i] > n || i + 1 > k)
            {
                v = i - 1;
                break;
            }
        }

        set<int> s;
        for (int i = 0; i <= v; i++)
            s.insert(a[i]), vis[a[i]] = 1;
        for (int i = n; i && (int)s.size() < k; i--)
        {
            if (vis[i])
                continue;
            s.insert(i);
        }

        for (auto x : s)
            cout << x << ' ';
        cout << '\n';
    }
}


D. Absolute Sorting(分类讨论)

题意

​ 给你一个由非0正整数组成的数组 \(a\) ,你可以选择一个数 \(v\) \((0 \le x \le 10^9)\) ,将 \(a_i\)改为\(|a_i \ - \ v|\)。

​ 是否存在这样的一个 \(v\) , 使更改后的数组 \(a\) 变为不降序列。请输出 \(v\) 。

思路

​ 对于相邻的两个数,我们对其进行分类讨论。设两个数为 \(x = a_i, \ y = a_{i+1}\)。

  • 当 \(x < y\) 时,由公式 \(-(x-v) \le (y-v)\) 得 \(v\) 的上界取值范围为 \((x + y) / 2\),下界为 0。
  • 当 \(x > y\) 时,由公式 \((x-v) \le -(y-v)\) 得 \(v\) 的下界取值范围为 \((x + y + 1) / 2\),上界为1e9。

​ 那么只要对每一对相邻的数的上下界,一起取一个交集,那就可以得解。

代码

void solve()
{
    int n;
    cin >> n;
    vector<int> a(n + 1);
    for (int i = 1; i <= n; i++)
        cin >> a[i];

    int l = 0, r = 1e9;
    for (int i = 2; i <= n; i++)
    {
        int x = a[i - 1], y = a[i];
        if (x == y)
            continue;
        if (x < y)
            r = min(r, (x + y) / 2);
        else
            l = max(l, (x + y + 1) / 2);
    }
    if (l > r)
        cout << "-1\n";
    else
        cout << l << '\n';
}


E. Permutation Game(博弈)

题意

​ 给定长度为 \(n\) 的排列,现在两个人对这个数组进行游戏。每位玩家每轮可以进行以下三种操作:

  • 可以重新排列所有蓝色下标上的数字。
  • 将一个红色下标染成蓝色下标。
  • 跳过回合。

​ \(A\) 先手, \(B\) 后手。当且仅当 \(A\) 可以通过重新排列得到一个上升排列或者 \(B\) 可以通过重新排列得到一个下降排列游戏结束,率先完成这一步的玩家胜,若经过极多的回合数都没有决出胜负,那么就是平局。请根据给定的排序,输出最后赢家或是平局。

思路

​ 首先我们可以发现有一个很奇怪的话。

​ If the game lasts for \(100^{500}\) turns and nobody wins, it ends in a draw.

​ 简单一想,可以想到是因为当前局面达到了一个平衡(雾),也就是说两个人无论是谁染色后都会变成必败态。接下来继续想染色,对于一个人来说,若序列中原本就有一些是位置与最终局面相对应的,那么这就是不需要染色的;反之,对于另一个人来说,这些位置是必须要染色的,且优先级更高。那么我们就可以统计一下,两个人需要染色的位置的数量,还有一些位置是与两边都没有利害关系的,但是想要达到最终局面也必须被染色的,这部分的位置是优先级较低的(因为你也不想为对面做嫁衣罢)。

​ 那么这样问题就被转化了判断以下三种情况:\(A\) 是否能在 \(B\) 染完之前染完,\(B\) 是否能在 \(A\) 染完之前染完,\(A\) 和 \(B\) 陷入平衡局面。

代码

void solve()
{
    int n, cnt1 = 0, cnt2 = 0, cnt3 = 0;
    cin >> n;
    vector<int> a(n + 1);
    for (int i = 1; i <= n; i++)
    {
        cin >> a[i];
        if (i == a[i])
            cnt1++;
        else if ((n - i + 1) == a[i])
            cnt2++;
        else
            cnt3++;
    }

    if (cnt2 + cnt3 <= cnt1)
        cout << "First\n";
    else if (cnt1 + cnt3 < cnt2)
        cout << "Second\n";
    else
        cout << "Tie\n";
}


F. Copy of a Copy of a Copy(排序,实现)

题意

​ 一开始有一个 \(n \times m\) 的01矩阵,对于这个矩阵,你可以对其进行两个操作:

  1. 拷贝,形成一个拷贝副本。
  2. 在矩阵中选择任一一个不在边界上且其上下左右的值都与其值不同的点,将其值反转。

​ 现在给出 \(k + 1\) 个拷贝版本,请找到初始矩阵,且还原这个操作序列的顺序,将其输出(保证合法即可)。

思路

​ 在做的时候,压根没看懂题,以为是个什么恶心模拟跑了,结果不是。看了题解发现是因为没看懂这个拷贝的意思。其实应该把这个拷贝,看作一次保存,给出你所有保存过的版本,然后还原操作序列。关于这个操作序列,他的顺序自然只和拷贝之外的另一个操作有关系。对矩阵进行操作2的话,这个矩阵中不在边界上且其上下左右的值都与其值不同的点就会减少一个,那么我们就数一下每个版本里的不在边界上且其上下左右的值都与其值不同的点的个数,对其从大到小排序,就可以找到初始矩阵,然后模拟这个操作2的过程,一步一步把操作序列推出来。

代码

int n, m, k;
struct Mat
{
    char g[35][35];
    int id, cnt;
} A[105];
int d[4][2] = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};

int main()
{
    cin >> n >> m >> k;
    for (int o = 1; o <= k + 1; o++)
    {
        auto &M = A[o];
        M.id = o;
        for (int i = 1; i <= n; i++)
            for (int j = 1; j <= m; j++)
                cin >> M.g[i][j];

        for (int i = 2; i <= n - 1; i++)
            for (int j = 2; j <= m - 1; j++)
            {
                int cnt = 0;
                for (int p = 0; p < 4; p++)
                {
                    int x = i + d[p][0], y = j + d[p][1];
                    cnt += (M.g[x][y] != M.g[i][j]);
                }
                if (cnt == 4)
                    M.cnt++;
            }
    }

    sort(A + 1, A + k + 2, [&](Mat a, Mat b)
         { return a.cnt > b.cnt; });

    vector<pair<int, int>> ans;
    for (int o = 2; o <= k + 1; o++)
    {
        const auto &M1 = A[o - 1], M2 = A[o];
        for (int i = 2; i <= n - 1; i++)
            for (int j = 2; j <= m - 1; j++)
                if (M1.g[i][j] != M2.g[i][j])
                    ans.push_back({i, j});
        ans.push_back({M2.id, -1});
    }

    cout << A[1].id << '\n';
    cout << ans.size() << '\n';
    for (auto [x, y] : ans)
    {
        if (y == -1)
            cout << 2 << ' ' << x << '\n';
        else
            cout << 1 << ' ' << x << ' ' << y << '\n';
    }
}


G. Gaining Rating

数学题,补不动。交给队友爹。

标签:le,int,题解,839,矩阵,数组,染色,Div,拷贝
From: https://www.cnblogs.com/DM11/p/17027158.html

相关文章

  • 【题解】CF700E Cool Slogans
    原题面很简洁,懒得概括了。思路后缀自动机+结论。这种题出题人没有十年脑血栓都没法出。结论1:\(s_{i-1}\)必定是\(s_i\)的后缀。考虑\(s_i\)中\(s_{i-1......
  • 【题解】CF1073G Yet Another LCP Problem
    题面很清楚,不概括了。思路后缀树+树剖。套路题。看到lcp考虑转化成后缀树上求lca,这里可以用SAM构造反串的parenttree解撅(f**kuukk)于是问题转化成:每次给......
  • 【题解】CF808E Selling Souvenirs
    题意多重背包,但数据范围很大并且体积小于等于三。思路乱搞。很自然地考虑将物品按照体积分成三类。显然对于同一类的物品从最大开始取最优,那么有一个贪心的想法。直......
  • 【题解】P5305 [GXOI/GZOI2019]旧词
    题面很清楚,不概括题意了。思路树剖。\(k=1\)的情况是P4211[LNOI2014]LCA具体来说,只需要\(\forall1\leqi\leqx\),将\(1\)到\(i\)的路径上每一个结点权值......
  • 题解 校内考20230104 T2 旗木双翼
    题目描述菲菲和牛牛在一块\(n\)行\(m\)列的棋盘上下棋,菲菲执黑棋先手,牛牛执白棋后手。棋局开始时,棋盘上没有任何棋子,两人轮流在格子上落子,直到填满棋盘时结束。落子......
  • LOJ 数列分块入门 9 题解题报告
    LOJ数列分块入门9题解题报告\(\text{ByDaiRuiChen007}\)I.数列分块入门1题目大意\(\text{Link}\)维护一个长度为\(n\)的序列,支持区间加,单点查值思路分析简......
  • IntelliJ IDEA常见问题解决办法汇总
     mac上idea升级到2020.2.2后,发现versioncontrol中的localchanges不见了!解决办法:View—>ToolWIndows—>Commit【点击下,就会提示要把这个Commit放在IDEA面板那个位置,选择......
  • git 不区分大小写问题解决
    使用vscode   更改vue文件为大驼峰的方式 发现本地代码和提交时的代码名称不同是因为git不区分大小写这时我们需要找到代码存放位置 鼠标右键  GitBashHer......
  • 1.4 vp Codeforces Round #838 (Div. 2)
    A-DivideandConquer题意:给出序列a,设b为a中元素总和。你可以选择a中任意元素,将它除以二(向下取整)。问最少需要多少次可以使b为偶数思路:将a划分为奇偶两个集合。a中偶数......
  • 异地多活回环同步问题解决方案
    1.异地多活:一般为两地三中心或者三地五中心,这样设计是为了在发生单点故障或网络分区时,集群能继续提供服务。两地三中心可以容忍机房级别灾难,三地五中心可以容忍城市级别灾......