首页 > 其他分享 >【题解】CF - 859C : Pie Rules

【题解】CF - 859C : Pie Rules

时间:2024-08-14 20:27:16浏览次数:13  
标签:分数 Rules 题解 Pie int 答案 两方 序列 操作

原题传送门

题目大意:

给定一个长为\(N (1 \leq N \leq 50)\)的序列,Bob 和 Alice 轮流从序列的最前端进行以下操作之一:

  • 取出序列最前端的数,并将其加到自己的分数中;
  • 取出序列最前端的数,将其加到对方的分数中,则下一轮可继续操作。

两人轮流操作直到序列被取完,分数多的一方获胜。

若两方都采用最佳策略,问在给定的情况下,两方最终的分数是多少。

题意分析:

我们先将题目简化,也就是不支持第二种操作,那么不难看出,此时两方的得分就与奇偶性有关。而支持操作一后,由于可以连续操作,此时奇偶性被改变,相当于双方将来的分数被交换了。所以我们只要求出此时双方将来的最优答案,并贪心地交换就可以了。我们从后向前遍历,并记录从\(i\)到\(n\)双方的最优答案,也相当于是当取到\(i\)时将来的答案。到一个新位置时,如果我们在获得当前的分数后还不如对方将来的分数,就直接交换两方的分数。最终代码十分简洁,复杂度\(O(N)\)。

AC代码

#include <bits/stdc++.h>

#define N 100050

using namespace std;

int n;
int a[N], p[5];//p记录双方当前以后的最优答案

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

	for(int i = n; i >= 1; i--){
	   if(p[i + 1 & 1] > p[i & 1] + a[i])
              swap(p[0], p[1]), p[i + 1 & 1] += a[i];
    	else p[i & 1] += a[i];
    }

	cout << p[0] << " " << p[1];

	return 0;
}

标签:分数,Rules,题解,Pie,int,答案,两方,序列,操作
From: https://www.cnblogs.com/XHyair-blogs/p/18359714

相关文章

  • 暑期模拟赛题解
    暑期模拟赛题解CSP-J模拟赛2024.7.5CSP-J模拟赛1T1简单二分,判断即可。T2\(60pts\)的状压是好写的。至于\(100pts\),考虑dp状态的合并,由于\(m\)的级别很小,考虑对后\(m\)个数状压,考察满足条件的情况。dp难以优化的时候考察本质相同的状态。T3数据范围显......
  • 【题解】【模拟】——帮贡排序
    【题解】【模拟】——帮贡排序帮贡排序题目背景题目描述输入格式输出格式输入输出样例输入#1输出#1提示1.题意解析1.1.结构体储存信息1.2.输入后调整职务的排序规则1.3.分配职务的方法1.4.职务的映射1.5.输出时的排序规则1.6.主函数2.代码帮贡排序题目背景在......
  • 洛谷P2789 直线交点数 题解
    解题思路考虑将直线分组,每组内直线互相平行,任意两组直线间交点数量等于两组内直线数量乘积。分组操作使用dfs,求出交点数量后加入set去重,输出set大小。时间复杂度O(2NN2)有点鬼畜但是可以通过。实现#include<cstdio>#include<unordered_set>inta[30];std::unordered_set......
  • 题解:CF1551D1 Domino (easy version)
    题解:CF1551D1Domino(easyversion)分析题目中保证\(n\timesm\)为偶数,下面进行分类讨论。情况一如果\(n\)和\(m\)都是偶数,那么可以分割成\(\frac{n}{2}\times\frac{m}{2}\)个\(2\times2\)的方块。根据上图我们发现,只要\(k\)满足\(0\lek\le\frac{n}{2}\time......
  • 题解:CF685A Robbers' watch
    题解:CF685ARobbers'watch感觉这题难点主要在理解题意。题意一天\(n\)个小时,一小时\(m\)分钟,手表用\(7\)进制表示时间(位数未填满补前导零),求问这个手表显示的每一位数字都不一样的时刻数量。分析因为是\(7\)进制,所以每一个数字位只可能出现\(0\sim6\)这\(7\)种......
  • P8776 最长不下降子序列 题解
    Statement最长不下降子序列(LIS),但是有一次机会,让序列中连续\(k\)个数改成同一个数。\(n\le10^5,a_i\le10^6\).Solution记\(f(i)\)为以\(i\)结尾的LIS长度,\(g(i)\)为以\(i\)开始的LIS长度,可预处理.答案一定是\(f(i)+k+g(j)\)这样拼接起来的,其中\(i+k+1\le......
  • (CF 10D)最长公共上升子序列(LCIS)(要求输出序列) - 题解
    最长公共上升子序列(LCIS)原题链接:CodeForces、洛谷时间限制:C/C++1000MS,其他语言2000MS内存限制:C/C++256MB,其他语言512MB描述给定两个整数序列,写一个程序求它们的最长上升公共子序列。当以下条件满足的时候,我们将长度\(N\)的序列\(S_1,S_2,...,S_N\)称为长度为\(M......
  • 【题解】CF1942C1 Bessie's Birthday Cake (Easy Version)
    \(\mathfrak{1st.\Preamble\|}\)前言题目传送门:CF1942C1Bessie'sBirthdayCake(EasyVersion)。蒟蒻在洛谷上第一篇通过的题解。\(\mathfrak{2nd.\Reasoning\|}\)思路其实只需要把选中的点组成一个新的多边形,然后我们就可以发现有\(x\)个点的多边形可以连出\(x-2......
  • 【知识】并查集的单点删除 &【题解】SP5150
    \(\mathfrak{1st.}\)前言-->题目传送门<--原先这道题的难度是紫,我觉得题目翻译看不懂,就去讨论版发了个贴,然后题管更新了题目翻译,并且把难度降到了蓝……\(\mathfrak{2nd.}\)思路赶时间或嫌啰嗦的可以直接跳到『思路归纳』。我们先从普通并查集开始思考对于删除单点\(x\),......
  • 【问题解决】git status中文文件名乱码
    问题复现解决办法在gitbash中直接执行如下命令gitconfig--globalcore.quotepathfalse原因通过gitconfig--help可以查看到以下内容:core.quotePathCommandsthatoutputpaths(e.g.ls-files,diff),willquote"unusual"charactersinthepathnamebyencl......