immix's blog

A. Subtraction Game 题意 有两个正整数 a,b (a<b)a,b\ (a<b)a,b (a<b)。 现在有一个游戏：初始有 nnn 个石子，每个玩家每回合可以拿走 aaa 个或 bbb 个石子。 请求出一个 nnn，使得在这个状况下，后手必胜。 解法 显然 a+ba+ba+b 一定是一个后手必胜的解。 123456789101112131415161718192021222324252627282930#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(){ ...

AK 了！我愿称之为信心场。 A. Rudolph and Cut the Rope 题意 有 nnn 个钉子，每个钉子高度在 aia_iai​，并且有一根长度为 bib_ibi​ 的绳子连接着钉子和糖。 问：想要把糖放到 h=0h=0h=0 的地方，至少要割断几根绳子？ 解法 若 ai>bia_i>b_iai​>bi​，这根绳子就要割掉，否则不用割掉。 1234567891011121314151617181920212223242526272829303132333435#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(&qu ...

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] 的哈希值可以表 ...

约定下标从 1 开始。 字符串匹配问题 给定字符串 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 ...

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 ...