codeforces 385 c
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:40
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: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:40
Codeforces Round #825 (Div. 2) (A~C1)
A. Make A Equal to BOrigional Link题目大意：给定只含 0,1 的序列 a,b。对序列 a 不限次数执行如下操作： 将 a_i 变为 a_i - 1 。 将 a 按照任意顺序重新排列。 求最少几步可以得到和 b 相同的序列 a。思想： 思维题。分为两种情况讨论：不排序 a 直接操作和先排序 a 再操作的情况。 同时遍历一遍 a 和 b，记录 a[i] != b[
日期 2023-06-12 10:48:40【题解】差分数组-codeForces-1197C – Array Splitting
题目链接：https://codeforces.com/contest/1197/problem/C题目大概意思是，给出一个不下降序列，定义cost是区间右端点的值减去区间左端点的值。要求把数组分为n段，求最小的cost。今下午训练的时候做到这道题我有点懵（毕竟我是菜鸡），然后就观察了一下，发现了一个小现象。把给出的数组的前后两个元素分别相减，就会得到一个新的数组。这个新数组的各个元素之和，就是某
日期 2023-06-12 10:48:40CodeForces – 1312D 组合数
这题主要就是涉及到满足条件的组合数，思路：从m个数中选择n-1个不同的数。由于里面的元素只有一个重复，而且重复的元素不能是最大值，那么就要从剩下的n-2个数中选择出一个最大值，下标为i。对于剩下的n-3个数，选x个排在最大值的左侧，这样的话，总共的情况数就是C(n-1,m)*(n-2)*(2^(n-3))那么代码就很简单了。但是问题来了，这个组合数会很大，要模除一个数。然后由于同余线性方程组没有除
日期 2023-06-12 10:48:40C. Polycarp Restores PermutationCodeforces Round #547 (Div. 3)
Codeforces Round #547 (Div. 3)复制 #include <bits/stdc++.h> #define ll long long using namespace std; int n,m; map<int,int> mp; ll pre[200005],s[200005],a[200005]; int main() { scanf(&qu
日期 2023-06-12 10:48:40【算法竞赛】Codeforces Round #841 (Div. 2) C, E
闲言赛时ABD，C题没做出，赛时其实想到过前缀和，然后就是没太想清楚怎么高效的利用前缀信息。Problem - C - Codeforces容易发现，当一个数是另一个数的平方时，有奇数个因数。而区间得到的结果，最多是2*n-1，联系数据范围，对答案有贡献（减少）的数较少。所以，利用异或运算的可逆性，从对答案有贡献的值倒推。而为了实现区间的倒推，可以尝试记录下前缀和s的当前值，每个前缀和出现过的次数
日期 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:40A. The Fair Nut and Elevator （Codeforces Round #526 (Div. 2)）
A. The Fair Nut and Elevator好笨啊QAQ。暴力枚举的题，连分类都不用。从电梯初始位置到第一层、人到第一层、间隔的层数，往返路程。#include <bits/stdc++.h> using namespace std; int a[105]; int main() { int n; while(~scanf("%d"
日期 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:40CodeForces - 282A Bit++ （水）
CodeForces - 282A Bit++ Submit Status DescriptionThe classic programming language of Bitland is Bit++. This language is so peculiar and complicated.The language is that peculiar as it h
日期 2023-06-12 10:48:40CodeForces - 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:40codeforces D. Design Tutorial: Inverse the Problem
题意：给定一个矩阵，表示每两个节点之间的权值距离，问是否可以对应生成一棵树，使得这棵树中的任意两点之间的距离和矩阵中的对应两点的距离相等！思路：我们将给定的矩阵看成是一个图，a 到 b会有多条路径， 如果存在一棵树，那么这个树中a- b的距离一定是这个图中所有a- b中路径长度最短的一条！所以我们根据边权，建立一棵MST树！再将MST树中的任意两点之间的距离求出来，看是否和矩阵中的对应的节点对距离
日期 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 Round #277(Div. 2) （A Calculating Function, B OR in Matrix, C Palindrome Transformation）
题意：计算f(n) = -1 + 2 -3 +4.....+（-1）^n *n的值 思路：偶数和 - 奇数和（或者用等差数列计算化简得到结果） #include algorithm #define N 10000 using namespace std; int main(){ long long n; cin n; if(n%2==0) cout n/2 endl
日期 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:40
codeforces B - Preparing Olympiad（dfs或者状态压缩枚举）
You have n problems. You have estimated the difficulty of the i-th one as integer ci. Now you want to prepare a problemset for a contest, using some of the problems youve made. A problemset for the c
日期 2023-06-12 10:48:40codeforces Round #320 (Div. 2) C. A Problem about Polyline(数学) D. "Or" Game(暴力，数学)
解题思路：就是求数 n 对应的二进制数中有多少个 1 解题思路:对（strength, i, j）按照strength进行递减排序，从左到右进行遍历，用b[N]表示i和j有关系！ 如果发现b[i]或者b[j]有关系了，则跳过这个strength， 否则b[i] =j, b[j] = i #include iostream #include algorithm #incl
日期 2023-06-12 10:48:40【Educational Codeforces Round 103 (Rated for Div. 2) C】Longest Simple Cycle
题目链接 链接 翻译 每一列的头尾会和前一列的第 \(a_i\) 和第 \(a_j\) 个节点相连，第 \(i\) 列有 \(c_i\) 个节点。 问你能形成的一个最长的环是多少。 题解 设 \(pre_i\) 表示从第 \(i\) 列的 两端 开始，往前延伸，形成的最长的环。 则 \(pre_i\) 有两种更新方式，第一种在第 \(i-1\) 列往两边开花，第二种，在第 \(i-1\) 列闭合
日期 2023-06-12 10:48:40【Educational Codeforces Round 101 (Rated for Div. 2) D】Ceil Divisions
题目链接 链接 翻译 定义一个数组 \(a_i = i\) 你每次可以选择两个下标 \(i\) 和 \(j\)，让你用 \(a_i\) 去除 \(a_j\) (向上取整)。 希望最后 \(n\) 个数字中剩下 \(n-1\) 个 \(1\) 以及 \(1\) 个 \(2\)。 且操作的次数不能超过 \(n+5\) 次。 题解 思路是这样的，对于 \(1\) 的产生，只需用 \(i\) 去除 \(
日期 2023-06-12 10:48:40【Educational Codeforces Round 102 C】No More Inversions
题目链接 链接 翻译 给你一个序列 \(a\), 是 1,2,3...k 按顺序组成的 \(n\ (n>=k)\) 个数字, 超过 \(k\) 了，又从右往左取。 然后，让你确定一个排列 \(p\)，使得它按照 \(a\) 中元素作为下标顺序取，得到的序列 \(b\) 中逆序对的个 数不超过原序列 \(a\)。并且，要求得到的序列 \(b\) 的字典序是最大的。 题解 做这题之前，先得知道
日期 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 #693 (Div. 3) D】Even-Odd Game
题目链接 链接 翻译 translation 题解 贪心，随便想想也能猜到，排序。然后哪一方最大的数字大(奇数和偶数)，就抢对方的(对方的奇偶性数字大)，或者拿自己的(自己的奇偶性大)。 这样，对于拿的那个人来说收益总是最大的。 不够了就随遇而安就行。。 代码 #include <bits/stdc++.h> #define lson l,mid,rt*2 #define rson
日期 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:401800*1【Codeforces Round #665 (Div. 2) D】Maximum Distributed Tree
题目链接 链接 翻译 让你给树上的每条边分配一个数字。要求这 \(n-1\) 个数的乘积要等于 \(k\) 分配的 \(1\) 的个数要尽可能少。 这个 \(k\) 质因数分解的时候，每个质因子的指数都是 \(1\)，且 \(k\) 是以告诉你它每个质因子的形式给出的。 要求树上任意两点之间的距离和最大。输出这个最大值。 题解 感觉证明做法的正确性会比做法本身难。。 首先解决两点之间距离和这个问
日期 2023-06-12 10:48:40【Codeforces 1453D】Checkpoints
题目链接 链接 翻译 每个阶段都有 \(\frac{1}{2}\) 的几率失败，失败了会回到上一个存档点。 想让玩家的期望尝试次数为 \(k\)，问你能否设计出一个不超过 \(2000\) 级台阶的策略，满足这个要求。 题解 如果只有一个 \(1\) 的话，那么期望尝试次数为 \(2\)。假设后面出现了一个 \(0\)，即 10，那么到达第 \(2\) 层且通过了第二层(能够到达第三层了)的期望
日期 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 #629 (Div. 3) D】Carousel
题目链接 链接 翻译 给你两种重量的物品, 重量分别为 \(S\) 和 \(W\), 数量分别为 \(cntS\) 和 \(cntW\)。 有两个人，第一个人的背包容量为 \(p\), 第二个人的背包容量为 \(f\)。要让这两个人拿走的物品的数量之和最大。 问你最大可能为多少。 即有数量限制，物品价值都相同为 \(1\) 要求最大数量。 题解 中间枚举的量记得要还原 代码 #include
日期 2023-06-12 10:48:40