- 2024-08-19Big Clique Everywhere 题解
给个链接:BigCliqueEverywhere。先说一下团(clique)是什么,其实就是完全图。考虑什么情况下不满足题意。我们可以先建出补图,下面的东西都在补图中完成。我们首先给出结论:如果该图中有奇环(不是二分图),则条件不成立,否则成立。这里证明一下:如果存在奇环,则把点集设为这个奇环中的点,那
- 2023-12-08『做题记录』[AGC032B] Balanced Neighbors
[AGC032B]BalancedNeighborslink:https://atcoder.jp/contests/agc032/tasks/agc032_bDescription 给定整数\(N\),构造一个从\(1\)到\(N\)编号的\(N\)个节点的无向图,使得:该图不含有重边和自环,并且是连通的。每个节点的所有邻接节点的编号之和相同。 \(N\l
- 2023-10-26ARC099
shaberround。A显然都会变成1。枚举穿过1的那次操作在哪,剩下两边的答案直接算出来就行。B不会。C完全子图的判定,直接考虑建立补图。那么补图一定是一张二分图。染色判定。如果我们划分为了\(n=x+y\)两个大小的完全子图那么答案就是\(\frac{x(x-1)+y(y-1)}{2}\),显然
- 2023-10-24<学习笔记> 二分图
二分图最大匹配:定义:给定一个二分图\(G\),即分左右两部分,各部分之间的点没有边连接,要求选出一些边,使得这些边没有公共顶点,且边的数量最大。方法:Dinic/染色二分图的最小顶点覆盖定义:假如选了一个点就相当于覆盖了以它为端点的所有边。最小顶点覆盖就是选择最少的点来覆盖所有的
- 2023-08-16CF1648E 题解
就是\(m\)组询问补图的最小生成树上的树链最大值。有两种基本思路求这棵树。第一种,Kruskal,基于找到最小的边使两端点不连通。考虑补图中\((x,y)\)的边权,它是原图最小生成树上的树链最大值。从小到大枚举补图的边,相当于从小到大枚举原图最小生成树的边\((u,v,w)\),然后:令原图
- 2023-07-10CodeForces 1508C Complete the MST
洛谷传送门AtCoder传送门比较需要观察的题。设\(v\)为所有边权异或和。直觉是设一条未确定权值的边边权为\(v\),其他的为\(0\)最优。证明大概就是讨论MST是否全部使用未确定权值的边。若全使用了,那么根据\(\oplusw\le\sumw\)可知\(\min\sumw=\oplusw\),并且
- 2023-07-09AE 制作简单动态壁纸
成品B站链接WallpaperEngine可用:搜索Alice_StarCried简述参考了B站的两个自学教程,都是直接搜能搜到的。PS、AE零基础。因为需要渲染所用电脑配置有一定需求,额外用了数位板。AE使用了现成脚本。从学习到制作完成总用时不过四天。所需技能为PS基本使用,包括抠图、补图等,
- 2023-06-21模拟赛碎碎念
P1285队员分组模拟赛出了一道只用求较小的一个组的人数的这题。赛时编了一个时间复杂度卡满可能会被卡常的做法,大概是这样的:如果给定的图是完全图,那么答案就是\(\lfloor\frac{n}{2}\rfloor\),否则就一定存在点对\((u,v)\)满足\(u\),\(v\)之间没有边相连。将\(u\)塞进点集
- 2023-06-02codeforces Connected Components(寻找补图的连通块)
http://codeforces.com/contest/920/problem/EE.ConnectedComponents?timelimitpertestmemorylimitpertestinputoutputn verticesand edges.Insteadof