网站建设公司 lnmp,扬州工程建设信息网站,网站内容页优化,开发高端客户最近做构造#xff0c;想对比下先做后看答案归纳#xff0c;留下思路之后直接看答案归纳#xff0c;然后再统一检测#xff0c;还有直接看答案#xff0c;归纳#xff0c;检测三种方法哪种效率高些#xff0c;于是先做个十五题试试第一个方法#xff0c;花3天写了15道构…最近做构造想对比下先做后看答案归纳留下思路之后直接看答案归纳然后再统一检测还有直接看答案归纳检测三种方法哪种效率高些于是先做个十五题试试第一个方法花3天写了15道构造等到归纳的时候已经有点忘了要看答案来回忆一下感觉是不如留思路之后对照答案。但是最终还是能归纳出一些简单东西效果还是可以的。 1.B. Same Parity Summands Problem - 1352B - Codeforces #分类构造 #数论 奇奇得奇奇偶得偶 题目提到如果有多个答案请打印其中任何一个可以考虑构造
已知一个数n求是否能够把n分解成k个的奇偶性相同的元素 如果k个元素有共同的奇偶性k个元素相加可以看作是k乘一个奇数或偶数。 且k个元素相加等于n可以看作k与一个奇数偶数的乘积等于n 因为奇偶数相乘根据情况有不同结果所以分类构造。 2.B. Sorted Adjacent Differences Problem - 1339B - Codeforces #直接构造 #排序 序列构造涉及到大小关系时要排序。 已知n长度的序列要对这个序列排序使得从第一项到最后一项相邻项差值的绝对值递增。 如果要构造一个相邻项差值递增或递减的序列可以考虑用一个有序的数组中间元素往两边差值递增。两边元素向中间差值递减 两边往中间则两个数的差值越来越小。 3.B1. Palindrome Game (easy version) Problem - 1527B1 - Codeforces #回文串 #博弈 #构造 #字符串 有一个字符串有两种操作 1.选择一个0变成1 2.反转这个字符串如果原本是不回文的。 每次翻转消耗一美元消耗美元数量少的获胜求获胜方。 修改回文串单个元素可以考虑奇数长度时n/21这个元素自己与自己回文这个点。 博弈从小情况开始讨论往后的复杂情况可以被拆分成小情况 4.C1. k-LCM (easy version) Problem - 1497C1 - Codeforces #最小公倍数 #分组构造 #lcm 三个数相加和为n; lcma,b,c) n/2; 让lcm内的元素满足某条件可以考虑 1元素互质时lcm等于乘积 2元素相等 3元素为124与其倍数 5.D. Districts Connection Problem - 1433D - Codeforces #图论 #归纳构造 有n个地区属于ai个匪帮要把这些地区用n-1条无向边连接起来同一匪帮的两个区域不能直接通过一条边连接求是否有解决方案。 同一匪帮不能连在一起则容易想到只有一个匪帮则无解 此时数学归纳尝试讨论2个匪帮可以把一个全部连到另一个然后另一个全部连到前一个。 3个匪帮因为匪帮间相互独立所以第3个匪帮也可以实行像第一个匪帮的操作全部连到另一个匪帮即可。 6.B. Jumps Problem - 1455B - Codeforces #归纳构造 对0第i次操作可以i或者-1求得到一个n的最少操作数。 考虑一直i直到n然后考虑把其中一些操作换成-1来凑出一个n 比如如果得到n2可以少掉一个1的操作然后多一个-1的操作。此时分析这种操作的前提因为得到的是中间的值所以要往两边归纳。往后看因为i的差值只有1的所以可以得到n3n4……nk。 往前看得到n 1 时由于1已经最小所以只能另外构造化成n2-1的情况比n2多一步要i1步。 如果是n1就只能凑出n2之后再-1了。 7.D. Corrupted Array Problem - 1512D - Codeforces — 问题-1512D- Codeforces #排序 #分类构造 序列构造涉及到大小关系时要排序。 有一个n2个元素的数组b这个数组b中 n个元素是a中的元素1个元素是a的总和1个是任意加入的元素。 要构造一个a数组
总和一定是比a中所有元素都要大的 b数组排序之后就可以把这个总和元素锁定在n1和n2的位置 因为新加入的元素大小未知。所以要讨论 x sum x sum 分类构造看是否能满足前缀和的要求。 8.C. Mocha and Hiking Problem - 1559C - Codeforces #图论 #分类构造 有n1个村庄2n-1条有向边有n-1条是从1连接到n的其余n条是连接前n个村庄n1村庄的。 求构造一条路线经过所有村庄每个村庄只经过一次。
由于每个村庄只能去一次且道路是从1到n的 所以只能从1开始或者从n1开始然后去到1 对于什么时候去n1 只有三种情况 1.直接从1到n然后去n1结束ar[1] 1 2.从n1开始然后去到1再一直走到n ar[n] 0; 3.从1开始中间i点去到n1然后返回i1点。 ar[i] 0 ar[i1] 1; 发现如果不满足1且不满足2时必然会满足3.所以必定有解。
9.C. A-B Palindrome Problem - 1512C - Codeforces — 问题-1512C- Codeforces #回文串 #字符串 #模拟 #直接构造 1-n下标回文串模拟时常用in-i1的指针 回文串构造一般要考虑奇数长度的中间点。 有一个由01组成的字符串以及0的个数1的个数 是未知的0或1 求是否能构造出满足条件的字符串。首先先判断一遍已知的串是否已经可以确定不是回文串了 找到数字然后看另一边是否相同或者为如果是就改成一样的数字否则如果不相同就无解。 然后还有一些可以直接消掉的问号要替换成回文的数字。 然后统计处理好的串里的数字数量直接sa–sb–就行如果得到了负值就是无解了。 然后遍历字符串找到并修改。 上面的操作不用考虑特殊中间点这里的替换就要了。因为是一边替换一遍修改数量 可以考虑通过i 是否 n-i1来判断是否是中间点。如果此时sasb不是奇数的话就是无解了否则谁大于0谁上。 其他的情况谁大于2谁上然后把为什么是大于2的上然后把回文串两边都修改了前面不是已经把已有的数字给减了一遍吗。如果这里修改的一边是数字一边是怎么办 这里卡壳了。 回看了一遍题目和代码懂了前面处理已经把串i和n-i1回文的形式了所以这里遇到一个就可以直接把n-i1也修改并且sa-2
10.A. Common Prefixes Problem - 1384A - Codeforces — 问题-1384A- Codeforces #直接构造 #字符串 有一个长度为n的序列ai要用小写字母构造n1个字符串第i和i1个字符串的公共前缀长度为ai 首先考虑长度找到最大的ai字符串要构造的最大长度就是ai了 i1个串然后只要在i的基础上在ai处把字符修改一下就会有一个与i长度为ai的公共前缀。
11.B. Reverse Binary Strings Problem - 1437B - Codeforces #直接构造 #字符串 有一个偶数长度的01串1和0各有n/2个可以对字串反转求让串变成101010或101010的交替形 式的最小操作次数。 翻转操作只有两端的元素排列会被改变所以每次操作必然可以让连续的1或0减少一个长度然后让一个0和1配对。 总共要配对的次数就是所有1的连续段长度或0连续段长度的最大值。 12.B. Before an Exam Problem - 4B - Codeforces — 问题-4B- Codeforces #直接构造 有一个天数还有一个总学习时长和每天最大学习时长和最小学习时长限制。 要把学习时长分配到每天 构造一种方案让每天的学习时长符合要求或无解输出NO
因为数据比较小只有1e2级别所以直接让每天的学习时长从最小值开始逐个递增直到够时长然后打破循环输出。 考虑这种操作的前提条件是总时长在最小学习时长的总和和最大学习时长的总和之间。
13.B. M-arrays Problem - 1497B - Codeforces — 问题-1497B- Codeforces #直接构造 #数论 有一个长度为n的数组和一个数m定义了一个m数组如果数组里相邻的元素的sum可以被m整除或者数组只有一个元素则被称为m数组。要求对数组划分使得每一个数组都是m数组的最小数组数量。
把数组里的全部元素取余后用哈希统计数量就得到了方便用来研究整除关系的数据。 首先余数为0的全部分在一个数组ar如果有则res 然后遍历1-m/2如果ar[i] ar[m-i] 则这两种情况可以全部放在一个组里。res前提条件是ar[i],ar[m-i]存在。 如果ar[i] ! ar[m-i] 则可以分出部分在一个组因为只是相邻总和被m整除所以可一个多分一种元素出去。多出来的部分单独成组。res abs(ar[i] - ar[m-i]);
divisible.可分的
14.B. Paranoid String Problem - 1694B - Codeforces #字符串 #归纳构造 当时完全看不懂的题现在看答案看懂了。 有一个字符串定义paranoid字符串一个长度为m的字符串如果有子串为01就可以把子串替换成1如果为10就可以把子串替换成0。若可以通过m-1次这样的操作来获得一个长度为1的字符串就把这个长度为m的字符串叫做paranoid字符串 求给定字符串中有多少个paranoid字符串
首先可以知道长度为1的子串肯定是paranoid字符串所以字符串有多长就至少会有多少个paranoid字符串 然后增加长度发现如果新增的数和前一个数不同包含这个新增数的所有子串就一定是paranoid字符串 构造出一种操作遍历字符串当前ar[i] ! ar[i-1]则 i 1就是在原来的基础上再多加一个长度会新增i 1个子串。子串数量是1 * 2 * 3 * …… * n 1对于0到n-1下标的字符串 不太确定 否则如果相同的话就是新增了一个长度为1的子串。
15.B. Prinzessin der Verurteilung Problem - 1536B - Codeforces #枚举 #暴力 #字符串 有一个字符串定义mex为字典序中不是给定字符串子串的第一个字符串 枚举字符串然后find函数查询就行。
