Codeforces
Codeforces 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:40Codeforces Round #805 (Div. 3)(A~C)
A. Round Down the Price题目大意Origional Link对于一个数N，求其最接近且不大于该数的10^m输出N-10^m思想初始化p = 1e10，循环枚举p = p / 10直到p < n代码#include <bits/stdc++.h> using namespace std; typedef long long LL; void solve()
日期 2023-06-12 10:48:40
Codeforces Round #806 (Div. 4)(A~F)
A. YES or YES?题目大意Origional Link判断是否是yes顺序的不区分大小写的字符串是则输出YES，否则输出NO思想读入暴力判断代码#include <bits/stdc++.h> using namespace std; void solve(){ string s; cin >> s; bool flag = 1;
日期 2023-06-12 10:48:40
Edu Codeforces Round 115 (Div. 2)
#NameAComputer Game 2 s, 256 MBx8894BGroups 4 s, 256 MBx5935CDelete Two Elements 2 s, 256 MBx4419DTraining Session 2 s, 256 MBx1583EStaircases 2 s, 256 MBx442FRBS3 s, 512 MBx159GThe Sum of Good Number
日期 2023-06-12 10:48:40
Codeforces Round #813 (Div. 2)(A~C)
A. Wonderful Permutation题目大意Origional Link给定长度为 n 的数组 a，元素互不相同每次可选择 a_i,a_j 进行交换求使得长度为 k 的子序列之和达到最小的交换次数思想对于子序列的和最小，应遵循最小排列即判断原序列中，前 k 个元素，有多少满足 a_i\le k，满足该条件则不需要交换，否则需要交换代码#include <bits/stdc++.h
日期 2023-06-12 10:48:40【算法竞赛】Codeforces Round #829 (Div. 2) A-F
闲言赛时A-D, C2卡了很久，思路有点糊了，其实还好，D感觉更简单，很容易看出，切了。A前面的Q至少后面要有一个A对应。用cnt来记，是Q就cnt ++, 是A就cnt = max(cnt-1, 0)B其实我乱搞构造的，证明的话可以看cf官方题解，大概就是先反证法证明答案不大于[n/2]，再证明[n/2]可构。n/2, n, n/2-1, n-1, ...分奇偶稍微讨论下即可for (int i
日期 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:40C. Prefixes and Suffixes ( Codeforces Round #527 (Div. 3) )
题意：给你一个 n 长度的字符串，给你 2n - 2 个子串，其中有 n - 1 个前缀和 n - 1 个后缀，输出一个合法的判断。题解： 找到 n - 1 长的子串一个是（假设第一个是）最长前缀，另一个是最长后缀。 判断假设是否正确，遍历所有子串，如果符合前缀 tot 加 1，如果 tot 不够 n - 1 或者我们假设的那个前缀从第二个开始不等于那个后缀的前 n - 2 个，也就是我们假设
日期 2023-06-12 10:48:40
CodeForces - 557B Pasha and Tea （模拟）
CodeForces - 557B Pasha and Tea Submit Status DescriptionPasha decided to invite his friends to a tea party. For that occasion, he has a large teapot with the capacity of w mi
日期 2023-06-12 10:48:40codeforces——Little Pony and Expected Maximum
所以最后的结果=sum((k/m)^n - ((k-1)/m)^n) (1 =k =m) 不要这样求（k^n/m^n）数据可能会很大！ #include iostream #include cstdio #include cmath using namespace std; int main(){ int n, m; while(cin m n){ double
日期 2023-06-12 10:48:40
codeforces D. Design Tutorial: Inverse the Problem
题意：给定一个矩阵，表示每两个节点之间的权值距离，问是否可以对应生成一棵树，使得这棵树中的任意两点之间的距离和矩阵中的对应两点的距离相等！思路：我们将给定的矩阵看成是一个图，a 到 b会有多条路径， 如果存在一棵树，那么这个树中a- b的距离一定是这个图中所有a- b中路径长度最短的一条！所以我们根据边权，建立一棵MST树！再将MST树中的任意两点之间的距离求出来，看是否和矩阵中的对应的节点对距离
日期 2023-06-12 10:48:40codeforces C. Design Tutorial: Make It Nondeterministic
题意：每一个人 都有frist name 和 last name！ 从每一个人的名字中任意选择first name 或者 last name 作为这个人的编号！通过对编号的排序，得到每一个人最终顺序！比较中的序列能否得到给定输出的序列一致！ #include iostream #include cstring #include cstdio #include string #
日期 2023-06-12 10:48:40codeforces George and Job
/* 题意：给一个长度为n的序列， 从中选择长度为m的k个区间（任意两个区间不会有公共部分） 使得所选择的区间的和最大！ 思路：这是一种很常见的dp dp[i][j] 表示的是前 i 个数选择 j 个 长度为m区间的最大和！ s[i]记录的是前 i 个数字的和！ dp[i][j] = max( dp[i - 1][j], dp[i - m][j - 1] + s[i]
日期 2023-06-12 10:48:40codeforces Restore Cube（暴力枚举）
/* 题意：给出立方体的每个顶点的坐标（是由源坐标三个数某几个数被交换之后得到的！）， 问是否可以还原出一个立方体的坐标，注意这一句话： The numbers in the i-th output line must be a permutation of the numbers in i-th input line! 我们只要对输入的每一行数据进行枚举每一个排列， 然后检查时
日期 2023-06-12 10:48:40codeforces C. Diverse Permutation(构造)
题意：1...n 的全排列中 p1, p2, p3....pn中，找到至少有k个|p1-p2| , |p2-p3|, ...|pn-1 - pn| 互不相同的元素！ 思路： 保证相邻的两个数的差值的绝对值为单调递减序列..... 如果够k个了，最后将没有访问到的元素直接添加到末尾！ #include iostream #include cstdio #include cstring
日期 2023-06-12 10:48:40codeforces C. Bits(数学题+或运算)
题意：给定一个区间，求区间中的一个数，这个数表示成二进制的时候，数字1的个数最多！如果有多个这样的数字，输出最小的那个！思路：对左区间的这个数lx的二进制 从右往左将0变成1，直到lx的值大于右区间的值rx！ #include iostream #include cstring #include cstdio #include algorithm using namespac
日期 2023-06-12 10:48:40codeforces Soldier and Number Game（dp+素数筛选）
outputstandard output Two soldiers are playing a game. At the beginning first of them chooses a positive integer n and gives it to the second soldier. Then the second one tries to make maximum possi
日期 2023-06-12 10:48:40Codeforces Round #326 (Div. 2) B. Pasha and Phone C. Duff and Weight Lifting
B. Pasha and Phone Pasha has recently bought a new phone jPager and started adding his friends phone numbers there. Each phone number consists of exactly n digits. Also Pasha has a number k and two
日期 2023-06-12 10:48:40【Educational Codeforces Round 101 (Rated for Div. 2) C】Building a Fence
题目链接 链接 翻译 让你放长度为 \(k\) 的长条，相邻两列必须有一个公共位置，路不是平的，长条必须放在某个高度之上。 且最高不能高过路高上面 \(k-1\)。 规定第一列和最后一列只能老老实实放在路面上。 问你能否符合上述要求放好所有的长条。 题解 每一列处理出来一个可能的长条占据的区域 \(Occpied\) 的上下界，然后以此来决定下一列可以放长条的上下界。 根据这个上下界，和第 \(
日期 2023-06-12 10:48:40【Codeforces Round #698 (Div. 2) C】Nezzar and Symmetric Array
题目链接 链接 翻译 给你 \(2n\) 个数字, 每个数字各不相同，如果 \(a[i]\) 存在的话，那么 \(-a[i]\) 也会存在于这个数组中。 定义 \(d_i\) 为 \(a_i\) 和所有数字的差的绝对值之和。 现在告诉你 \(d_i\)，让你还原出来原始的 \(a_i\)。 题解 我们假设 \(a_1,a_2,a_3...a_n\) 分别为最大的 \(n\) 个正数(会对应 \(
日期 2023-06-12 10:48:40【Codeforces Round #695 (Div. 2) A】Wizard of Orz
题目链接 链接 翻译 translation 题解 98901234.... 写题解的时候才发现题目名字里有个ORZ 代码 /* */ #include <bits/stdc++.h> using namespace std; int main(){ #ifdef LOCAL_DEFINE freopen("in.txt", "r", stdin); #endif
日期 2023-06-12 10:48:40【Codeforces Round #693 (Div. 3) C】Long Jumps
题目链接 链接 翻译 translation 题解 动规。 \(f[i] = f[i+a[i]]+a[i]\) 类似这样?...倒着推一下，注意边界就行。 代码 #include <bits/stdc++.h> #define lson l,mid,rt*2 #define rson mid+1,r,rt*2+1 #define LL long long using namespac
日期 2023-06-12 10:48:40【Codeforces Round #693 (Div. 3) B】Fair Division
题目链接 链接 翻译 translation 题解 先用 \(2\) 然后用 \(1\) 补来凑n/2就行。 挺显然的一个贪心。 代码 #include <bits/stdc++.h> #define lson l,mid,rt*2 #define rson mid+1,r,rt*2+1 #define LL long long using namespace std; const
日期 2023-06-12 10:48:40【Codeforces Global Round 7 D2】Prefix-Suffix Palindrome (Hard version)
题目链接 链接 翻译 让你选择字符串 \(s\) 的一个前缀和一个后缀(可以为空), 然后拼成一个字符串。 要求这个字符串得是一个回文串，且这个字符串的长度不能超过原串 \(s\) 的前提下最长。 输出这个字符串, hard 版本，长度小于等于 \(10^6\) 题解 接上文 现在的问题相当于要求从头部开始的连续回文串长 还是 以最后一个字符结尾的回文串长。 分开两步做，开头连续的情况，则将 \
日期 2023-06-12 10:48:40【Codeforces Alpha Round #20 C】Dijkstra?
题目链接 链接 翻译 让你求出 \(1\) 到 \(n\) 的最短路，打印路径。 题解 最短路堆优化。 记得 \(dis\) 数组开 \(long long\), 不然溢出会导致 \(TLE\) 问题 >_< 代码 \(1\) 是 \(multiset\) 写法。 代码 \(2\) 是 \(priority\ queue\) 写法。 代码1 #include <bits/std
日期 2023-06-12 10:48:40【 Educational Codeforces Round 93 (Rated for Div. 2) D】Colored Rectangles
题目链接 链接 翻译 题目描述挺绕的。 有 \(3\) 种颜色的棍子吧。 每种颜色棍子提供的时候都是一对一对给的(也即两根两根地给，然后颜色相同,长度也相同)。 每种颜色有 \(limited\) 对不同长度棍子。 然后题目的意思是说选两种不同颜色，然后分别选一对棍子。(这样就有 \(4\) 根棍子了) 组成矩形，相同颜色的在对边(长度相同所以都在对边)。 问你这些棍子组成的矩形和的最大值是多少
日期 2023-06-12 10:48:40【Codeforces Round #643 (Div. 2) C】Count Triangles
题目链接 链接 翻译 让你找 \(3\) 条边 \(x,y,z\), 要求 \(A\le x\le B\le y\le C\le z\le D\) 且 \(x,y,z\) 能组成三角形。 问你这样的 \(x,y,z\) 的个数。 题解 对于最后选出来的边，我们只需要关注 \(x+y\) 是不是大于 \(z\) 就好了 (两边之和大于第三边)。 因为 \(x<=y<=z\) 且 \(x
日期 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 C】Element Extermination
题目链接 点我呀 翻译 给你一个排列，你每次可以将 \(a[i]<a[i+1]\) 中的 \(a[i]\) 或者 \(a[i+1]\) 删掉。 问你，最后能不能删得只剩下 \(1\) 个元素。 题解 考虑最大的元素 \(n\), 想想它是不是能一直往左删元素? 但是删到第一个元素的时候，就不能再删了，因为 \(n\) 可能不是最后一个元素，如果再删的话，就没有 其他元素能删掉 \(n\)
日期 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 #639 (Div. 2) C】Hilbert's Hotel
题目链接 点我呀 翻译 一个旅馆内有无限多个房间, 每个房间里面都只有一个人住。 这些房间和所有的整数对应。 现在对于房间号为整数 \(k\) 的房间, 里面的人要移动到 \(k + a_{k\ mod\ n}\) 号房间。 给你 \(n\), 和整型数组 \(a\) , 问你移动之后, 是不是每个人都只占据一个房间, 以及每个房间是不是都没有空。 题解 这题就特别明显, 是想让你把 \(0\)
日期 2023-06-12 10:48:40