首页 > 其他分享 >CF Round #839 E. Permutation Game

CF Round #839 E. Permutation Game

时间:2023-02-05 11:11:49浏览次数:56  
标签:puts int 839 CF else Game && Longrightarrow Tie

原题链接
洛谷翻译版

博弈论

我们假设A是先手,B是后手
对于两人来说,最优策略就是先把不在正序(or逆序)正确位置的数染上色,乘对方还没有染完,就交换
总共有三种情况:

  1. A需要染,B不需要染 \(\Longrightarrow\) a
  2. B需要染,A不需要染 \(\Longrightarrow\) b
  3. A和B都需要染 \(\Longrightarrow\) c

b \(>=\) a+c,则A赢(A是先手,所以可以取等)
a \(>\) b+c,则B赢
其他情况都是平局

AC代码如下:

#include<bits/stdc++.h>
using namespace std;
#define pii pair<int, int>
#define pdd pair<double, double>
typedef long long ll;
void solve()
{
    int n;
    int a=0, b=0, c=0;
    cin >> n;
    for(int i=1; i<=n; i++)
    {
        int x;
        cin >> x;
        if(x != i && x == n-i+1) a++;
        if(x != n-i+1 && x == i) b++;
        if(x != i && x != n-i+1) c++;
    }
    if(a == b && c!=0) puts("Tie");
    else if(a > b)
    {
        if(a > b+c) puts("Second");
        else puts("Tie");
    }
    else
    {
        if(b >= a+c) puts("First");
        else puts("Tie");
    }
}
int main()
{
    int t;
    cin >> t;
    while (t--)
        solve();
    return 0;
}

标签:puts,int,839,CF,else,Game,&&,Longrightarrow,Tie
From: https://www.cnblogs.com/zhouzhihao/p/17093051.html

相关文章

  • 【CF52B】Right Triangles
    updateon2022.04.26:修改了一处炸掉的格式。一、题意题目给我们一个\(n\timesm\)的字符矩阵,求三个*为顶点且直角边水平或竖直的三角形。二、思路首先想到的显然是......
  • 【CF549G】Happy Line
    首先你直接模拟复杂度上天,不能通过此题。由于有解时最后单调不降,那么我们考虑排序。排什么?找不变量。假设当前\(a_i,a_{i+1}\)需要进行操作。那么结果变成\(a_{i+1}......
  • 2022game总结
    游戏总结-对马岛之魂 9/10-战神410/10-战神5   9/10-地平线2西之绝境   10/10-stray 8/10-银河护卫队 8/10![GhostofTsushima_20220311234141](......
  • CF1270G Subset with Zero Sum
    CF1270GSubsetwithZeroSum-洛谷|计算机科学教育新生态(luogu.com.cn)普通序列抽数,要求和为\(0\),则只能暴力搜索。那突破口肯定是\(i-n\lea_i\lei-1\)......
  • 题解 ARC155D Avoid Coprime Game
    题解ARC155DAvoidCoprimeGame题意给定一个可重集\(S\),保证\(\gcd_{x\inS}(x)=1\),维护一个初始为\(0\)的整数\(G\),双方轮流操作,每次每人选择\(S\)中一个数......
  • 关于长链剖分的数组实现 | CF1009F Dominant Indices
    请容许我不理解一下为什么这题题解几乎全都是指针实现/kk其实长链剖分是可以直接用数组来写的。考虑朴素DP。设\(f_{u,i}\)表示以点\(u\)为根的子树中与点\(u\)距......
  • 论文阅读: CCF A(ICSE) 2022 MVD: 基于流敏感图神经网络的内存相关漏洞检测
    Abstract:内存相关漏洞对现代软件的安全构成了严重威胁。尽管基于深度学习的方法在一般性漏洞检测方面取得了成功,但在应用于内存相关漏洞检测时,仍然受到流信息利用不......
  • 每日一道思维题——CF1691C - Sum of Substrings
    题意:给定一个长度为n的字符串算由SiSi+1构成的子字符串值如00为0,01为1,10为10,11为11F(s)为所有值之和求出此值的最小值思路:优先将1放到最后,其次将1放在开头其余的位置......
  • CF765F Souvenirs 题解
    Preface在会压位Trie的前提下,本题最好想的做法应该是压位Trie+回滚莫队,可是竟然没人写这个做法的题解?Solution我们先转化题意:设\(a_i\)在\([l,r]\)中的前驱后继......
  • python AES CFB 记录
    aescipher=AES.new(aeskey,AES.MODE_CFB,aesiv,segment_size=128)segment_size(integer)--(OnlyMODE_CFB).Thenumberofbitstheplaintextandciphertextarese......