CodeForces

Special Permutation CodeForces – 1352G(构造)

Special Permutation CodeForces – 1352G(构造)

思路:一开始想复杂了,直接搞的图论,TLE了。后来发现其实可以直接构造。前四个我们可以构造出2 3 1 4 的形式,如果n>=4的话,那么可以左右来回放置,这样就可以构造成功。只有n<=3的时候才不能构造成功。 代码如下: #include using namespace std; int n; inline string fcs(int i) { string tt=""; whil... »

CodeForces – 1327E(dp)

CodeForces – 1327E(dp)

题目大意给定n(n > 3331332 > 3332333 > 3333334 > 3334335 > 3335336 > 3336337 > 3337338 > 3338339 > 3339330 > 3330………… »

CodeForces – 1344D Monopole Magnets(dfs)

CodeForces – 1344D Monopole Magnets(dfs)

题目链接:点击查看 题目大意:给出一个 n * m 的矩阵,’ # ‘ 代表黑色方格,’ . ‘ 代表白色方格,现在可以在任意方格上摆放任意个单向磁铁,磁铁具有的一个性质是:每秒钟 N 极磁铁会向同行或同列的 S 极磁铁靠拢,但 S 极磁铁不会移动,需要构造一种方案,使得: 无论如何移动,N 极磁铁都无法到达白色方格 存在一种移动方案,使得 N 极磁... »

CodeForces_1348EF – Phoenix and Memory  贪心+线段树找区间最小值

CodeForces_1348EF – Phoenix and Memory 贪心+线段树找区间最小值

这题如果没有输出2个解就很简单。 是个之前做过的类型: 把所有限制按R排序, 然后每次取出R最小的,然后从其L开始选,尽量选能选的中最小的。 这样选如果能选完,就说明有解。 贪心正确性显然:R大的至少可以选则R做为点来用。所以按R升序遍历,每次优先选左边的,能让后边的可选的更多。 用set维护可选的数即可。 这题加了个输出2个方案。 我们考虑最简单的情况:即确定一个序列后,是否有2个位置,posi... »

在这里插入图片描述

CodeForces1230 F. Konrad and Company Evaluation (复杂度分析)

题意: 有n个人m个敌对关系, 一开始第x个人的工资是x 有q次操作,每次操作会给一个人的编号x 然后将x的工资变为所有人中最多的。 如果a和b是敌对关系,a的工资比b高,那么a会嘲讽 如果a嘲讽b,b嘲讽c,那么(a,b,c)是一个三元组 问每次操作之后一共有多少对三元组 数据范围:n,m<=1e5,q<=1e5 三元组图例(未修改工资时): 图中三元组一共4组: 4->3-&... »

在这里插入图片描述

【3.29百度笔试编程解析】CodeForces 149D 括号染色问题 dp+dfs好题

题目大意 给一个给定括号序列,给该括号上色,上色有三个要求 1、只有三种上色方案,不上色,上红色,上蓝色 2、每对括号必须只能给其中的一个上色 3、相邻的两个不能上同色,可以都不上色 题目分析 求0-len-1这一区间内有多少种上色方案,很明显的区间DP dp[l][r][i][j]表示l-r区间两端颜色分别是i,j的方案数 0代表不上色,1代表上红色,2代表上蓝色 对于l-r区间,有3种情况 1... »

CodeForces – 1328F Make k Equal(模拟)

题目链接:点击查看 题目大意:给出一个数列 a ,现在有两种操作: 找到一个最小值,使其值加一 找到一个最大值,使其值减一 注意这里找到一个最值进行的操作,是针对最值不唯一的情况,题目问至少需要进行多少次操作,可以使得某个数字出现的次数大于等于 k 次 题目分析:一道不知道为什么放在F题的F题。。因为E题卡了半个小时最后还没解决掉,还剩十分钟结束比赛的时候看到群友说F题是模拟,抓紧时间去读题,读完... »

CodeForces – 1327D Infinite Path(图论综合)

CodeForces – 1327D Infinite Path(图论综合)

题目链接:点击查看 题目大意:首先给出一个 1 ~ n 的排列,用 p 数组表示,再给出给个点的颜色,用 c 数组表示 然后抛出Infinite Path的定义:对于某个 i ,p[ i ] , p[ p[ i ] ] , p[ p[ p[ i ] ] ] 无限嵌套下去,且每个位置的颜色相同,即 c[ i ] = c[ p[ i ] ] = c[ p[ p[ i ] ] ] = c[ p[ p[ ... »

CodeForces – 1325D Ehab the Xorcist(构造+思维)

题目链接:点击查看 题目大意:给出一个 u 和一个 v ,要求构造出最短的一个数组,使得 所有元素异或的结果为 u  所有元素之和的结果为 v 输出构造的结果 题目分析:情况稍微比较复杂的一道构造题,读完题后,先根据样例特判,当 u 和 v 为 0 时,答案为 0 ,当 u 和 v 相等时,答案为 u,当 u > v 时,答案为 -1,这些根据样例的提示应该不难想 接下来我们应该构造通项,根... »

CodeForces – 1324 D. Pair of Topics 思维+多解法

CodeForces – 1324 D. Pair of Topics 原题地址: http://codeforces.com/contest/1324/problem/D 基本题意: 给你一个数组,找符合(i bi + bj 的序列对的数量。 基本思路: 本质上我们设 ci = ai – bi 那么原式可以换为 ci + cj > 0,所以我们可以有几个思路: pb... »

CodeForces – 1324F Maximum White Subtree(树形dp)

题目链接:点击查看 题目大意:给出 n 个点组成的树,每个点都有一个颜色,非黑即白,现在问对于每个点而言,选出一个连通块,使得白色点的个数与黑色点的个数做差最大 题目分析:记录一下div3的第一次ak,实际上应该是伪ak,感谢zx学长最后抬了我一手F题,dp真的是天克我,不过通过这个题真的学到了不少 首先这个题,题意给出的subtree一定别想当然以为是子树,我一开始就是因为这里读错题然后就被卡懵... »

CodeForces – 1312E Array Shrinking(区间dp)

题目链接:点击查看 题目大意:给出 n 个数,现在可执行的操作是: 找到相邻且数值相等的两个数,即 abs( i – j ) == 1 && a[ i ] == a[ j ] 使得两个数合并为一个数,且数值变为 a[ i ] + 1 问如何操作,能使得最终数列的长度最短 题目分析:最优性问题,且是对区间操作的,而且数据范围满足 n^3 的时间复杂度,综上可以考虑区间dp... »

CodeForces – 1312D Count the Arrays(组合数学)

题目链接:点击查看 题目大意:给出一个 n 和 m ,求满足条件的数组有多少个 数组包含 n 个元素 每个元素的取值为 1 ~ m 包含且仅包含一对相同的元素 存在一个位置 pos ,使得 [ 1 , pos ] 内严格递增,[ pos , n ] 内严格递减 题目分析:读完题后不难看出是一道排列组合的题目,本着先选数,再排序的原则,我们一步步分析 首先我们需要选出 n 个元素才能构成一个数组,因... »

(a_1 + a_2) oplus (a_1 + a_3) oplus ldots oplus (a_1 + a_n) \ oplus (a_2 + a_3) oplus ldots oplus (a_2 + a_n) \ ldots \ oplus (a_{n-1} + a_n)

CodeForces – 1323D Present(思维+数学)

题目链接:点击查看 题目大意:给出一个数列 a ,求出   题目分析:如果暴力的话显然时间复杂度是 n * n 的,我们应该想办法去优化,比赛的时候想用线段树,但是不会在维护异或的前提下区间加法,也想过用矩阵维护,但丝毫没什么用呀,队友想到了可以按位维护,也就是维护26个线段树,我觉得太麻烦了就放弃这个题了,补题的时候看了题解,感觉题解已经说的很明白了,在这里再记录一下吧,感觉还是自己太菜了,需要... »

CodeForces – 1316B String Modification(找规律)

题目链接:点击查看 题目大意:给出一个字符串 s ,需要求出一个 k ,满足 i ∈ [ 1 , n – k + 1 ]中,每个s[ i : i + k – 1 ]都反转一遍,使得最后得到的字符串字典序最小,若有多个 k 满足条件,求出最小的那个 k  题目分析:读完题后最暴力的方法是 n * n * n ,显然是不行的,考虑是否有规律可循,自己手动模拟了一下发现确实有规律... »

CodeForces – 1305D Kuroni and the Celebration(思维,互动题)

题目链接:点击查看 题目大意:给出一个由 n 个点组成的树,现在可以询问 n/2 次(向下取整)LCA,确定根节点是哪个节点 题目分析:因为最多只能求 n/2 次lca,每次需要两个节点作为参数,也就是说每个点我们至多遍历一遍,读完题后没什么思路,队友给我提示说可以参考树上启发式合并的思想,从叶子结点向上不断合并找到根节点,由此我感觉可以根据度来找到叶子结点,每次询问两个叶子结点的LCA,直到存在... »

CodeForces – 1315D Recommendations 并查集

CodeForces – 1315D Recommendations 并查集 一开始想用优先队列做,一直TLE 我一开始是按照序号从小到大,时间从小到大排序的,但是这样是不对的,对于序号重复的值而言,时间越小就可以进行越多次操作(贪心思想),那么这多次操作具体是多少呢,是出现重复的次数-1,相当于距离 做法:按照时间从大到小,序号从小到大,用并查集维护祖先,用来表示该点最终需要加到多大... »

CodeForces – 1313C2 Skyscrapers (hard version)(单调栈+dp)

题目链接:点击查看 题目大意:给出 n 块连续的空地可以建造摩天大楼,政府有规定,每块地最高只能建 a[ i ] 的高度,同时每栋大楼需要满足一个规则,即每栋大楼的两侧不允许同时存在比自己高的大楼,输出一种方案,使得总高度之和最大 题目分析:C1题目的数据范围是 1e3 ,直接两层 for 暴力枚举每个位置作为最高点就可以了,没有难度的暴力就不多说了,直接说一下C2题目的 5e5 该如何处理吧 看... »

CodeForces – 1313B Different Rules(数学+思维)

题目链接:点击查看 题目大意:一共有 n 个人,进行两轮比赛,假设第一轮比赛的名次为 x ,第二轮的名次为 y ,那么这个人的得分为 x + y ,最后的排位会按照得分的非严格升序排列,有一个人在第一轮的名次为 x ,第二轮的名次为 y ,问这个人最终最好的名次和最差的名次分别是多少 题目分析:个人感觉难度大于C题的一道B题。。 参考视频:https://www.bilibili.com/vide... »

CodeForces – 1300E Water Balance(贪心)

题目链接:点击查看 题目大意:给出 n 个数字组成的序列,现在可以对数列进行多次操作,每次操作可以选择其中一段连续的数列,用其平均数替换原位置,换句话说,若原连续数列为 1 2 3,则可以替换为 2 2 2,问如何操作可以使得最后答案的字典序最小 题目分析:因为要使得字典序最小,我们可以在线操作,因为涉及到平均数,我们可以将数列分为几个不同的区块,每个区块的平均值都相同,对于每加入的一个新的数字 ... »

在这里插入图片描述

F – Three Paths on a Tree CodeForces – 1294F

先找树的直径树的直径两点的确定方法:先取树上随意一点x;一次dfs求出x能到达的最远点 便是树的直径的一端点a;再来一次dfs求出a能到达的最远点 便是树的直径的另一端点b;对于这道题,bfs找到一个端点到那么这个点就是c点;方法二:树形dp,我还不会作者:yang1008610010 »