- 2024-08-182024百度之星决赛部分题解(难度排序前六题)
前言手速6题,可惜第四题磨了几个小时没磨出来,多做一题就金了,还是实力差了点,最后银牌前列。下面的题解是根据代码回忆大概的题意,主要是给出来赛时的参考代码A.状压题意:学校集训队总的有\(n\)个人,保证\(n\)是3的倍数,每个人有个人实力\(a_i\),每两个人之间有配合程度\(b_{i
- 2024-08-18并查集(保姆级讲解)
文章目录什么是并查集查找合并例题代码什么是并查集并查集是一种树形的数据结构。支持两种操作**查找:**确定某个元素在那个集合**合并:**将两个集合的元素合并在一起查找1.朴素查找2.优化查找合并1.朴素合并2.优化合并因为朴素合并的时间复杂度已经
- 2024-08-18P4689 [Ynoi2016] 这是我自己的发明 与 P5268 [SNOI2017] 一个简单的询问0
思路:首先可以先考虑没有换根的情况。先将树拍到dfn序上,那么一个子树\(u\)的所有点的dfn序区间为\([dfn_u,dfn_u+siz_u-1]\)。那么询问变为:每次给定两个区间\([l_1,r_1],[l_2,r_2]\),对于在第一个区间内的点\(x\)和在第二个区间的点\(y\),若\((x,y)\)有贡献,当且仅
- 2024-08-18字符串(长期)
字符串序言字符串说实话我不算是很擅长,但是我还是想写一点东西。字符串是一种存储字符的数据结构,本身来说这个并不难,但是因此也拓展出了非常非常多的算法。很多人学习字符串的基本算法时就被劝退了,但殊不知这只是字符串的起点。所以,坚持地学习下去吧,等你有一天层次高了后,你会
- 2024-08-17ABC 367 题解
AtCoderBeginnerContest367题解:\(Problem\hspace{2mm}A-Shout\hspace{2mm}Everyday\)题目链接opinion:~~code:#include<bits/stdc++.h>#definelllonglong#definepiipair<int,int>usingnamespacestd;lla,b,c;intmain(){ i
- 2024-08-17Trie树,字典树
题目链接字典树的介绍字典树也叫(Trie树),字典树有插入和查询两个操作,我们先假设我们已经插入了单词be、fake、beef、face这几个单词,那么我们可以建树。当我们查询be、fa、fAKe、fac时,答案分别为:\(2,2,0,1\)。字典树的插入我们可以给树上的每个节点标号,比如上面的树,可标为:
- 2024-08-17如何让你的C语言程序打印的log多一点色彩?(超级实用)
接着上一篇文章《由字节对齐引发的一场“血案“》在平常的调试中,printf字体格式与颜色都是默认一致的。如果可以根据log信息的重要程度,配以不同的颜色与格式,可以很方便的查找到要点。1、printf字体显示语法说明printf(“\033[显示方式;字体颜色;背景颜色m字符串\033[0m”)
- 2024-08-16了解一下宏定义#define吧c++
在C++中,宏定义是通过 #define 指令实现的,它用于创建符号常量或宏函数。这是一种预处理指令,意味着它在编译之前被处理。下面是宏定义的用法、理解和重点。宏的基本语法定义常量:#definePI3.14159这里,PI 是一个常量,它的值是 3.14159。在代码中每次使用 PI 时,编译器
- 2024-08-16CSP22
题面T1放了个啥?T1读假了好几遍首先一行不能为空,一列的空位必须相邻,一列可以为空点击查看代码#include<bits/stdc++.h>#definespeed()ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);#definelllonglong#definepbpush_back#defineullunsignedlonglong
- 2024-08-162-sat 模板
2-Sat\[\begin{align*}&\LARGE\color{Red}大意:\\&有n个数a_i,m个约束条件都需要满足\\&条件形如(i,a,j,b)\quada_i=a\\text{or}\a_j=b\\\\\\&\LARGE\color{Red}思路:\\&让a_i表示0,a_{i+n}表示1\\&转换条件表达式成:\\&a_i=a\\\te
- 2024-08-16我的板子
读写优化优化一#ifdef_WIN32 #definegetchar_getchar_nolock #defineputchar_putchar_nolock#else #definegetchargetchar_unlocked #defineputcharputchar_unlocked#endiftemplate<typenameT>inlinevoidrd(T&x){ x=0;intf=1;charch=ge
- 2024-08-16「杂题乱刷2」CF1183E & CF1183H
vp到的。题目链接CF1183ESubsequences(eazyversion)CF1183HSubsequences(hardversion)解题思路考虑动态规划。设\(dp_{i,j}\)表示考虑到字符串前\(i\)个字符中选取的字符长度为\(j\)的不同的子序列数量。于是我们就有以下转移:\(dp_{i,j}=dp_{i-1,j}+dp_{
- 2024-08-16主席树做题记录
主席树做题记录。主席树,即可持久化权值线段树。P3248[HNOI2016]树难爆了这题。题目中会多次把模板树的某个子树放到大树上的某个节点下,我们把这一整个子树看作一个大节点,把模板树、大树分别维护。具体的,模板树上需要倍增维护两点之间的距离,dfs序。大树上需要维护:大树上
- 2024-08-16[AGC064C] Erase and Divide Game
link感觉题解说的都很不清晰,这里只谈个人理解。考虑操作的本质是什么,两人从低到高确定二进制下的每一位填的数,并且场上只保留对应后缀的数字,当场上没有数字时当前操作者输。设\(f[i,S]\)表示确定了前\(i\)位,填的数为\(S\),接下来先手是否能赢,那么有\(f[i,S]=\neg(f[i
- 2024-08-16P6805 [CEOI2020] 春季大扫除
思路:首先随意钦定一个不是叶子节点的节点为根节点。然后考虑对于一个不是根节点的点\(u\),肯定需要至少一个叶子去与\(u\)子树之外的叶子节点配对。考虑\(u\)到\(fa_u\)的这条边,首先至少有一个叶子节点穿过,然后设\(p_u\)表示\(u\)中的叶子节点个数:若\(p_u\)为偶
- 2024-08-15C语言学习--常量
提示:在程序设计中,常量是一个至关重要的概念。目录前言4.1基本介绍4.2经常使用的常量4.2.1整数常量4.2.2浮点常量4.2.3字符常量4.2.4字符串常量4.2.5案例演示4.3常量的定义4.3.1定义常量的两种方式4.4#define预处理器4.5const关键字4.6const和#defin
- 2024-08-15暑假集训csp提高模拟21
赛时rank47,T120,T20,T330,T445赛时最后想到了T1的正解,可惜没有打出来。整场比赛都在死磕T1的神秘构造,导致本来可以AC的T2没有写,开题的策略不行,太容易死磕了。T1黎明与萤火DestructionofaTree贪心构造。先给一组数据Input:501234Output:YES24135
- 2024-08-15CSP21
总结:两个题的checker我都自己写了一个,MD,耽误太多时间了,\(Linux\)的\(checker\)使用要加g++checker.cpp-o程序名这题,性质题,首先发现一个树\(n-1\)条边,每次删偶数条边,所以\(n\)必须是奇数,其次我们发现优先删去深度深的点较为优,删完后,我们发现还剩下一些散点散树,再\(dfs\)一
- 2024-08-15C语言最后一讲——预处理超详解
文章目录1.预定义符号2.`#define`定义常量3.`#define`定义宏4.带有副作用的宏参数5.宏替换的规则6.宏函数的对比7.#和##7.1#运算符7.2##运算符8.命名约定9.`#undef`10.命令行定义11.条件编译12.头文件的包含12.1头文件被包含的方式:12.1.1本地文
- 2024-08-14D43 2-SAT+前缀优化 P6378 [PA2010] Riddle
视频链接: P6378[PA2010]Riddle-洛谷|计算机科学教育新生态(luogu.com.cn)//2-SAT+前缀优化O(n+m)#include<iostream>#include<cstring>#include<algorithm>usingnamespacestd;#definex0(x)x//点#definex1(x)x+n//反点#definep0(x)x+2*n
- 2024-08-14ARC125E Snack
小清新网络流优化题首先不难想到一个trivial的网络流模型,即建立源点\(S\)和汇点\(T\)对于每个食物\(i\),连\(S\toi\),容量为\(A_i\)的边;对于每个人\(j\),连\(j\toT\),容量为\(C_j\)的边;同时所有食物向每个人\(j\)连容量为\(B_j\)的边直接跑Dinic复杂度显然爆
- 2024-08-14CF1528C Trees of Tranquillity
小清新找性质题,想到关键就很简单考虑在第一棵树上枚举一条从\(1\)到某个点的链,显然这些点之间满足第一个限制,现在只要在这些点中选出尽可能多的点满足第二个限制即可在第二棵树上两个点没有祖先关系,等价于它们对应的DFS序区间相离而两个点的DFS序区间显然要么相离要么包
- 2024-08-13CF1943C Tree Compass
思路:考虑往直径方向想,设直径的长度为\(d\)。首先可以注意到一个性质:每次操作最多只会覆盖住直径的\(2\)个点,那么答案的下界即为\(\lceil\frac{d}{2}\rceil\)。分类讨论一下。若\(d\)为奇数,则存在唯一的一个直径中心\(u\):那么答案为\((u,0),(u,1),\cdots,(u,\l
- 2024-08-13字符串算法
KMP算法前言update2024.7.31今天重写了一篇KMP板子,之前是蒟蒻(现在也是),写的都是什么鬼,甚至没过模板题。感觉KMP优化没什么用,但是暂时保留吧。简介用模式串匹配文本串(主串)。对于一个模式串,找出每个位置的border(最长相等的前缀后缀),即为\(next\)数组。失陪时就跳到bord
- 2024-08-13基础知识
编译器用大括号给数组赋初始值就会导致编译出来的exe文件包含这个数组的空间。简单来说就是inta[N]={};会让可执行文件不运行的时候也占据这个数组的内存,会导致编译出来的可执行文件过大。因此大的数组不要用大括号赋初值。关键字template函数模板C++中的模板特性会