题号：CF1847A~F
A
题意：
给定一个数组 \(\{x_1,x_2,\cdots,x_n\}\) 和一个整数 \(k\)，记 \(f(l,r)=\sum_{i=0}^{i < r-l} |x_{l+i}-x_{l+i+1}|\)，求将数组划分为 \(k\) 个部分的划分方案，使得对每个部分的 \(f(l,r)\) 之和最小.
题解：
简单题，首先我们注意到，如果将 \(l,l+1\) 隔开，那么 \(|x_l-x_{l+1}|\) 这个数就不会计入答案，那么令 \(b_i=|x_i-x_{i+1}|(i<n)\)，那么问题就变为从 \(b\) 中选出最大的 \(k\) 个数减掉。方法很多
read(n);read(k);int ans=0;
for(int i=1;i<=n;i++)read(a[i]);
for(int i=1;i<n;i++)b[i]=abs(a[i+1]-a[i]);
sort(b+1,b+n);reverse(b+1,b+n);
for(int i=k;i<n;i++)ans+=b[i];
cout<<ans<<"\n";
B
乔纳森正在与迪奥的吸血鬼手下战斗。其中有 \(n\) 个吸血鬼，它们的强度分别为 \(a_1, a_2,\cdots, a_n\)。
将 \((l,r)\) 表示由索引 \(l\) 到 \(r\) 的吸血鬼组成的一组。乔纳森意识到每个这样的组的强度取决于它们的最弱环节，即按位与操作。更具体地说，组 \((l,r)\) 的强度等于 \(f(l,r) =\) \(a_l \ \& \ a_{l+1} \ \& \ a_{l+2} \ \& \cdots \& \ a_r\)。这里，\(\&\) 表示按位与操作。
乔纳森希望能快速击败这些吸血鬼手下，因此他会将吸血鬼分成连续的组，使得每个吸血鬼正好属于一组，并且这些组的强度之和尽量小。在所有可能的分组方式中，他希望找到组数最多的方式。
给定每个吸血鬼的强度，找出在所有可能的分组方式中，拥有最小强度之和的组的最大数量。
题解：
注意到，\(\&\) 肯定是单调不增的。那么显然最小强度之和必定是整个序列 \(\&\) 的值，故本质上问题是从前往后或从后往前找到若干个拼在一起，\(\&\) 和为0的段。
read(n);int ans=1;
for(int i=1;i<=n;i++)read(a[i]);
k=(1ll<<33ll)-1ll;int cnt=0;
for(int i=1;i<=n;i++){
k&=a[i];
if(k==0){
k=(1ll<<33ll)-1ll;
++cnt;
}
}
ans=max(ans,cnt);
cnt=0,k=(1ll<<33ll)-1ll;
for(int i=n;i;--i){
k&=a[i];
if(!k){
++cnt;k=(1ll<<33ll)-1ll;
}
}
ans=max(ans,cnt);
cout<<ans<<"\n";
C
DIO 意识到星尘十字军已经知道了他的位置，并且即将要来挑战他。为了挫败他们的计划，DIO 要召唤一些替身来迎战。起初，他召唤了 $ n $ 个替身，第 $ i $ 个替身的战斗力为 $ a_i $。依靠他的能力，他可以进行任意次以下操作：
- 设当前的替身数量为 \(m\)。
- DIO 选择一个序号 \(i \text{ } ( 1 \le i \le m )\)。
- 接着，DIO 召唤一个新的替身，其序号为 \(m+1\)，战斗力为 \(a_{m + 1} = a_i \oplus a_{i + 1} \oplus \ldots \oplus a_m\)。其中，运算符 \(\oplus\) 表示按位异或。
- 现在，替身总数就变成了 \(m+1\)。
但对于 DIO 来说，不幸的是，星尘十字军通过隐者之紫的占卜能力，已经知道了他在召唤替身迎战的事情，而且他们也知道初始的 \(n\) 个替身的战斗力。现在，请你帮他们算一算 DIO 召唤的替身的最大可能战斗力（指单个替身的战斗力，并非所有替身战斗力之和）。
题解：
手玩一下，容易发现本质上 \(a_x(x>m)\) 无论怎么选，都必定是 \(a_1\sim a_m\) 的某一个子段的异或值。所以就变成了Trie板子题。
D
给出一个长度为 \(n\) 的字符串 \(s\)，字符串仅由 0 或 1 构成。
给出 \(m\) 个区间 \([l_i,r_i]\) (\(1\le i\le m\),\(1\le l_i\le r_i\le n\))，你需要将字符串 \(s\) 的子段 \([l_i,r_i]\) 依次拼接，得到新的字符串 \(t\)。
你可以对字符串 \(s\) 进行操作，每次操作可以交换任意两个字符的位置，注意操作不是实际改变，不会影响后续的询问。定义对于字符串 \(s\)，\(f(s)\) 表示最小的操作次数，使得拼接得到的新字符串 \(t\) 的字典序最大。
然后有 \(q\) 次询问，每次询问给出一个位置 \(x_i\)，表示将原字符串 \(s\) 的 \(x_i\) 位置取反，注意是实际改变，会影响后续的询问。相应的，\(t\) 字符串也会发生改变。你需要求出每次询问后，\(f(s)\) 的值。
E
交互题。 \(n\le 5000\)，询问次数不超过 \(500\)。
序列 \(a\) 长为 \(n\)，其中 \(1\le a_i\le 4\)，每一次询问给出3个 \(i,j,k(i<j<k)\)，输入以 \(a_i,a_j,a_k\) 为边长的三角形的面积的平方乘16的结果，特别地，如果构不成三角形，输入0，求这个序列。
F
给定一个无穷长的整数数列的前 \(n\) 项 \(a_1,a_2 \dots a_n\)，且对于任意 \(i > n\)，\(a_i=a_{i-n}|a_{i-n+1}\).
你需要处理 \(q\) 次询问。每次询问给定一个整数 \(x\)，请找出最小的 \(i\) 满足 \(a_i>x\)。如果不存在这样的 \(i\)，输出 −1 。