- 博客(47)
- 收藏
- 关注
RSS订阅原创 七选五 排列组合+容斥/错排
好题，或许是因为我太菜了题面分析法一：容斥不难想到用排列组合，问题就转化为：从 kkk 个空中选 xxx 个空，使它们全部填匹配的数字，而剩下的 k−xk-xk−x 个空全都不匹配。即 ans=C(x,k)×...ans=C(x,k)\times...ans=C(x,k)×...难点就在后面那里，怎么求出 k−xk-xk−x 个空全都不匹配的方案数。考虑 A(k−x,n−x)A(k-x,n-x)A(k−x,n−x) 为随便向这里面填数的方案数，显然这里面会有一些数恰巧匹配，所以我们需.
2021-05-29 23:54:00
3971
4
原创 「NOI2010」超级钢琴
linkRMQ练手题，只要不把题目读错就是道水题。因为是连续的，不妨考虑前缀和。注意这里超级和弦不同值它们的位置不同（不是值）。即求 max(∑pre[r]−pre[l−1])max({\sum pre[r]-pre[l-1]})max(∑pre[r]−pre[l−1])。把所有的数放进优先队列里显然是不行的。套路，考虑将所有的左端点放进优先队列里面，则为一个五元组 (i,l,r,v,num)(i,l,r,v,num)(i,l,r,v,num)，vvv 表示 max(pre[l→r]−pre[i
2021-05-12 14:10:41
197
原创 「APIO2017」商旅
link不难证明，这个商人不会沿着同样的路径（e.g.1->2->3->1->2->3->1）走两次，因为答案都是一样的。这样 33pts33pts33pts 的暴力就有了。考虑正解，有点像01分数规划？考虑二分最后答案，则val[x1][x2]+val[x2][x3]+...+val[xn][x1]time[x1][x2]+time[x2][x3]+...+time[xn][x1]>=mid\frac {val[x1][x2]+val[x2][x3]+..
2021-05-12 13:24:59
105
原创 CF10E Greedy Change
link其实这种题涉及到很多的证明，大胆猜想不要怕错先想想我们要干什么，肯定是使真实值比贪心值小啊。考虑什么时候真实值比贪心值小，不妨观察一下样例。（方便理解）trick：对于一个数 a[L]a[L]a[L]，找到一个离 a[L]a[L]a[L] 较近的值，使贪心算法后要用更多零碎的值（这显然对吧）。考虑具体怎么实现，对于一个区间 (l,r](l,r](l,r]，只取里面的数，使得总和为 X(X略大于a[l])X(X略大于a[l])X(X略大于a[l])，使取完 a[l]a[l]a[l] 后，需要
2021-05-11 19:49:56
115
原创 「THUPC 2021 初赛」区间矩阵乘法
linkans=∑i∑j∑ka[p1+d∗i+j]×a[p2+d∗j+k](0≤i,j,k<d)ans=\sum_i \sum_j \sum_k a[p1+d*i+j]\times a[p2+d*j+k] (0\le i,j,k<d)ans=∑i∑j∑ka[p1+d∗i+j]×a[p2+d∗j+k](0≤i,j,k<d)因为这个 kkk 的加 111 只会导致每次后面那个数的下标加 111，考虑前缀和。令 pre[i]=∑a[k](k<=i)pre[i]=\sum a[k
2021-05-11 13:42:07
402
2
原创 [HNOI2016]大数 题解
题面样例11 121121 3 1 6 1 5 1 4532分析易知 [l,r]=∑a[i]∗10r−i≡0 (mod p)[l,r]=\sum a[i]*10^{r-i}\equiv 0\ (mod\ p)[l,r]=∑a[i]∗10r−i≡0 (mod p)ppp 与 101010 不互质，又因为 ppp 为质数，所以 p=2p=2p=2 或 p=5p=5p=5，这种情况 [l,r]≡a[1]≡ 0 (mo
2021-05-04 17:30:15
125
原创 采花 题解
题面样例10 32 3 2 4 5 1 2 5 6 22 3 4 5 3 7 6 6 7 730分析（p.s.在这篇文章中，最大链指所有儿子到根节点的路径中最大的那一条）易想到缩点。发现缩点后连反边是一棵树（其实是森林）。于是问题就转化为，给你一棵树，从中找 kkk 个叶子|使他们到根节点的路径|所有节点的并集|的权值和最大，这样每次找权值和最大的那一条即可，找到后直接向上爬每个元素更新，再加个线段树+优先队列，可以做到 O(klog22(n))\mathcal {O}(klog
2021-05-04 17:26:17
139
原创 分组 题解
题面样例6 12 81 22 33 43 23 14 14 51 56 55 63 66 33分析可以说是一个套路/思维模式吧不难想到 O(n3/k)\mathcal{O}(n^3/k)O(n3/k) （kkk 为常数）的暴力，二分优化一下 O(n2log2(n))\mathcal{O}(n^2log_2(n))O(n2log2(n))。考虑时间复杂度为什么会这么高，发现是二分时进行了太多冗余的操作。考虑缩短二分上下界。不妨设现在要取的边的数量为 ttt，
2021-04-29 13:37:53
627
原创 JOISC 2014 Day1 T2「たのしい家庭菜園」题解
见注释。#include <cstdio>#include <algorithm>#include <cmath>#include <cstring>#include <climits>#define LL long longusing namespace std;const int MAXN = 3e5 + 5;void read(int &x) { x = 0; int f = 1; char c = getchar
2021-04-29 13:33:07
128
原创 [九省联考2018]劈配
link分析70pts70pts70pts 的暴力很显然。考虑正解，全题最大的难点就是怎么选同一志愿中的老师。感觉似乎不好选，不妨跳出这个想法，你会发现同学和老师有着对应关系，想到了什么？匈牙利算法！于是，我们直接在里面找增广路即可。但是还有个问题，一个老师可以选多个学生，我们将找增广路变形一下即可。这样就可以回答第一个问题了。对于第二个问题，显然二分，预处理出前 iii 个同学选完老师后连边的状态即可。有点微微难码。。。Code#include <cstdio>#include
2021-04-12 09:46:49
113
原创 「九省联考 2018」IIIDX
题面分析60pts60pts60pts 贪心做法很显然对吧，把它看成一棵树很显然对吧。不妨将权值从小到大排序。对于一个点 xxx 的子树，每次取 n−siz[x]+1→nn-siz[x]+1\to nn−siz[x]+1→n 的权值即可，这种贪心在权值不相等的情况是可行的。p.s.siz[x]siz[x]siz[x] 为 xxx 的子树大小。而权值不相等时，这种做法显然有问题。不妨思考一下，对于一个点 xxx，要取第 iii 小的权值要满足什么条件？对的，要满足 iii 以及 iii 右边（即
2021-04-09 09:51:08
244
原创 CF599E Sandy and Nuts
这题挺难的，因为 n≤13n\le 13n≤13，很自然地想到状压（雾）。题目dp 式子令 dp[i][j]dp[i][j]dp[i][j] 表示在状态 iii 下，当前根为 jjj 的方案数，显然，加第二维方便转移。可以写出一下转移方程：dp[i][j]=∑dp[u][t]×dp[u xor i][j]dp[i][j]=\sum dp[u][t]\times dp[u\ xor\ i][j]dp[i][j]=∑dp[u][t]×dp[u xor i][j]
2021-04-08 14:05:17
141
原创 CF392C Yet Another Number Sequence 题解
显然是一道矩阵加速的题。发现不好做，不妨推一下式子。ai=f(i)∗ika_i=f(i)*i^kai=f(i)∗ik<=>ai=(fi−1+fi−2)∗ik<=> a_i=(f_{i-1}+f_{i-2})*i^k<=>ai=(fi−1+fi−2)∗ik<=>ai=(fi−1∗(i−1+1)k+fi−2∗(i−2+2)k)<=> a_i=(f_{i-1}*(i-1+1)^k+f_{i-2}*(i-2+2)^k)<=>ai
2021-04-03 23:08:52
114
原创 AT2000 [AGC002F] Leftmost Ball 排列组合+dp
题意分析令 dp[i][j]dp[i][j]dp[i][j] 为选 iii 个白色球，选 jjj 个其他颜色的方案总数。则 dp[i][j]=dp[i−1][j]+dp[i][j−1]×(n−j+1)×Cn×k−i−(k−1)(j−1)−1k−2(i>=j)dp[i][j]=dp[i-1][j]+dp[i][j-1]\times (n-j+1)\times C_{n\times k-i-(k-1)(j-1)-1}^{k-2}(i>=j)dp[i][j]=dp[i−1][j]+dp[i][
2021-03-30 20:07:05
104
原创 浅谈动态dp
（大佬勿喷）（请不要嘲笑我讲得不清楚，因为我太菜了。。。）（请不要嘲笑我看了题解再写题解，因为我实在是太菜了。。。）P4719 [模板]“动态 DP”&动态树分治令 dp[x][0]dp[x][0]dp[x][0] 为以 xxx 为根不选 xxx 的最大权独立集的大小。令 dp[x][1]dp[x][1]dp[x][1] 为以 xxx 为根选 xxx 的最大权独立集的大小。令 yyy 的 xxx 的子节点。这题可以很容易写出dp式：dp[x][0]=∑max(dp[y][0],dp[
2021-03-13 22:16:02
199
1
原创 「BZOJ3727 PA2014」Final Zadanie 思维
题面分析不妨看看，b[fa[x]]−b[x]b[fa[x]]-b[x]b[fa[x]]−b[x] 等于什么，手算一下，发现是 xxx 子树的总人数 - 不为 xxx 子树成员的总人数。（这个性质还是很容易发现的。）然后我想的是（如果你只想看正解，后四排可跳过。）令 c[x]=b[fa[x]]−b[x]c[x]=b[fa[x]]-b[x]c[x]=b[fa[x]]−b[x]。令 xxx 为现在的结点，sonsonson 为其儿子，upupup 为它上面的一堆元素。则 ∑c[son]=−(sizes
2021-03-09 20:14:59
117
2
原创 「CSP-S 2019」 Emiya 家今天的饭 题解
题面样例2 3 1 0 10 1 13分析考虑正着限制最大的数不超过一半不好做，那我们可以反着来。令 dp[i][j][k]dp[i][j][k]dp[i][j][k] 为第 iii 行，此列指定数 pointpointpoint 数量为 jjj 个，选的非指定数的个数为 kkk 的方案数。则一共有三种情况Case 1:Case\ 1:Case 1: dp[i][j][k]=dp[i−1][j][k]dp[i][j][k] = dp[i - 1][j][k]d
2021-03-09 13:43:32
318
1
原创 COCI 2019/2020 Contest #1 T3「Džumbus」树形背包好题
题面样例1 010001100003 21 2 31 21 3323502214 132 3 4 19 20 21 5 22 6 7 23 8 10 141 21 31 42 52 63 73 83 94 108 1110 1310 1212 143454423875分析神仙题，，难啊，，妙啊，，起初我在想怎么分配几个子节点的名额，，结果设个 dp2dp2dp2 就完事了。令 dp[x][k][f]dp[x]
2021-02-20 20:16:46
299
原创 后缀数组（SA）倍增法总结
前言听老师讲之前听说是字符串，比较虚（因为一直认为这东西很抽象）。。听后才发现只要认真听还是不难的。。引入读入一个长度为 nnn 的由大小写英文字母或数字组成的字符串，请把这个字符串的所有非空后缀按字典序从小到大排序，然后按顺序输出后缀的第一个字符在原串中的位置。位置编号为 111 到 nnn。思路法一：暴力 O(n2log2(n))O(n^2log_2(n))O(n2log2(n))。法二：在 sortsortsort 中用二分+Hash，O(nlog2(n))O(nlog^2(n))O(n
2020-12-21 13:19:58
416
1
原创 NOIP2020总结
T1 : 打了 bfsbfsbfs，没用高精度（感觉高精度会T）T2：不知道在想什么，，明明只用Hash就能A，，，我不仅没搞出正解，全为一个字母的分都没骗，，明明有一点思路，当时就是想不出来，，浪费了很多时间而且万一我那个sb暴力退化到了 O(n3)O(n^3)O(n3)（对，你没看错，就是O(n3)O(n^3)O(n3)），T2暴力的分就没了，，T3：暴力没打，，搞sbT2、T4T4 : 暴力，应该 pts 40pts\ 40pts 40T2sb题没打出来算是一个遗憾了。
2020-12-08 13:49:48
647
7
原创 [COCI2016-2017#1] Mag 树形dp题解
题意你将获得一棵由无向边连接的树。树上每个节点都有一个魔力值。我们定义，一条路径的魔力值为路径上所有节点魔力值的乘积除以路径上的节点数。例如，若一条路径包含两个魔力值分别为 3,53,53,5 的节点，则这条路径的魔力值为 3×5/2=7.53\times 5/2=7.53×5/2=7.5。请你计算，这棵树上魔力值最小的路径的魔力值。输入格式第一行输入包含整数 n(1≤n≤106)n(1≤n≤10^6)n(1≤n≤106)。表示树中的节点数。 接下来 n−1n−1n−1行中的每一行包含两个整数，
2020-11-24 20:31:37
170
原创 关于生成随机数
当我们需要对拍或其他操作时，常常需要生成随机数。注：随机数不是真的随机，是算出来的。那随机数又该怎么生成呢？1.rand()rand()rand()rand()函数生成 [0，32767][0，32767][0，32767] 间的随机数。头文件：#include <cstdlib>2.time()time()time()time() 返回从格林威治时间1970年01月01日00时00分00秒起至现在的总秒数。头文件：#include <ctime>3.srand
2020-11-15 15:52:39
369
原创 最近点对分治算法
问题对于平面上给定的 NNN 个点，给出所有点的坐标，即输入是平面上的 NNN 个点，输出是 NNN 点中具有最短距离的两点。方法法一：暴力，时间复杂度 O(n2)O(n^2)O(n2)。法二：分支，时间复杂度 O(nlog(n))O(nlog(n))O(nlog(n))。当然，此博客讲法二。分析对于一个点我们可以将他们按 yyy 坐标的升序排序（当然可以反过来），取中间那个点的 yyy 坐标设为 midymidymidy 作为中间轴，分半，如图。对于直线的左右两边，都可以用分治，分别求出最
2020-11-12 12:41:37
598
原创 CSP.2020总结
这次 cspcspcsp 是很不理想的，打自闭了。。。pjpjpj:本来一切还好，T2T2T2 过大样例时打了 fcfcfc，结果上面显示不匹配，当时看了很久，查不出错，挺慌的（考完才知道行末多了个空格就会这样）。看了 15min15min15min，把这道题放下了，看 T3T3T3,暂时没有思路，就看 T4T4T4。想了一会后，得出 O(n2m)O(n^2m)O(n2m) 的 pts70pts70pts70 做法（如果不会被卡的话），想了 40min40min40min左右，细节调了 30min3
2020-11-07 21:36:49
652
原创 求拓展欧几里得最小整数解（全网最通俗）
前言此博客是求满足 ax+by=cax+by=cax+by=c 的 xxx 的最小整数解。为什么是最通俗的呢？因为我做这个的时候看网上的题解都看不懂。。。正文不妨设存在两个方程使得 ax1+by1=cax_1 + by_1 = cax1+by1=c，a(x1−n)+by2=ca(x_1-n)+by_2=ca(x1−n)+by2=c。则 y1=(c−ax1)/by_1 = (c - ax_1)/by1=(c−ax1)/b，y2=(c−ax1+an)/by_2 = (c - ax_1 + a
2020-10-24 11:15:32
730
原创 [CF1394D] Boboniu and Jianghu 树形DP题解
题目描述输入输出一行一个整数表示答案样例输入1540 10 30 50 202 3 2 3 11 21 32 42 5输出1160输入251000000 1 1 1 11000000 1 1 1 11 21 31 41 5输出24000004输入310510916 760492 684704 32545 484888 933975 116895 77095 127679 989957402815 705067 705067 705067 6
2020-10-19 21:10:16
181
1
原创 [CF908D] New Year and Arbitrary Arrangement 期望DP题解
题面样例输入11 1 1输出12输入23 1 4输出2370000006分析这道题显然是期望DP。由于终止状态有很多，不妨考虑 逆推。定义 dp[i][j][k]dp[i][j][k]dp[i][j][k] 为前面已有 iii 个 ′a′'a'′a′， jjj 个 ′b′'b'′b′， kkk 个 ′ab′'ab'′ab′ 的情况下，再在最后去掉一个字母后， ′ab′'ab'′ab′ 的期望个数。令 Pa=papa+pbPa = {pa \over {pa + pb}}
2020-10-06 19:13:34
984
2
原创 [CF1265E] Beautiful Mirrors 期望DP题解
题意简述GM 有 n(1≤n≤2∗105)n(1≤n≤2*10^5)n(1≤n≤2∗105) 面镜子，他每天问其中一面镜子“GM 帅不帅”，iii 号镜子有 pi%(1≤pi≤100)p_i\%(1≤pi≤100)pi%(1≤pi≤100) 的概率回答帅。第一天，GM 会从 111 号镜子开始问起。如果某天 GM 问了 i(i≠n)i(i≠n)i(i=n)号镜子，并且镜子回答帅，那么第二天 GM 会问 i+1i+1i+1 号镜子。如果某天 GM 问了 nnn 号镜子，并且镜子回答帅，那么 GM 就
2020-10-05 07:48:57
1138
13
原创 [NOIP2018]普及组题解
有好久都没写博客呢了。。。标题统计签到题。#include <cstdio>#include <algorithm>#include <cmath>#include <cstring>using namespace std;char a;int ans;int main() {// freopen("title.in", "r", stdin);// freopen("title.out", "w", stdout); while((
2020-08-26 22:34:09
316
6
原创 明辨是非 并查集题解
题目描述给 nnn 组操作，每组操作形式为x y px\ y\ px y p。当 ppp 为 111 时，如果第 xxx 个变量和第 yyy 个变量可以相等，则输出YES，并限制他们相等；否则输出 NO，并忽略此次操作。当 ppp 为 000 时，如果第 xxx 个变量和第 yyy 个变量可以不相等，则输出 YES，并限制他们不相等；否则输出 NO，并忽略此次操作。输入格式第一行为一个正整数 nnn。 接下来 nnn 行每行三个整数：xxx， yyy，ppp
2020-08-12 17:31:18
284
原创 [JSOI2008]Blue Mary的战役地图 Hash题解
题目描述Blue Mary最近迷上了玩Starcraft(星际争霸) 的RPG游戏。她正在设法寻找更多的战役地图以进一步提高自己的水平。由于Blue Mary的技术已经达到了一定的高度,因此，对于用同一种打法能够通过的战役地图，她只需要玩一张，她就能了解这一类战役的打法，然后她就没有兴趣再玩儿这一类地图了。而网上流传的地图有很多都是属于同一种打法，因此Blue Mary需要你写一个程序，来帮助她判断哪些地图是属于同一类的。具体来说，Blue Mary已经将战役地图编码为n×nn \times nn×n
2020-08-09 20:39:21
204
1
原创 「NOI2015」程序自动分析 并查集题解
题目描述在实现程序自动分析的过程中,常常需要判定一些约束条件是否能被同时满足。考虑一个约束满足问题的简化版本：假设x1x_1x1,x2x_2x2,x3x_3x3,…代表程序中出现的变量，给定nnn个形如xi=xjx_i=x_jxi=xj或xi≠xjx_i≠x_jxi=xj的变量相等/不等的约束条件，请判定是否可以分别为每一个变量赋予恰当的值，使得上述所有约束条件同时被满足。例如，一个问题中的约束条件为：x1=x2x_1=x_2x1=x2，x2=x3x_2=x_3x2=x3，x3
2020-08-09 20:08:37
217
1
原创 TSP问题(旅行商问题) 状压DP求解
题目描述某乡有nnn个村庄(1≤n≤161\leq n \leq 161≤n≤16)，有一个售货员，他要到各个村庄去售货，各村庄之间的路程sss(0<s<10000<s<10000<s<1000)是已知的，且AAA村到BBB村与BBB村到AAA村的路大多不同。为了提高效率，他从商店出发到每个村庄一次，然后返回商店所在的村，假设商店所在的村庄为SSS，他不知道选择什么样的路线才能使所走的路程最短。请你帮他选择一条最短的路。输入格式村庄数nnn，商店所在村庄和各村之间的
2020-08-01 15:47:53
1080
2
原创 树状数组 模板总结
前言此博客主要贴模板，若还未学习树状数组的同学请未进。(dalaodalaodalao除外)概念树状数组(BinaryBinaryBinary IndexedIndexedIndexed Tree(B.I.T)Tree(B.I.T)Tree(B.I.T)也称作FenwickFenwickFenwick TreeTreeTree)是一个区间查询和单点修改复杂度都为log(n)log(n)log(n)的数据结构。主要用于查询任意两点之间的所有元素之和。lowbitlowbit是什么?lowbit(
2020-07-27 20:02:40
99
原创 数三角（count.cpp）题解
题目描述这是一个数三角的游戏。长度为111或sqrt(2)sqrt(2)sqrt(2)的小木棍放在一个网格上。如图所示，有水平的，垂直的或对角的。对角放置的木棍可以交叉。将木棍随意地放在网格上得到的图案可能不含三角形，也可能含一个或多个三角形。如下图所示(aaa),(bbb),(ccc),(ddd)和(eee)分别含有222,555,121212,000,000个三角形。你的任务是写一个程序数出一个图案中的三角形个数。输入格式输入文件count.incount.incount.in包括N+1N
2020-07-25 20:35:56
1068
7
原创 震惊！全网最详细的STL总结！
前言禁止转载，违者必究。STL，即Standard Template Library。相信大家都知道这是啥，以下为基本的STL模板总结。1.queuequeuequeuequeue，队列，是实现"先进先出"的容器，，不可用下标或迭代器访问。头文件：#include <queue>定义方式：queue <typename> name;其中typenametypenametypename指数据类型（如intintint、charcharchar、结构体、容器等），n
2020-07-22 19:46:29
318
2
原创 「CF149D」括号涂色 区间DP好题
题目描述Petya遇到了一个关于括号序列的问题： 给定一个字符串SSS，它代表着正确的括号序列，即 “(((” 与 “)))” 是匹配的。例如：“(())()(())()(())()” 和 “()()()”是正确的，“)())())()”与“(()(()(()”则不是正确的。 在正确的括号序列中，一个左边的括号一定是匹配一个右边的括号（反之亦然）。例如，在下图中，第 333 个括号匹配第 666 个括号，第 444 个括号匹配第 555 个括号。现在你需要对一个正确的括号序列做涂色操作，严格满足以下三个
2020-07-19 21:08:09
230
1
原创 「NOIP 2013」火柴排队 题解
题目描述涵涵有两盒火柴，每盒装有 nn 根火柴，每根火柴都有一个高度。 现在将每盒中的火柴各自排成一列， 同一列火柴的高度互不相同， 两列火柴之间的距离定义为：∑(ai−bi)2\sum (a_i-b_i)^2∑(ai−bi)2。其中 aia_iai 表示第一列火柴中第 iii 个火柴的高度，bib_ibi 表示第二列火柴中第 iii 个火柴的高度。每列火柴中相邻两根火柴的位置都可以交换，请你通过交换使得两列火柴之间的距离最小。请问得到这个最小的距离，最少需要交换多少次？如果这个数字太大，请输
2020-07-10 17:17:15
872
1
原创 「IOI 1998」Polygon (区间DP题解)
题目翻译“多边形游戏”是一款单人益智游戏。游戏开始时，给定玩家一个具有NNN个顶点NNN条边（编号1∼N1 \sim N1∼N）的多边形，如图1所示，其中N=4N = 4N=4。每个顶点上写有一个整数，每个边上标有一个运算符 +++（加号）或运算符 ×\times×（乘号）。第一步，玩家选择一条边，将它删除。接下来在进行 N−1N-1N−1 步，在每一步中，玩家选择一条边，把这条边以及该边连接的两个顶点用一个新的顶点代替，新顶点上的整数值等于删去的两个顶点上的数按照删去的边上标有的符号进行计算得到
2020-06-26 10:26:21
531
1
空空如也
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人