div.2专题

Codeforces#295(Div.2)A、B(模拟+BFS)

解题报告链接：点击打开链接 C. 题目链接：点击打开链接解题思路：对于给定的字符串，取出现次数最多的字母（可以同时有多个）。由这些字母组成长度为n的字符串，求有多少种组合。最后用数学知识即可。完整代码： #include <algorithm>#include <iostream>#include <cstring>#include <climits>

【CodeForeces】【#290_(div.2)_C】拓扑排序

题意：给出n个单词，已知单词们已经按“字典序”递增排好。问题是，这个“字典序”并不是传统的abc，而是26个字母的未知排列。你需要做的是求出这个排列。当然有一些重复的特殊情况之类的，就不多说了。思路：拓扑排序，将26个字母视作26个点，根据给出的单词表，可以从中处理出一些数据，即“某字母a小于某字母b”，然后就在a到b建一条边。建好图之后拓扑排序得到答案。遗憾的是，题目有cheat

BestCoder Round #62 (div.2)Clarke and five-pointed star（极角排序，判断五边形）

题目链接题意：给你五个点，问这五个点是否可以组成正五边形（正五角星，等价于正五边形）。解答：先极角排序，（让五个点按照顺时针或者逆时针的顺序）然后我们计算五条边是不是一样，然后在看对角线是不是都一样。 #include<cstdio>#include<iostream>#include<algorithm>#include<cmath>#include<set>#includ

BestCoder Round #62 (div.2)Clarke and food （简单贪心）

题目链接题意：有个背包容量是V，现在有n个物品，每个物品有一个体积，问背包最多能装多少个。解法：先排序，从小到大选。 #include<cstdio>#include<iostream>#include<algorithm>#include<cmath>#include<set>#include<map>#include<string>#include<cstring>

BestCoder Round #61 (div.2)

比赛的时候过了两道，第三道超时20分钟过得 A题简单，我用了17分钟才写出来，看了界面熊大大的status,四分钟，直接把我吓傻，看了他的代码才知道，与大大之间的差距有多大： #include <iostream>#include <cstdio>#include <cmath>#include <cstring>#define LL long long#define pir pir

codeforces#244（div.2） C

动漫节一游回来之后一直处于一种意识模糊的状态看到大家都陆陆续续地过了C心里还是有点着急（自己没思路啊囧）其实当时就在想该如何找到DFS中的一个环，然后再找到环路上最小的一个值把所有环路上最小的值加起来就是结果，后来看到有人在群里说是tarjan求强连通分量，我就愉（bei）快（shang）地去睡觉了第二天起来就学习了一下强连通分量的相关知识和tarjan，现在整理下思路 http

codeforces#253 div.2 PD

这场CF挺有意思的，在做B的时候卡住了，本想放弃去看球赛了，但是一咬牙坚持下来，没想到最后还紫了（虽然又是要div1一日游的节奏T_T）感觉这种DP方法挺有意思的（一看就是菜鸟的思路T_T），因此还是总结一下~ 首先我将dp[i][j]定义为在前i个人中选出j个人最大的期望,那么就转化成了一种很基础的dp模型但是问题的关键在于如何找到dp的转移关系呢? 那么也应该和对应模型是相同的

CodeforcesRound#749(Div.1+Div.2,basedonTechnocup2022EliminationRound1)-C. Omkar and Determination-题解

在这里插入代码片目录 Codeforces Round #749 (Div. 1 + Div. 2, based on Technocup 2022 Elimination Round 1) - C. Omkar and DeterminationProblem DescriptionInputOutputSample InputSample OnputNote 题目大意解题思路AC代

CodeforcesRound#749(Div.1+Div.2,basedonTechnocup2022EliminationRound1)-B. Omkar and Heavenly Tree-题解

目录 Codeforces Round #749 (Div. 1 + Div. 2, based on Technocup 2022 Elimination Round 1) - B. Omkar and Heavenly TreeProblem DescriptionInputOutputSample InputSample OnputNote 题目大意解题思路AC代码 Cod

Codeforces Round#769(Div.2)E1+E2 Distance Tree

题目树是无环的连通无向图。加权树具有分配给每条边的权重。两个顶点之间的距离是连接它们的路径上的最小权重之和。给定一棵具有 n 个顶点的加权树，每条边的权重为 1。将 d(v) 表示为顶点 1 和顶点 v 之间的距离。如果可以在任意两个顶点 a 和 b (1≤a,b≤n) 之间临时添加一条权重为 x 的边，则令 f(x) 为 max{d(v),1<=v<=n} 的最小可能值。请注意，经过此操

Codeforces Round#767(Div.2) F2. Game on Sum (Hard Version)

题目参考F1 仅有输入数据范围修改：输入的第一行包含一个整数 t (1≤t≤105) — 测试用例的数量。测试用例的描述如下。每个测试用例由一行包含三个整数 n、m 和 k (1≤m≤n≤106,0≤k<109+7) — 回合数，Bob 必须加多少个数和 Alice 可以选择的最大数。保证所有测试用例的 n 总和不超过 106。题解：由F1我们知道DP状态转移方程为 DP

Codeforces Round#767(Div.2) E. Grid Xor

题目：注：集合{s1，s2，…，sm}的异或和被定义为 s 1 ⊕ s 2 ⊕ … ⊕ s m s_1⊕s_2⊕…⊕s_m s1⊕s2⊕…⊕sm，其中⊕ 表示按位异或运算。在赢得IOI后，维克多给自己买了一个n×n的网格，每个单元格中都包含整数。n是一个偶数。第i行和第j列单元格中的整数为 a i , j a_{i,j} ai,j。不幸的是，Mihai从Victor那里偷走了网

Codeforces Round#769(Div.2) C. Strange Test

题意给定两个数，A-B，一共有三种操作 1.A=A+1； 2.B=B+1; 3.A=A|B; 问使得A=B的最小操作步数。题解：由于第一种操作和第二种操作不可能同时使用，所以要么是A++=B，要么是A++然后或为B，不然就是,用第三种操作使得A>=B，然后B++使得A=B（此时B为B变化后的值） #include<bits/stdc++.h>using namespace std;

Codeforces Round#769(Div.2) B. Roof Construction

题意给定一个0至n-1的全排列，一个排列的消耗为数字与其相邻的异或，问如何排列能使消耗最小，并给出排列。题解我们首先来考虑消耗最小能是多少，异或的特点是相同为0，不同为1，考虑最高位的1，无论如何放置，无法使得最高位1的附近没有最高位为0，比如说 000 ，001，010，011，100，101，110，111 我们将最高位为1的放在最左边，由于不能放最高位为0的，那我们依次从左到右区

Codeforces Round#767(Div.2) A. Download More RAM

题意：给你一个初始的运行内存，每个硬盘有运行内存和运行完后可以获得的内存，也就是运行完一个你可以运行的内存后你会获得一些内存，比如初始内存为 10，一个硬盘的运行内存为10，可获得内存为20，运行完后你就变成30的内存，你只能运行运行内存小于你当前的值的硬盘。题解结构体排序，把运行内存小的放在前面然后依次运行累加即可。 #include<bits/stdc++.h>using na

Codeforces Round#768(Div.2) F. Flipping Range

题意：给定一个数组a，与一个集合B，每次可以选择集合B中的一个元素作为翻转a中一段的大小。使得 ∑ a i \sum a_{i} ∑ai最大题解：如果我们有x、y∈B（假设x>y），等价于拥有一个x-y大小置入B中，方法是乘以从大小为 x-y 的区间的位置开始的大小为 x 的区间,和一个大小为 y 的区间，结束于与区间 x 相同的位置.或者，将一个大小为 x 的区间与大小为 x−y

Codeforces Round#768(Div.2) E. Paint the Middle

题意：给定编号从 1 到 n的 n 个元素，元素 i 具有值 ai 和颜色 ci，最初,对于所有 i，ci=0。可以应用以下操作: 选取三个元素i、j、k（1≤i<j<k≤n），使得ci、cj、ck都等于0且ai=ak，则令cj =1。问 m a x ∑ c i max\sum ci max∑ci为多少题解：可以将这题看成区间覆盖的问题，只要两头有个相同的数显然可以将中间所有的ci

Codeforces Round#768(Div.2) C. And Matching

题意：给定一个值n，表示数组为[0-n-1]，其中n一定是2的整数幂，将数字两两配对分别为a[i]，b[i]，使得 ∑ a i & b i = k \sum a_{i} \&b_{i}=k ∑ai&bi=k, 题解： 1.直接构造出一个答案为k，使得剩下的组合都为0即可。我们知道: n-1&k=k设c（k）为k的补码, k&c(k)=0 再分情况讨论： Case 0<=k<n−1

Codeforces Round 931(Div.2) A~D2

A. Too Min Too Max （数学）题意：给定长度为 n n n的数组 a a a，求下列表达式的最大值， ( i , j , k , l ) (i,j,k,l) (i,j,k,l)为不同的索引 ∣ a i − a j ∣ + ∣ a j − a k ∣ + ∣ a k − a l ∣ + ∣ a l − a i ∣ |a_i - a_j| + |a_j - a_k| + |a

Codeforces Round #666（Div.2）A~D题题解

A .Juggling Letters 题目传送门 Juggling Letters 题意给你n个字符串，字符串si中的任意一个字母可以插入到任意一个字符串（包括自己）的任意位置，问是否能构成n个完全相同的字符串。思路思路很清晰，只需每种字母的数量%n==0即可 AC Code #include<bits/stdc++.h>using namespace std;char

Codeforces Round #665(Div.2)题解BCD

B.Ternary Sequence 题目传送门 Ternary Sequence 题目大意有两个由0,1,2组成的数组a和b，分别给你a数组和b数组中0,1,2的个数，其中满足求C的和的最大值思路贪心 1、通过观察我们发现正的贡献只有a(2)*b(1)=2,负的贡献只有a(1)*b(2)= -2，其他的情况则都为0。按照贪心的思想，a(1)*b(2)应该尽可能的少，而

Codeforces #280 (Div.2 A~E)

比赛地址 Codeforces Round #280 (Div. 2) 492A. Vanya and Cubes 题意： Vanya要堆金字塔，第1层要1个方块，第2层要1+2个，第3层要1+2+3个，以此类推。现在Vanya有n个方块，求能堆的金字塔的最大高度。 n < 10 ^ 4。题解：设金字塔高度为h，则需要的积木数为\sum_{i = 1} ^ {h} {\su

Codeforces #277.5 (Div.2 A~F)

比赛地址 Codeforces Round #277.5(Div.2) 489A. SwapSort 题意：给定一个长度为n的序列，每次可以选择序列中的两个元素交换位置，求任意一组交换次数不超过n次的方案，使交换后的序列是按升序排列的。 n <= 3000。题解：我们可以使用选择排序来解决这个问题。虽然选择排序会进行O(n^2)次比较，但是它具有一个很好的性质，我们可

洛谷P7918 【洛谷月赛LGR-096 Div.2 T2】 [Kubic] Lines题解

这道题是普及-，结果我比赛时想了整整一个小时。。。果然我还是太菜了啊QAQ 题目大意解题思路佬曰：“有人看到这道题直接网络流。” 网络流？最大独立集？大可不必。题目中最关键的一句话其实是注意：输入数据不保证 gcd ⁡ ( a , b ) = 1 \gcd(a,b)=1 gcd(a,b)=1。真是一语点醒梦中人。事实上，我们需要充分利用 a a a, b b b

Codeforces 1279(A，B，C，D) round79(rated for Div.2 )

传送门 A. New Year Garland 题意：将r个红灯和g个绿灯b个蓝灯串成一串，如果能使相邻两个灯不同色就输出YES，否则输出NO。（开头和结尾可以同色）。思路：简单的思路，个数最多的灯max，个数最少的灯min，个数居中的灯mid。只要是(max-min)>mid+1;就是合法的方案。 AC代码： #include<bits/stdc++.h>using namespa

Codeforces 1287（A，B，C）round#612(Div.2)

传送门 A. Angry Students 题意：给你一串字符由"A"，"P"组成，左侧的A会每秒感染右侧相邻的一个P，问多少秒后右侧全部的P被感染完。思路：直接找到每个A后面有几个A连续在一起，找到这个最大值输出即可。 AC代码： #include<bits/stdc++.h>using namespace std;#define rep(i,a,n) for(int i=a;i