CodeForces - 1140C
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 #808 (Div 2.) A·B·C
A. Difference Operations原题链接Origional Link思想：代码#include <bits/stdc++.h> using namespace std; const int N = 1e6 + 3; int a[N]; void solve(){ int n; cin >> n; for(int i = 1
日期 2023-06-12 10:48:40【题解】codeforces-1194B
https://codeforces.com/contest/1194/problem/B这道题其实是一道思维题，主要是要把情况考虑清楚，然后在代码上把逻辑理顺，就能做出来。题目给出了cross的定义：所在行和列都全部被涂黑。这道题分析可以知道，要对每行和每列的白色格子进行计数，然后相加。然后，很自然的可以想到，如果行列相交的位置是白色格子，那么这个格子就被计数了两次，就需要在总数上减一。如果白色
日期 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:40
CodeForces – 1312D 组合数
这题主要就是涉及到满足条件的组合数，思路：从m个数中选择n-1个不同的数。由于里面的元素只有一个重复，而且重复的元素不能是最大值，那么就要从剩下的n-2个数中选择出一个最大值，下标为i。对于剩下的n-3个数，选x个排在最大值的左侧，这样的话，总共的情况数就是C(n-1,m)*(n-2)*(2^(n-3))那么代码就很简单了。但是问题来了，这个组合数会很大，要模除一个数。然后由于同余线性方程组没有除
日期 2023-06-12 10:48:40Educational Codeforces Round 137 (Rated for Div. 2)（A~E）
D和E在补了，在补了。。。A. PasswordOrigional Link题目大意：给定 n 个 0\sim 9 之间不能使用的数字，保证剩余的数大于 2。任意两个数子组合，每个数字可使用两次，组成一个四位密码。求在剩余的可选数字中，能组成的密码数量。思想：签到题。任意两个数字可组成的密码数量固定为 6。则总数量为剩余数字中的两两组合的数量乘 6。即设剩余的数的数量为 x = 10 - n，总密
日期 2023-06-12 10:48:40
Codeforces 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. 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: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:40
Codeforces 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 B. Strongly Connected City(dfs水过)
题意：有横向和纵向的街道，每个街道只有一个方向，垂直的街道相交会产生一个节点，这样每个节点都有两个方向，问是否每一个节点都可以由其他的节点到达....思路：规律没有想到，直接爆搜！每一个节点dfs一次，记录每个节节点被访问的次数！如果每个节点最终的访问次数和所有节点的数目相同，则输出“YES", 否则输出”NO“ #include queue #include string #inc
日期 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【Codeforces Round #695 (Div. 2) C】Three Bags
题目链接 链接 翻译 给你 \(3\) 个多重集，第 \(i\) 个集合有 \(n[i]\) 个数字。 从两个不同集合中分别取出数字 \(x\) 和 \(y\)，则从两个集合中分别删去 \(x\) 和 \(y\), 然后在第 \(1\) 个集合中(取出 \(x\) 的那个集合) 加入元素 \(x-y\)。 要求最后只有一个集合中剩下一个数字，问你这个数字最大可以是多少。 题解 思维 把操作 \(
日期 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 Round #693 (Div. 3) F】New Year's Puzzle
题目链接 链接 翻译 给你一个 \(2*n\) 的方格，让你用 \(1*2\) 的骨牌，横着或者竖着放，铺满整个方格。 其中有一些被黑色方块阻挡，不能放骨牌。问你可不可行。 题解 首先考虑 整个方格 第一列，如果两行都是空的。 那么考虑第二列的几种情况: 第二列也是空的，那么第一列放竖的没问题。 第二列有一个方格被堵住了，那么第一列只能竖着放了，不然铺不满(注意这是第一列，它之前没有列了) 第
日期 2023-06-12 10:48:40【Codeforces Round #223 (Div. 1) C】Sereja and Brackets
题目链接 链接 翻译 给你一个区间，让你输出其中合法的括号序列(不要求连续)的最长的长度。 题解 线段树 在节点上维护当前这个区间内左右括号已经匹配了的对数 \(mb[rt]\) 另外维护两个用于合并的数组 \(lb[rt]\) 表示还没有用来匹配的左括号的数目，\(rb[rt]\) 则是右括号。 \(trick\) 就是，在合并的时候因为区间已经足够小了。两个子区间不考虑有匹配的情况了，现在只
日期 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 #629 (Div. 3) D】Carousel
题目链接 链接 翻译 给你两种重量的物品, 重量分别为 \(S\) 和 \(W\), 数量分别为 \(cntS\) 和 \(cntW\)。 有两个人，第一个人的背包容量为 \(p\), 第二个人的背包容量为 \(f\)。要让这两个人拿走的物品的数量之和最大。 问你最大可能为多少。 即有数量限制，物品价值都相同为 \(1\) 要求最大数量。 题解 中间枚举的量记得要还原 代码 #include
日期 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 #648 (Div. 2) D】Solve The Maze
题目链接 链接 翻译 让所有的好人都能到(n,m)。所有的坏人都不能到(n,m)。 墙不能走,空格可以改为放墙。 问你可不可能。 题解 只要把坏人相邻的四个格子考虑一下,为空格的放成墙即可。 考虑被换成墙的空格，如果其他好人要通过这个墙才能到达终点，那么这个坏人也能跟着到达终点。无解。 所以不会对其他好人到终点造成影响。 代码 #include <bits/stdc++.h> usi
日期 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 #669 (Div. 2) E】Egor in the Republic of Dagestan
题目链接 点我呀 翻译 你是小 \(A\) 的管家，小 \(A\) 要从点 \(1\) 到点 \(n\)，点与点之间的边(有向边)有黑色(0)和白色(1)两种, 你可以给每个点涂色 (黑色/白色)。 黑色的点，只能沿着黑色的边接着走，白色的点同理，即如果 \(x\) 是黑色的，那么你接下来只能沿着边 \((x,y)\) 走，这条边 \((x,y)\) 也得是黑色的。 每个点的颜色由你决定，你不想
日期 2023-06-12 10:48:40【Codeforces Round #669 (Div. 2) D】Discrete Centrifugal Jumps
题目链接 点我呀 翻译 你在位置 \(1\)，然后想要到位置 \(n\)，每个位置都有一个高度 \(h[i]\), 你可以从位置 \(i\) 跳到位置 \(j\), 当且仅当以下情况之一满足: \(i + 1 = j\) \(min(h[i],h[j]) > max(h[i+1..j-1])\) 即 \(i\) 到 \(j\) 这一段里的每个位置的高度都低于 \(h[i]\) 和 \(h
日期 2023-06-12 10:48:40【Codeforces Round #635 (Div. 2) A】Ichihime and Triangle
题目链接 点我呀 翻译 给你3条边x, y, z的范围, 且满足x < y < z, 让你选出3条合法的边, 使得这3条边能组成三角形。 保证答案总是存在。 题解 因为x < y < z, 所以x(y)和z相加的话, 肯定是大于y(x)的。 因此只要判断x+y是不是大于z就可以了。 因为说了一定会有解, 所以, 找最大的x和y, 和最小的z输出。一定能满足x+y >
日期 2023-06-12 10:48:40【Codeforces Round #645 (Div. 2) F】 Tasty Cookie
题目链接 【题目翻译】 给你两个长度都为n的正整数数组,让你把A数组通过两种操作变成B数组。 支持的两种操作: 1.R操作:把A数组翻转。 2.P操作:把A数组变成A数组的前缀和数组,即a[i]=∑a[j] (1<=j<=i)。 如果P操作的次数超过2*10^5,则不用输出操作序列(只需输出第二种操作个数就行),否则输出所有的操作序列 【题解】 因为P操作是求前缀和操作
日期 2023-06-12 10:48:40【Educational Codeforces Round 88 (Rated for Div. 2) A】Berland Poker
题目链接 【题目翻译】 n张牌要平均分配给k个人(k是n的因子) 然后有m张鬼牌,剩下n-m张是普通牌。 让你分配普通牌和鬼牌。 使得最后的得分最高。 最后的得分=鬼牌数最多的那个人的鬼牌减去其他k-1人中鬼牌最多的那个人的鬼牌数。(最后答案可能为0) 【题解】 显然尽量先让一个人拿满k张鬼牌(不足就算了) 然后剩下的m-min(k,m)张鬼牌全都平均地分配给其余k-1个人就好了。
日期 2023-06-12 10:48:40【Educational Codeforces Round 81 (Rated for Div. 2) B】Infinite Prefixes
题目链接 【题解】 把0看成是1,把1看成是-1 求一个前缀和。 pre[i] = pre[i-1]+1 得到delta = pre[n] 显然对于每个位置的值pre[i] 再复制一遍s的话。 下一个s的该位置,也即i+n的前缀和显然为pre[i]+delata 那么无限的情况就很显然了。 即pre[i]==x，而且delata==0. 只要出现一个这种情况,就是无限。 其他情况,每个位置
日期 2023-06-12 10:48:40