Codeforces Round#768(Div.2) F. Flipping Range

Codeforces Round#768(Div.2) F. Flipping Range 题意：

给定一个数组a，与一个集合B，每次可以选择集合B中的一个元素作为翻转a中一段的大小。使得 ∑ a i sum a_{i} ∑ai​最大

题解：

如果我们有x、y∈B（假设x>y），等价于拥有一个x-y大小置入B中，方法是乘以从大小为 x-y 的区间的位置开始的大小为 x 的区间,和一个大小为 y 的区间，结束于与区间 x 相同的位置.或者，将一个大小为 x 的区间与大小为 x−y 的区间在相同位置结束的区间与另一个大小为 y 的区间相乘，该区间的起点与大小为 x 的区间相同。

对于两个元素 x,y∈B(x>y)，可以将 x−y 添加到 B，重复这样做可以得到 gcd(x,y).
让 g=gcd(b1,b2,…,bm:bi∈B)，通过应用前面的归约 g 是可以得到的最小元素，所有其他元素将是它的倍数。然后问题简化为，将大小为 g 的区间乘以 -1−任意次数，最大化 ∑ a i sum a_{i} ∑ai​

让我们定义大小为 n（0 索引）的字符串 s=000…00，如果第 i 个元素不乘以 -1 ,则si=0，否则 si =1 。该 *** 作翻转大小为 g 的子字符串中的所有 s的值。
让我们将 fx定义为所有 si值的异或，其中 i mod g =x，注意 fx的取值 大小为0≤x≤g−1。
在任何 *** 作中，f 的所有值都会同时变化，因为它们在开始时都是 0，只有使所有 fi 相等的 s 的状态是可达的。
证明所有fi相等的s的所有状态都是可达的
让我们从 s的任何状态开始，使得 f=000…00 并重复选择最右边的 i，使得 si=1 和i≥g−1，并翻转以该位置结尾的子字符串，在尽可能多地这样做之后，对于 g−1≤i≤n−1，si=0.对于任何 0≤i

在此之后，可以使用 dp解决问题。
令dp[i][0]为ai，ai-g,ai-2g,…,ai-kg的最大值，其中：

同理dp[i][1]为：ai-g,ai-2g,…,ai-kg的最大值，其中：

最终答案为：

#include 
using namespace std;
typedef long long ll;

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    int T;
    cin >> T;

    while(T--)
    {
        int n,m;
        cin >> n >> m;
        vector a(n),b(m);
        for(int i=0;i> a[i];

        int g=0;
        for(int i=0;i> b[i];
            g=__gcd(g,b[i]);
        }

        vector> dp(g,vector(2));
        for(int i=0;i					
										


					

						
欢迎分享，转载请注明来源：内存溢出
原文地址: http://outofmemory.cn/zaji/5714877.html