- 博客(135)
- 收藏
- 关注
RSS订阅原创 2021 CCPC威海 I. Distance （min25筛）
题目链接题意是给出n的哈斯图，求∑i∑jdis(i,j)\sum_i\sum_j dis(i,j)∑i∑jdis(i,j)，dis(i,j)dis(i,j)dis(i,j)表示iii和jjj的最短路径长度。（哈斯图为，如果x∣yx|yx∣y则有一条y−xy-xy−x的边，权值为y/xy/xy/x）解题思路：官方题解的做法非常的简约和优雅，这里记录一下推了很久常数又大的纯min25筛做法。。我们让f(i)f(i)f(i)表示iii的所有 质因数∗*∗指数 的和。例如f(12)=2∗2+3,f(4
2021-12-09 23:53:39
659
原创 1458F - Range Diameter Sum（分治+数据结构）
题目链接题意给一颗n点无根树，令D(x,y)D(x,y)D(x,y)表示编号在[x,y][x,y][x,y]的点组成的树的直径，求∑l=1n∑r=l+1nD(l,r)\sum_{l=1}^n\sum_{r=l+1}^nD(l,r)∑l=1n∑r=l+1nD(l,r)解题思路考虑分治，可以把当前[l,r]的问题分解成[l,mid]的问题和[mid+1,r]的子问题。现在考虑如何快速所有左端点在[l,mid][l,mid][l,mid],右端点在[mid+1,r][mid+1,r][mid+1,r
2021-01-21 17:42:19
321
原创 2020 CCPC(长春) B-The Tortoise and the Hare (树套树 or 整体二分)
题意给一个序列a1,a2,....ana_1,a_2,....a_na1,a2,....an，一个数字m。两种操作输入l,r,kl, r, kl,r,k，询问al,al+1…ara_l,a_{l+1}\dots a_ral,al+1…ar中，每秒前(r-1+1-k)小的数都+1，问该区间中所有数字都<m的情况最多持续几秒x,yx,yx,y，令a[x]=ya[x]=ya[x]=y一共q次操作，对于每次操作1输出答案数据范围1≤n,q≤1e5,1≤m≤1e9,ai<m1\l
2020-11-10 16:34:47
491
原创 2020 湖南省大学生程序设计竞赛(HNCPC)题解
题目来源A. 2020-substring签到题。设dp[i]为[1~i]的串有多少个连续2020，如果s[i-3,i]是“2020”那么dp[i] = max(dp[i-1], dp[i-4), 否则dp[i] = dp[i-1]B. 2020-vs-2018观察可以发现只要看有多少个被o包围的联通快即可。3个联通快就是2018否则是2020C. absolute-difference-equation这题里面的差分取绝对值运算，其实相当于是异或运算。那么可以把每一次变换后的结果写出来观察一下
2020-10-21 10:38:45
3182
原创 2019 ICPC North America Qualifier F. Prospecting
题意：给一颗n点树，有边权和点权。边看成堆着土的隧道，土的数量就是边权，如果土的数量不为0，那么这条边不可以走，挖走1个土消耗1块钱。点上的权值x代表走到这个点能得到x块钱。有一个需要抵达的终点。起点为0。从起点出发，可以选择一个能走到的隧道并挖隧道里面的土。可以不用挖完。走到点上一定会获得点权的钱。如果当前钱的数量小于0就破产问最少需要多少钱可以走到终点问至少带多少钱可以让你在最坏的情况下依然可以到达终点。x[i]表示点i的权值，y[i]表示i的父亲边的权值n<=1e5n <= 1
2020-10-02 16:39:22
1201
原创 CSP-CCF2020(第20次) 第五题 解密密码本 题解（AC自动机+字典树+DP）
题意：给n个单词，要你构造长度为k的密文，使得密文解密后是由这n个单词构成的解密书，有k页，一开始在第1页，每页26行。第i行一个字符a和一个数字b表示密文i解码后变成a，并翻到第b页并且构造的密文中的子串不能出现给出的单词。问k=1,2,3…m时候的方案数n <= 50, 单词总长度 <= 50, m <= 2000给出的单词不会出现重复，也不会有一个是另一个的前缀。单词可以重复在明文中出现。解题思路：看一下限制条件：长度要为k密文中不可以出现任何子串为某个单词明
2020-09-27 17:07:16
1074
1
原创 2020 CCPC网络选拔赛部分题解
1002 Graph Theory Class题意：给n个结点1,2,…n，i和j之间的边权是lcm(i+1,j+1)，问最小生成树边权和解题思路：让所有结点变成2,3,4…n+1.这样把其中所有质数向2连边，所有合数向它的因子连边。这样答案为[3,n+1]数字和+[3,n+1]质数和。然后套min25板子就行，难点是需要知道min25板子（#include <bits/stdc++.h>using namespace std;const int N = 1000010;int k
2020-09-21 19:09:24
3629
2
原创 校内练习1：Central Europe Regional Contest 2019 解题报告
A . ABB题意：给出字符串S，求在S后面最少加多少个字符串使得其为回文串。n≤2e5n \le 2e5n≤2e5解题思路：相当于找一个最小的i使得S[i+1, n]为回文串，直接枚举i然后用字符串hash判断回文串即可。#include<bits/stdc++.h>#define ll long long#define pb push_back#define lowbit(x) ((x)&(-(x)))#define mid ((l+r)>>1)#def
2020-08-26 10:23:28
588
原创 2020杭电多校第三场部分题解(1004, 1005, 1006, 1009)
1004 Tokitsukaze and Multiple可以处理出每个点i作为划分的右端点，它最近的左端点为L[i]，然后问题就转换成了若个个区间，求彼此之间不相交的情况下最多有几个共存。经典问题，这里用DP解决#include<bits/stdc++.h>#define ll long long#define pb push_back#define lowbit(x) ((x)&(-(x)))#define mid ((l+r)>>1)#define ls
2020-07-28 17:24:01
481
1
原创 2020杭电多校第二场部分题解(1001, 1005, 1006, 1007, 1009, 1010, 1012)
1001 Total Eclipse题意：给一个n点m边的图，每个点有点权。每次可以选择一个点权全是正数的点组成的连通块，让它们的权值整体-1.问让全部的点权变为0需要多少次操作.(1≤n,m≤1e5)(1\le n,m\le 1e5)(1≤n,m≤1e5)（一开始题目意思其实是任选若干个点组成的连通块，后来出题人发现不对劲就改成这样的题意了）解题思路：对于一个连通块来说，可以一直操作 min(ai)min(a_i)min(ai)次（aia_iai是连通块内权值最小的那个点)，然后最小的那些点就会
2020-07-23 22:39:46
1462
原创 2020杭电多校第一场部分题解（1004, 1005, 1006, 1009, 1011)
1004 Distinct Sub-palindromes前置知识点：无题意：问本质不同的回文子串个数最少的长度为n的字符串有多少种，答案对1e9+7取模解题思路：其实是一个思维题，先考虑n很大的时候，如果是如abcabc…这样排列，本质不同的回文子串个数就是3，稍微画一画会当n>=4的时候本质不同回文子串个数不可能小于3个，而如果是3个就最多有3个字母. 当是3个字母的时候，肯定不可以有相邻的相同字母，也不能有一个位置左右两边是同一个字母，那么就只能是abcabc……这种形式了。所以n>
2020-07-22 12:15:59
1497
原创 [Gym-101482] G - Gathering(三分套三分+前缀和)
题意2维平面给n个整点, 找出一个整点(x,y)使得这个整点到其他n个点的曼哈顿距离和最小,同时需要满足每个点到这个(x,y)的曼哈顿距离不超过d.n≤1e5,0≤xi,yi≤1e9,0≤d≤2e9n\le 1e5, 0 \le x_i, y_i \le 1e9, 0 \le d \le 2e9n≤1e5,0≤xi,yi≤1e9,0≤d≤2e9解题思路如果没有"每个点到这个(x,y)的...
2020-04-20 12:10:39
248
原创 1327G - Letters and Question Marks(AC自动机+状压DP)
题目链接题目大意：给kkk个字符串t1,t2,...tkt_1,t_2,...t_kt1,t2,...tk，tit_iti有权值cic_ici.令F(T,t)F(T,t)F(T,t)表示字符串TTT中包含多少个ttt，G(T)=∑i=1kF(T,ti)∗ciG(T)=\sum_{i=1}^kF(T,t_i)*c_iG(T)=∑i=1kF(T,ti)∗ci。现在给出一个字符串S...
2020-03-30 11:23:31
323
原创 1327F - AND Segments (区间限制下的DP计数)
题目链接题目大意：有nnn个数字a1,a2,..ana_1,a_2,..a_na1,a2,..an组成数组aaa，mmm个限制条件，第iii个限制条件[li,ri,xi][l_i,r_i,x_i][li,ri,xi]表示需要满足ali&ali...&ari=xia_{l_i}\&a_{l_i}...\&a_{r_i}=x_iali&ali...
2020-03-29 19:30:38
347
原创 梯度下降法实现逻辑回归(python 代码)
逻辑回归很好的学习博客在逻辑回归中，损失函数的定义为最大似然估计，也就是所有样本判断正确的可能性相乘。令h(xi)h(x_i)h(xi)表示对输入的xxx判断为1的概率一般我们定义h(xi)=11−e−zh(x_i)=\frac{1}{1-e^{-z}}h(xi)=1−e−z1，其中z为x∗θTx*\theta^Tx∗θT，xxx为输入参数，θ\thetaθ为当前求出的参数。为什么用这...
2020-03-08 17:02:30
1116
2
原创 Dancing Links舞蹈链求解精确覆盖问题（C++代码）
很多问题（如求解数独等）都可以转化成求解精确覆盖问题，如果能有一个方便的代码求解这个问题是极好的。于是伟大的前辈们就发明了X算法，利用十字循环链表(dancing link)求解这个问题。https://blog.csdn.net/whereisherofrom/article/details/79220897https://www.cnblogs.com/grenet/p/3145800....
2020-03-07 13:02:12
537
原创 CodeForces 1303G - Sum of Prefix Sums（点分治+李超树）
题意给一颗树，每个点有点权，求树上一条路径u1,u2,...uku_1,u_2,...u_ku1,u2,...uk获得点权数组au1,au2,...auka_{u_1},a_{u_2},...a_{u_k}au1,au2,...auk。要使得它的前缀和的前缀和最大，求这个最大值。解题思路树上路径的问题会想到用点分治去解决，以点分治的想法，如何把当前一条路径和现存的路径信息合...
2020-02-17 10:55:36
387
原创 Codeforces Round #620 (Div. 2) 题解
A - Two Rabbits水题#include<bits/stdc++.h>#define ll long long#define pb push_back#define lowbit(x) ((x)&(-(x)))#define mid ((l+r)>>1)#define lson rt<<1, l, mid#define rson...
2020-02-16 16:33:49
316
原创 CodeForces 1303F - Number of Components（删边并查集）
题意一个n∗mn*mn∗m的地图，一开始全是颜色0.Q次询问，每次把(x,y)(x,y)(x,y)的格子变成颜色ccc。问每次操作完之后有多少个同色联通块。保证cic_ici以单调不降的顺序给出，且保证ci≤max(1000,2e6/(nm))c_i\le max(1000,2e6/(nm))ci≤max(1000,2e6/(nm))解题思路可以按照不同的颜色分别统计。那么修改一个位...
2020-02-14 23:01:57
483
原创 Codeforces 1301F - Super Jaber（思维+BFS）
题意n∗mn*mn∗m的地图上，每个格子有一个颜色。最多kkk种颜色。每次可以花费111时间去相邻格子，或者花费111时间跳到相同颜色格子。QQQ次查询(x1,y1),(x2,y2)(x1,y1), (x2,y2)(x1,y1),(x2,y2)问从(x1,y1)(x1,y1)(x1,y1)到(x2,y2)(x2,y2)(x2,y2)最少时间为多少。解题思路从起点到终点，两种可能：没有跳。...
2020-02-14 20:53:32
287
原创 Codeforces 1301E - Nanosoft（二维RMQ+二分）
题意给一个n∗mn*mn∗m的矩形，每个格子有一个颜色。总共4种颜色。一个合法的正方体是由左上四分之一为颜色1，右上四分之一为颜色2，左下四分之一为颜色3，右下四分之一为颜色4构成。QQQ次查询，每次查询子矩阵(x1,y1,x2,y2)(x1,y1,x2,y2)(x1,y1,x2,y2)中最大的合法正方体面积。如果不存在，输出0.n,m≤500,q≤3e5n,m\le 500, q\le ...
2020-02-14 20:47:03
271
原创 Educational Codeforces Round 82 (Rated for Div. 2)(ABCDE部分题解)
A Erasing Zeroes直接模拟B National Project算出最后一轮前需要几轮，然后加上剩余需要的天数。最后判断一下是不是比n小，如果是就再多做几天。这题wa 3发心态小崩#include<bits/stdc++.h>using namespace std;int main(){ int T;cin>>T; while(T...
2020-02-13 12:33:46
142
原创 Codeforces 1253F - Cheap Robot（最短路+并查集/Kruskal树）
题目大意n点m边无向图，k个关键点，q个询问（a，b）。问从a到b需要的最小容量c是多少。保证a，b是关键点。你能量池最多有c能量，每次走边消耗边权那么多的能量。在关键点会补满能量。每次询问需要的最少能量。k,n≤1e5,q,m≤3e5k,n\le1e5,q,m\le 3e5k,n≤1e5,q,m≤3e5解题思路以所有关键点为源求一遍多源最短路，然后对于一个点uuu,如果当前能量x<...
2020-02-11 20:28:38
315
原创 2019 CCPC-Final G.Game on the Tree(长链剖分+DP)
题目大意两个人在一个以1为根的树上玩游戏，一开始硬币在1。然后每一轮，如果当前硬币在u，当前的人可以选择一个v把硬币移动到v，条件是移动的距离要大于上一轮的人移动的距离。第一个人可以随便移动。问给出的树有多少个以1为根的子图可以让后手必胜。n≤2e5n\le2e5n≤2e5解题思路这题很容易推出来当1是树直径的中点的时候后手必胜。然后想要得到1是树直径中点的方案数，可以先得到1的每个儿...
2020-02-05 22:29:56
938
原创 Codeforces Round #616 C - Prefix Enlightenment(带权并查集维护二分图)
题意给你nnn个灯的开关状态，再给你kkk个子集。选择一个子集将会按下子集中所有数字对应的开关。mim_imi表示前iii个灯全部开启最少要选取多少个子集，求出所有的mi(i∈[1,n])m_i(i\in [1,n])mi(i∈[1,n])一些限制：任意三个子集的交集都是空集。一定存在一种选取方式使得所有的灯都亮着n,k≤3e5n,k\le 3e5n,k≤3e5解题思路：先观...
2020-02-03 12:43:02
320
原创 2019 ICPC Asia 南昌 Regional J. Summon（矩阵快速幂优化DP+polya定理）
题意：长度为n(n<1e5)n(n<1e5)n(n<1e5)的环，填四种颜色，有mmm个要求(m<256)(m<256)(m<256)，每个要求限制一个长度为444的序列XXXXXXXXXXXX不许在环中出现，问有多少合法方案。（通过旋转可以变相同的算同一种方案）解题思路：前置知识点：polay定理在粗略的学习polay定理之后，我只记住了对于没有限制的...
2020-02-02 21:22:06
655
原创 Educational Codeforces Round 81 (题解)
第一次AK div2，有点小开心。A. Display The Number题目大意：给nnn个火柴棍，求能组成的最大的数字是多少。解题思路：贪心，如果是奇数那就第一位为7后面都是1，否则全是1.#include<bits/stdc++.h>using namespace std;int main(){ int T;cin>>T; whil...
2020-01-30 13:43:23
1780
原创 2019 ICPC 南昌 Regional K. Tree（树上启发式合并 + 动态开点线段树）
题意求以111为根的nnn个点的有根树上，满足下面条件的有序点对(x,y)(x,y)(x,y)数目（点iii的权值为viv_ivi）:一个点不为另一个点的祖先vx+vy=vlca(x,y)v_x+v_y=v_{lca(x,y)}vx+vy=vlca(x,y)xxx到yyy的路径长度小于等于给定的值 kkkn,k≤1e5,0≤vi≤nn,k\le 1e5, 0\le v_i\l...
2020-01-29 17:25:53
838
2
原创 2019 ICPC 南昌 Regional A. 9102(离线处理 && 带删并查集)
题意：需要维护一个可持久化的带删并查集。解题思路：可持久化数据结构如果没有强制在线就尝试离线建一颗时间顺序的树，然后直接处理，解决完一个儿子再回溯操作就行了。因为要回溯所以这里的并查集并没有路径压缩而是采用启发式合并。#include<bits/stdc++.h>using namespace std;const int maxn = 1e6 + 50;struct no...
2020-01-28 19:13:22
649
原创 2019 ICPC 南昌 Regional B. A Funny Bipartite Graph(状压DP)
题意一个二分图，左右各有nnn个点，左边第iii个点有一个属性mim_imi，它在一个图中的价值为midim_i^{d_i}midi，其中did_idi为它在图中的度数(特殊的，如果度数为000，则价值为000)，求一个该二分图的子图使得右边的每个点度数都不为000且总价值最小，输出最小价值。如果无解输出−1-1−1有若干个限制条件(i,j)(i,j)(i,j)表示子图中左边的点iii...
2020-01-28 17:02:03
772
原创 2019 ICPC 南京 Regional F. Paper Grading(字典树DFS序剖分+树套树)
题意：有nnn个字符串s1,s2...sns_1,s_2...s_ns1,s2...sn，qqq个操作：1 Q k l r1\ Q\ k\ l\ r1 Q k l r，给出字符串QQQ，求sl,sl+1...srs_l,s_{l+1}...s_rsl,sl+1...sr中和字符串QQQ公共前缀长度大于等...
2020-01-28 15:54:11
687
原创 2019 ICPC 南京 Regional I. Space Station(DP && 哈希)
题意：有nnn个数字a1,2,..na_{1,2,..n}a1,2,..n，你的初始能量为a0a_0a0，每次只能选取小于等于当前能量的数字，选完数字aia_iai后当前能量会加上aia_iai，求选完所有数字的方案数 mod 1e9+7mod\ 1e9+7mod 1e9+7n≤1e5,0≤ai≤50n\le1e5,0\le a_i\le 50n≤1e5,0≤ai...
2020-01-28 14:00:23
958
原创 2020 CCPC Wannafly Winter Camp Day3 F. 社团管理 (DP && 分治)
题意：有nnn个数字a1,2...na_{1,2...n}a1,2...n,要分成k段，每段的价值为段内满足[ai==aj]and[i==j][a_i==a_j] and[i==j][ai==aj]and[i==j]的(i,j)(i,j)(i,j)对数。(n,ai≤1e5,k≤min(n,20))(n,a_i\le 1e5,k\le min(n,20))(n,ai≤1e5,k≤min(...
2020-01-26 13:11:43
268
原创 整体二分学习笔记
今天学了一下整体二分，和CDQ分治有点像，都是把询问整合起来一起按顺序处理。原理解释传入它的参数一般是4个(l,r,L,R)( l,r,L,R)(l,r,L,R),代表下标为[L,R]的操作中，询问的答案在[l,r]之间，修改的权值在[l,r]之间。它解决问题的一个经典例子是区间第k大的问题。区间第k大问题，被拆成两种操作：位置pospospos处增加一个权值为xxx的数查询位置[l...
2020-01-23 20:26:18
176
原创 2020 CCPC Wannafly Winter Camp Day6 H. 异或询问 (异或性质&&前缀和)
题意给定一个序列a1,2..na_{1,2..n}a1,2..n,定义f(x)=(a种小于等于x的数字数目)2f(x)=(a种小于等于x的数字数目)^2f(x)=(a种小于等于x的数字数目)2。QQQ个询问 l r x\ l\ r\ x l r x，查询∑i=lrf(i xor x)\sum_{i=l}^rf(i...
2020-01-22 18:53:02
607
原创 2020 CCPC Wannafly Winter Camp Day6 D. 递增递增（DP）
题意：nnn个范围[li,ri],ai∈[li,ri][l_i,r_i],a_i\in[l_i,r_i][li,ri],ai∈[li,ri],求所有符合限制的单调不增序列的元素和的总和。解题思路：因为是a是单调不降的，所以他们区间的左端点应该是单调不降的，右端点是单调不增的。可以分区间讨论。2n个点划分出2n个区间，然后用dp(i,j)dp(i,j)dp(i,j)表示考虑了前i个...
2020-01-22 13:23:20
413
原创 2020 CCPC Wannafly Winter Camp Day2 B.萨博的方程式(数位DP)
题意：萨博有个方程式：x1 xor x2 … xor xn=k(xi∈[0,mi])x_1\ xor\ x_2\ \dots\ xor \ x_n=k\quad (x_i\in[0,m_i])x1 xor x2 … xor xn=k(xi∈[0,mi])n≤50, k,mi...
2020-01-21 16:27:09
431
原创 2020 CCPC Wannafly Winter Camp Day6 (部分题解)
感谢敦哥敦哥友好签到题大放送，A题数目最多的一场7-1 6A. Convolution∑i=1n∑j=1n2aiaj\sum_{i=1}^n\sum_{j=1}^n2^{a_ia_j}∑i=1n∑j=1n2aiaj这个式子看上去很像卷积，如果是卷积的话直接NTT就做完了，所以我们想办法康康能不能化成卷积形式：2aiaj=2(ai+aj)2−ai2−aj2=2−ai2∗2−aj2∗2(...
2020-01-17 22:34:29
1080
原创 2020 CCPC Wannafly Winter Camp Day5 (部分题解)
这场是英文题面QAQ，dlstql7-1 5A. Alternative Accounts每个数字有一个状态表示它在各个集合的情况：0表示不在任何集合，1表示在第一个集合，3表示在第一个和第二个集合……显然，状态为0的数字可以不用管，状态为2k−12^k-12k−1的数字必定单独一个占一个集合。那么当k=2，状态为1的和为2的可以彼此配对，构成max(num[1],num[2])max(n...
2020-01-16 22:49:56
964
1
原创 2020 CCPC Wannafly Winter Camp Day3（部分题解）
这场待补的题蛮多……留个坑7-1 3A. 黑色气球听队友说随便搞搞就过了，没仔细听怎么写的，就康康代码吧ps：坑点是n=2的时候答案是1 1#include<iostream>#include<algorithm>#include<cstdio>#include<cstring>#include<queue>#inclu...
2020-01-16 22:26:58
812
4
空空如也
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人