首页 > 其他分享 >题解【[ABC155F] Perils in Parallel】(未完成)

题解【[ABC155F] Perils in Parallel】(未完成)

时间:2024-05-04 17:45:03浏览次数:26  
标签:题解 差分 转化 异或 ABC155F bigoplus 区间 diff Parallel

题目链接

两个常规转化:

灯的坐标与区间坐标都很大,不妨将其离散化,转化为 \(1\sim n\) 的点与\(1\sim n\) 的操作区间。

对于一段区间取反,可以理解为对一段区间异或 \(1\),转化为在异或差分数组上操作,即差分数组 \(diff_i=a_i\bigoplus a_{i-1}\),区间 \([l,r]\) 异或 \(1\) 转化为差分数组操作即:\(diff_l\bigoplus 1,diff_{r+1}\bigoplus 1\)。

转化完的方向:由于存在传递关系,可以利用点对进行建图,即在 \(l,r+1\) 之间连边,再在图上研究性质。

标签:题解,差分,转化,异或,ABC155F,bigoplus,区间,diff,Parallel
From: https://www.cnblogs.com/zhangyuzhe/p/18172504

相关文章

  • 5月3日模拟赛题解(李时珍的皮肤衣 , 马大嘴的废话 , SSY的队列 , 清理牛棚 , 历史の研究)
    T1李时珍的皮肤衣发现是二进制进位,所以直接快速幂即可。#include<bits/stdc++.h>#defineint__int128inlineintread(){charch=getchar();intx=0,f=1;for(;ch<'0'||ch>'9';ch=getchar())if(ch=='-')f=-1;for(;ch>='0'......
  • 题解:ssy的队列
    题目链接题目描述SSY是班集体育委员,总喜欢把班级同学排成各种奇怪的队形,现在班级里有\(N\)个身高互不相同的同学,请你求出这\(N\)个人的所有排列中任意两个相邻同学的身高差均不为给定整数\(M\)的倍数的排列总数。输入格式共三行:第一行为\(N\)第二行为\(N\)个不同的......
  • P10064 [SNOI2024] 公交线路 题解
    弱化版:CF1827EBusRoutes。对于\(n=2\)的情况可以判掉,剩下的情况取一个度数大于一的点作为根。首先发现如果叶子间满足条件,那么整棵树也满足条件。考虑叶子间什么时候满足条件,记点\(x\)通过最多一条路径可以到达的所有点的集合为\(S_x\),则需满足\(\forallx,y\in\mathbf......
  • [国家集训队] 矩阵乘法 题解
    发现实际上就是二维静态区间最大值,可以用整体二分维护。时间复杂度\(O((q+n^2)\log\max(a_{i,j})\logn^2)\)。#include<bits/stdc++.h>#definelllonglongusingnamespacestd;constintW=310005;constintQ=6e4+5;intn,q,w,ans[Q];intc[505][505],m;voidadd(i......
  • 题解【[ABC147F] Sum Difference】
    题目链接下为口胡题解:入手方向推导:直接考虑题目所给式子显然困难:\[w(S)=\sum_{i\inS}A_i-\sum_{i\notinS}A_i\]因为两个式子虽然相关但是都在变化,不妨转化为:\[w(S)=2\times\sum_{i\inS}A_i-\sum_{i=1}^nA_i\]这样只用求出有多少个不同的\(\sum_{i\inS}A_i\)。由于......
  • CF1968E.Cells Arrangement-构造(给个和题解不同的做法)
    link:https://codeforces.com/problemset/problem/1968/E题意:需要构造一个\(n\timesn\)的棋盘,在上面放\(n\)枚棋子,设集合\(\mathcal{H}\)表示两两之间曼哈顿距离构成的集合,要让\(|\mathcal{H}|\)最大。给出放棋子的方案。首先说说题解的做法…考虑把距离为奇数和偶数的......
  • 题解:CF1926G
    题目传送门思路发现权值为C的点可以选择看做是权值为S或为P的点,所以问题转换为怎么给C点赋值可以使答案最小,考虑树形dp。\(f_{i,0/i,1}\)表示\(i\)点赋值为S或P时最少要删除几条边。但如果当前点权值不为C的话,那显然他的父亲节点应该选择和他权值相同的点才......
  • 题解:AT_abc298_h [ABC298Ex] Sum of Min of Length
    分析模拟赛签到题。考虑分讨。分两种情况:\(L=R\)。\(L\neR\)。对于第\(1\)种情况,用换根DP求一个\(i\)为根时所有点的深度和就行。对于第\(2\)种情况,钦定$dep_R\gedep_L$。很显然,\(R\)为根的子树中所有点都是离\(R\)更近。假设在\(L\)到\(R\)的路径......
  • 题解【[ABC077D] Small Multiple】
    题目链接题意简述:给定正整数\(K\),求数位之和最小的\(K\)的倍数的数位和。错误方向:\(K\)的倍数一定满足\(K\timesS\),根据\(K\)的特征构造出合适的\(S\)。正确方向考虑直接构造出K的倍数,由于从1开始可以通过×10和+1构造出所有数字,并且在此......
  • 【题解】P4711 「化学」相对分子质量
    Problem给定一个长度为\(L\)的化学式,求出此化学式的相对分子质量。例:十二水合硫酸铝钾(明矾)\(KAl(SO_4)_2\cdot12H_2O\).输入格式形为:KAl(SO_{4})_{2}~12H_{2}OSolve清新小模拟。定义一下“结账”这个概念,分为三种:原子结账,即为当单独的一个(一坨)原子计算完成后,计入所属......