首页 > 其他分享 >Painting Game (博弈论)

Painting Game (博弈论)

时间:2022-09-02 15:22:07浏览次数:72  
标签:后面 博弈论 填黑 人要 Game Painting

题目:  Virtual Judge (vjudge.net)

题目大意: 2个人轮流对长条方格填黑, 黑的地方不能够相邻. 一个人要尽量填黑,一个人要尽量不填黑, 当不能填的时候就结束

题解思路:

  • 博弈题 为了达到各自的目的,进行贪心操作,
  • 对于填少的人就直接 在 当前黑块的后面2块进行填,就可以了
  • 对于填多的人,很容易就想到直接在他的后面空一格填一个黑色的, 但是这个不是最优的
  • 而是在后面第4个填黑,这样就可以保证 5格里面 有3个都是黑色的

反思: 

  • 这种最优的步骤不是那么容易好想,可以用暴力来看看能不能有更优的解

 

标签:后面,博弈论,填黑,人要,Game,Painting
From: https://www.cnblogs.com/Lamboofhome/p/16650056.html

相关文章

  • CF1720E. Misha and Paintings
    题意给出n*n的矩阵,ai,j∈[1,n*n],现在要矩形覆盖若干次,每次把一个正方形的ai,j改为x,求最少的次数使得最后有k种不同的数n<=500题解设sum为初始不同的数,若sum<k则显然只......
  • 题解 UVA1343 The Rotation Game
    题解区都是\(\text{IDA*}\),实际上这题\(\text{A*}\)也可以,代码也很简单。Solution首先由于整个棋盘的形状是已知的,所以我们可以先处理出\(\text{A~H}\)操作对应行列......
  • [USACO12JAN]Video Game G【AC自动机+DP】
    “Canamanstillbebraveifhe’safraid?”“Thatistheonlytimeamancanbebrave.”每天六点多起床,整理好寝室内务后就去图书馆研读论文和处理邮件,完成后......
  • Codeforces Round #815 (Div. 2) E. Misha and Paintings
    人生中第一个AC的codeforces题,大概太难了,光是看答案就看了整整一下午,最后还是在b站上搜到讲解视频才明白的。俺们阿B真的是太厉害啦这道题首先容易看出当矩阵中数字个数......
  • NC51222 Strategic game
    题目链接题目题目描述Bobenjoysplayingcomputergames,especiallystrategicgames,butsometimeshecannotfindthesolutionfastenoughandthenheisvery......
  • [题解]轮流拿牌问题_一道博弈论笔试题(C++)
    题目A和B轮流从一个数组左右两端取数,A先B后,每次取一个数,最终取数总和大者获胜,两人每次都会选择最有利的策略,求获胜者取数的和。思路笔试时遇到的一道算法题,也是博弈论中......
  • 先手的微弱优势——两道博弈论题的解析
    博弈论的题往往可以通过直接计算Sprague-Grundy函数来解决。本文将介绍两道较为相似的例题,在他们的设定下,大多数情况输赢仅由双方的优势程度所决定,而先手的优势则被限定在......
  • Game Engine MetaData Creation With Clang
    ALittleContexttoStart我的hobby引擎使用一个系统,任何类或者结构体可以有metadata,但是这不是严格必须的。除此之外,每个metadata开启的类型,并不要求去有一个虚函数表......
  • 《博弈论》— 人生何处不博弈
    ......
  • [题解] Codeforces 1720 E Misha and Paintings 结论
    算是诈骗题?令一开始就存在的颜色数为cnt。k>=cnt的情况,显然每次找一个出现不止一次的颜色,然后把这个颜色的恰好一个方块替换成一种没有出现过的颜色就可以了,\(k-cnt\)次解......