- 博客(64)
- 收藏
- 关注
RSS订阅原创 树上问题
A - BZOJ5314 潜入行动树形dpdp[u][0-k][0/1][0/1]第一维是节点编号第二维是已使用的灯的数量第三维表示当前节点是否有灯第四维表示当前节点是否被点亮处理子节点时相当于做了前缀和优化，tmp表示对于同一父节点当前子节点前所有其他子节点处理完后的结果。这样每个子节点处理的复杂度为O(k2)O(k^2)O(k2)#include<bits/stdc++.h>using namespace std;const int maxn=1e5+10;const
2021-02-20 22:50:48
142
原创 计算几何 2020牛客暑期多校训练营（第二场） B Boundary
计算几何题意：给n个点，一个圆边界过(0,0),求使这个圆边界过n各店中尽可能多的点，求最多过的点数。解法：对所有点与(0,0)做中垂线，对于每条中垂线分别求与其他中垂线的交点，答案为做多交点数+1。#include<bits/stdc++.h>using namespace std;const int maxn=2e3+10;struct point{ double x,y; point(){} point(double _x,double _y){
2020-07-14 01:03:32
185
原创 一般图最大匹配 带花树 2020牛客暑期多校训练营（第二场）I 1 or 2
一般图最大匹配 带花树 2020牛客暑期多校训练营（第一场）I 1 or 2标签（空格分隔）： 一般图最大匹配kuangbin的模板https://www.cnblogs.com/kuangbin/p/3278621.html求一般图最大匹配，这道题的难点在于建图，把每个节点分成它的度个节点，把每条边分成两个节点，之后对于每条边，两个边分成的节点相连，边的两个端点的节点分别与其端点分成的度个节点相连之后求最大匹配，如果为完美匹配，则为Yes，否则No。对于完美匹配，若一个边的一个端点不与由点分解的
2020-07-13 22:35:35
147
原创 微积分 2020牛客暑期多校训练营（第二场）J Easy Integration
微积分 2020牛客暑期多校训练营（第二场）J Easy Integration标签（空格分隔）： 微积分微积分用Beta函数很好求。一开始用分步积分来做的，但是做到一半没有继续做下去，属实不应该。用三角函数和分部积分也可以解推导过程可参考https://blog.csdn.net/weixin_45539557/article/details/107305843#include<bits/stdc++.h>using namespace std;typedef long l
2020-07-13 21:38:07
119
原创 置换 2020牛客暑期多校训练营（第二场）J Just Shuffle
置换 2020牛客暑期多校训练营（第二场）J Just Shuffle标签： 置换 JAVA大数 逆元 快速幂题意：A为一个置换，Ak=PA^k=PAk=P,k是素数，求AP一定在A生成的循环群中，设Ax=PA^x = PAx=PAxk=AA^{xk} = AAxk=A设A的周期为mxk≡1(modm)xk\equiv1\pmod mxk≡1(modm)x为k对于A周期的逆元之后快速幂求AxA^xAximport java.math.BigInteger;import java.uti
2020-07-13 18:37:30
153
原创 单调队列 2020牛客暑期多校训练营（第二场）F Fake Maxpooling
实现最大池化其实就是单调队列的滑动窗口，从一维到二维只是多求了一遍而已。滑动窗口算法的关键在于用双端队列维护当前窗口内的值和位置，保持值单调，队首位置在窗口以外的移出队列，纸样就可以保证队首一直是当前窗口内的最值,复杂度O(mn)。#include<bits/stdc++.h>using namespace std;typedef long long ll;const int maxn=5e3+10;int mat[maxn][maxn];int mat_second[maxn
2020-07-13 18:25:58
116
原创 COGS 2479. [HZOI 2016]偏序 CDQ分治套CDQ分治解决四维偏序问题
四维偏序裸题给定一个有n个元素的序列，元素编号为1~n，每个元素有三个属性a,b,c，求序列中满足i<j且ai<aj且bi<bj且ci<cj的数对(i,j)的个数。两篇题解题解一第二篇是CDQ的归并排序的写法题解二关键点在于第二层要处理的是234维，按第二维排序，第三维CDQ，第四维树状数组，第二层CDQ与普通CDQ的不同之处仅在于不仅要判断第三维的大小关系，还要判断第一维的大小关系。#include<bits/stdc++.h>#define lowbi
2020-07-10 09:32:06
202
原创 P3157 [CQOI2011]动态逆序对
题目描述现在给出 1∼n 的一个排列，按照某种顺序依次删除 m 个元素，你的任务是在每次删除一个元素之前统计整个序列的逆序对数。输入格式第一行包含两个整数 n和 m，即初始元素的个数和删除的元素个数。以下 n 行，每行包含一个 1∼n 之间的正整数，即初始排列。接下来 m 行，每行一个正整数，依次为每次删除的元素。输出格式输出包含 m 行，依次为删除每个元素之前，逆序对的个数。CDQ分治求解动态逆序对，即在有删除操作的情况下求逆序对数，出坐标、数值外，把时间作为第三个维度，即可转换为三维偏序
2020-07-10 01:54:58
221
原创 AT1219 [JOI2013]歴史の研究
回滚莫队题目描述IOI国历史研究的第一人——JOI教授，最近获得了一份被认为是古代IOI国的住民写下的日记。JOI教授为了通过这份日记来研究古代IOI国的生活，开始着手调查日记中记载的事件。日记中记录了连续N天发生的时间，大约每天发生一件。事件有种类之分。第i天(1<=i<=N)发生的事件的种类用一个整数Xi表示，Xi越大，事件的规模就越大。JOI教授决定用如下的方法分析这些日记：1.选择日记中连续的一些天作为分析的时间段2.事件种类t的重要度为t×(这段时间内重要度为t的事件数)
2020-07-09 18:43:39
268
原创 SP10707 COT2 - Count on a tree II
树上莫队题目描述给定一个n个节点的树，每个节点表示一个整数，问u到v的路径上有多少个不同的整数。输入格式第一行有两个整数n和m（n＝40000，m＝100000）。第二行有n个整数。第i个整数表示第i个节点表示的整数。在接下来的n-1行中，每行包含两个整数u v，描述一条边（u，v）。在接下来的m行中，每一行包含两个整数u v，询问u到v的路径上有多少个不同的整数。输出格式对于每个询问，输出结果。参考题解莫队其实树上莫队和树链剖分的思想是一样的，就是把树映射到，正常的dfs序，使得每棵
2020-07-09 17:23:16
139
原创 luoguP1903 [国家集训队]数颜色 / 维护队列
带修改莫队经典题目关于莫队的一篇很好的blog题目描述墨墨购买了一套N支彩色画笔（其中有些颜色可能相同），摆成一排，你需要回答墨墨的提问。墨墨会向你发布如下指令：1、 Q L R代表询问你从第L支画笔到第R支画笔中共有几种不同颜色的画笔。2、 R P Col 把第P支画笔替换为颜色Col。为了满足墨墨的要求，你知道你需要干什么了吗？输入格式第1行两个整数N，M，分别代表初始画笔的数量以及墨墨会做的事情的个数。第2行N个整数，分别代表初始画笔排中第i支画笔的颜色。第3行到第2+M行，每行分
2020-07-09 15:59:37
156
2
原创 BZOJ-3262-陌上花开
问题：有n朵花，每朵花有三个属性：花形(s)、颜色©、气味(m)，又三个整数表示。现要对每朵花评级，一朵花的级别是它拥有的美丽能超过的花的数量。定义一朵花A比另一朵花B要美丽，当且仅当Sa>=Sb,Ca>=Cb,Ma>=Mb。显然，两朵花可能有同样的属性。需要统计出评出每个等级的花的数量。第一行为N,K (1 <= N <= 100,000, 1 <= K <= 200,000 ), 分别表示花的数量和最大属性值。以下N行，每行三个整数si, ci, mi (
2020-07-09 02:02:01
117
原创 HDU-6534-Chika and Friendly Pairs
2019CCPC湘潭邀请赛的C题大小为n的数组，m次查询，查询区间[l，r]内大小差距不超过k的数对的个数，可离线。m范围[1,27000],n范围[1,27000]这是一道分块+莫队+树状数组的题目将使用分块降低莫队复杂度为O(n)O(\sqrt n)O(n),用莫队+树状数组维护当前区间的答案，树状数组维护的是当前区间内每个数的数量，增加区间每加入一个数x，结果增加当前区间内[x-k,x+k]的数的个数并在树状数组中这个数的数量加一；减小区间时每去掉一个数x，树状数组中这个数的数量减一，结果减少
2020-07-09 00:52:21
268
原创 linux——文件系统高级操作
文章目录读文件的方式vi -R filenamecat filenameviewpgshell重定向输出重定向输入重定向EOFcat-A参数创建文件复制文件读文件的方式vi -R filename安装vi要占用较大存储空间cat filename不适合查看超过一页的文件view占用空间小，方便跳转翻页pg已经废弃，被less和more代替shell重定向输出重定向覆盖重定向...
2020-04-10 11:05:12
248
原创 操作系统学习笔记——第四章 互斥、同步与通讯
文章目录并发进程前驱图程序的顺序执行顺序程序特性并发程序特性程序并发执行的条件读集与写集Bernstein条件与时间有关的错误进程互斥共享变量临界区域共享变量和临界区域的表示进程互斥的定义实现互斥的要求调度原则软件实现petersom算法Dekkel算法Lamport面包店算法Eisenberg/Mcguire算法进程互斥的硬件实现硬件提供“测试并建立”指令（test_and_set)硬件提供“交...
2020-04-04 22:33:21
1559
原创 Codeforces Global Round 7
文章目录A. Bad Ugly NumbersB. Maximums题目A. Bad Ugly Numbers题目：对于给定的正整数n，构造一个整数，满足以下条件：大于0总共有n位没有任何一位等于0不被其任何一位的数字整除判断是否存在这样的整数，存在则输出该整数，不存在输出-1答案：脑筋急转弯，当n等于1时，不存在这样的数，一位数不管是什么都被他的个位整除当n>1时，...
2020-03-30 17:13:29
142
原创 DES弱密钥
先来回顾一下des的加密过程在不考虑奇偶校验的情况下DES的弱密钥共有以下8个：0x01010101010101010xFEFEFEFEFEFEFEFE0xE0E0E0E0F1F1F1F10x1F1F1F1F0E0E0E0E0x00000000000000000xFFFFFFFFFFFFFFFF0xE1E1E1E1F0F0F0F00x1E1E1E1E0F0F0F0F这些...
2020-03-27 15:58:15
7635
1
原创 操作系统学习笔记——第三章 中断与处理机调度
文章目录第三章 中断与处理机调度中断与中断系统中断的概念中断装置中断源中断字强迫性中断自愿性中断中断向量中断嵌套系统栈中断优先级中断屏蔽中断处理程序考虑系统状态的进程状态转化图程序性中断处理机调度考虑因素调度参数阵发期剥夺式调度和非剥夺式调度先到先服务算法（FCFS）短作业优先（SJF）最短剩余时间优先算法(SRTN)最高响应比优先(HRN)最高优先数算法(HPF)循环轮转算法(RR)多级队列算法...
2020-03-25 22:45:14
1679
原创 操作系统学习笔记——第二章 进程、线程与作业
文章目录第二章 进程、线程与作业多道程序设计目标单道程序设计的缺点多道程序设计的提出进程的引入定义并行和并发的区别进程状态(基本状态)状态转换进程控制块（PCB）进程的组成进程上下文切换进程的队列进程类型进程的特征进程间相互联系进程间相互作用进程的创建与撤销第二章 进程、线程与作业多道程序设计目标提高吞吐率吞吐量=作业道数全部处理时间吞吐量=\frac{作业道数}{全部处理时间}吞吐量=...
2020-03-25 20:51:58
512
原创 操作系统学习笔记——第一章 操作系统概述
教材：左万利、王英老师编著、高等教育出版社出版的《计算机操作系统》（第4版）文章目录第一章 操作系统概述第一章 操作系统概述
2020-03-25 19:02:10
434
原创 中英文情感分析模型汇总
中文BertThe code for CCF-BDCI-Sentiment-Analysis-BaselineCCF BDCI 2019 互联网新闻情感分析 复赛top8 代码讲解CCF大数据与计算智能大赛互联网新闻情感分析训练框架基于预训练模型的文本分类模板，CCF BDCI新闻情感分析初赛A榜4/2735，复赛1%CCF BDCI 2019 互联网新闻情感分析...
2020-03-21 16:28:58
4688
原创 IA32汇编语言程序设计——Virtualbox、NASM、Fixvhdwr环境搭建
文章目录VirtualBoxNASMnasmideFixvhdwr测试VirtualBox出现的问题：安装包不能运行解决方案：链接64位选amd6432位选x86进行运行然后按步骤安装即可安装时一定要选择图中给的系统和版本，不要装成别的这里的位置选择它默认给的就好了，不然后面写磁盘时可能会出错。NASM出现的问题：出现此问题的原因主要有两个：路径错误没有写...
2020-03-17 02:57:06
1996
2
原创 Codeforces Round #627 (Div. 3)
文章目录A Yet Another Tetris ProblemB Yet Another Palindrome ProblemC Frog JumpsD Pair of TopicsE Sleeping ScheduleF Maximum White Subtree题目A Yet Another Tetris Problem问题：俄罗斯方块，只能用宽为1，高为2的木块，给初始高度，问是否可...
2020-03-15 22:32:32
226
原创 Codeforces Round #628 (Div. 2)
文章目录A EhAb AnD gCdB CopyCopyCopyCopyCopyC Ehab and Path-etic MEXsD Ehab the Xorcist提莫A EhAb AnD gCdB CopyCopyCopyCopyCopyC Ehab and Path-etic MEXsD Ehab the Xorcist
2020-03-15 01:13:23
206
原创 The 2017 North America Qualification Contest
文章目录A Birthday CakeB Bumped!C Canonical Coin SystemsD Cat and MiceE Company PicnicF GlitchBotG Greeting CardH Imperfect GPSI Odd GnomeJ Progressive ScrambleK Space ProbeL Suspension BridgesM Umbral De...
2020-03-15 01:07:54
320
原创 Educational Codeforces Round 83 (Rated for Div. 2)
文章目录A - Two Regular PolygonsB - BogosortC - Adding PowersD - Count the ArraysE - Array Shrinking提莫A - Two Regular Polygons问题：判断能否通过对正n边形选取m个顶点，形成中心重合且顶点为选取的m个点的正m变形答案：判断n是否整除m即可，是则YES，否则NO。#inclu...
2020-03-10 23:16:29
201
原创 CodeCraft-20 (Div. 2)
文章目录A - Grade AllocationB - String ModificationC - Primitive PrimesD - Nash MatrixE - Team BuildingA - Grade Allocation#include<bits/stdc++.h>using namespace std;typedef long long ll;int ma...
2020-03-08 01:22:58
171
原创 Codeforces Round #625 (Div. 2, based on Technocup 2020 Final Round)
文章目录A - Contest for RobotsB - Journey PlanningC - Remove AdjacentD - Navigation SystemA - Contest for Robots#include<bits/stdc++.h>using namespace std;typedef long long ll;int a[1001],b[100...
2020-03-04 18:03:23
123
原创 Codeforces Round #624 (Div. 3)
文章目录A - Add Odd or Subtract EvenB - WeirdSortC - Perform the ComboD - Three IntegersE - Construct the Binary TreeF - Moving PointsA - Add Odd or Subtract Even#include<bits/stdc++.h>using name...
2020-02-25 14:10:42
106
原创 Codeforces Round #621 (Div. 1 + Div. 2)
文章目录A - Cow and HaybalesB - Cow and FriendC - Cow and MessageD - Cow and FieldsA - Cow and Haybales#include<bits/stdc++.h>using namespace std;typedef long long ll;int main(){ ll t; ...
2020-02-23 23:31:48
113
原创 Codeforces Round #620 (Div. 2)
文章目录ABCDEA#include<bits/stdc++.h>using namespace std;typedef long long ll;int main(){ ll x,y,a,b; ll t; cin>>t; while(t--){ cin>>x>>y>>a>&...
2020-02-22 23:42:33
91
原创 Codeforces Round #619 (Div. 2)
题目A - Three Strings#include<bits/stdc++.h>using namespace std;typedef long long ll;int main(){ int t; cin>>t; while(t--){ string a,b,c; cin>>a>&g...
2020-02-21 19:29:09
138
原创 Codeforces Round #618 (Div. 2)补题
A - Non-zero#include<bits/stdc++.h>using namespace std;typedef long long ll;const ll maxn=2e5+10;ll a[maxn];int main(){ ll t; scanf("%lld",&t); while(t--){ ll n; ...
2020-02-20 20:50:40
92
1
原创 Educational Codeforces Round 82 (Rated for Div. 2)补题
A - Erasing Zeroes#include<bits/stdc++.h>using namespace std;typedef long long ll;int main(){ ll t; cin>>t; while(t--){ string s; cin>>s; ll f...
2020-02-20 20:07:55
129
原创 Codeforces Round #617 (Div. 3) Editorial
文章目录A - Array with Odd SumB - Food BuyingC - Yet Another Walking RobotD - Fight with MonstersE1 - String Coloring (easy version)E2 - String Coloring (hard version)F - Berland Beauty题解A - Array with ...
2020-02-05 18:35:21
181
原创 Codeforces Round #616 (Div. 2)补题
文章目录A - Even But Not EvenB - Array SharpeningC - Mind ControlD - Irreducible Anagrams题目A - Even But Not Even#include<bits/stdc++.h>#define de(x) cout<<#x<<' = '<<x<<e...
2020-02-03 18:48:37
119
原创 Educational Codeforces Round 81
文章目录A - Display The NumberB - Infinite PrefixesC - Obtain The StringD - Same GCDsE - Permutation SeparationA - Display The Number#include<bits/stdc++.h>#define de(x) cout<<#x<<' ...
2020-01-30 18:56:49
135
原创 Educational Codeforces Round 72 (Rated for Div. 2)
文章目录A - Creating a CharacterB - Zmei GorynichC - The Number Of Good SubstringsD - Coloring EdgesE - Sum Queries?F - Forced Online Queries Problem题目A - Creating a Character#include<bits/stdc++.h&...
2020-01-25 22:04:37
99
原创 Codeforces Round #590 (Div. 3)补题
文章目录A - Equalize Prices AgainB - Social NetworkC - PipesD - Distinct Characters QueriesE - Special PermutationsF - Yet Another Substring Reverse题目A - Equalize Prices Again#include<bits/stdc++.h&...
2020-01-25 20:25:53
106
空空如也
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人