首页 > 其他分享 >「Solution Set」7/4

「Solution Set」7/4

时间:2023-07-04 10:11:35浏览次数:51  
标签:连边 Set 一个点 反转 Solution 然后 子树 SAT

「SDOI / SXOI2022」无处存储

链加链求和。

考虑先搞出随机撒点,然后建虚树,这样比较好维护一点。

然后就是正常的整块打 tag,散块暴力加之类的。

我写的好麻烦/kk

「LibreOJ Round #11」Misaka Network 与 Accelerator

我们考虑暴力 2-SAT,最多要连 \(O(n^2)\) 条边,时间空间都接受不了。

如果是点分治的话一个点要向其他子树的所有符合条件的点连边,时空复杂度还是不对。

然而如果是边分治,从一个点只向对面的一棵子树连边,也就是一次只会用到两个子树,那么每次只需要搞两颗线段树,然后直接连就可以了。

然后还是要搞清 2-SAT 的连边方式的/kk

我错了,我不会边分治,【数据删除】,我真的错了。

CF662B Graph Coloring

没有水平

我们考虑如果固定一个点是否反转,与它相邻的点是否反转是固定的。所以转化成 2-SAT,然后考虑如果反转一个点,那么整张图都会反转。所以假设要把整张图染成红色的,那么就连一个 2-SAT 的图出来,然后跑一边是否合法以及如果第一个点不反转需要转多少个点。

反转无脑 2-SAT 就对了。

[CTSC2008] 网络管理

没有水平题。

先整体二分一下,然后就是链求和。但是这样好像是 \(O(n\log ^3 n)\) 的。

所以我们考虑把所有的加法转化成子树加,然后求和是单点求和,求出的是自己到根的值,然后求个 lca 减一下就行。

这样能换成树状数组。复杂度 \(O(n\log ^2 n)\)。

标签:连边,Set,一个点,反转,Solution,然后,子树,SAT
From: https://www.cnblogs.com/cc0000/p/17524930.html

相关文章

  • nohup、setsid 与 disown 的不同之处【转】
    nohup、setsid与disown都可以用来让需要长期运行的程序在退出终端后继续在后台运行。然而它们实现这一目的的原理不同,因此使用起来也有一些不同。  退出终端时发生了什么  让我们先看看终端退出时发生什么:  当终端被挂断或伪终端程序被关掉,若终端的CLO......
  • 「Solution Set」7/3
    P4433[COCI2009-2010#1]ALADIN我们发现就是区间加一个等差数列,但是要取模后的。我们考虑加一个首项为\(A\),公差为\(B\),项数为\(n\)的等差数列,还要对\(C\)取模。那么和就是这样的:\(\sum\limits_{i=0}^{n-1}Bi+A-\lfloor\frac{Bi+A}{C}\rfloor\timesC\)然后前面两......
  • 【cs 50】lab4 & problemset4 -ing
    (1)lab4-Smileyhelpers.c#include"helpers.h"voidcolorize(intheight,intwidth,RGBTRIPLEimage[height][width]){//Changeallblackpixelstoacolorofyourchoosingfor(inti=0;i<height;++i){for(intj=0;j<width;++......
  • Inno setup 脚本判断 Microsoft Visual C++ Redistributable 不同版本区别
    有个需要是需要在安装包安装初始化时安装MicrosoftVisualc++2013Redistributable也就是判断软件安装前需不需要运行vcredist_x64.exe和VC_redist.x64.exe这两个程序第一反应就是可以通过注册表判断是否已经安装过环境但测试发现需求的两个版本不同,注册表位置竟然也不......
  • superset(二)基本使用详细示例以及superset权限控制介绍
    Superset系列文章superset(一)详细部署步骤(python3.7.15、windows11)及验证异常处理superset(二)基本使用详细示例以及superset权限控制介绍(文章目录)本文简单的介绍了superset的基本使用步骤的示例,以及superset的权限控制。本文部分数据来源于互联网。本文分为2个部分,即通......
  • django.db.models.query.QuerySet格式的数据输出
    1、deffindmtm2(request):importserializerimportjson#多对多跨表正向查询#res=softlist.objects.filter(hostlists__ip="10.116.6.177").values("softname")res2=softlist.objects.filter(hostlists__ip="10.116.9.233"......
  • 如何在JavaScript中使用Promise.allSettled()
    您是否曾经在JavaScript中使用过Promise,并且当有人拒绝并毁掉一切时感到沮丧?你编写了一些基于Promise的代码,一切都进展顺利,然后繁荣——一个小小的Promise被拒绝,整个链条就会崩溃。你的代码逐渐停止,你想知道为什么JavaScript不能忽略这个小问题并继续它的快乐之路。好......
  • Illiquid asset
    Definitionof'Illiquid'Thestateofasecurityorotherassetthatcannoteasilybesoldorexchangedforcashwithoutasubstantiallossinvalue.Illiquidassetsalsocannotbesoldquicklybecauseofalackofreadyandwillinginvestorso......
  • Definition of 'Cash Settlement( versus physical delivery of the reference obliga
    Definitionof'CashSettlement(versus physicaldeliveryofthereferenceobligation)Asettlementmethodusedincertainfutureandoptioncontractswhereby,uponexpiryorexercise,thesellerofthefinancialinstrumentdoesnotdelivertheactual......
  • Linux Subreaper 机制及内核态逃离方法(PR_SET_CHILD_SUBREAPER, prctl, systemed)
    PS:要转载请注明出处,本人版权所有。PS:这个只是基于《我自己》的理解,如果和你的原则及想法相冲突,请谅解,勿喷。环境说明  无前言  由于某些其他的原因,我们在测试另外一个问题的时候发现了一个奇怪的现象:在我们一直朴素的认知下,如果一个程序创建了parent-process和child-......