avatar
Articles
19
Tags
20
Categories
4

RedGrey的博客

RedGrey的博客

循环最长公共子序列/Cyclic Longest Common Subsequence
Created2023-11-14|编程竞赛/Competitive Programming
循环最长公共子序列 参考:https://arxiv.org/pdf/1208.0396.pdf 问题描述 我们需要求两个循环序列的最长公共子序列,对于循环序列来说,把任意一个元素作为起始元素都认为是同一个序列,例如,循环序列’algorithm’同时也可以写作’rithmalgo’或者’thmalgori’,对于正常的序列’algorithm’和’grammar’来说,最长公共子序列为’grm’,但是对于循环序列来说,它们的最长公共子序列是’grma’ 预备知识 对于普通的非循环序列的最长公共子序列来说,记两个序列分别为A,BA,BA,B,AAA的元素个数为mmm,BBB的元素个数为nnn,例如AAA为BBAABBAABBAA,BBB为ABABBABABBABABB,可以将其转化为有向图,每个单元格可以看作图中的一个节点,向右或者向下可以连一条边,对于单元格(i,j)(i,j)(i,j)来说,如果A[i]A[i]A[i]和B[j]B[j]B[j]的元素相同,则从(i−1,j−1)(i-1,j-1)(i−1,j−1)向(i,j)(i,j)(i,j)斜着连一条边,如下图所示,记该有向图 ...
凸包技巧/Convex Hull Trick
Created2023-11-07|编程竞赛/Competitive Programming
凸包技巧 参考:https://codeforces.com/blog/entry/63823 问题描述 我们想要快速地计算对于某个固定的xxx,下述算式集合中的最大值: maxj∈S(kj∗x+bj)max_{j \in S}(k_j*x+b_j) maxj∈S​(kj​∗x+bj​) 此外,插入一个新的jjj对应的算式到集合中也应该需要高效地完成。 思路 注意算式kj∗x+bjk_j*x+b_jkj​∗x+bj​的形式,它相当于斜率为kjk_jkj​,与yyy轴交点为kjk_jkj​的直线,所以这个问题就相当于是给定一系列直线与一个特定的xxx值,求在横坐标为xxx时,这一系列直线中最大的yyy值;如果将所有的直线画出来,你会发现最大值将是一个凸包的边缘,如下图所示: 一些观察到的结论 在凸包上的每一条线都在一段连续的xxx值区间内是最大值,相反,不在凸包上的线是无用的,这些线永远不会是最大值 在凸包上所有线的斜率都不一样,斜率的顺序同时决定了他们在凸包上的位置。斜率值较小的线在凸包上位于斜率比它大的线的左侧 因此,一个可行的策略是只维护凸包上的线,而不保存那些无用的线 一 ...
集合的二进制表示法
Created2023-10-25|编程竞赛/Competitive Programming
集合的二进制表示法 概述 有一个包含nnn个不同元素的集合,假设为:{1,2,3,..,n}\{1,2,3,..,n\}{1,2,3,..,n},他的子集个数有2n2^n2n个,当nnn的大小不是特别大的时候,例如n≤30n\le 30n≤30时(约等于107374182410737418241073741824),我们则可以在合理的时间内枚举出它的所有子集。 子集的表示方法 数组表示法 直接用数组表示集合,这种表示方式比较直接,c++中的任何容器类型都可以用来存储集合 01 bit串表示法(二进制表示法) 使用一个整数的二进制形式来表示集合,二进制数第i个bit位为0,则表示全集中的第i个元素不在子集中,二进制数第i个bit位为1,则表示在子集中;例如一个包含3个元素的集合{1,2,3}的所有子集,可以用<8的整数来表示: 0 -> 000 -> {} 1 -> 001 -> {1} 2 -> 010 -> {2} 3 -> 011 -> {1,2} 4 -> 100 -> {3} 5 -&g ...
(Hard) AtCoder Educational DP Contest - J. Sushi
Created2023-10-19|编程竞赛/Competitive Programming
原题链接:https://atcoder.jp/contests/dp/tasks/dp_j J - Sushi Time Limit: 2 sec / Memory Limit: 1024 MB Problem Statement There are N dishes, numbered 1,2,…,N1,2,…,N1,2,…,N. Initially, for each i(1≤i≤N)i(1≤i≤N)i(1≤i≤N), Dish iii has ai(1≤ai≤3)a_i(1≤a_i≤3)ai​(1≤ai​≤3) pieces of sushi on it. Taro will perform the following operation repeatedly until all the pieces of sushi are eaten: Roll a die that shows the numbers 1,2,…,N1,2,…,N1,2,…,N with equal probabilities, and let iii be the outcome. If there ...
(Medium) CSES - Counting Tilings
Created2023-10-09|编程竞赛/Competitive Programming
原题链接:https://cses.fi/problemset/task/2181 Counting Tilings Your task is to count the number of ways you can fill an n×mn×mn×m grid using 1×21×21×2 and 2×12×12×1 tiles. Input The only input line has two integers nnn and mmm. Output Print one integer: the number of ways modulo 109+710^9 +7109+7. Constraints 1≤n≤101\le n\le101≤n≤10 1≤m≤10001\le m\le10001≤m≤1000 Example Input: 14 7 Output: 1781 题目描述 有1∗21*21∗2大小的砖,可以横着铺也可以竖着铺,问有多少种不同方法,可以铺满n∗mn*mn∗m大小的网格(不考虑对称、翻转等情况) 解决方案 我们把短的边设为水平方向,长的边设为竖直方向,我们从 ...
(Easy) Library Checker - Montmort Number
Created2023-09-13|编程竞赛/Competitive Programming
原题链接:https://judge.yosupo.jp/problem/montmort_number_mod Montmort Number Let aka_kak​ be the number of size kkk permutations ppp s.t. pi≠ip_i \ne ipi​=i for each iii. Given N,MN,MN,M. For each i=1,⋯,Ni=1,⋯,Ni=1,⋯,N, print bk=akmod  Mb_k=a_k\mod Mbk​=ak​modM. Constraints 1≤N≤1061\le N \le 10^61≤N≤106 1≤M≤1091\le M \le 10^91≤M≤109 Input N M Output b1 b2 ... bnb_1 \ b_2\ ...\ b_nb1​ b2​ ... bn​ Sample #1 1210 1000 1 2 9 44 65 54 33 96 61 #2 1220 9982443530 1 2 9 44 265 1854 14833 133496 1334961 1 ...
(Easy) CSES - Binomial Coefficients
Created2023-09-12|编程竞赛/Competitive Programming
原题链接:https://cses.fi/problemset/task/1079 Binomial Coefficients Your task is to calculate nnn binomial coefficients modulo 109+710^9+7109+7. A binomial coefficient (ab)\binom{a}{b}(ba​) can be calculated using the formula a!b!(a−b)!\frac{a!}{b!(a-b)!}b!(a−b)!a!​. We assume that aaa and bbb are integers and 0≤b≤a0≤b≤a0≤b≤a. Input The first input line contains an integer nnn: the number of calculations. After this, there are nnn lines, each of which contains two integers aaa and bbb. Output Print ...
组合数学相关
Created2023-09-08|数学/Math
来源:https://usaco.guide/CPH.pdf#page=217 概述 组合数学研究的是:如何对对象的组合进行计数,通常的目标是为了高效地计算出组合的个数,而不用单独生成每一个组合。 例如,考虑将一个正整数nnn拆分成≤n\le n≤n的正整数的和的方法个数(不同顺序视作不同方法),例如,对于4来说,有8种方法: 1+1+1+1 1+1+2 1+2+1 2+1+1 1+3 2+2 3+1 4 组合问题往往能够使用递归函数解决,例如上述问题,我们可以使用f(n)f(n)f(n)来代表拆分方法的个数,例如f(4)=8f(4)=8f(4)=8,f(n)f(n)f(n)可以使用如下公式递归计算得到 f(n)={1,n=11+f(1)+...+f(n−1),n>1f(n)= \left\{ \begin{array}{lr} 1 , & n=1 \\ 1+f(1)+...+f(n-1) , & n\gt 1 \end{array} \right. f(n)={1,1+f(1)+...+f(n−1),​n=1n>1​ 上述公式的含义是,如果选kkk作 ...
如何使用Hexo发布新文章
Created2023-09-05|备忘
hexo基础环境搭建 https://zhuanlan.zhihu.com/p/102592286 1. 创建一个新的md文件 1$ hexo new "title" 该命令默认会在source/_posts下创建一个title.md文件 2. 本地测试 1$ hexo server 3. 生成静态html文件 1$ hexo generate or 1$ hexo g 4. 发布并上传到github 1$ hexo deploy or 1$ hexo d 如果hexo d执行失败,如果开了vpn或者代理,可能需要打开一个新的bash界面再次尝试执行该命令,因为老的bash可能使用了老的代理设置,需要打开一个新的bash刷新一下 1234567开启代理软件后设置代理git config --global http.proxy 127.0.0.1:7890git config --global https.proxy 127.0.0.1:7890取消代理git config --global --unset http.proxygit config --glob ...
12
avatar
RedGrey
Articles
19
Tags
20
Categories
4
Follow Me
Announcement
愿你我都有美好生活
Recent Post
Static Top Tree(静态顶树?)2024-04-30
(2859) CodeChef October Challenge 2015 - Jump mission/JUMP2024-04-27
(6.9 Hard) Kattis - 2017 ICPC Mid-Atlantic Regional Contest - Avoiding Airports2024-04-19
Open-Sora使用初次探索2024-04-01
(*2700) ICM Technex 2018 and Codeforces Round 463 (Div. 1 + Div. 2, combined) F. Escape Through Leaf2024-03-24
Categories
  • AI1
  • 备忘1
  • 数学/Math3
  • 编程竞赛/Competitive Programming14
Tags
数论/Number Theory Derangements 文生视频 几何/Geometry Hexo 循环最长公共子序列/Cyclic Longest Common Subsequence AIGC 凸包技巧/Convex Hull Trick OpenSora 最长公共子序列/Longest Common Subsequence 树/Tree 动态规划/Dynamic Programming 位掩码/Bitmask 深度优先搜索/DFS 扩展欧几里得算法 Static Top Tree 组合数学/Combinatorics 二项式系数/Binomial Coefficients 辗转相除法 线段树/Segment Tree
Archives
  • April 20244
  • March 20242
  • February 20241
  • January 20241
  • December 20231
  • November 20233
  • October 20233
  • September 20234
Info
Article :
19
UV :
PV :
Last Update :
©2020 - 2024 By RedGrey
Framework Hexo|Theme Butterfly