Codeforces Round #821 (Div. 2)

A.Consecutive Sum

题目大意

给定一个长度为$n$的数组$a$，可做以下操作至多$k$次：
选择两个下标$i$和$j$，要求$i\ mod\ k=j\ mod\ k$，然后交换$a_i$和$a_j$
操作完后，任意选连续$k$个数，这些数的的和是你的分数，问分数最多是多少

简介

想法的本质是基于数据随机的均摊，不是数据结构

核心思想

把值相同的区间合并成一个节点保存在$set$中

2023年上海市大学生程序设计竞赛-四月赛

A. 宝石划分

题目大意

海盗们获得了$n$颗相同的宝石(宝石无法切割)
船上共$m$个海盗，他们希望能够完美地瓜分这些宝石，即每个人获得的宝石数量相同，但是目前可能无法完美地瓜分
他们商量：如果在座的各位无法完美地瓜分这些宝石，就随机把一个人扔下船，直到可以让每个海盗分到的宝石一样多为止
求最终每个海盗获得的宝石数量

Meal beside toilets

2022 CCPC Mianyang Onsite

A. Ban or Pick, What’s the Trick

题目大意

两个队伍分别有$n$个英雄可以选择，价值分别为$a_1, \cdots, a_n$和$b_1, \cdots, b_n$
两队轮流操作，每次可以选己方英雄池内$1$个英雄或者禁用对方英雄池内$1$个英雄
最终每方得分为选取英雄价值前$k$大的价值和，对于一方来说，得分差越大方案越优，求双方在最优策略下，两队得分差

Bad ass BoBo

Bobo’s big success

Codeforces Round #864 (Div. 2)

D. Li Hua and Tree

题目大意

李华有一棵$n$个节点的有根树，根节点为$1$，第$i$个节点有点权$a_i$
定义一个非叶子节点的重儿子为其所有儿子里子树大小最大的，若有多个大小相同的则取编号最小的
维护$m$次操作
操作一：求以$x$为根的子树的点权和
操作二：记$x$的父亲为$fa_x$，重儿子为$hs_x$，切断$(x, fa_x)$之间的边，新加一条$(hs_x, fa_x)$之间的边
操作二不保证$x$是叶子节点，若$x$是叶子，就忽略该操作

With Bobo

组合游戏概念

$1$.两个玩家
$2$.一个状态集合
$3$.游戏规则是指明玩家在一个状态下可以移动到哪些其他状态
$4$.玩家轮流进行移动
$5$.若当前处于某个状态，玩家根据规则无法移动，则游戏结束
$6$.游戏会在有限步以内结束(有向无环$DAG$)

$P$态和$N$态

$P$态：走到这个状态的玩家赢的状态
$N$态：从这个状态走的玩家赢的状态
至少能走到一个$P$态的状态是$N$态
只能走到$N$态的状态是$P$态
正常规则：终态是$P$态(无法走的人输)
反常规则：终态是$N$态(无法走的人赢)