CodeTON Round 7 (Div. 1 + Div. 2, Rated, Prizes!)
看到B官方题解写了一堆，而如果能注意到一些性质，几行就写完了 题意：给一个A，B构成的字符串，可以将“AB”翻转成"BA",问最多可以进行多少次翻转？ 实际上在手动模拟以后发现，由于题目限制了每个位置只能翻转一次，所以情况简单了不少。 只要还没过最后一个B，那么最后一个B之前的所有A就会被反转。真正无效的部分是开头就是B，以及末尾的A，所以我们只需要找到第一个A，最后一个B即可，这两之间的所有位置都会被颠倒 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061// Problem: B. AB Flipping// Contest: Codeforces - CodeTON Round 7 (Div. 1 + Div. 2, Rated, Prizes!)// URL: https://codeforces.com/contest/1896/problem/B// Memory...
分治初步
分治初步 归并排序求逆序对 Sol：在归并排序过程中，本身就是分治思想，递归的对左区间排序，右区间同理。对于已经有序两段进行合并只需要O(n)O(n)O(n)的时间，递归共log2nlog_{2}{n}log2n层，时间复杂度为O(nlog2n)O(nlog_{2}{n})O(nlog2n) debug:1.对于没有到达边界的一段也需要放入临时数组，并且继续统计答案 2，先审核一遍代码，出现了没有调用函数，只打个括号的情况，没有报错，需要注意 1234567891011121314151617181920212223242526272829int solve(int l,int r){ if(l==r)return 0; int mid=(l+r)>>1; int res=solve(l,mid)+solve(mid+1,r); int pl=l,pr=mid+1; int...
贡献法解决子串问题
对于一个字符串 SSS，我们定义 SSS 的分值 f(S)f(S)f(S) 为 SSS 中恰好出现一次的字符个数。 例如 f(“aba”)=1f (“aba”) = 1f(“aba”)=1，f(“abc”)=3f (“abc”) = 3f(“abc”)=3, f(“aaa”)=0f (“aaa”) = 0f(“aaa”)=0。 现在给定一个字符串 S[0…n−1]S[0…n-1]S[0…n−1]（长度为 nnn），请你计算对于所有 SSS 的非空子串 S[i…j](0≤i≤j<n)S[i…j] (0 ≤ i \le j < n)S[i…j](0≤i≤j<n)， f(S[i…j])f (S[i…j])f(S[i…j]) 的和是多少。 贡献法：考虑当前这个字母可以在多少个子串中贡献，找到左边最近的相同字母，右边最近的相同字母，左右乘法原理计算可贡献子串数 会爆longlong，并且只开ans不够 实现：...
和为k的连续子序列 存在吗
题意是这样的，给你一个串，只有 T 和 W。令 T=2，W=1，将其变成数字串。然后每次给一个k,问是否存在一个子段和为k 一筐题目： https://www.acwing.com/problem/content/description/4040/ 基础版本，只需要存在性并输出任意一组合法解 https://www.luogu.com.cn/problem/P3514 英文版基础版本，只需要存在性并输出任意一组合法解 https://codeforces.com/contest/1896/problem/D 带修改版本但不用输出具体是哪段 https://www.luogu.com.cn/problem/P6859 带修改版本并且需要输出左端点最小的解 https://qoj.ac/contest/1404/problem/7684?v=1 ...
交互题专题
交互题专题 每次输出后，必须刷新标准输出：fflush(stdout); https://atcoder.jp/contests/practice/tasks/practice_2 题意：询问q次之内完成对元素的排序。一个是对26个元素在100次之内。一个是对5个元素排序在7次之内。 分析：对于26-100的情况，我们想到用类似于插入排序的二分，每次插入的时候二分插入的位置，这样子询问比较次数是logn，但是元素移动次数单词是O(n)O(n)O(n)的，但我们只关心交互的次数，所以算法没问题。再考虑对于5—7的这个数学小问题的具体做法： 7次比较完成5个元素的排序： 有五个数字，[a, b, c, d, e]，进行排序。以下排序均按从小到大进行排序： 将a与b进行排序，排序结果为[a’, b’]，共用1次比较，累计1次比较； 将c与d进行排序，排序结果为[c’, d’]，共用1次比较，累计2次比较； 将a’与c’进行比较，若a’ < c’，则a’ < c’ < d’，同时a’ < b’；否则 c’ < a’ <...
三分法
三分法是二分法的变种，他最基本的用途是求单峰函数的极值点。 三分适用的情况：有唯一的最大值，满足最大值左侧严格单调递增，右侧严格单调递减（或左减右增）。强调严格单调，这样在确定最值是才能判断最值的位置，否则三分法不能缩小左右边界。 三分整数模板 整数的三分可能具有不确定性，可以通过改变while循环的条件while(l+3<r)来缩小范围，再通过小范围暴力更新答案 对于边界的暴力不仅省去了处理边界，甚至常数也有提升，原因未知 凹函数的极小值 123456789101112131415int sfmin(){ int l=0,r=1e9; while(l+2<r){ //cerr<<l<<" "<<r<<endl; int m1=(r-l)/3+l; int m2=r-(r-l)/3; if(cal(m1)>cal(m2))l=m1; else r=m2; } int ans=cal(l); for(int...
双指针具有单调性
双指针的题目往往是看起来需要O（n),我们一般枚举一个指针，然后我们发现另一个指针不走回头路，不论是哪个方向，这样我们的时间复杂度就是O(n). 从例题来看: 给定一个字符串，我们希望找到最短长度区间能包含所有字母类型。 核心：对于左端点固定的时候，我们找到最小的r，然后我们考虑i右移动一位，这时候我们的j是一定不会回头的，因为不回头，都已经少了一个字母且当前假设已经不包含所有字母了，。 所以i和j都是单调移动的 https://codeforces.com/contest/701/problem/C 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263// Problem: C. They Are Everywhere// Contest: Codeforces - Codeforces Round 364 (Div. 2)// URL:...
一类区间查询对应答案具有单调性--维护前缀对应端点最大值
https://www.luogu.com.cn/problem/P8773 [蓝桥杯 2022 省 A] 选数异或 题目描述 给定一个长度为 nnn 的数列 A1,A2,⋯ ,AnA_{1}, A_{2}, \cdots, A_{n}A1,A2,⋯,An 和一个非负整数 xxx, 给定 mmm 次查询, 每次询问能否从某个区间 [l,r][l, r][l,r] 中选择两个数使得他们的异或等于 xxx 。 Solution:我们预处理每个端点对应的左边最近的配点，然后O(1)O(1)O(1)回答询问。 详细来说，对于每个右端点我们找到其左边最近的对应位置。进一步，我们考虑对于一个区间，我们只需要存在一个点他的对应端点在区间内就可以了，于是我们需要维护对应端点的区间最大值，RMQ问题可以线段树或者st表解决。 但我们可以利用我们只需要回答存在性，而不用具体回答，我们只需要维护前缀最大值，对于每个查询只需要检验ans[r]>=l即可 1234567891011121314151617181920212223242526int a[N];int...
CCF认证——202109-2 贡献的变化——差分维护，前缀和算答案
https://www.acwing.com/problem/content/4010/ http://118.190.20.162/view.page?gpid=T130 脑子一热抱着玩的心态试了一下三分，当然炸了，就当初认识三分了。 正解是考虑p的变化的影响，p变成p+1的时候，答案的值取决于 p属于 相邻递增数对的值域区间 的数量。也可以考虑递减的情况，两种情况只需要考虑一种，对所有数都考虑都考虑那一种就可以了，两种代码都AC了。 分析：如果 a[i]>a[i−1] 意味着当p取到 a[i−1]+1 到 a[i] 之间的值时，非零段+1 使用数组cnt[]，cnt[i]...
最新文章