洛谷P3810（陌上花开）（三维偏序，cdq分治） 题目链接：传送门  思路：  PS：cdq是一种思路，因为最早是被陈丹琦引入国内的，所以就叫 cdq 分治了。  本题中的三维偏序可以取等号，所以需要注意（a,b,c）相等的情况。这时不能定义顺序，所以我们记录该元组的数量即可。 对于每个元组，我们先记录严格小于(a,b,c)元组的数量，再加上与之相等元组的数量就是这个小于等于指这个元组答案。 所以我们先将所有元组按a，b，c分别为第一，第二，第三关键字进行从小到大排序。那么对于第i个元组，严格小于这个元素的元组只会在      i    i   i 左边。然后进行cdq分治。 对于区间   ...

codeforces 1214E.Petya and Construction Set（构造） 题目链接：传送门 题意：     现在有     2   ∗   n    2*n   2∗n个顶点，并且给一个长度为     n    n   n的数组     d   [   ]    d[]   d[]，让我们构建一颗树，满足树上顶点     2   ∗   i   −   1    2*i-1   2∗i−1与顶点     2   ∗   i    2*i   2∗i之间的距离为     d   [   i   ]    d[i]   d[i]。对于结果输出     2   ∗   n   ...

codeforces 1207F. Remainder Problem(平方启发) 题目链接：传送门 题意： 现在有一个大小为500000的数组，初始每个元素都为0，索引从1开始，现有两个操作： 1 x y–代表将索引为x的元素值加y 2 x y–代表求数组中所有索引满足取余x等于y的的元素值和。 思路： 对于每个查询如果采用暴力的方式话时间复杂度为     O   (   N   /   x   )    O(N/x)   O(N/x)，其中N为数组大小。这对x较大的时候可以使用这种方法。 对于      x    x   x 较小时，假设      x   ≤   K    x\le K ...

题目链接： Let Them Slide 题意： 现有n行w列的墙,每行有一排连续方块，一排方块可以左右连续滑动，且每个方块都有一个价值，第i 列的价值定义为这列的方块的价值和。求1到w列中每列的最大价值。注：如果一个位置没有方块，那么这个位置的价值为0 思路：  我一直没想到可以这样实现，颠覆了我当时混乱的思想。       对于第      i    i   i 行的第      j    j   j 个方块，如果这排方块的总长度为     c   n   t    cnt   cnt，那么可以算出来该方块可以移动到     [   j   ,   w   +   j   −   c   ...

回文树/回文自动机小结  bilibili视频链接:https://www.bilibili.com/video/av25326779?from=search&seid=4331486820600953253 学习博客链接：<https://blog.csdn.net/u013368721/article/details/42100363 建议先看视频了解再看博客学习。 以下博文目的仅供自己参考复习。  ​ 回文自动机是一个两颗树的森林，两棵树的根分别代表偶长度回文字符串节点树的根，和奇长度回文字符串节点树的根，其中每个不同节点都代表一个不同的回文字符串，经过证明得出长度为   ...

题目链接：传送门 题意： 给出两个字符串A，B。求A的所有回文串在B中出现次数的和。 思路： 我们可以分别对A，B字符串构建一颗回文树，根据回文树的结构，我们可以同时遍历两个回文树都有的回文串节点，然后计算贡献即可。 代码： #include <bits/stdc++.h> #define mset(a,b) memset(a,b,sizeof(a)) using namespace std; typedef long long ll; typedef pair<int,int> P; const int N=2e5+100; struct PA_tree { stat...

题目链接： 传送门 题意： 一个字符串的价值为其字符串中出现字符的种类个数，现在给你一个字符串S，求S中所有回文串的价值。 思路： 我们可以构建一颗回文树，并且在构建过程记录每个回文串节点中字符种类个数。最后遍历所有不同的回文串节点统计和即可。 代码： #include <bits/stdc++.h> #define mset(a,b) memset(a,b,sizeof(a)) using namespace std; typedef long long ll; typedef pair<int,int> P; const int N=3e5+10; struct P...

以下部分参考：https://blog.csdn.net/xiamoyanyulrq/article/details/83022632  使用安装包安装： JDK官网下载地址:https://www.oracle.com/java/technologies/jdk8-downloads.html 1）：官方下载对应的.gz包: 这里以jdk-8u181-linux-x64.tar.gz为例  我们可以在Ubantu自带的Firefox浏览器下载，然后保存文件，文件默认在home的下载文件夹中  查看下载后的tar.gz文件 $ cd ~/下载  这里 ~指的是home目录,cd ~/下载 指进...

使用JAVA语言Swing进行GUI程序设计 在扫雷S项目的GUI设计中主要遇到了一下问题并且解决。  怎么在JDIalog对象中添加组件 怎么自定义容器中组件的位置和大小 在设定了布局管理器的容器中怎么控制某一块的高度或者宽度 怎么返回一个指定大小的ImageIcon对象 怎么给按钮设置三种（四种状态的Icon） 怎么给窗口设置半透明   注：大多数查找API文档和从网络论坛中查找较为方便  1.怎么在JDIalog对象中添加组件 向对话框JDialog对象中组件只能通过添加一个JPanel，在JPanel中添加组件即可。  参考博客：https://blog.csdn.net/xietan...

Game HDU - 6669(思维+DP) 题目链接：HDU - 6669  思路： ​ 对于区间     [   a   ,   b   ]    [a,b]   [a,b]，关键点有     a   ,   a   +   1   ,   b   −   1   ,   b    a,a+1,b-1,b   a,a+1,b−1,b。我们首先处理出所有区间的关键点，然后去重。容易知道，对于每个任务完成的位置一定在某个区间的关键点上。 ​ 那么我们用     d   p   [   i   ]   [   k   ]   ​    dp[i][k]​   dp[i][k]​代表站在关键点  ...

欧拉降幂（扩展欧拉定理）  前言：之前+看过欧拉降幂，但误以为gcd(a,mod) > 1也能之间加上phi(mod), 在一次网络名额赛中有道裸欧拉降幂，接下来就是自己写着只有理论上的欧拉降幂来写题，硬搞了4个小时才A了。本想着不能在一个地方失败两次来写了这篇博客。  附上公式：  当     b   <   p   h   i   (   m   )   ​    b<phi(m)​   b<phi(m)​时，      a   b    %   m   =    a   b    %   m   ​    a^b\%m=a^b\%m​   ab%m...

洛谷P2624 [HNOI2008]明明的烦恼（Prufer序列+组合数学） **题目：**给你n个节点的树中某些节点的度数，其他节点的度数任意，问有多少种满足题意的树。 思路： ​ 假设给出n个节点的K个节点度数确定，且分别为      d   1    ,    d   2    ,    d   3    .   .   .    d   k    ​    d_1,d_2,d_3...d_k​   d1​,d2​,d3​...dk​​。我们令      a   i    =    d   i    −   1    a_i=d_i-1   ai​=di​−1, 且设     s   u...

Prufer序列（无根树与序列的互相转化及其性质） 什么是Prufer序列？ Prufer序列是将一个带有节点编号的无根树转化为一个序列的过程，且每一个无根树唯一的确定一个prufer序列。反过来也成立。  Prufer序列的性质  原树中顶点      v    v   v 的度数     −   1   =    - 1=   −1= 序列中顶点v的出现次数 n个顶点的无根树的Prufer序列的长度为n-2 一个Prufer序列与一个无根树一一对应   将无根树转化为Prufer序列 方法： 一棵树要得到普吕弗序列，方法是逐次去掉树的顶点，直到剩下两个顶点。考虑树T，其顶点为{1, 2, ...

POJ 2942(点双连通分量+无向图判奇环) 题目链接：传送门 题意：  来自kuangbin模板  POJ 2942 Knights of the Round Table 亚瑟王要在圆桌上召开骑士会议，为了不引发骑士之间的冲突， 并且能够让会议的议题有令人满意的结果，每次开会前都必须对出席会议的骑士有如下要求： 1、 相互憎恨的两个骑士不能坐在直接相邻的2个位置； 2、 出席会议的骑士数必须是奇数，这是为了让投票表决议题时都能有结果。 注意：1、所给出的憎恨关系一定是双向的，不存在单向憎恨关系。 2、由于是圆桌会议，则每个出席的骑士身边必定刚好有2个骑士。 即每个骑士的座位两边都必定各有一...