immix's blog

前言 单调队列和单调栈有什么关系？两者都利用了某个性质维护了满足单调性的数据结构，及时排除不可能的决策，来方便快速处理一些问题。 单调队列和单调栈解决的是不同的问题，并不是一个问题的两种解法。 单调队列 算法 单调队列可以解决「滑动窗口」内的最值问题。 所谓「滑动窗口」，指的是一段移动的区间，并且区间的左端点和右端点都单调递增。 「滑动窗口」可以是固定长度，也可以不固定长度。 不妨假设我们要维护的是窗口的最大值，单调队列的核心思想在于如果一个数后来，还更大，那它就一定特别优秀，所以比之前它小的所有数可以全部扔掉（不可能成为答案），不影响答案。 通过一个伪代码来看一下这个数据结构（这个维护的是窗口内的最大值）： 插入： 12while(单调队列有元素 && 单调队列队尾小于插入元素)弹出队尾;插入要插入的元素到队尾; 也就是说，在插入一个元素时，我们弹出队尾所有比它劣的元素（因为它们出现早还比它劣，就直接扔掉）。这样之后，单调队列中，值满足单调递减，且下标满足单调递增。 取最大值： 12while(单调队列队首元素在窗口外)弹出队首；返回队首； 也就是说，取最大值时，有可 ...

感受数学的威力吧 A. Vika and Her Friends 题意 在一个 n×mn\times mn×m 的棋盘上，小 A 站在位置 (x,y)(x,y)(x,y)，还有 kkk 个小 A 的朋友，分别在 (x1,x2),…,(xk,yk)(x_1,x_2),\ldots,(x_k,y_k)(x1​,x2​),…,(xk​,yk​)。 每一秒，小 A 先向四周走一步，然后每个朋友根据小 A 的行动自己走一步。当在某一秒末尾，小 A 和某个朋友的坐标重合，那么这个朋友就抓到了小 A。 求是否有朋友能抓到小 A。 解法 朋友能抓到小 A 的充要条件是初始状态下，他们的曼哈顿距离为偶数。我们来说明一下： 不难发现，无论朋友和小 A 怎么动，他们的曼哈顿距离都只会变化偶数，所以若初始曼哈顿距离为奇数，则一定抓不到。 接下来只需要证明当曼哈顿距离是偶数的时候一定能抓到。 由于这个场地有边界，直观感受小 A 和朋友的距离不可能保持无限不变（我不会证明，但这就是 OI 的特点，能猜就行了），因此偶数一定有解。□\square□ 123456789101112131415161718192021 ...

本工具可以在 OI 系列竞赛中使用（只要你的省份提供了 NOI Linux）。 Sanitizer 在编译时通过加入开关 -fsanitize=undefined 来检查未定义行为。 只有 Clang 和 Linux 环境下的GCC可以使用这个功能。（所以立马换到linux吧） 先来看一个例子： 12345678#include<bits/stdc++.h>using namespace std;int main(){ int a = 1e9; printf("%d\n",a*a); return 0;} 显然这段代码会发生有符号整数溢出，这是一个未定义行为。输入 g++ test2.cpp -o test2 -Wall -fsanitize=undefined。进行运行，得到结果： $ ./test2 test2.cpp:6:11: runtime error: signed integer overflow: 1000000000 * 1000000000 cannot be represented in t ...

A. Order Something Else 题意 ABC 特有的 A 题题意，容易读错。 有一件商品价格为 PPP 元，你可以原价购买，或者多买一件其他商品后以 QQQ 元购买。 其他商品的价格为 D1,D2,…,DnD_1,D_2,\ldots,D_nD1​,D2​,…,Dn​。 请问入手这个商品最少要花多少钱？ 解法 答案为 min⁡{P,Q+min⁡Di}\min\{P,Q+\min D_i\}min{P,Q+minDi​} 12345678910111213141516171819202122232425262728#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")# ...

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