首页 > 其他分享 >【大联盟】20230707 xor(xor) CF1456E 【XOR-ranges】

【大联盟】20230707 xor(xor) CF1456E 【XOR-ranges】

时间:2023-07-22 11:23:32浏览次数:56  
标签:aa 20230707 XOR int mid read ff xor

就我不会 *3500 /kel

题目描述

here

题解

做法考虑从高位往低位处理,由于有限制的数它的值数确定的,没限制的数值不需要管,因为肯定可以是答案为 \(0\)。

所以我们考虑区间 DP,我们令 \(f_{i,l,r,0/1,0/1}\) 表示从高往低到第 \(i\) 位,最左侧 \(l\) 还有限制,第一个 \(0/1\) 表示 \(x_l\) 在上界还是下界,最右侧 \(r\) 还有限制,第二个 \(0/1\) 表示 \(x_r\) 是上界还是下界。

合并时相当于某一个数限制被解除,算一下这一位的贡献即可。

代码

记录

#include <bits/stdc++.h>
#define SZ(x) (int) x.size() - 1
#define all(x) x.begin(), x.end()
#define ms(x, y) memset(x, y, sizeof x)
#define F(i, x, y) for (int i = (x); i <= (y); i++)
#define DF(i, x, y) for (int i = (x); i >= (y); i--)
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
template <typename T> void chkmax(T& x, T y) { x = max(x, y); }
template <typename T> void chkmin(T& x, T y) { x = min(x, y); }
template <typename T> void read(T &x) {
	x = 0; int f = 1; char c = getchar();
	for (; !isdigit(c); c = getchar()) if (c == '-') f = -f;
	for (; isdigit(c); c = getchar()) x = x * 10 + c - '0';
	x *= f;
}
const int N = 55;
int n, k;
ll a[N], b[N], c[N], f[N][N][N][2][2], ff[N][N][N][2][2][2][2];
signed main() {
	// freopen("xor.in", "r", stdin);
	// freopen("xor.out", "w", stdout);
	read(n), read(k);
	F(i, 1, n) read(a[i]), read(b[i]);
	F(i, 0, k - 1) read(c[i]);
	ms(f, 0x3f), ms(ff, 0x3f);
	F(i, 0, n) f[k][i + 1][i][1][1] = f[k][i + 1][i][1][0] = f[k][i + 1][i][0][1] = f[k][i + 1][i][0][0] = 0;
	DF(i, k - 1, 0) {
		F(l, 1, n + 1)
			F(r, l - 1, n)
				F(a, 0, 1)
					F(b, 0, 1) F(aa, 0, 1) F(bb, 0, 1) {
						ll A = (a ? ::a[l - 1] : ::b[l - 1]), B = (b ? ::a[r + 1] : ::b[r + 1]);
						ll val = 0;
						if (l != 1 && r != n) val = (((A >> i) & 1) ^ ((B >> i) & 1) ^ aa ^ bb) * c[i];
						ff[i][l][r][a][b][aa][bb] = f[i + 1][l][r][a][b] + val;
					}
		F(len, 1, n)
			for (int l = 1, r = len; r <= n; l++, r++)
				F(mid, l - 1, r - 1)
					F(a, 0, 1)
						F(b, 0, 1)
							F(c, 0, 1) F(aa, 0, 1) F(bb, 0, 1) {
								if ((::a[mid + 1] >> (i + 1)) != (::b[mid + 1] >> (i + 1)) && ((b && !((::a[mid + 1] >> i) & 1)) || (!b && ((::b[mid + 1] >> i) & 1))))
								chkmin(ff[i][l][r][a][c][aa][bb], ff[i][l][mid][a][b][aa][1] + ff[i][mid + 2][r][b][c][1][bb]);
							}
		F(l, 1, n + 1)
			F(r, l - 1, n)
				F(a, 0, 1)
					F(b, 0, 1)
						f[i][l][r][a][b] = ff[i][l][r][a][b][0][0];
	}
	F(len, 1, n)
		for (int l = 1, r = len; r <= n; l++, r++)
			F(mid, l - 1, r - 1)
				F(a, 0, 1)
					F(b, 0, 1)
						F(c, 0, 1)
							chkmin(f[0][l][r][a][c], f[0][l][mid][a][b] + f[0][mid + 2][r][b][c]);
	cout << min(min(f[0][1][n][1][0], f[0][1][n][1][1]), min(f[0][1][n][0][0], f[0][1][n][0][1]));
	return 0;
}

标签:aa,20230707,XOR,int,mid,read,ff,xor
From: https://www.cnblogs.com/zhaohaikun/p/17573039.html

相关文章

  • Codeforces 1456E - XOR-ranges
    考虑一个\(L\lex\leR\)的数\(x\),必然是一段前缀贴着\(L\)或者\(R\),然后下一位脱离了\(L\)和\(R\)的限制,后面随便乱填。注意到一个性质,对于某一位\(d\),考虑这一位上没有限制的那些位置,最优方案肯定是令其等于其左边(或者右边)第一个有限制的数的第\(d\)位上的值。这......
  • AGC034F RNG and XOR
    类似随机游走,令\(f_i\)为第一次操作到\(i\)的期望操作次数,\(p_i\)为每次操作数为\(i\)个概率,显然有:\[f_i=\begin{cases}0&i=0\\1+\sum\limits_{j\;\text{xor}\;k\=\i}p_jf_k&i\neq0\end{cases}\]显然可以高斯消元,不过是\(O(2^{3n})\)的,寄飞。考虑到转移过程中有......
  • CF1083F The Fair Nut and Amusing Xor
    简要题意:给你两个序列\(a,b\),一次操作可以将\(a\)的某一个长度为\(k\)的子区间全部异或上任意值,\(f(a,b)\)为使得\(a\)和\(b\)相同的最少的操作数量。支持单点修改\(a,b\),并在开头和每次修改后输出\(f(a,b)\)的值。\(n,k,q\le2\times10^5,w\le2^{14}\)。题解......
  • CF1456E XOR-ranges
    题面传送门好题。首先比较自然的,相当于按照数位DP的方法,将\([l,r]\)剖成\(k\)段,其中每一段都是最高若干位确定,底下若干位任取的形式。这样在\([l,r]\)里面选择相当于在这\(O(k)\)个区间里面选择。然后假设我们依次选择好了,考虑如何计算答案。答案显然是位独立的,对于......
  • 20230707-NOIP模拟赛(多校联训)
    20230707T1.信号传输(signal)考场思路先把这\(n+k+1\)个点都转化到平面直角坐标系上面又是没有想清楚就开始打代码(但至少比昨天好,懂得放弃)本来想的是按照x轴从左到右扫一遍每一次处理这一列上的每个点复杂度是\(O(n)\)但是后面想到有可能信号是从后面的点传送过来的所以我......
  • 20230707巴蜀暑期集训测试总结
    T1SPFA就能过!给我震惊到了。可以斜率优化。对每个站点维护一个凸包。\[f(x)=Ax^2+Bx+C\\dp_{v,q}=\min_{i=0}^{p}\{dp_{u,i}+f(p-i)\}\\(i,dp_{x,i}+Ai^2-Bi)\]T2考场想了想区间dp,有点思路但是时间不多了有点慌,打个暴搜直接跑。相当于将位置当作第二关键字比较,最大的数......
  • 「NOIP 模拟赛 20230707」T2 - 涂照片 题解
    题目大意原题有一个\(n+1\timesm+1\)的网格。对于每一行\(i\),都要将左侧的一些格子\((i,1),(i,2),\ldots,(i,x)\)涂黑,其中\(x=k\)的概率为\(a_{i,k}\)。同理对于每一列\(j\),都要将上方的一些格子\((1,j),(2,j),\ldots,(x,j)\)涂黑,其中\(x=k\)的概率为\(b_{k,......
  • 20230707-编程语言的变量覆盖
    实现一个特性时,发现自定义的变量position覆盖了类的属性Position,近期发现始终存在的一个难以复现的窗口还原 BUG可能被因此修复了。也曾Debug过,但没能复现。问题的解决就是这样,只要你还惦记着,问题总会被解决。对于大小写不敏感度编程语言,尤其要注意大小写,所以我和我的朋......
  • 成语积累 20230707
    璞玉浑金:璞玉:未经人工雕琢的玉;浑金:没有冶炼过的金子。比喻人的品质纯美质朴,或指天然浑朴的精美之器。多用来形容人的品质淳朴善良。例句:这个小姑娘来自四川偏远的山区,给人一种~的感觉。例句2:现在的人都太现实,那种~的人基本很难找到了。假途灭虢:假:借;途:道路;灭:消灭;虢:春秋时诸侯国。......
  • AtCoder Beginner Contest 308 G Minimum Xor Pair Query
    洛谷传送门AtCoder传送门考虑没有删除操作怎么做。可以动态维护\(ans\),新加进来一个\(x\),我们计算\(\min\limits_{y\inS}x\oplusy\)。对\(S\)建01Trie,然后从高位往低位按位贪心,在01Trie上优先往与\(x\)这一位相同的方向走,但是前提是它的子树内有数,对于01Trie......