泰安招聘网站有哪些,网站登录页面怎么做,广州建设局,网吧装修设计公司今天更新一道1月27号晚上div2的C题作为素材#xff0c;感觉用到了我的构造题总结模型#xff0c;我总结了一系列的模型和例题。 摘要#xff1a;
Part1 定义边界贪心法
Part2 题意
Part3 题解
Part4 代码
Part5 思维构造题模型和例题 Part1 边界贪心…今天更新一道1月27号晚上div2的C题作为素材感觉用到了我的构造题总结模型我总结了一系列的模型和例题。 摘要
Part1 定义边界贪心法
Part2 题意
Part3 题解
Part4 代码
Part5 思维构造题模型和例题 Part1 边界贪心法(该题所用到的模型)
边界贪心法对于整体而言我们去除已经定好的情况剩下难以确定的情况我们从其最边缘的位置去考虑、去假设一般要在问题的最边界处考虑一般最边界决定总体的走向后面会给例题以及其它的模型及其例题。 Part2 题意Problem - A - Codeforces 题意 给定,再给定一个长度为的字符串S该字符串满足只包含前k个小写字母字符, 要求判断能否找到所有的长度为且字符组成只包含前个小写字母字符的字符串为S的子序列删除一些元素后其余元素顺序不变而组成的序列,能输出YES,不能输出NO,并构造出该字符串它满足不是S的子序列。 Part3 题解: 题解 1、已知 2、我们不妨从头到尾遍历当满足划分一个块即块中元素恰好包含了所有的前个元素当出现必然是最后一个块因为它往后无法得到全部元素一直到最后才能满足否则就可以一直往后合并。 3、接下来我么分好了块假设有表示分出的块 我们进行分类讨论 3.1 当那我们必然能从每个块分别拿出任意字符组成长度为n的子序列。 3.2 当此时我们证明一定是无解的 3.2.1 首先我们证明第一个命题所有满足块的最后一个元素必然只存在一个在当前块中当最后一个元素有两个我们必然可以让块的右边界往左边移动矛盾。 3.2.2 证明从前往后每次取块中最后一个元素的序列一定是唯一的已知有, 其中满足的是当舍弃最后一个块的元素我们知道该块中仅仅只有一个这样的元素(由3.2.1得), 只能在前面的块找到 显然也只由一个在块中所以一直往前必然无法找到新的可替代的所以唯一。 3.2.3 所以取每个块的最后一个元素得到的并且它是唯一的我们只需要在后面补上任意元素使得就一定不是S的子序列。 Part4 代码(C) C代码(边界贪心法) #include bits/stdc.h
#define int long long
#define ff first
#define ss second
using namespace std;
using PII pairint, int;
constexpr int N 1e6 10;
constexpr int inf 0x3f3f3f3f;
int n, k, m;
// int us[N][30], uss[N][30];
void solve() {cin n k m;string s; cin s; string ans ; int o 0; for(int i 0; i m; i ) {setchar se; se.insert(s[i]); int j i; while(se.size() k j 1 m) { j; se.insert(s[j]); }if(se.size() k) {for(int j 0; j k; j )if(se.count((a j)) 0) {ans (a j); break; }}else o , ans s[j]; i j; }if(o n) cout YES endl; else {cout NO endl; while(ans.size() n) ans a; cout ans endl;}
}
signed main() {ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); int ts; cin ts; while(ts -- ) solve(); return 0;
} Part5 思维构造题模型和例题
1、前后缀贪心比如说观察前后缀的sum去看以后怎么考虑最好。Problem - 1903C - Codeforces
2、双指针贪心法考虑两端相消或者相互作用还有就是考虑左右边界。 Problem - 1891C - Codeforces
Problem - 1907D - Codeforces
3、转换观察法有些关系可以抽象成图观察图的某些性质去总结规律。也可以抽象成一个集合两个集合相等可以说明有解可构造。Problem - 1891C - Codeforces
4、打表找规律一般没什么规律可循即可打表找规律一般和数论有关的很喜欢考acm也喜欢考属于人类智慧题。Problem - 1916D - Codeforces
5、公式推导演算常见的分为公式的等价变形、公式的化简这个常考一般需要先证明某些性质可以直接抵消一般如果原公式处理起来很复杂时就可以考虑。Problem - 1889B - Codeforces
6、考虑奇偶数去简化问题或者分类问题从其中的一些运算性质入手因为奇数偶数的加减以及%运算这个结论很重要的结果的奇偶性是固定的Problem - 1898C - Codeforces
7、根据性质构造模型看看能不能分成几个块几个不同的集合再选择算法去解决。Problem - 1873G - Codeforces
8、考虑从小到大处理或者是从大到小处理有时候先处理小的对大的不会有影响或者反过来这样的处理顺序是最完美的。Problem - 1904D2 - Codeforces
9、边界贪心法一般要在问题的最边界处考虑有时候这样做结果是最优的或者考虑边界上的影响假如让影响最小就使得影响 固定值 。 Problem - E - Codeforces and Problem - 1903C - CodeforcesProblem - A - Codeforces
