- 2024-08-19快读模板(QAQ)
#include<bits/stdc++.h>usingnamespacestd;#defineint__int128#defineendl'\n'#defineiosios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);constintN=2e5+5;constintC=2e3+5;constintinf=0x3f3f3f3f3f3f3f3f;int
- 2024-08-19分块 and 莫队
分块一种暴力的数据结构,十分朴素的做法。能够处理许多问题。基础分块例\(1\):P3372【模板】线段树1经典老题,这次使用分块做法。我们将整个序列分为若干大小为\(T\)的块,记录其块的和和懒标记,对\([l,r]\)进行操作时,设左边界\(l\)位与块\(q\),左边界\(r\)位与块\(p\)
- 2024-08-19题解:AT_abc367_c [ABC367C] Enumerate Sequences
大致题意让你按照字典序输出一些长\(n\)的序列,序列中的数字有范围,且序列和需要为\(k\)。分析直接深搜。搜索的时候对从第一个元素开始,每个元素从小到大枚举所有可能的值,这样就保证答案按照字典序升序排列。用一个vector存储序列,到达边界之后计算一遍和,判断是否满足条件,然
- 2024-08-18P10660 BZOJ2759 一个动态树好题 题解
从题目名字看出此题需要用动态树解决对于任意\(i\),都有唯一的\(p_i\)与之对应,由\(p_i\)向\(i\)连边,\(n\)种关系显然构成一基环树森林。对于环上的节点,一个点可以自己表示自己,所以可以直接解出该点的权值,其他点从环上的点直接推出即可。考虑如何动态维护这个过程,一个点上
- 2024-08-18P10238 [yLCPC2024] F. PANDORA PARADOXXX
这里主要是了解一下套路,首先说一下树的直径的性质。1.任何一个点到它所在的联通块中距离最远的点一定是树的直径两点之一。2.两个连通块合并以后,新的树的直径一定为原先两个连通块中树的直径中的两个。了解完这个,我们来看这道题,根据树的直径的性质,我们可以来维护连通块,那一个
- 2024-08-18题解:AT_abc367_d [ABC367D] Pedometer
首先肯定要单层循环枚举元素,然后想方法求出一个元素的所有答案。一开始我写了一个二分找\(m\)倍数的方法,发现\(m\)小的时候还不如暴力。于是联想到之前做过的一道题,可以借助于取模的前缀和数组。对于当前元素\(i\),如果一个元素之前的前缀和与\(i\)之前的前缀和对\(m\)
- 2024-08-18线段树模板,洛谷原题P3373
线段树区间乘、加,范围求和,QWQ原题#include<bits/stdc++.h>#definePIIpair<int,int>#defineintlonglong#defineDBdoublenamespaceFastIO{ inlineintread(intMOD,int&ret){ charch=getchar();intngtv=1; if(MOD==0){while(ch<
- 2024-08-18字符串(长期)
字符串序言字符串说实话我不算是很擅长,但是我还是想写一点东西。字符串是一种存储字符的数据结构,本身来说这个并不难,但是因此也拓展出了非常非常多的算法。很多人学习字符串的基本算法时就被劝退了,但殊不知这只是字符串的起点。所以,坚持地学习下去吧,等你有一天层次高了后,你会
- 2024-08-17【模板】数据结构
数据结构权值BIT上二分struct{intn,t[N]; intkth(intk){ intp=0;rFor(i,__lg(n),0)if(p+(1<<i)<n&&k>t[p+(1<<i)])p+=1<<i,k-=t[p]; returnp+1; }};zkw线段树李超线段树线段树合并,分裂可持久化\(01
- 2024-08-17『模拟赛』暑假集训CSP提高模拟23
Rank玩蓝图玩的A.进击的巨人(原题都是牛客的,没号所以不挂了)赛事看到概率期望一眼润,但是又可惜暴力分,遂打(最坏情况下)\(\mathcal{O(n^2)}\)暴力,结果很给力啊,调出来小样例后大样例嗖的一下就过了,惊喜了属于是,喜提100pts。事实上跑这么快是因为0的数量很平均,导致复杂度大
- 2024-08-17stm32 printf 重定向问题
最终解决方案新建一个stm32_printf.h头文件,在main.c中include#ifndefSTM32_SPIDMA_MODE_STM32_PRINT_H#defineSTM32_SPIDMA_MODE_STM32_PRINT_H#include"stm32f1xx_hal.h"#include"string.h"externUART_HandleTypeDefhuart1;voidprint_f(char*str){
- 2024-08-17P10886 【MX-S3-T2】「FeOI Round 1」Journey 题解
我们肯定是要先求出来一个位置被加的次数,然后和权值乘一下就行。对于一个位置\(i\),右端点\(b\)肯定是随便选,一共\(n-i+1\)种情况。再是对于每一种步长\(c\),左端点\(a\)都有\(\left\lceil\dfrac{i}{c}\right\rceil\)种取值,暴力计算,时间复杂度\(O(n^2)\)。(提交记录)考虑
- 2024-08-17[考试记录] 2024.8.17 csp-s模拟赛21
T1Set解析思考+组合题场上只能想到暴力01背包再加上bitset优化,很好打。本应该有60pts(?或者更多),不曾想由于spj的一些未知原因喜提systemerror,全部cancelled。喜提0pts。
- 2024-08-17P10888 【MX-S3-T4】「FeOI Round 1」醒餞の鳥 (feat. Feryquitous) 题解
话说这题真的有紫吗(问号注意到数据范围中提到$\sum{nm}\le2\times10^5$,这里实际上是隐含了\(\min(n,m)\le\sqrt{2\times10^5}\)的。我们考虑根据\(n\)和\(m\)的大小关系设计出不同的算法。\(m<n\)一个比较直接的想法是对于每一个科目先按该科目的分数排序,这样
- 2024-08-172024杭电多校第九场
1007简单博弈,队友做的#include<bits/stdc++.h>usingnamespacestd;constintN=2e5;intn,a[N+5],b[N+5],A,B;boolvis[N+5];inlineintread(){intx=0;boolf=1;charch=getchar();for(;ch<'0'||ch>'9';ch=getchar())f^=(ch==
- 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-16『模拟赛』暑假集训CSP提高模拟22
Rank非常好重测,使我Rank--A.法阵原[CF1503E]2-Coloring出题人注:原题3100,张口放T1一眼高难度题,于是果断开始暴力打表,但我的打表程序十分暴力,跑\(n=6,m=9\)的点就已经开始硬控了,遂只拿到30pts。打表就不用放了吧,等我咕咕正解。B.连通块同[yLCPC2024]F.PANDORA
- 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主席树做题记录
主席树做题记录。主席树,即可持久化权值线段树。P3248[HNOI2016]树难爆了这题。题目中会多次把模板树的某个子树放到大树上的某个节点下,我们把这一整个子树看作一个大节点,把模板树、大树分别维护。具体的,模板树上需要倍增维护两点之间的距离,dfs序。大树上需要维护:大树上
- 2024-08-168.16 PTA练习
7-1-11装箱问题假设有N项物品,大小分别为s1、s2、…、si、…、sN,其中si为满足1≤si≤100的整数。要把这些物品装入到容量为100的一批箱子(序号1-N)中。装箱方法是:对每项物品,顺序扫描箱子,把该物品放入足以能够容下它的第一个箱子中。请写一个程序模拟这种装箱过程,
- 2024-08-16zkw线段树
事情的起因是我某天吃晚饭时打算找个电子榨菜,然后b站搜索线段树,看到了一个名叫zkw线段树(即非递归线段树),由于不是面向Oier的,所以饭后我又找了几个博客看,现在写下心得记录(其实只是不想在书签留3个位置给线段树)为什么要学习非递归线段树,这个问题大部分博客解释为普通线段树
- 2024-08-15『模拟赛』暑假集训CSP提高模拟21
Rank意外地还凑合,本来以为这场要GG了。A.黎明与萤火原[CF963B]DestructionofaTree签,勉强签了。开始脑子乱,胡乱打了一个含有3个dfs函数,每个函数里含两次遍历链式前向星,不负众望大样例T了。后来也是摸着摸着就出正解了,先一遍dfs跑出基本的数据,然后再一遍df
- 2024-08-15自动机合集(未完)
备注:我不知道fail会不会和什么东西重名。(因为感觉这个单词挺完整的)自动机的概念不是很清楚自动机的概念。暂且认为:自动机是一个有向图。点(状态)代表字符串(可能不止一个),边(转移)(可能)带一个字符,表示在字符串的末尾加上这个字符后到达的状态。有一个源点(PAM有两个),代表初始状态。有
- 2024-08-142024表达式求值
P06330.表达式求值Description一个数学表达式由下列元素组成:左括号,右括号,加号,减号,乘号,正号,负号,整数(无前导0)。给出一个长度不超过100的数学表达式,求它的值,要求考虑括号和乘法的优先级,计算过程中的临时值的绝对值保证不会超过整数范围。给出的表达式保证合法以及符合人的书写习
- 2024-08-14『模拟赛』暑假集训CSP提高模拟20
Rank有点可惜,暴力打满就并列Rank1了。A.Kanon原[JOI2021Final]雪玉签。考虑到每两个球之间的距离是恒不变的,因此我们可以通过找到每个球控制的边界得到答案,每个区间正好可以得出左边球的右边界和右边球的左边界。记录每个区间的标号和长度,按长度升序sort一遍,然