immix's blog

A. The Man who became a God 题意 给定 nnn 个正整数，a1,a2,…,ana_1,a_2,\ldots,a_na1​,a2​,…,an​，把它们分成 kkk 连续的段，每段的值为相邻两数的差绝对值的和。求每段和的最小值。 1≤k≤n≤1001\le k \le n \le 1001≤k≤n≤100。 解法 1 （动态规划） 设 fi,jf_{i,j}fi,j​ 代表前 iii 个数分成 jjj 段的最小值 (i≥j>0)(i\ge j > 0)(i≥j>0)。 fi,j=min⁡j−1≤k<i(fk,j−1+∑p=k+1j−1∣ap−ap+1∣)f_{i,j}=\min_{j-1 \le k < i} \left( f_{k,j-1}+ \sum_{p=k+1}^{j-1} |a_p-a_{p+1}| \right) fi,j​=j−1≤k<imin​​fk,j−1​+p=k+1∑j−1​∣ap​−ap+1​∣​ 边界条件 f1,1=0f_{1,1}=0f1,1​=0。复杂度 O(n2)O(n^2)O(n2)。 123 ...

简单场。 A. New Scheme 题意 给出八个整数，求是否满足如下条件： 都在 [100,675][100,675][100,675] 的范围内； 都是 252525 的倍数； 单调不下降。 代码 12345678910111213141516171819202122232425262728293031323334#include<bits/stdc++.h>using namespace std;using ll=long long;using ull=unsigned long long;using pii=pair<int,int>;#define begend(x) x.begin(),x.end()#define mem0(x) memset(x,0,sizeof(x))#define YES puts("Yes")#define NO puts("No")int read(){ int f=1,x=0;char c=getchar(); while(!isdigit(c))
...

总表 刘汝佳，陈锋《算法竞赛入门经典训练指南》第 1 章——算法设计基础 更新中…… 题号 题目名称（点击跳转题解） 备注 UVA 11636 Hello World! 递推 UVA 11039 Building Designing 贪心 UVA 1368 DNA Consensus String 贪心 UVA 10970 Big Chocolate 模拟，公式 UVA 10382 Watering Grass 贪心，区间覆盖 UVA 10905 Children’s Game 贪心 UVA 1422 Processor 二分答案，贪心 UVA 11627 *Slalom 暂缺 UVA 11100 The Trip, 2007 贪心 UVA 1450 Airport 二分答案 UVA 1467 *Installation 暂缺 UVA 1344 Tian Ji – The Horse Racing 贪心 UVA 11389 The Bus Driver Problem 贪心 UVA 1418 *WonderTeam 暂缺 ...

例题来自《信息学奥赛一本通·提高篇》。 哈希函数 设字符串为 s=c1c2…cms=c_1c_2\ldots c_ms=c1​c2​…cm​，定义哈希函数 f(s)=(c1bm−1+c2bm−2+⋯+cmb0) mod Mf(s)=(c_1b^{m-1}+c_2b^{m-2}+\dots+c_mb^0)\bmod Mf(s)=(c1​bm−1+c2​bm−2+⋯+cm​b0)modM。其中 MMM 为一大质数，bbb 为小于 MMM 的任意整数。 比如说这样： 123456789const int b=114,M=1e9+9;int h(char* str){ int l = strlen(str); int res=0; for(int i=0;i<l;i++){ res=((ll)res*b+str[i])%M; } return res;} O(1) 求子串哈希 先预处理数组 HiH_iHi​ 代表字符串 sss 前 iii 位的哈希值。则字串 [l,r][l,r][l,r] 的哈希值可以表 ...

字符串匹配问题 给定字符串 s1s_1s1​，以及模式串 s2s_2s2​，求 s2s_2s2​ 在 s1s_1s1​ 内的所有出现位置。 一个很朴素的想法就是一位一位进行比较，复杂度 O(MN)O(MN)O(MN)，M,NM,NM,N 为两字符串长度。 123456789101112131415const int N = 1e6+5;char s1[N],s2[N];void brute_force(){ int l1 = strlen(s1); int l2 = strlen(s2); for(int i=0;i+l2<=l1;i++){ bool flag=1; for(int j=0;j<l2;j++){ if(s1[i+j]!=s2[j]){ flag=0;break; } } if(flag)printf("match at %d\n", ...

众所周知，平衡树是提高数据结构。 平衡树 平衡树首先是一颗二叉搜索树 (BST)。二叉搜索树的定义如下： 空树是二叉搜索树。 若二叉搜索树的左子树不为空，则其左子树上所有点的附加权值均小于其根节点的值。 若二叉搜索树的右子树不为空，则其右子树上所有点的附加权值均大于其根节点的值。 二叉搜索树的左右子树均为二叉搜索树。 我们不难发现，在二叉搜索树上可以很方便的进行如下操作： 从大到小遍历 查询最值 插入元素 删除元素 求元素排名 求排名为 k 的元素 除了第一个操作复杂度为 O(n)O(n)O(n)，其他这些操作的复杂度都是 O(h)O(h)O(h) 的，其中 hhh 为树的高度。最坏情况下，二叉搜索树会退化成一条链，于是复杂度都退化为 O(n)O(n)O(n)，这是我们不希望看到的。因此，出现了平衡树的概念。平衡指：每一个结点的左子树和右子树高度差最多为 111，这样就可以保证所有复杂度都是在 O(log⁡n)O(\log n)O(logn) 级别完成的。 set 首先，在你写平衡树之前，先想想 STL 的 set （或者 multiset） 够不够你用。 从大到小遍历：可以 ...

U N R A T E D 今回のコンテストは、採点の遅れの影響で、Unratedとさせていただきます。申し訳ありません。 /　Due to the delay in scoring, this contest will be Unrated. We are sorry for the inconvenience. A. Echo 题意 给定一个字符串。每个字符输出两遍。 代码 1234567891011#include<bits/stdc++.h>using namespace std;int main(){ int x;cin>>x; string s;cin>>s; for(auto x:s){ cout<<x<<x; } return 0;} B. Base 2 题意 给定 A0,A1,…,A63A_0,A_1,\ldots,A_{63}A0​,A1​,…,A63​ 求 A020,A121,…,A63263A_02^0,A_12^1 ...

填坑。 前两期： 网络流初步 —— 最大流算法 (2023/01/25) 网络流初步（2）—— 最小割 (2023/01/26) 费用流 现在，网络中新增了一个属性：费用。 设边 u,vu,vu,v 的费用为 w(u,v)w(u,v)w(u,v)。则当 (u,v)(u,v)(u,v) 的流量为 f(u,v)f(u,v)f(u,v) 时，费用为 f(u,v)w(u,v)f(u,v)w(u,v)f(u,v)w(u,v)。 现在，你需要保证流量最大的前提下，使费用最小，称作最小费用最大流（Min Cost Max Flow）。 做法 算法 用贪心算法。只需每次找费用最小的增广路，然后不断增广即可，证明略去，但是记住只要没有负圈这个算法就是正确的。（注意：原图费用不可以出现负圈） 数据结构 怎么存图？注意在费用流中是需要处理重边问题的，还需要方便的获取反向边。 习惯上，我们采用的是边表+邻接表记录出边在边表中的下标的数据结构。一条边和他反向边是存在一起的，即在边表的下标可以通过异或 1 得到。（0^1=1，1^1=0，6^1=7,7^1=6） 如果不明白，看以下代码理解。 1234567891 ...

数！论！ 逆元是个好东西，不会也要背板子。 乘法逆元 定义 若 ax≡1(modp)ax\equiv 1 \pmod pax≡1(modp)，则称 xxx 为 aaa 在模 ppp 意义下的乘法逆元，记作 a−1a^{-1}a−1。 此时存在 x/a≡xa−1(modp)x/a\equiv xa^{-1} \pmod px/a≡xa−1(modp)。这样就可以方便的计算在模意义下的除法操作。 例：在 p=13p=13p=13 时，3×9≡1(mod13)3\times 9 \equiv 1 \pmod {13}3×9≡1(mod13)。则对于任意 xxx，都有 x÷3≡9x(mod13)x\div 3\equiv 9x \pmod {13}x÷3≡9x(mod13)。 验证一下：27÷3=9,27∗9=243=18×13+927\div 3 = 9, 27*9 = 243 = 18 \times 13 + 927÷3=9,27∗9=243=18×13+9。 为什么？ 为什么若 aa−1≡1(modp)aa^{-1}\equiv 1 \pmod paa−1≡1(modp)，则 x/a ...

来学数学！ 拓展欧几里得算法 (EXGCD) 求 ax+by=gcd⁡(a,b)ax+by=\gcd(a,b)ax+by=gcd(a,b) 的整数解。 例：求 6x+15y=gcd⁡(6,15)=36x+15y=\gcd(6,15)=36x+15y=gcd(6,15)=3 的整数解。 有一组整数解 x=3,y=−1x=3,y=-1x=3,y=−1。（解不唯一） 求一组可行解 设存在 x1,y1,x2,y2x_1,y_1,x_2,y_2x1​,y1​,x2​,y2​，满足 {ax1+by1=gcd⁡(a,b)bx2+(a mod b)y2=gcd⁡(b,a mod b)\left\{ \begin{aligned} &ax_1+by_1=\gcd(a,b)\\ &bx_2+(a\bmod b)y_2=\gcd(b,a\bmod b)\\ \end{aligned} \right. {​ax1​+by1​=gcd(a,b)bx2​+(amodb)y2​=gcd(b,amodb)​ 因为 gcd⁡(a,b)=gcd⁡(b,a mod b)\gcd(a,b)=\gcd(b,a\ ...