immix's blog

(3/6) rating: 1761 -> 1801 (+40) A. Desorting 题意 给定一个序列 a1,a2,…,ana_1,a_2,\ldots,a_na1​,a2​,…,an​。每一次操作，你可以选定一个下标 iii，给 a1,a2,…,aia_1,a_2,\ldots,a_ia1​,a2​,…,ai​ 加上 111，给 ai+1,ai+2,…,ana_{i+1},a_{i+2},\ldots,a_nai+1​,ai+2​,…,an​ 减上 111。 求要使这个序列变成非有序的，至少需要进行几次操作？ 解法 不难发现，序列是非有序的等价于存在下标 iii，使 ai>ai+1a_i>a_{i+1}ai​>ai+1​。因此，我们只需要找到原序列中差最小的两个元素，并将这两个元素弄成无序的即可。 可以发现，操作次数为 ⌊ai+1−ai2⌋+1\lfloor \frac {a_{i+1}-a_{i}}{2}\rfloor +1⌊2ai+1​−ai​​⌋+1，特判一下原来就有序的情况。 1234567891011121314151617181920212 ...

A - First ABC 题意 给定一个含有 A，B，C 的字符串。 求其的最短前缀，使得这个前缀同时包含 A，B 和 C。 解法 维护 A，B，C 是否出现即可。 1234567891011121314151617181920212223242526272829303132333435363738394041424344#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")#define Yes puts("Yes")#define No puts("No")#define er ...

div.4 dddd A. To My Critics 题意 给定 333 个整数，求是否有两个加起来大于等于 101010。 解法 12345678910111213141516171819202122232425262728293031323334353637383940414243#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")#define Yes puts("Yes")#define No puts("No")#define errorf(...) fprintf(s ...

通称马拉车算法。 NOI 大纲评级：8 级（NOI 级）。 回文串 一个字符串有 O(n2)O(n^2)O(n2) 个子串。事实上，存在一个算法可以在 O(n)O(n)O(n) 复杂度内找到所有回文子串。 这是利用了回文串的一个性质，若 s[l..r]s[l..r]s[l..r] 是回文串，则 s[l+1..r−1]s[l+1..r-1]s[l+1..r−1] 也是回文串。 因此，我们只需要记录以某个字符为中心的回文串的最长长度。 统一奇数偶数长度 众所周知，偶数长度回文串的中心在中间两个字符的中间，我们可以通过一些转化，使得我们只需要处理奇数长度回文串的情况。 具体来说，往每两个字符中间插入一个不存在的字符（比如说 #），特别的，为了防止越界，我们在开头加上 ^，结尾加上 $。 123456789scanf("%s",stmp);int l=strlen(stmp);s[0]='^';s[1]='#';int n=2;for(int i=0;i<l;i++){ s[n++]=stmp[i]; s[ ...

前言 单调队列和单调栈有什么关系？两者都利用了某个性质维护了满足单调性的数据结构，及时排除不可能的决策，来方便快速处理一些问题。 单调队列和单调栈解决的是不同的问题，并不是一个问题的两种解法。 单调队列 算法 单调队列可以解决「滑动窗口」内的最值问题。 所谓「滑动窗口」，指的是一段移动的区间，并且区间的左端点和右端点都单调递增。 「滑动窗口」可以是固定长度，也可以不固定长度。 不妨假设我们要维护的是窗口的最大值，单调队列的核心思想在于如果一个数后来，还更大，那它就一定特别优秀，所以比之前它小的所有数可以全部扔掉（不可能成为答案），不影响答案。 通过一个伪代码来看一下这个数据结构（这个维护的是窗口内的最大值）： 插入： 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 ...