首页 > 其他分享 >CF #814 D2 - Burenka and Traditions (hard version)

CF #814 D2 - Burenka and Traditions (hard version)

时间:2022-08-29 18:17:56浏览次数:94  
标签:Burenka Traditions int len 异或 区间 操作 include 814

DP + map优化转移

Problem - D2 - Codeforces

题意

给 n (1 <= n <= 1e5) 个元素的数组,每次操作可以选一个区间 \([l,r]\) 和一个非负整数 x,花 \(\lceil \frac {r-l+1}2\rceil\) 的代价让 \([l,r]\) 的元素 a[i] ^= x, 求最小代价使数组元素全部为 0

思路

  1. 因为操作长度为 len 的区间,产生的效果与代价和操作 \(\lfloor\frac {len}2\rfloor\) 次长度为 2 的区间 + len % 2 次长度为 1 的区间一样,所以之后只操作长度为 1 或 2 的区间, 代价均为 1

  2. 由于代价是区间长度除以 2 向上取整,所以最好操作偶数长度的区间

  3. 基于 1,2 中贪心的思想,每次尽量操作长度为 2 的区间,因此就先对 \(a[1],a[2]\) 操作,为了让它们尽量变为 0,可以选择让它们都异或 \(a[1]\) ,这样 \(a[1]\) 为 0, \(a[2]=a[1]\;xor\;a[2]\)

  4. 同理,对于一段长度为 len 的区间 \([l,r]\), 若要把它们都变为 0,按上述方案操作,操作 len - 1 次后 \([l,r-1]\) 都已变为 0, a[r] = a[l] ^ a[l+1] ^ ... ^ a[r], 此时若 \([l,r]\) 的异或和为 0,则可以省一次操作;否则 \(a[r]\) 还要异或上自身,为了使操作数变小,就是要操作异或和为 0 的区间尽量多(因此也可以转换为找到互不相交的异或和为 0 的区间数量,答案为 n - 该数量,下文并不是这种转移,但也是对的)

  5. 设 \(f[i]\) 为把前 i 个变为 0 的代价, 初始化 \(f[i]=f[i-1]+1\), 表示 \(a[i]\) 单独操作一次

    从 1 到 i - 1 枚举 idx,若 \([idx,i]\) 的异或和为 0,表示操作 \([idx,i]\) 这个区间后可以省一次代价,用 \(f[idx-1]+i-idx\) 更新答案,复杂度为 \(O(n^2)\)

  6. 可以用 map 存下前缀异或和 为 x 的最靠后(用靠后的下标转移肯定比靠前的要优,这也是把转移复杂度从 \(O(n)\) 降到 \(O(1)\) 的关键)的下标 i,即 \(mp[s[i]]=i\);

    假设枚举到 r,找到 \(l=mp[s[r]]\), 表示 \(s[l]==s[r]\), 即 \([l+1,r]\) 的异或和为 0,直接用 \(f[r]=min(f[r],f[l]+r-l-1)\) 更新答案

#include <iostream>
#include <algorithm>
#include <cstring>
#include <vector>
#include <cmath>
#include <map>
using namespace std;
#define endl "\n"

typedef long long ll;
typedef pair<int, int> PII;

const int N = 1e5 + 10;
int a[N];
int s[N], f[N];
map<int, int> mp;
int n;
void init()
{
	mp.clear();
	mp[0] = 0;
}
int main()
{
	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	int T;
	cin >> T;
	while(T--)
	{
		cin >> n;
		init();
		for (int i = 1; i <= n; i++)
		{
			cin >> a[i];
			s[i] = s[i-1] ^ a[i];
		}
		for (int i = 1; i <= n; i++)
		{
			f[i] = f[i-1] + 1;
			int t = s[i];
			if (mp.count(t))
			{
				int idx = mp[t];
				f[i] = min(f[i], f[idx] + i - idx - 1);
			}
			mp[s[i]] = i;
		}
		cout << f[n] << endl;
	}
    return 0;
}

标签:Burenka,Traditions,int,len,异或,区间,操作,include,814
From: https://www.cnblogs.com/hzy717zsy/p/16636853.html

相关文章

  • Codeforces Round #814 (Div. 2) A-D2
    A:ChipGame题意:只能向上走和向右走,走到右上角,最后一步谁操作谁就赢只要判断总步数的奇偶性就可以了//-------------------------代码----------------------------......
  • CodeForces-1719D Burenka and Traditions
    BurenkaandTraditions贪心由于代价是向上取整的,因此可以直接考虑成两种方式:选择两个相邻的数,让他们同时异或上一个值选择一个数字,让他变成\(0\)由此可见,最多......
  • 814 C Fighting Tournament
    写的时候思路想到了,但是不怎么会维护。这儿贴一个比较好理解的维护方式,用的双端队列。#include<bits/stdc++.h>usingnamespacestd;#defineintlonglong#pragma......
  • CF1718C Tonya and Burenka-179
    显然只需要考虑\(k\vertn\)。如果直接维护是\(O(nd(n)\logn)\)的,很寄。可以证明如果\(\frac{n}{k}\)不是素数则不优。这个很好理解,比如对于\(n=12,k=2,6\),所有\(......
  • Codeforces Round #814 (Div. 2)(补题中)
    战绩:  有铁头娃A.ChipGame猜了个结论,第一次猜的是n==m,第二次猜的是n+m的奇偶性。严格证明也比较简单。由于只能向右向上,我们每次移动相当于缩减问题规模。那么......
  • CF Round 814 Div2 题解
    A题ChipGame(签到)给定一个\(n\)行\(m\)列的方格矩阵,左下角是\((1,1)\),右上角是\((m,n)\)。(采取了类似笛卡尔坐标系的表示法,不是普通的\(x\)行\(y\)列)Burenka......
  • Codeforces Round #814 (Div. 2)
    A.ChipGame题目描述BurenkaandTonyaareplayinganoldBuryatgamewithachiponaboardofn\timesmcells.Atthebeginningofthegame,thechipisl......
  • Codeforces Round #814 (Div. 2)
    比赛链接CodeforcesRound#814(Div.2)D2.BurenkaandTraditions(hardversion)给出\(n\)个数,每次可以选择一个区间和一个数,将该区间的所有数异或上该数,代价为区......
  • 20220814 idea_springboot_启动 Cannot load driver class: com.mysql.cj.jdbc.
    1问题Cannotloaddriverclass:com.mysql.cj.jdbc.Driver 2解决方案2.1已解决2.1.1首先,去查看项目中MySQL的版本如果找不到,说......
  • 20220814 idea_SpringBoot_启动 jpa 启动 Access to DialectResolutionInfo canno
    1问题AccesstoDialectResolutionInfocannotbenullwhen'hibernate.dialect'notset 2解决方案2.1未解决直接用这个问题搜索,使用了很......