首页 > 其他分享 >CF Round 814 Div2 题解

CF Round 814 Div2 题解

时间:2022-08-17 20:44:39浏览次数:79  
标签:10 Burenka int 题解 队头 CF leq 814 dp

A题 Chip Game(签到)

给定一个 \(n\) 行 \(m\) 列的方格矩阵,左下角是 \((1,1)\),右上角是 \((m,n)\)。(采取了类似笛卡尔坐标系的表示法,不是普通的 \(x\) 行 \(y\) 列)

Burenka 和 Tonya 轮番在矩阵上进行游戏,Burenka 先手。初始状态下,在起点 \((1,1)\) 处有一个棋子,轮到某个人时,它可以选择将棋子向上或者向右移动奇数格(但是不可以超出边界),无法移动者判负(也就是先到达右上角终点者胜利)。

试求出在采取最优策略的情况下,获胜者会是谁。

\(T\leq 10^4,1\leq n,m\leq 10^9\)

如果 \(m\) 是偶数,\(n\) 是奇数,那么 Burenka 先手必胜:他只要直接走到 \((m,1)\) 处,然后 Tonya 就尴尬了:因为 \(n\) 是奇数,所以他不可能一步走到 \((m,n)\),只能走到 \((m,y)\) 处(\(y<n\) 且 \(y\) 是偶数),那么 Burenka 就再向上走 \(n-y\) 步即可。\(m\) 奇 \(n\) 偶时候同理(由对称性可得)。

如果 \(m,n\) 奇偶性相同,那么 Burenka 不可能一部走到终点,而其走完一部之后,必然使得对方进入了奇偶不同的状态(即先手必胜态),故 Burenka 先手必败。(采取了 SG 博弈的思想,虽然出题人可能只是想让我们模拟一下)。

综上,得到结论:\(n,m\) 奇偶性相同时先手必败,否则先手必胜。

#include<bits/stdc++.h>
using namespace std;
int main()
{
    int T;
    cin >> T;
    while (T--) {
        int n, m;
        cin >> n >> m;
        puts((n + m) % 2 ? "Burenka" : "Tonya");
    }
    return 0;
}

B题 Mathematical Circus(数学)

给定 \(n\) 个整数 \((1,2,\cdots,n)\)(保证 \(n\) 是偶数)和整数 \(k\),问我们能否将这些整数分成 \(\frac{n}{2}\) 对,每一对都类似 \((a,b)\),并使得 \((a+k)b\) 是 4 的倍数?

\(T\leq 10^4,n,\sum n\leq 2*10^5,0\leq k\leq 10^9\)

我们直接让 \(k\) 对 4 先取一下模,方便后面分类讨论。

如果 \(k=1,3\),那就让 \(a\) 是奇数,\(b\) 是偶数就行了,类似 \((1,2),(3,4),\cdots,(n-1,n)\) 这样就行(观察样例也能看出来)。

如果 \(k=2\),也就是让 \((a+2)b\) 是 4 的倍数,我们将 \([1,n]\) 内整数也按照对 4 的取模值划分,分成 \((1,2,3,0)\) 四类,那么我们发现(也可以通过观察样例得到),可以构造 \((3,0)\) 和 \((2,1)\) 这两种配对,使得 \(a+2,b\) 里面至少有一个是 4 的倍数。

\(k=0\) 时,也就是让 \(ab\) 是 4 的倍数,因为至少有一半奇数,不可能让两个奇数进一个组,所以每个组都得有一个奇数(就让他们是 \(a\))吧,那么就得要求 \(b\)(也就是剩下的每一个偶数)都是 4 的倍数,显然不可能。

#include<bits/stdc++.h>
using namespace std;
void solve()
{
    int n, k;
    cin >> n >> k, k %= 4;
    if (k == 0) {
        puts("NO");
        return;
    }
    puts("YES");
    if (k == 2) {
        for (int i = 1; i <= n; i += 2) {
            if (i % 4 == 1) printf("%d %d\n", i + 1, i);
            else printf("%d %d\n", i, i + 1);
        }
    }
    else {
        for (int i = 1; i <= n; i += 2)
            printf("%d %d\n", i, i + 1);
    }
}

int main()
{
    int T;
    cin >> T;
    while (T--) solve();
    return 0;
}

C题 Fighting Tournament(模拟优化)

给定一个长度为 \(n\) 的排列 \(\{a_n\}\),初始状态下,将该排列按照下标顺序放入一个队列中。

接着,进行无穷次操作,每次操作都会取出队头两个元素并进行“战斗”,胜者还放在队头,反之放入队尾(显然,两个元素相互“战斗”,肯定是大的那个赢)。

接下来有 \(q\) 次询问,每次询问给定 \(i,k\),问 \(a_i\) 这个数在 \(k\) 轮操作后,一共胜了多少局?

\(2\leq n\leq 10^5,1\leq q\leq 10^5,1\leq a_i\leq n,1\leq i \leq n,1\leq k\leq 10^9\),多组数据不影响数据范围

手玩几组样例后,发现:当最大的那个元素 \(n\) 到达队头时,后面的每一个操作都是它赢(没有人比它大,所以就一直呆在队头)。类似的,我们发现:如果原序列中 \(x\) 前面有比 \(x\) 大的,那么 \(x\) 的赢的次数就一定为 0(等 \(x\) 到队头的时候,前面那个数比它大,\(x\) 去队尾,然后发现队头直接变成 \(n\) 了);相反,如果 \(x\) 前面的数都小于 \(x\),那么直接看看后面 \(x\) 还能赢多少次,输了后放到队尾,下一次也就碰到 \(n\) 而赢不了了。

那么,我们分类讨论,得到结果:

  1. \(a_i=n\),判断 \(n\) 还要几轮到队头,之后就一直赢

  2. \(\exist j<i,a_j>a_i\),那么赢的次数就是 0

  3. \(\max\limits_{1\leq j\leq i}a_j=a_i\),判断 \(a_i\) 还要几轮到队头,然后赢一局(如果 \(i=1\) 就跳过这个赢的一局),随后看后面还有连续多少数是小于 \(a_i\) 的。这东西可以二分或者线段树或者啥的,但是作为 Div2C,我们还是用一些相对简单的方法:构造前缀最大值 \(s_i=\max\limits_{1\leq j\leq i}a_i\),那么对于 \(a_i\),找出最大的 \(d\),使得 \(s_d=a_i\) 即可,而这可以用另外一个方式代替:

    for (int i = 1; i <= n; ++i)
        farPos[s[i]] = i;
    

    那么 d=farPos[a[i]]。(也就是针对记录一下每个数的最右端点)

#include<bits/stdc++.h>
using namespace std;
const int N = 100010;
int n, q, a[N], s[N], pos[N];
void solve()
{
    cin >> n >> q;
    for (int i = 1; i <= n; ++i) {
        cin >> a[i];
        s[i] = max(s[i - 1], a[i]);
        pos[s[i]] = i;
    }
    while (q--) {
        int i, k, ans;
        cin >> i >> k;
        if (s[i] > a[i]) ans = 0;
        else if (a[i] == n) {
            int d = max(i - 2, 0);
            ans = max(k - d, 0);
        }
        else {
            int d = max(i - 2, 0);
            if (k <= d) ans = 0;
            else ans = min(k - d, pos[a[i]] - i + (i > 1));
        }
        cout << ans << endl;
    }
}
int main() {
    int T;
    cin >> T;
    while (T--) solve();
    return 0;
}

D1题 Burenka and Traditions (easy version)(贪心,DP)

给定一个长度为 \(n\) 的序列 \(\{a_i\}\)。

现在,你可以执行若干次操作,每次操作都自行指定 \(l,r,x\),然后消耗 \(\lceil\frac{r-l+1}{2}\rceil\) 的能量,来将区间 \([l,r]\) 内所有元素都和 \(x\) 异或一下。

问,至少需要多少能量,才能将所有元素变为 0?

\(1\leq n,\sum n\leq 5*10^3,0\leq n\leq 5*10^3\)

发现了一个贪心的性质:反正操作需要消耗的能量和区间长度相关,那么我们只进行长度为 1 或者 2 的操作即可(大区间操作不如拆成若干个小区间,还更灵活),这使得序列操作整体上变得有序了(从前往后即可,不会出现明显的无序性)。

我们考虑 \(dp_i\) 为将前 \(i\) 个数全部变成 0 所花的能量,但是这显然不够,因为有时候我们对 \(i\) 进行操作时候,需要 \(a_{i-1}\) 是其他的数(这点可以看样例)。那么,我们加上一个维度 \(j\),用 \(dp_{i,j}\) 表示将前 \(i-1\) 个数变为 0,最后一个数变为 \(j\) 的所需代价。

那么,只进行长度为 1 的区间操作,有 \(dp_{i,j}=dp_{i-1,0}+(a_i\not=j)\),进行长度为 2 的区间操作,则有 \(dp_{i,j\oplus x}=dp_{i-1,j}+1\)。处理一下边界条件后跑一次线性 DP 即可,最后答案就是 \(dp_{n,0}\)。

注意一下,\(j\) 的范围是 \([0,8191]\),因为要考虑一下异或后会大于 \(n\) 的状态。

#include<bits/stdc++.h>
using namespace std;
const int N = 5010;
int n, a[N];
int dp[N][8192];
int solve()
{
    //read
    cin >> n;
    for (int i = 1; i <= n; ++i)
        cin >> a[i];
    //solve
    for (int i = 0; i < 8192; ++i)
        dp[1][i] = 1;
    dp[1][a[1]] = 0;
    for (int i = 2; i <= n; ++i) {
        //do opt len 1
        for (int j = 0; j < 8192; ++j)
            dp[i][j] = dp[i - 1][0] + (a[i] != j);
        //do opt len 2
        for (int j = 0; j < 8192; ++j)
            dp[i][a[i] ^ j] = min(dp[i][a[i] ^ j], dp[i - 1][j] + 1);
    }
    return dp[n][0];
}
int main() {
    int T;
    cin >> T;
    while (T--) cout << solve() << endl;
    return 0;
}

标签:10,Burenka,int,题解,队头,CF,leq,814,dp
From: https://www.cnblogs.com/cyhforlight/p/16596670.html

相关文章

  • CF 做题记录
    CF1360DBuyingShovels*1300link:Problem-1360D-CodeforcesAC:Submission#167227323-CodeforcesCF1338A PoweredAddition*1500link:Problem-1338A-Codefo......
  • CF578C题解
    看到题面的第一眼是这玩意儿关于x是单谷的,证明稍微想了一下:设\(f[k]\)和\(g[k]\)是原序列中长度为\(k\)的子区间的最大子区间和最小子区间,给定\(x\)时答案就相......
  • CF145C Lucky Subsequence
    题目链接:洛谷CodeforcesProblem这题目翻译真的神了,好多歧义,看不懂,给一个本人翻译:给你一个长度为\(n\)的序列\(a\),定义幸运数为仅含有\(4\)或\(7\)的数,你需要取......
  • CF1719C Fighting Tournament 题解
    思路根据题意,很容易看出,每个人都完成一次比赛后,即完成\(n-1\)轮之后,力量值最大的人会留在第一的位置,且在第\(n-1\)轮完成后,除了力量值最大的人,其他人的胜场数都不会再......
  • CF1719A Chip Game 题解
    题目传送门。思路当其中一个人不能动的时候,这个人一定位于点\((n,m)\)上。令点\((n,m)\)为终点。当\(n\)和\(m\)都是奇数或当\(n\)和\(m\)都是偶数时,赢的人......
  • CF1719B Mathematical Circus 题解
    一道不错的构造题。思路先说一句废话,能被\(4\)整除的数在除以\(2\)之后得到的数还是一个偶数。我们可以根据\(k\)的奇偶性以及\(k\)除以\(2\)之后的奇偶性分......
  • Codeforces Round #814 (Div. 2)
    A.ChipGame题目描述BurenkaandTonyaareplayinganoldBuryatgamewithachiponaboardofn\timesmcells.Atthebeginningofthegame,thechipisl......
  • BSOJ7020题解
    脑抽了。考场上应该做掉这题的。所以实际挂分从100pts变成了200pts/fn/fn/fn考虑用一个二元组来维护链,\((f,g)\)表示这个集合的所有链的点权和为\(f\),有\(g\)条链,目......
  • CF1719B Mathematical Circus
     题意简述:对于给定的$n,k$,能否将$1,2,3,...,n$($n$为偶数),两两分组.求对于每个分组($x_i$,$y_i$),是否全部满足$4\mid(x_i+k)*y_i$,如果分组全部......
  • CF1368B
    题目简化和分析:因为要求长度最小,所以我们每个字符就应该发挥最大的价值,不会有没有作用的字符。设有\(x_1\)个\(c\),\(x_2\)个\(o\),\(x_3\)个\(d\),\(x_4\)个\(......