P9852 [ICPC2021 Nanjing R] Windblume Festival 题解(SPJ)

2024-01-17 22:44

本文主要是介绍P9852 [ICPC2021 Nanjing R] Windblume Festival 题解(SPJ),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

[ICPC2021 Nanjing R] Windblume Festival

单击此处下载原神

题面翻译

给一个长度为 n n n 环形整数序列 a a a, 每次操作可以任意选择一个下标 x x x,令 $ a_x = a_x - a_{(x\bmod n)+1}$,之后移除 a ( x m o d n ) + 1 a_{(x\bmod n)+1} a(xmodn)+1

最后会剩下一个元素,要求最大化这个元素。

数据范围 1 ≤ n ≤ 1 0 6 , − 1 0 9 ≤ a i ≤ 1 0 9 1\le n\le10^6,-10^9\le a_i\le 10^9 1n106,109ai109

题目描述

The Windblume Festival in Mondstadt is coming! People are preparing windblumes for Barbatos and for those they love and adore. The Windblume Festival is also an opportunity to improve the relationships people have.

During the festival, a famous game will be played every year, invented by Jean, the Acting Grand Master of the Knights of Favonius. In the game, n n n players numbered from 1 1 1 to n n n stand in a circle, each holding an integer with them. Each turn, one player will be removed. The game will end when there is only one player left.

For each turn, let k k k be the number of players remaining and a i a_i ai be the integer player i i i holds. Two adjacent players, x x x and ( x m o d k + 1 ) (x \bmod k + 1) (xmodk+1) are selected and player ( x m o d k + 1 ) (x \bmod k + 1) (xmodk+1) is removed from the game. Player x x x’s integer will then change from a x a_x ax to ( a x − a x m o d k + 1 ) (a_x - a_{x \bmod k + 1}) (axaxmodk+1). Player y y y in this turn will become player ( y − 1 ) (y - 1) (y1) in the next turn for all x < y ≤ k x < y \le k x<yk, though the integer they hold will not change.

Jean wants to know the maximum possible integer held by the last remaining player in the game by selecting the players in each round optimally.

输入格式

There are multiple test cases. The first line of the input contains one integer T T T indicating the number of test cases. For each test case:

The first line contains one integer n n n ( 1 ≤ n ≤ 1 0 6 1 \le n \le 10^6 1n106) indicating the initial number of players.

The next line contains n n n integers a i a_i ai ( − 1 0 9 ≤ a i ≤ 1 0 9 -10^9 \le a_i \le 10^9 109ai109) where a i a_i ai is the integer held by player i i i at the beginning.

It is guaranteed that the sum of n n n of all test cases will not exceed 1 0 6 10^6 106.

输出格式

For each test case output one line containing one integer indicating the maximum possible integer.

样例 #1

样例输入 #1

5
4
1 -3 2 -4
11
91 66 73 71 32 83 72 79 84 33 93
12
91 66 73 71 32 83 72 79 84 33 33 93
13
91 66 73 71 32 83 72 79 84 33 33 33 93
1
0

样例输出 #1

10
713
746
779
0

提示

For the first sample test case follow the strategy shown below, where the underlined integers are the integers held by the players selected in each turn.

{ 1 ‾ , − 3 , 2 , − 4 ‾ } \{\underline{1}, -3, 2, \underline{-4}\} {1,3,2,4} (select x = 4 x = 4 x=4) → \to { − 3 , 2 , − 5 ‾ } \{-3, \underline{2, -5}\} {3,2,5} (select x = 2 x = 2 x=2) → \to { − 3 , 7 ‾ } \{\underline{-3, 7}\} {3,7} (select x = 2 x = 2 x=2) → \to { 10 } \{10\} {10}.

以上来自 以上来自 以上来自原神 洛谷 洛谷 洛谷

解题思路

我们先列出 3 种情况:只有负数,只有正数,正负数都有。

  • 只有负数:以 − 11 , − 4 , − 5 , − 45 −11,−4,−5,−45 11,4,5,45 为例,发现得数最大为: 57 57 57
  • 只有正数:以 11 , 4 , 5 , 45 11,4,5,45 11,4,5,45 为例,发现得数最大为: 57 57 57
  • 正负数都有:以 − 11 , 4 , − 5 , 45 −11,4,−5,45 11,4,5,45 为例,发现得数最大为: 65 65 65

我们发现,如果 n n n 个数中正负数都有,输出的值即为所有数的绝对值之和;如果 n n n 个数中只有正数或负数,那输出的数为所有数的绝对值之和,减去最小的绝对值的两倍。

说得简单一点,就是模拟。

AC Code

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int Maxn = 1e6 + 10;
int T, n, a[Maxn];
int minn = INT_MAX, sum1, sum2;
int ans;
inline void solve() {minn = INT_MAX, sum1 = sum2 = 0;ans = 0;cin >> n;if (n == 1) {cin >> a[0];cout << a[0] << endl;return;}for (int i = 1; i <= n; i++) {cin >> a[i];}bool flag = 1;for (int i = 1; i <= n; i++) {if (a[i] > 0) {flag = 0;break;}}if (flag) {for (int i = 1; i <= n; i++) {a[i] = abs(a[i]);}}for (int i = 1; i <= n; i++) {minn = min(minn, a[i]);sum1 += a[i];sum2 += abs(a[i]);}if (minn < 0) {ans = sum2;} else {ans = sum1 - minn * 2;}cout << ans << endl;
}
inline void work() {cin >> T;while (T--) {solve();}
}
signed main() {ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);work();return 0;
}

这篇关于P9852 [ICPC2021 Nanjing R] Windblume Festival 题解(SPJ)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/617420

相关文章

C++ | Leetcode C++题解之第393题UTF-8编码验证

题目: 题解: class Solution {public:static const int MASK1 = 1 << 7;static const int MASK2 = (1 << 7) + (1 << 6);bool isValid(int num) {return (num & MASK2) == MASK1;}int getBytes(int num) {if ((num &

C语言 | Leetcode C语言题解之第393题UTF-8编码验证

题目: 题解: static const int MASK1 = 1 << 7;static const int MASK2 = (1 << 7) + (1 << 6);bool isValid(int num) {return (num & MASK2) == MASK1;}int getBytes(int num) {if ((num & MASK1) == 0) {return

C - Word Ladder题解

C - Word Ladder 题解 解题思路: 先输入两个字符串S 和t 然后在S和T中寻找有多少个字符不同的个数(也就是需要变换多少次) 开始替换时: tips: 字符串下标以0开始 我们定义两个变量a和b,用于记录当前遍历到的字符 首先是判断:如果这时a已经==b了,那么就跳过,不用管; 如果a大于b的话:那么我们就让s中的第i项替换成b,接着就直接输出S就行了。 这样

【秋招笔试】9.07米哈游秋招改编题-三语言题解

🍭 大家好这里是 春秋招笔试突围,一起备战大厂笔试 💻 ACM金牌团队🏅️ | 多次AK大厂笔试 | 大厂实习经历 ✨ 本系列打算持续跟新 春秋招笔试题 👏 感谢大家的订阅➕ 和 喜欢💗 和 手里的小花花🌸 ✨ 笔试合集传送们 -> 🧷春秋招笔试合集 🍒 本专栏已收集 100+ 套笔试题,笔试真题 会在第一时间跟新 🍄 题面描述等均已改编,如果和你笔试题看到的题面描述

LeetCode 第414场周赛个人题解

目录 Q1. 将日期转换为二进制表示 原题链接 思路分析 AC代码 Q2. 范围内整数的最大得分 原题链接 思路分析 AC代码 Q3. 到达数组末尾的最大得分 原题链接 思路分析 AC代码 Q4. 吃掉所有兵需要的最多移动次数 原题链接 思路分析 AC代码 Q1. 将日期转换为二进制表示 原题链接 Q1. 将日期转换为二进制表示 思路分析

牛客小白月赛100部分题解

比赛地址:牛客小白月赛100_ACM/NOI/CSP/CCPC/ICPC算法编程高难度练习赛_牛客竞赛OJ A.ACM中的A题 #include<bits/stdc++.h>using namespace std;#define ll long long#define ull = unsigned long longvoid solve() {ll a,b,c;cin>>a>>b>

P2858 [USACO06FEB] Treats for the Cows G/S 题解

P2858 题意 给一个数组。每天把最左或者最右的东西卖掉,第 i i i个东西,第 d a y day day天卖出的价格是 a [ i ] ∗ d a y a[i]*day a[i]∗day。 记忆化搜索 void dfs(int l,int r,int day,ll sum){if(v[l][r]>=sum)return;v[l][r]=sum;if(l>r)//这就是dp答案{

【C++题解】1272. 郭远摘苹果

欢迎关注本专栏《C++从零基础到信奥赛入门级(CSP-J)》 问题:1272. 郭远摘苹果 类型:二维数组 题目描述: 郭远有一天走到了一片苹果林,里面每颗树上都结有不同数目的苹果,郭远身上只能拿同一棵树上的苹果,他每到一棵果树前都会把自己身上的苹果扔掉并摘下他所在树上的苹果并带走(假设郭远会走过每一棵苹果树),问在郭远摘苹果的整个过程中,他身上携带的最多苹果数与最小苹果数的差是多少?

【最新华为OD机试E卷-支持在线评测】机器人活动区域(100分)多语言题解-(Python/C/JavaScript/Java/Cpp)

🍭 大家好这里是春秋招笔试突围 ,一枚热爱算法的程序员 ✨ 本系列打算持续跟新华为OD-E/D卷的三语言AC题解 💻 ACM金牌🏅️团队| 多次AK大厂笔试 | 编程一对一辅导 👏 感谢大家的订阅➕ 和 喜欢💗 🍿 最新华为OD机试D卷目录,全、新、准,题目覆盖率达 95% 以上,支持题目在线评测,专栏文章质量平均 94 分 最新华为OD机试目录: https://blog.

2023 CCPC(秦皇岛)现场(第二届环球杯.第 2 阶段:秦皇岛)部分题解

所有题目链接:Dashboard - The 2023 CCPC (Qinhuangdao) Onsite (The 2nd Universal Cup. Stage 9: Qinhuangdao) - Codeforces 中文题面: contest-37054-zh.pdf (codeforces.com) G. Path 链接: Problem - G - Codeforces