CodeForces 448
Codeforces 414B
大家好，又见面了，我是你们的朋友全栈君。题目链接附上代码：#include <cstdio> #include <cstring> #include <bits/stdc++.h> #define mod 1000000007 int n, k; // dp[len][last] int dp[2005][2005]; int main(void) {
日期 2023-06-12 10:48:40Codeforces Round #807 (Div 2.) A·B·C
A. Mark the Photographer原题链接Original Link思想将所有人的身高存入数组 ，用sort排序利用双指针，以n为分界线，判断是否满足条件前n个人的身高+ x小于等于后n个人的身高代码#include <bits/stdc++.h> using namespace std; const int N=1e6+3; int a[N]; int main(
日期 2023-06-12 10:48:40
Codeforces Round #754 (Div. 2) C-E
#NameAA.M. Deviationx14701BReverse Sortx11165CDominant Characterx8864DTreelabelingx1791EArray Equalizerx580FPalindORmex41C. Dominant Character（暴力+剪枝、思维）题意给你一个只含有’a’, b’, ‘c’ 的字符串，长度1e5内，让你寻找最短的子串满足：长度
日期 2023-06-12 10:48:40
Codeforces Round #826 (Div. 3)（A~D）
A. Compare T-Shirt SizesOrigional Link题目大意：给定不同衬衫大小的尺寸编号如：S,M,L。除 M 之外，X 作为尺寸前缀代表其倍数大小。如：XXL\gt XL,XXS\lt XS。给定两个代表衬衫尺寸的字符串，判断衬衫大小。思想：签到题。判断模拟即可。代码：#include <iostream> #include <cstring> #
日期 2023-06-12 10:48:40
Codeforces Global Round 23（A~C）
A. MaxminaOrigional Link题目大意：给定长度为 n 只包含 0,1 的序列 a，和一个整数 k，保证 (2\le k\le n\le 50)。不限次数进行如下操作： 将连续且相邻的两个元素变为较小的一个。 将连续的 k 个区间的元素变为区间内元素最大的哪一个。 求给出的序列是否可以变为只包含 1 的序列。思想：签到题。保证 (2\le k\le n\le 50) 即保证了
日期 2023-06-12 10:48:40Codeforces Round #828 (Div. 3) （A~D）
A. Number ReplacementOrigional Link题目大意给定一个序列 a 和一个字符串 s。可以将相同的 a_i 替换为 s_i，若a_i 对应的替换规则唯一。求是否可以在满足上述条件下完成替换。思想：思维。当 s_i 所对应的 a_i 首次出现时建立对应规则。若 s_i 对应的 a_i 出现过且规则不同说明无法完成替换。代码：#include <iostream>
日期 2023-06-12 10:48:40CodeForces - 999C Alphabetic Removals
C - Alphabetic RemovalsYou are given a string consisting of lowercase Latin letters. Polycarp wants to remove exactly characters ( ) from the string . Polycarp uses the following algorithm t
日期 2023-06-12 10:48:40CodeForces - 999B Reversing Encryption
B - Reversing EncryptionA string of length can be encrypted by the following algorithm:iterate over all divisors of in decreasing order (i.e. from to ),for each divisor , reverse the substring (i
日期 2023-06-12 10:48:40A. Vasya and Book ( Codeforces Educational Codeforces Round 55 )
题意：当前在看书的第 x 页，每次可以向前或者向后翻 d 页，这个书一共 n 页，问能否用最小操作翻到第 y 页。 题解：三种情况：1、直接翻能到的一定最短。 2、先翻到第一页，然后往后翻，翻到第 y 页。3、先翻到第 n 页，然后往前翻，翻到第 y 页。#include<bits/stdc++.h> using namespace std; typedef long long l
日期 2023-06-12 10:48:40
A. Vova and Train ( Codeforces Round #515 (Div. 3) )
题意：一条 L 长的路，一列车长在这条路的 l 到 r 之间，只有在 v 倍数时有灯，但是在 l 到 r 之间的灯是看不见的，问最大看见的灯的个数？ 题解：L / v 表示总共的灯的个数， r / v 、( l - 1 ) / v 表示前 r 、（ l - 1 ) 长的路有多少灯，减一下就可以了。 （ 难题补不上了，QAQ，写个水题，放松一下）#include <iostream>
日期 2023-06-12 10:48:40Codeforces 842B Gleb And Pizza几何，水详解编程语言
Gleb ordered pizza home. When the courier delivered the pizza, he was very upset, because several pieces of sausage lay on the crust, and he does not really like the crust. The pizza is a circle of r
日期 2023-06-12 10:48:40
CodeForces 91A Newspaper Headline
题目描述 A newspaper is published in Walrusland. Its heading is s 1 , it consists of lowercase Latin letters. Fangy the little walrus wants to buy several such newspapers, cut out their headings, glue
日期 2023-06-12 10:48:40codeforces——Little Pony and Sort by Shift
/* 题目大意：给你一个序列，不断地将最后边的数值移动到最前边，问最少经过多少次可以变成一个单调递增的序列！ 如果不能则输出-1。 如果该序列按照不断从后向前移动排序成功，那么该序列要么只有一个单调递增的序列， 或者有两段单调递增的序列（1..k 和 k+1..n）并且 （k+1...n)中的最大值num[n] =（1...k）中的最小值num[1] #include io
日期 2023-06-12 10:48:40codeforces B. Design Tutorial: Learn from Life
题意：有一个电梯，每一个人都想乘电梯到达自己想要到达的楼层！从a层到b层的时间是|a-b|， 乘客上下电梯的时间忽略不计！问最少需要多少的时间.... 这是一道神题啊，自己的思路不知不觉的就按照注解的思路走了,想着用优先队列模拟一下，可能还是没有模拟好吧，一直哇！但是同学的优先队列模拟过了！ 没想到是greedy算法简单的几行就解决了！ #include iostream #i
日期 2023-06-12 10:48:40codeforces MUH and Important Things
/* 题意：给一个序列，表示每一项任务的难度，要求完成每一项任务的循序是按照难度由小到大的！输出三种符合要求的工作顺序的序列！ 思路：直接看代码.... #include iostream #include cstring #include cstdio #include algorithm #define N 2005 using namespace std; st
日期 2023-06-12 10:48:40codeforces B. Friends and Presents(二分+容斥)
题意：从1....v这些数中找到c1个数不能被x整除，c2个数不能被y整除！并且这c1个数和这c2个数没有相同的！给定c1, c2, x, y， 求最小的v的值！思路： 二分+容斥，二分找到v的值，那么s1 = v/x是能被x整除的个数s2 = v/y是能被y整除数的个数，s3 = v/lcm(x, y)是能被x,y的最小公倍数整除的个数！ 那么 v-s1 =c1 v-s2 =c2 v-s3 =c
日期 2023-06-12 10:48:40【Educational Codeforces Round 102 D】Program
题目链接 链接 翻译 给你一个长度为 \(n\) 的序列，每个字符为加法或减法操作，这些操作按顺序执行，且初始的时候你的数字为 \(0\)。 现在给你 \(m\) 个询问，这些询问用区间 (l,r) 描述，表示从 \(l\) 开始到 \(r\) 结束这一段的操作被忽略了。 然后剩下的操作还是按顺序执行的话，问你最后在数字变化的过程中，会出现多少个不同的数字。 题解 首先不同的数字个数，就是在变换
日期 2023-06-12 10:48:40【Codeforces Round #693 (Div. 3) G】Moving to the Capital
题目链接 链接 翻译 注意是有向图，不然这题读起来会觉得题目很奇怪。。 题解 bfs 求最短路 d[1..n]，然后对于 \(d_i<d_j\) 的边连实线，否则连虚线。 就可以做 dp 了，对于实线 dp[x] = min(dp[x],dp[y]),对于虚线 dp[x] = min(dp[x],d[y]) 。 虚线只能走一次嘛。然后实线还能顺着往下走。妥妥的记忆化，当然不要忘了待在原地不
日期 2023-06-12 10:48:40【Codeforces Round #695 (Div. 2) E】Distinctive Roots in a Tree
题目链接 链接 翻译 给你一棵树，树上的每一个节点都带有权值。 让你统计这样的点 \(x\) 的个数，使得以 \(x\) 为根的时候，所有以 \(x\) 开始，以某个节点结束的路径中每个节点的权值 都是唯一的，即每个权值都只出现了一次。 称这样的 \(x\) 为 \(distinctive\ root\), 统计所给的树中这样的 \(distinctive\ root\) 的个数。 题解 如图
日期 2023-06-12 10:48:40【Codeforces Round #693 (Div. 3) E】Correct Placement
题目链接 链接 翻译 translation 题解 线段树，只要维护一个以 \(w\) 为下标，然后线段树上的值维护的是这个范围的 \(w\) 里面, 最小的 \(h\) 所在的位置即可。 涉及到一些离散化的操作，所以代码看起来比较丑陋。 然后查询的时候，如果想找小于 \(w\) 和 \(h\) 的，就先在 \(1..w-1\) 这个范围里找最小的 \(h_{min}\) 然后用这个 \(h_{
日期 2023-06-12 10:48:40【Educational Codeforces Round 97 (Rated for Div. 2) C】Chef Monocarp
题目链接 链接 翻译 给每道菜确定一个取出时间，每道菜对不愉快程度的贡献为它取出的时间和最佳取出时间差的绝对值。 要求最后不愉快程度之和最小，求这个最小值。 题解 动态规划，一个很显然的贪心是，我们把 \(t\) 进行排序，然后依次从小到大地顺序分配每个菜是最好的。 也即时间小的菜分配对应的时刻也应该要靠前。 最后用到的时刻一定不会超过 \(2*n\)。所以定义 \(f[i][j]\) 表示前
日期 2023-06-12 10:48:40【Codeforces 1461E】Water Level
题目链接 链接 翻译 让你维持水位始终在 [l,r] 这个范围 且，你每天开始的时候可以加(所以也可以不加) \(y\) 升水，然后结束的时候会少掉 \(x\) 升水(固定)。 一开始水位是 \(k\)，问你这样(水位始终在 [l,r] 这个区间) 能否持续 \(t\) 天。 题解 如果 \(y<x\)，那么显然水位只会一直下降。则一开始如果水位大于 \(r-y\) 那么就每次只减少 \(
日期 2023-06-12 10:48:40【Codeforces Round #650 (Div. 3) D】Task On The Board
题目链接 链接 翻译 将 \(s\) 删掉 \(|s|-m\) 个字符之后，剩下的 \(m\) 个字符任意排序得到 \(t\)。根据 \(t\) 上每个字符的字典序的大小关系生成了一个序列 \(b\)。 现在告诉你 \(s\) 以及 \(m\) 和 \(b\) 让你输出某个可能的 \(t\)。 题解 \(trick\) 就是每次找到 \(b\) 的值为 \(0\) 的位置，其他不为 \(0\)
日期 2023-06-12 10:48:40【Codeforces Round #644 (Div. 3) F】Spy-string
题目链接 链接 翻译 让你构造一个和 \(n\) 个字符串都只有【最多一个地方】不同的字符串 题解 只考虑第一个字符串，假设第 \(i\) 个位置不同，那么每个位置都有 \(26\) 种可能(其中一种是和本身一样) 看看得到的字符串是不是符合要求的就好。 代码 #include <iostream> #include <string> using namespace st
日期 2023-06-12 10:48:40【Codeforces Global Round 9 D】Replace by MEX
题目链接 点我呀 翻译 给你一个长度为 \(n\) 的数组。 你可以将某个位置上的数字换成 \(mex\) 最多 \(2*n\) 次。 让你把这个数组变成不下降的，这个数组中的数字都在 \(0..n\) 之间。 \(mex\) 表示没有出现过的最小的整数。 题解 构造题，我们可以把目标改为让最后的数组变成 \(0,1,2\cdots n-1\)。 可以这样做，一开始肯定有很多位置 \(a[i]!
日期 2023-06-12 10:48:40【Codeforces Round #639 (Div. 2) A】Puzzle Pieces
题目链接 点我呀 翻译 给你一个拼图, 问你能不能把它拼成一个 \(n \times m\) 的方格图。 题解 会发现, 只有 \(2 \times 2\) 的能拼出来, 或者是一个长条形的。 往下或者往右一直延伸这样, 然后宽度或高度为1。 代码 #include<bits/stdc++.h> #define ll long long #define rei(x) scanf("%
日期 2023-06-12 10:48:40【Codeforces Round #635 (Div. 2) C】Linova and Kingdom
题目链接 点我呀 翻译 给你一棵树, 让你在这棵树上选择恰好k个点, 这k个点是发展工业的, 然后其余的n - k个点发展旅游业。 但是根节点(约定1号节点是根节点)例外, 它可以发展旅游业也可以发展工业(不过后面会发现这条件没啥用。。)。 假设x是你选出来的k个点中的一个, 对于所有的x, 你需要求出每个节点x到根节点1会经过的 发展旅游业 的节点个数\(cnt_i\), 然后对cnt求和,
日期 2023-06-12 10:48:40【Codeforces Round #667 (Div. 3) F】Subsequences of Length Two
题目链接 点我呀 翻译 你可以把字符串 \(s\) 中的某个字符改成任意一个字符最多 \(k\) 次，这样做之后，问你最后形成的 \(s\) 中最多会有多少个 \(t\) 子序列。 题解 设 \(f[i][j][l]\) 表示前 \(i\) 个字符，修改了 \(j\) 次, 有 \(l\) 个 \(t[1]\) 字符, \(t\) 作为子序列最多出现的次数。 假设已经求得了前 \(i\) 个字符
日期 2023-06-12 10:48:40【Codeforces Round #668 (Div. 2) D】Tree Tag
题目链接 点我呀 翻译 给你一棵树，一个人(\(Alice\))在 \(a\) 处，一个人(\(Bob\))在 \(b\) 处，其中 \(a\) 每次可以移动到距离(经过的边的个数)为 \(da\) 以内的任意一个点上，\(b\) 每次可以移动到距离为 \(db\) 以内的任意一个点上。 在 \(a\) 上的人 \(Alice\) 先移动，问 \(A\) 能否在有限次的移动过后和 \(Bob\)
日期 2023-06-12 10:48:40【Codeforces 1389D】Segment Intersections
题目链接 点我呀 翻译 给你 \(n\) 对区间，一开始每对区间都是 [l1,r1] 和 [l2,r2]。 每对区间你都可以求他们的交集的长度，长度定义是尾巴减头部 (不用加 \(1\))，每对区间的交集和加起来，要求最后的交集的和大于等于 \(k\)。 并且你可以扩展 \((x,y)\) 成为 \((x-1,y)\) 或 \((x,y+1)\) 问你最少需要多少次这样的扩展操作才能满足要求。
日期 2023-06-12 10:48:40【Codeforces 1385 E】Directing Edges
题目链接 点我呀 翻译 给你一个 \(n\) 个节点 \(m\) 条边的图，但是有一些边的方向还没有确定。 问你能否将其中没有确定方向的边确定了，使得最后形成的整张图没有环。 题解 一说就会做的题。 先将已经确定了方向的边作为图的边，然后在这个有向图的基础上跑拓扑排序。 记录下每个节点在拓扑排序中的序号。 然后在最后输出答案的时候，对于没有确定方向的边，将其方向改为从拓扑排序序号小的节点指向序号
日期 2023-06-12 10:48:40