标签 - 解题记录

? 解题记录 ? ? 模板 ? ? 排序 ?    2024-03-26 17:49:23    2    0    0
看到网上有许多快速排序和快速选择的代码,但是相当一部分都有些错误,这里放一下自己的写法 快速排序模板题:https://www.luogu.com.cn/problem/P1177 快速选择模板题:https://vjudge.net/problem/POJ-2388 #include <cstdio>#include <cstdlib>#include <algorithm>using namespace std;const int maxn = 1e6 + 5;int n, a[maxn];void kth_element(int * l,
? 解题记录 ? ? 网络流 ? ? 最大流 ?    2021-01-27 11:14:26    1540    0    0
链接标题 复习最小路径覆盖 最小路径覆盖是指对于给定的DAG,用最少的路径将其所有点覆盖,路径不相交。最小路径覆盖建图如下: 变式1:最小链覆盖 用最少的路径将其所有点覆盖,路径可以相交 做法:使用floyd传递闭包重连边,然后进行最小路径覆盖 变式2:最长反链 指选择最多的点,使得两两之间不能互相到达 做法:对偶问题:最长反链等于最小链覆盖 本题中发现球是依次加入的,如果有两个球和为完全平方数那么小的向大的连接单向边,一个柱子就相当于一条路径。那么可以知道K" role="presentation" style="position: relative;"&
? 解题记录 ? ? 数学 ?    2020-11-01 12:13:03    975    0    0
https://ac.nowcoder.com/acm/contest/7502/J 题目大意: 定义串 S1=[1]Sm=Sm&#x2212;1+[m]+Sm&#x2212;1" role="presentation" style="width: 100%; position: relative;">S1=[1]Sm=Sm−1+[m]+Sm−1S1=[1]Sm=Sm−1+[m]+Sm−1 S^1=[1]\\ S^m=S^{m-1}+[m]+S^{m-1} 其中&#x2032;+&#x2032;" role="presentation"
? 解题记录 ? ? 哈希 ?    2020-11-01 12:03:11    1046    0    0
https://ac.nowcoder.com/acm/contest/7502/G 题目大意: 给定一个长度为n" role="presentation" style="position: relative;">nnn数组,每一次可以进行如下操作: 1、将数组划分为前后两段 2、将这两段分别翻转 问最后可能得到多少种数组? 多组数据 &#x03A3;n&#x2264;2&#x00D7;106" role="presentation" style="position: relative;">Σn≤2×106Σn≤2×106\Sigma
? 解题记录 ? ? SPOJ ? ? 亚线性筛 ?    2020-09-23 08:18:19    782    0    0
传送门 题意:计算&#x03C3;0(i3)" role="presentation" style="position: relative;">σ0(i3)σ0(i3)\sigma_0(i^3)的前缀和 以前雅礼集训的时候就听说过这题,好像是洲阁筛板子? 但是如今世道不同了,Min&#x005F;25" role="presentation" style="position: relative;">Min_25Min_25Min\_25筛可以把这种东西吊起来筛! 当p&#x2208;Prime,f(pc)=3c+1" role="present
? 解题记录 ? ? SPOJ ? ? 亚线性筛 ?    2020-09-23 08:18:17    545    0    0
传送门 题意:计算σ0(ik)\sigma_0(i^k)的前缀和 一道牛逼题目,Min_25Min\_25筛写的很简短。 当p∈Prime,f(pc)=ck+1p\in Prime,f(p^c)=ck+1 且当p∈Prime,f(p)=k+1p\in Prime,f(p)=k+1 又因为前缀和∑ni=1k+1=n(k+1)\sum^n_{i=1}k+1=n(k+1)可以O(1)O(1) 直接Min_25Min\_25筛就行了,复杂度O(1011)O(10^{11})能过。 #include<cstdio>#include<algorithm>#
? 解题记录 ? ? Atcoder ?    2019-03-22 19:24:21    854    0    0
A - Colorful Subsequence 简化版题意:输入一个字符串,输出每种字母的个数+1" role="presentation" style="position: relative;">+1+1+1的乘积的结果&#x2212;1" role="presentation" style="position: relative;">−1−1-1。 |S|&#x2264;105" role="presentation" style="position: relative;">|S|≤105|S|≤105|S| \le 10^5 题解:按照题意模拟就
? 解题记录 ? ? FFT|NTT ? ? 树链剖分 ? ? 虚树 ? ? 组合数 ?    2019-03-18 12:09:49    1141    0    3
题目描述 给你一棵n个点的树,每一个点有个颜色ci" role="presentation" style="position: relative;">cicic_i。定义一种颜色的树是:把该颜色的点两两路径上的点和边都拿出来构成的图形。你可以选出k" role="presentation" style="position: relative;">kkk种颜色来,求:有多少种方案可以使每种颜色交集产生的树非空。对k&#x2208;[1,m]" role="presentation" style="position: relative;">k∈[1,m]k∈[1,m]k
? 解题记录 ? ? LOJ ? ? FFT|NTT ? ? 动态规划 ?    2019-03-16 07:59:01    626    0    0
传送门 题解: 考虑怎么做这道题。 首先发现性质: &#x6539;&#x53D8;&#x6B21;&#x6570;=2&#x00D7;&#x603B;&#x64CD;&#x4F5C;&#x6570;&#x2212;&#x7B54;&#x6848;&#x4E2D;&#x2032;1&#x2032;&#x7684;&#x4E2A;&#x6570;" role="presentation">改变次数=2×总操作数−答案中′1′的个数改变次数
? 解题记录 ? ? HDU ? ? 容斥 ? ? 莫比乌斯函数 ?    2019-03-15 15:47:54    534    0    0
GTW likes tree Time Limit: 7000/3500 MS (Java/Others) Memory Limit: 131072/131072 K (Java/Others) Total Submission(s): 191 Accepted Submission(s): 38 Problem Description GTW has a tree of n nodes, in which m nodes are special nodes. The value of node i is vi. Dis(x,y) is defined as