immix's blog

A. Tales of a Sort 题意 给定一个序列 {an}\{a_n\}{an​}。 现在每次操作为 ∀i,ai←max⁡(0,ai−1)\forall i, a_i\leftarrow \max(0,a_i-1)∀i,ai​←max(0,ai​−1)。 求进行多少次操作后序列变为有序？ 解法 进行模拟，每次遇到一个逆序的就不断进行操作直到这个逆序被消除。 复杂度 O(n2)O(n^2)O(n2)（可优化至 O(n)O(n)O(n)）。 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051#include<bits/stdc++.h>using namespace std;using ll=long long;using ull=unsigned long long;using pii=pair<int,int>;#define all(x) x.begin(),x.end()#define mem0(x) memset( ...

A - To Be Saikyo 题意 有 nnn 个人，实力分别为 p1,p2,…,pnp_1,p_2,\ldots,p_np1​,p2​,…,pn​。 请问第一个人实力需要增加多少才能严格大于后面所有的人？ 解法 如果只有一个人，答案是 000。 否则答案是 max⁡(0,max⁡(p2,p3,…,pn)+1−n)\max(0,\max(p_2,p_3,\ldots,p_n)+1-n)max(0,max(p2​,p3​,…,pn​)+1−n)。 12345678910111213141516171819202122232425262728293031323334353637383940#include<bits/stdc++.h>using namespace std;using ll=long long;using ull=unsigned long long;using pii=pair<int,int>;#define all(x) x.begin(),x.end()#define mem0(x) memset(x,0,sizeof(x))#defin ...

线段树维护区间最大子段和 区间最大子段和，指的是区间中一段连续的数的和的最大值，形式化的写作 max⁡l,r∑i=lrai\max_{l,r}\sum_{i=l}^ra_imaxl,r​∑i=lr​ai​。 单独求一个区间的最大子段和可以使用动态规划算法在 O(n)O(n)O(n) 时间内求出。但是，如果涉及到区间更改，或求一个子区间的区间最大子段和就无法如此做了。 事实上，使用线段树完全可以用来维护最大子段和。 定义 我们给每个节点维护四个值：区间和 sumsumsum，从左端点开始的最大子段和 lslsls，在右端点结束的最大子段和 rsrsrs，总共的最大子段和 msmsms。 123struct Node{ int sum,ls,rs,ms;}; pushup 我们考虑如何将这四个值由下面的两个区间 lch,rchlch,rchlch,rch 更新得到（pushup 操作）。 区间和 sumsumsum sum=sumlch+sumrchsum=sum_{lch}+sum_{rch}sum=sumlch​+sumrch​。 从左端点开始的最大子段和 ...

A - Chord 题意 给定一个字符串，判断 sss 是否是 ACE, BDF, CEG, DFA, EGB, FAC, 中 GBD 的一个。 解法 字面意思。 12345678910111213141516171819202122232425262728293031323334#include<bits/stdc++.h>using namespace std;using ll=long long;using ull=unsigned long long;using pii=pair<int,int>;#define all(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(stderr, ...

A. Dalton the Teacher 题意 有 nnn 个数 a1,a2,…,ana_1,a_2,\ldots,a_na1​,a2​,…,an​。 现在每次操作可以交换两个数，请求出最少的操作数，使得 ∀1≤i≤n,ai≠i\forall 1\le i \le n, a_i\ne i∀1≤i≤n,ai​=i。 解法 设当前满足 ai=ia_i=iai​=i 的数数量为 xxx。 可以证明，答案为 ⌊x+12⌋\big \lfloor \dfrac{x+1}{2} \big \rfloor⌊2x+1​⌋。 证明： 必要性：一次操作只能调换两个数的位置，至少需要 ⌊x+12⌋\big \lfloor \dfrac{x+1}{2} \big \rfloor⌊2x+1​⌋ 次操作才能调换每一个数。 充分性：我们构造一个合法方案。如果 xxx 是偶数，我们直接两两一换即可。如果 xxx 是奇数，我们先将 x−1x-1x−1 两两一换，显然最后一个数一定能在前 x−1x-1x−1 个数中找到一个能和它换的。 12345678910111213141516171819202122232425 ...

Rk#57 (1h22min AK, Unofficial) A. Escalator Conversations 题意 有一个电梯，有 mmm 级台阶，第 i (1≤i≤m)i\ (1\le i \le m)i (1≤i≤m) 级高度为 i⋅ki\cdot ki⋅k。 现在你的身高为 HHH，其他有 nnn 个人的身高为 h1,h2,…,hnh_1,h_2,\ldots,h_nh1​,h2​,…,hn​。 两个人可以对话，当且仅当它们站在不同的电梯台阶上且电梯台阶的高度差等于它们的身高差。请问：你可以分别和不同的几个人对话？ 解法 两个人可以对话，当且仅当身高差 Δh=p⋅k (p∈Z,1≤p<m)\Delta h = p\cdot k\ (p \in Z,1\le p <m)Δh=p⋅k (p∈Z,1≤p<m)，O(n)O(n)O(n) 遍历每一个人判断条件即可。 1234567891011121314151617181920212223242526272829303132333435363738394041424344#include<bits/stdc+ ...

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