- 博客(204)
- 收藏
- 关注
RSS订阅原创 Educational Codeforces Round 116 (Rated for Div. 2)
比赛链接题目链接题解链接难度主要算法A. AB BalanceA. AB Balance900思维B. Update FilesB. Update Files1100暴力C. BanknotesC. Banknotes1400贪心D. Red-Blue Matrix2400E. ArenaE. Arena2100DP，组合数学...
2021-11-01 20:10:10
276
原创 Educational Codeforces Round 116 (Rated for Div. 2) E. Arena
E. Arena题目链接题目大意：有n个人，每人有ai点生命值(ai <= k),每次每人会对其他所有人造成1点伤害。生命值低于1的会死亡，给出 n 和 k ，问有多少种情况会出现场上无人存活输出答案总数%9982443532 , 1, 1 和 1 , 1 , 2 被视为两种思路：这题直接求好像有点困难， 我们采取间接法也就是先求出剩下一个人的情况， 再用总数去减（最后肯定要么剩一个，要不全部死亡）这里我们可以定义状态dp[n][k]n个人生命值在k内最后省一个人的方案数然后考
2021-11-01 19:58:38
331
原创 Educational Codeforces Round 116 (Rated for Div. 2) C. Banknotes
C. Banknotes题目链接题目大意：有n种不同类型的货币，每种货币是10 ^ ai （ai ≤ 9）,现在有一个函数f(x)为 精确表示x所需的最小纸币数量问 f(x) > k 的最小x（如果题意不清楚可以再去仔细看看样例）思路：由于货币都是10的指数形式的且要所需纸币量最小，所以如果能用大的尽量用大的所以对于每个数我们最多可以用ai+1/(ai−1)a_{i+1}/(a_i - 1)ai+1/(ai−1)次因为，如果你用10张10，肯定不如用1张100最大的除外
2021-11-01 18:06:13
255
原创 Educational Codeforces Round 116 (Rated for Div. 2) B. Update Files
B. Update Files题目大意：有n个人，最初只有1知道消息，每次每个人可以传递一次消息给另一人，每次传递最多只有k个人可以进行传递，问最小需要多少次才能使所有人都知道消息思路：如果不考虑k第一次有1个人可以传第二次有2个人可以传第三次有4个人可以传第n次就有2 ^ n个人可以传然后我们枚举前64次，如果次数超过k则弹出，或者传递完也弹出因为有k的限制，我们后面只能传k个人就需要 ⌈(n−pre[i])/k⌉\lceil(n - pre[i] )/k\rceil⌈(n−pre
2021-11-01 17:34:47
172
原创 Educational Codeforces Round 116 (Rated for Div. 2) A. AB Balance
A. AB Balance题目大意：给出一个只有a 和 b 的字符串，你可以将a改成b，也可以将b改成a，问最少修改几次可以使字符串中ab , ba 的数量相等，输出修改后的字符串思路：因为这里的ab, ba 是连续的，所以中间如果出现aaaa, bbbb这种连续的没有任何意义我们将其缩起来，将连续的变成一个最后就只会剩下a和b相间的字符串eg ： ababababab ， bababababa，abababababa这时我们去搜一遍， 如果ab 数量 等于 ba 数量， 那么皆大欢喜，直
2021-11-01 17:24:57
226
原创 2020CCPC长春F. Strange Memory （树上启发式合并 + 下标拆位）
F. Strange Memory题目链接题目大意：有一个根为1的树，每个点都有一个点权ai，求∑i=1n∑j=i+1n[aixoraj==alca(i,j)]∗(ixorj)xor指异或\sum_{i = 1}^{n}\sum_{j = i+1}^{n}[a_i xor a_j == a_{lca(i, j)}]*(i xor j)\\xor指异或i=1∑nj=i+1∑n[aixoraj==alca(i,j)]∗(ixorj)xor指异或思路：1、只有对子树的询问2、没有修改
2021-10-31 11:54:59
195
原创 Noob Notes(6)——VScode常见配置、插件推荐以及常见问题（一）（Error Lens 不显示错误的原因和解决方案）
VScode 插件推荐以及常见问题Chinese (Simplified) (简体中文)Code Runnerbackground-cover插件安装在这，直接搜就好Chinese (Simplified) (简体中文)汉化插件，基本必装，装完重启VScode就好了Code Runner程序运行插件，有一个就够了推荐设置往下滑，推荐勾选这两个，第一个是启用Code Runner，第二个是运行前保存不然每次运行前都按一下保存挺麻烦的Code Runner 运行的快捷键是 Ctr
2021-10-29 15:13:51
5301
9
原创 Codeforces Round #751（A - C）
题目链接题解链接难度主要算法A. Two SubsequencesA. Two Subsequences800B. Divine ArrayB. Divine Array1100暴力C. Array EliminationC. Array Elimination1300思维，枚举D. Frog Traveler1900E. Optimal Insertion2300F. Difficult Mountain2700...
2021-10-26 15:57:43
180
原创 Codeforces Round #751 (Div. 2) C. Array Elimination
C. Array Elimination题目大意：给出n个数，你可以任意次选择其中任意k个数进行操作，使这k个数减去其按位与（&）的和， 最终使n个数都为0，找出有多少个这样的k思路：手模下样例可以看出，对于每一位，设1的个数为s，那么满足条件的k一定是s的因子，因为只有这样才能完美的消掉每一个1。然后对于整个数，我们肯定要找出每一位都能满足条件的k，才能使整个数为0AC代码：#include <bits/stdc++.h>#define PII pair<in
2021-10-26 15:51:08
386
原创 Codeforces Round #751 (Div. 2) B. Divine Array
B. Divine Array题目大意：给你n个数，每个数可以进行一种变换，使其变成当前这个数的个数，即a[i] = cnt[a[i]] .有m次询问问第x个数变换k次后的值思路：可以注意到其数据很小，只有2000，而且我们很容易发现，当一个数变换一定次数后其值将不再发生改变，所以我们可以暴力处理出n个数变换n次后的值时间复杂度完全够AC代码：#include <bits/stdc++.h>#define PII pair<int,int>#define ll
2021-10-26 15:36:52
245
原创 Codeforces Round #751 (Div. 2) A. Two Subsequences
A. Two Subsequences题目大意：给你一个字符串 s。您需要找到两个非空字符串 a 和 b，以满足以下条件：字符串 a 和 b 都是 s 的子序列。对于每个索引 i，字符串 s 的字符 si 必须恰好属于字符串 a 或 b 之一。字符串 a 是字典序最小可能的；字符串 b 可以是任何可能的字符串。给定字符串 s，打印任何有效的 a 和 b。思路：字典序最小当然就是s中的最小字母了，b可以是任意，那么就是s减去a后的字符串了AC代码：#include <bits/st
2021-10-26 15:30:56
263
原创 Codeforces Round #750 (Div. 2) F1. Korney Korneevich and XOR (easy version)
F1. Korney Korneevich and XOR (easy version)题目大意：给出一个长度为n的序列，问其递增子序列的异或和有多少种情况，并输出所有情况子序列为原序列删除若干个元素得到的序列思路：DP，因为ai最大只有500，异或和最大也就是512，用dp[j]表示异或和为j的递增子序列中的最小值，只要ai比这个最小值大，说明有这种情况AC代码：#include <bits/stdc++.h>#define PII pair<int,int>#
2021-10-25 21:13:33
406
2
原创 Codeforces Round #750 (Div. 2) E. Pchelyonok and Segments
E. Pchelyonok and Segments题目大意：在一个数组中找出不相交的k个区间，第一个区间长度为k，使区间长度递减的同时，区间和递增，问最大的k是多少（可以从任意点开始为第一个区间）思路：利用前缀和来O（1）求区间和，然后很容易知道k绝对不会超过500（等差数列前n项和）显然是个区间DP状态dp[i][k] 为 i - n 取k个区间的区间最大值，我们反过来求递减的状态转移：if(dp[i+j][j-1]!=0 && sum[i] - sum[i+j] &l
2021-10-25 20:10:02
244
原创 Codeforces Round #750 (Div. 2)（A - F1）
题目链接题解链接难度主要算法A. Luntik and ConcertsA. Luntik and Concerts（内附结论证明）思维B. Luntik and SubsequencesB. Luntik and Subsequences思维C. Grandma Capa Knits a ScarfC. Grandma Capa Knits a Scarf（本题解图文结合，理解更简单）思维，暴力D. Vupsen, Pupsen and 0D....
2021-10-25 19:13:41
244
原创 Codeforces Round #750 (Div. 2) D. Vupsen, Pupsen and 0
D. Vupsen, Pupsen and 0题目大意：给出一个大小为n的数组a，|ai| ≤ 1e4, n ≤ 1e5让你构造一个数组b使得 ∑inai∗bi=0且∑in∣bi∣<=1e9\sum_i^n a_i * b_i = 0\\且\sum_i^n|b_i| <= 1e9i∑nai∗bi=0且i∑n∣bi∣<=1e9思路：首先我们可以知道两个数ai, aj,我们肯定是可以通过 ai * aj - aj * ai = 0来构造b的，再进行一个优化，我们交换后再
2021-10-25 19:04:27
231
原创 Codeforces Round #750 (Div. 2) C. Grandma Capa Knits a Scarf（本题解图文结合，理解更简单）
C. Grandma Capa Knits a Scarf题目大意：给出一个字符串，你可以删除若干个相同字符，问最少删除多少个字符可以使字符串变成一个回文串思路：首先我们从外往里找，找出第一个不相等的字符如果要想通过删除变成回文串，那么删除的必然是这两个字符之一所以我们继续往里枚举两种情况（上图是删b，和删c）如果相同就跳过，不相同就删除我们可以删除的那个字符，如果删除不了该种情况就不行，如果两种情况都不行，那么就是-1了AC代码：#include <bits/stdc
2021-10-25 18:42:13
629
原创 Codeforces Round #750 (Div. 2) B. Luntik and Subsequences
B. Luntik and Subsequences题目大意：给出一个长度为n的序列，其和为s问有多少个和为s - 1的子序列子序列由序列删除若干个元素而来思路：每次只能从原序列中删除0 和 1且1必须有，每个0有删与不删两种状态答案很显然，就是ans=sum1∗2sum0其中sum1是1的个数，sum0是0的个数ans = sum1 * 2^{sum0} \\其中sum1是1的个数，sum0是0的个数ans=sum1∗2sum0其中sum1是1的个数，sum0是0的个数AC代码：#
2021-10-25 18:23:41
151
原创 Codeforces Round #750 (Div. 2) A. Luntik and Concerts（内附结论证明）
A. Luntik and Concerts题目大意：将a个1，b个2，c个3，分成两份，使两份的差值尽可能小，问最小差值注意a,b,c>=1思路：直接判断所有数总和的奇偶性就好了，因为，a,b,c至少为1，所以只有0,1两种可能证明：我们可以同时将a,b,c减1，答案不会变化，也可以将其中任意一种减2，答案也不会变化，这样，a,b,c之间的差值就不会大于1，然后只要通过一边放b，一边放c来使差值加1减1，放a也是差值加1减1，所以差值最大只能是1了。答案也显然就是 (a + 2 *
2021-10-25 18:11:40
212
2
原创 Codeforces Round #748 (Div. 3)
Codeforces Round #748 (Div. 3)比赛链接题目题解难度主要算法A. ElectionsA. Elections800B. Make it Divisible by 25B. Make it Divisible by 25900模拟C. Save More MiceC. Save More Mice1000贪心D1. All are SameD1. All are Same1100暴力，思维D2. Half
2021-10-14 20:01:39
185
原创 Codeforces Round #748 (Div. 3) E. Gardener and Tree
E. Gardener and Tree题目链接题目大意：给出一棵树，问对其进行k次操作还剩多少个节点，操作是：删除当前所有叶子结点思路：直接bfs模拟即可，但是要特判一个情况，只剩孤立节点的情况。AC代码：#include <bits/stdc++.h>#define pii pair<int,int>#define ll long longusing namespace std;const double eps = 1e-8;const int m
2021-10-14 19:27:01
156
原创 Codeforces Round #748 (Div. 3) D2. Half of Same
D2. Half of Same题目链接题目大意：有n个数，你可以使任意数减k任意次，问能使超过一半的数相等的最大的k思路：直接暴力枚举，细节看代码注释AC代码：#include <bits/stdc++.h>#define pii pair<int,int>#define ll long longusing namespace std;const double eps = 1e-8;const int maxn = 1e5 + 10;const in
2021-10-14 19:22:45
165
原创 Codeforces Round #748 (Div. 3) D1. All are Same
D1. All are Same题目链接题目大意：有n个数，你可以使任意数减k任意次，问能使所有数相等的最大的k思路：找出所有数减到最小值所需的数的gcd,然后枚举其倍数，然后枚举到第二小值减最小值这个数，再大就不可能了相当暴力，最坏直接全枚举一遍（D2做法）AC代码：#include <bits/stdc++.h>#define pii pair<int,int>#define ll long longusing namespace std;const
2021-10-14 19:19:59
254
1
原创 Codeforces Round #748 (Div. 3) C. Save More Mice
C. Save More Mice题目链接题目大意：在一个坐标轴上，有 1 只猫（位于0）、k只老鼠， 还有位于n的老鼠洞，猫和老鼠轮流行动，老鼠先，每次可以让一只老鼠移动一个单位长度，猫也是，猫抓到了老鼠会吃掉，问最多有多少只老鼠可以进老鼠洞（进了老鼠洞就不会被猫吃）思路：直接贪心就好，离洞进的优先，能走的步数不会发生改变，所以这样贪心最优AC代码：#include <bits/stdc++.h>#define pii pair<int,int>#define
2021-10-14 19:09:08
340
原创 Codeforces Round #748 (Div. 3) B. Make it Divisible by 25
B. Make it Divisible by 25题目链接题目大意：给出一个数，你可以删除任意数位，问最少删除多少次才能使删除后的数能够被25整除思路：能被25整除的数的性质：最后的两位数必须是00、 25 、50、75这几个数然后就是模拟模拟再模拟，细心细心再细心AC代码：#include <bits/stdc++.h>#define pii pair<int,int>#define ll long longusing namespace std;
2021-10-14 19:00:57
236
原创 Codeforces Round #748 (Div. 3) A. Elections
A. Elections题目链接题目大意：有三个人进行选举，分别有a, b, c票，问每个人各需要多少票才能成为第一。思路：对于每个人，肯定要变得比其他两个人最大值还要大一才行，或者三者唯一最大就是自己本身所以 每个人的答案就是 max(0, max(其他两人) - 自己 + 1)AC代码：#include <bits/stdc++.h>#define pii pair<int,int>#define ll long longusing namespace
2021-10-14 18:56:38
164
原创 HH的项链 、采花 （莫队，莫队思想结合树状数组）
目录HH的项链莫队做法树状数组做法采花HH的项链这道题主要有两个数据版本也主要有两个做法一个是莫队时间复杂度O(nn)时间复杂度O(n \sqrt n)时间复杂度O(nn)另一个是树状数组时间复杂度O(nlogn)时间复杂度O(n log n)时间复杂度O(nlogn)洛谷题目链接牛客题目链接牛客的这道题数据会水一点，莫队可以过题目描述：输入样例61 2 3 4 3 531 23 52 6输出样例224第一种主要做法莫队做法就是个裸的莫队了，没什么好
2021-10-14 15:07:04
88
原创 Noob Notes(5)——VS（Visual Studio）的一些常用的设置，( 使用printf和scanf的报错，万能头文件，背景)
VS（Visual Studio）的一些常用的设置（一）使用printf 和 scanf 报错，必须用-s的解决办法（二）在Visual Studio中使用万能头文件（三）背景设置（一）使用printf 和 scanf 报错，必须用-s的解决办法把这个复制进去WIN32_DEBUG_CONSOLE_CRT_SECURE_NO_WARNINGS就好了或者在代码最开头加上这个#pragma warning(disable : 4996)（二）在Visual Studio中使
2021-09-26 22:24:34
2382
5
原创 Python学习日记（1）Python 环境搭建 与 IDE的配置（PyCharm与VScode）
Python学习日记（1）Python 环境搭建IDE的配置PyCharmPython 环境搭建搭建环境，就是需要编程用的语言和用什么进行编程，用什么进行调试的这几个条件的总和。下面开始手把手教你搭建这里以Windows为例首先我们先到Python官网下载安装器Python3的最新版本（目前是3.9.7 ---- 2021.9.14）一定要勾选，这样可以让他自动添加环境变量这样环境就搭建好了可以进行一个小测试window + R调出命令提示符输入 python --v
2021-09-14 16:25:29
418
原创 Codeforces Round #641 (Div. 2)
题目题解链接难度主要算法A. Orac and FactorsA. Orac and Factors900思维B. Orac and ModelsB. Orac and Models1400DPC. Orac and LCMC. Orac and LCM1600数论D. Orac and MediansD. Orac and Medians2000贪心，思维...
2021-09-13 14:30:14
80
原创 Codeforces Round #641 (Div. 2) D. Orac and Medians
D. Orac and Medians原题链接题目大意：给出n个数的序列，定义一个操作，将区间[l , r]内的数都变成其中位数区间大小为偶数时取偏左边那个问能否将n个数都变成k思路：一道贪心，首先肯定要满足至少存在一个k然后要出现连续3个数中至少有两个数大于等于k，出现一次即可首先对于3个数中至少有两个数大于等于k，我们就可以使这3个数都大于等于k，然后不断的使其他数都大于等于k。如果等于k，那更好，对于大于k的，我们用一个与其相邻的k构成一个区间进行操作，因为他大于k，所以两个数都
2021-09-13 14:22:21
96
原创 Codeforces Round #641 (Div. 2) C. Orac and LCM
C. Orac and LCM原题链接题目大意：给出n个数，求一个由这n个数任意两个数的LCM组成的序列的所有数的GCD思路：首先对于两个数的gcd和lcm我们换种思路求我们先将两个数质因数分解gcd就是所有公共因子的最小次幂的乘积比如说 24 和 1024=23∗310=2∗5 24 = 2^3 * 3 \\ 10 = 2 * 524=23∗310=2∗5gcd（24,10）=2 gcd（24,10）= 2 gcd（24,10）=2lcm就是所有因子乘积，公共因子取两数的最大
2021-09-13 14:14:36
73
原创 Codeforces Round #641 (Div. 2) B. Orac and Models
B. Orac and Models原题链接题目大意：给出一个序列，从中选出一些数，选出后的序列，满足左边值的下标要能整除右边值的下标（左边值的下标 < 右边值的下标）（在原序列的下标），并且左边的值 < 右边的值。给出n个数，要求求出满足条件的最长的序列的长度。思路：一道挺简单的DP，别看错题就好QWQAC代码：#include<cstdio>#include<iostream>#include<cstring>#include<
2021-09-13 13:44:36
76
原创 Codeforces Round #641 (Div. 2) A. Orac and Factors
A. Orac and Factors原题链接题目大意：定义一个函数f（n）,f（n）= n的不为1的最小因子现在给出一个操作，使 n = n + f（n）问对于数n，进行操作k次后的值思路：我们可以知道在进行一次操作后，得到的数n一定是2的倍数证明：对于偶数，显然对于奇数，其最小因子不可能的偶数，所以奇数加奇数，变成偶数所以我们只需要进行一次操作，剩下的k - 1次操作都是加2答案就是 n+f（n）+2（k−1）n + f （n）+ 2 （k-1）n+f（n）+2（k−1）AC
2021-09-13 13:36:10
76
原创 Educational Codeforces Round 113 (Rated for Div. 2)
题目题解链接难度主要算法A. Balanced SubstringA. Balanced Substring暴力B. Chess TournamentB. Chess Tournament思维C. Jury MeetingC. Jury Meeting思维，组合数学D. Inconvenient PairsD. Inconvenient Pairs思维...
2021-09-10 17:43:47
113
原创 Educational Codeforces Round 113 (Rated for Div. 2) D. Inconvenient Pairs
D. Inconvenient Pairs原题链接题目大意：在一个大小为 1e6 * 1e6的矩形中有n条横着的马路（水平）有m条竖着的马路（竖直）有k个人问有多少对人（两个人）之间走马路的距离大于他们的曼哈顿距离思路：首先，对于站在 十字路口 的人，到达其他人的距离一定是等于其曼哈顿距离的那么对于不在十字路口的人我们会发现，与其距离大于曼哈顿距离的一定人，一定是在其上面的路或者下面的路（拐两个弯）或者左边右边的路（不在同一条路！）我们为了不重复计算只取上面，或者只取左边注意这
2021-09-10 17:37:11
179
原创 Educational Codeforces Round 113 (Rated for Div. 2) C. Jury Meeting
C. Jury Meeting原题链接题目大意：有n个数，每次依次给数减一，如果已经为0则跳过，减完再从头开始。问有多少个序列（由这n个数组成）满足条件：不连续减一个数两次思路：首先，很容易想到，如果 最大的数（记为maxx） 比 次大的数（记为b） 大2以上，是不可能找到一个序列满足条件的，因为，在最后序列一定会是maxx - b,如果它不是1的话，那可能会连续减两次所以 次大数一定要比最大数小1 才能找出序列再往下想当最大数有多个时，减到最后一定会有多个1，不管怎样都满足条件，答案为
2021-09-10 17:17:03
176
原创 Educational Codeforces Round 113 (Rated for Div. 2) B. Chess Tournament
B. Chess Tournament原题链接题目大意：有n个人，两两进行一次比赛每个人都一个要求（1或2）1：不输任意一场比赛2：最少赢一场比赛问能否找出满足条件的情况，能就YES，不能就NO能的话输出比赛情况思路：首先对于要求1的人我们让他全部平局，因为这样不会造成一个人赢一个人输的情况如果赢了一个要求为1的人，那样就不满足了所以，我们让要求1的人全部平局对于要求2的人我们让他赢一个人，显然他不能赢要求为1的人，只能赢要求为2的人了那么我们找出所有要求为2的人让他们互
2021-09-10 16:57:19
181
原创 Educational Codeforces Round 113(Rated for Div. 2) A. Balanced Substring
A. Balanced Substring原题链接题目大意：给出一个字符串，其中只包含a 和 b让你找出任意一个区间[l,r]，区间内 a的数量和b的数量相等找不到就输出 -1 -1思路：数据范围很小，直接暴力就好AC代码：#include<cstdio>#include<iostream>#include<cstring>#include<algorithm>#include<queue>#define ll lon
2021-09-10 16:50:37
229
原创 Codeforces Round #643 (Div. 2)
题目题解链接难度主要算法A. Sequence with DigitsA. Sequence with Digits1200思维B. Young ExplorersB. Young Explorers1200贪心C. Count TrianglesC. Count Triangles1800差分，思维D. Game With ArrayD. Game With Array1400思维，构造E. Restorer DistanceE. ...
2021-09-07 14:25:11
72
原创 Codeforces Round #643 (Div. 2) E. Restorer Distance
E. Restorer Distance原题链接题目大意：给你n个数有三种操作1.使一个数加一，花费A2.使一个数减一，花费R3.使一个数加一，一个数减一，花费M问，使所有数相等的最小操作数思路：看到这道题首先想到的是二分，但是我们仔细想想，最终相等的数无论是加一还是减一，都可以使操作数增加或减少，不满足单调性每一个最终的数，都可以与之对应一个最小操作数，这样就会形成一个波浪形的曲线，让你求最大值，这就可以类比与二次函数，这里我们就可以明白了，三分！具体就看代码了，还有一个注意点就
2021-09-07 14:15:53
94
空空如也
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人