- 博客(505)
- 收藏
- 关注
RSS订阅转载 Codeforces Round #589 (Div. 2)
目录 Contest Info Solutions A. Distinct Digits B. Filling the Grid C. Primes and Multiplication D. Complete Tripartite E. ...
2019-09-30 08:43:00
242
转载 2018 Benelux Algorithm Programming Contest (BAPC 18)
目录 Contest Info Solutions A A Prize No One Can Win B Birthday Boy C Cardboard Container D Driver Disagreement E Entirely...
2019-09-28 15:34:00
486
转载 Educational Codeforces Round 71
目录 Contest Info Solutions A. There Are Two Types Of Burgers B. Square Filling C. Gas Pipeline D. Number Of Permutations ...
2019-08-25 09:43:00
264
转载 Codeforces Round #581 (Div. 2)
目录 Contest Info Solutions A. BowWow and the Timetable B. Mislove Has Lost an Array C. Anna, Svyatoslav and Maps D1. Kirk and a B...
2019-08-25 09:22:00
158
转载 Codeforces Round #580 (Div. 1)
目录 Contest Info Solutions A. Almost Equal B. Shortest Cycle Contest InfoPractice LinkSolvedABCDEF2/6O...
2019-08-25 08:58:00
130
转载 2019中国大学生程序设计竞赛（CCPC） - 网络选拔赛
目录 Contest Info Solutions A - ^&^ B - array C - K-th occurrence D - path E - huntian oy F - Shuffle Card ...
2019-08-24 10:26:00
782
转载 Educational Codeforces Round 70
目录 Contest Info Solutions A. You Are Given Two Binary Strings... B. You Are Given a Decimal String... C. You Are Given a WASD-string......
2019-08-09 21:58:00
112
转载 Educational Codeforces Round 69
目录 Contest Info Solutions A. DIY Wooden Ladder B. Pillars C. Array Splitting D. Yet Another Subarray Problem E. Culture ...
2019-07-23 09:58:00
122
转载 Codeforces Global Round 4
目录 Contest Info Solutions A. Prime Minister B. WOW Factor C. Tiles D. Prime Graph E. Archaeology F1. Short Color...
2019-07-21 08:30:00
120
转载 Codeforces Round #574 (Div. 2)
目录 Contest Info Solutions A. Drinks Choosing B. Sport Mafia C. Basketball Exercise D1. Submarine in the Rybinsk Sea (easy editio...
2019-07-18 07:35:00
88
转载 Educational Codeforces Round 68
目录 Contest Info Solutions A.Remove a Progression B.Yet Another Crosses Problem C.From S To T D.1-2-K Game E.Count The Re...
2019-07-15 19:29:00
82
转载 The Preliminary Contest for ICPC China Nanchang National Invitational
目录 Contest Info Solutions A. PERFECT NUMBER PROBLEM D. Match Stick Game G. tsy's number H. Coloring Game' I. Max answer...
2019-07-08 22:18:00
104
转载 【LOJ #3144】「APIO 2019」奇怪装置
题意：定义将一个\(t\)如下转换成一个二元组：\[f(t) = \begin{cases}x = (t + \left\lfloor \frac{t}{B} \right \rfloor) \bmod A\\y = t \bmod b \end{cases}\]询问\([l_i, r_i]\)之间的\(t_i\)能够转换成多少个本质不同的二元组。思路：考虑\((x...
2019-07-07 23:09:00
139
转载 AtCoder Beginner Contest 133
目录 Contest Info Solutions A. T or T B.Good Distance C. Remainder Minimization 2019 D. Rain Flows into Dams E. Virus Tree...
2019-07-07 21:58:00
111
转载 AtCoder Beginner Contest 132
目录 Contest Info Solutions A. Fifty-Fifty B. Ordinary Number C. Divide the Problems D. Blue and Red Balls E. Hopscotch Ad...
2019-07-07 21:52:00
196
转载 Codeforces Round #572 (Div. 2)
目录 Contest Info Solutions A. Keanu Reeves B. Number Circle C. Candies! D1. Add on a Tree D2. Add on a Tree: Revolution ...
2019-07-06 20:36:00
72
转载 牛客练习赛49
目录 Contest Info Solutions A. 筱玛爱地理 B. 筱玛爱阅读 C.筱玛爱历史 D. 筱玛爱线段树 E. 筱玛爱游戏 Contest InfoPractice Li...
2019-07-06 17:33:00
126
转载 The 10th Shandong Provincial Collegiate Programming Contest
目录 Contest Info Solutions A. Calandar B. Flipping Game C. Wandering Robot D. Game on a Graph E. BaoBao Loves Reading ...
2019-07-05 09:46:00
461
转载 Codeforces Educational Codeforces Round 67
目录 Contest Info Solutions A. Stickers and Toys B. Letters Shop C. Vasya And Array D. Subarray Sorting E. Tree Painting ...
2019-07-01 19:26:00
114
转载 2018 Nowcoder Multi-University Training Contest 2
目录 Contest Info Solutions A. run D. monrey G. transform H. travel I. car J. farm Contest...
2019-06-30 08:52:00
50
转载 2018 Nowcoder Multi-University Training Contest 5
Practice LinkA. gpa题意：有\(n\)门课程，每门课程的学分为\(s_i\)，绩点为\(c_i\)，要求最多删除\(k\)门课程，使得gpa最高。gpa计算方式如下：\[\begin{eqnarray*}gpa = \frac{\sum s_ic_i}{\sum s_i}\end{eqnarray*}\]思路：首先删去的课程越多，gpa肯定不会变得...
2019-06-30 08:13:00
47
转载 2018 Nowcoder Multi-University Training Contest 10
Practice LinkJ. Rikka with Nickname题意：给出\(n\)个字符串，要求依次合并两个串\(s, t\)，满足将\(t\)合并到\(s\)中变成\(r\)，使得\(s\)是\(r\)的前缀，并且\(t\)是\(r\)的一个子序列。思路：动态维护序列自动机，贪心插入即可。代码：#include <bits/stdc++.h>usin...
2019-06-30 08:05:00
57
转载 2018 Nowcoder Multi-University Training Contest 1
Practice LinkJ. Different Integers题意：给出\(n\)个数，每次询问\((l_i, r_i)\)，表示\(a_1, \cdots, a_i, a_j, \cdots, a_n\)中有多少个不同的数。思路：先分别离线求出\(a_1, \cdots a_i\)以及\(a_j, \cdots, a_n\)中有多少个不同的数。再考虑有多少个数既在\(...
2019-06-30 07:52:00
70
转载 Codeforces Round #571 (Div. 2)
A. Vus the Cossack and a Contest签。#include <bits/stdc++.h>using namespace std;int main() { int n, m, k; while (scanf("%d%d%d", &n, &m, &k) != EOF) { if (min...
2019-06-29 08:34:00
58
转载 Codeforces 1183F Topforces Strikes Back
题意：有\(n\)个问题，每个问题的难度为\(a_i\)，最多选出三个问题\(x, y, z\)，要求\(两两之间不能存在整除关系\)，求最多能获得多大难度的问题集，一个问题集的难度为集合里面所有问题难度的总和。思路：考虑从小到大枚举一个数，然后用set维护加入的数，对于一个数\(x\)，去掉它的所有因数，去找最大的那个\(y\)，然后去掉\(y\)的所有因数，再找一个最大的\(...
2019-06-27 12:18:00
76
转载 Codeforces 1180E Serge and Dining Room
题意：有\(n\)个菜肴，有\(m\)个小朋友，每个菜肴的价格为\(a_i\)，每个小朋友有\(b_i\)元钱，小朋友从\(1 \rightarrow m\)依次购买菜肴，当第\(i\)个小朋友轮到的时候，他会购买他买的起的最贵的，否则就离开。要求支持修改第\(i\)个菜肴的价格和修改第\(i\)个小朋友的拥有的钱数的两种操作，每次操作完成给出\(m\)个小朋友买完后剩下的最贵的菜肴...
2019-06-26 15:44:00
166
转载 Codeforces 1175E Minimal Segment Cover
题意：有\(n\)条线段，区间为\([l_i, r_i]\)，每次询问\([x_i, y_i]\)，问要被覆盖最少要用多少条线段。思路：\(f[i][j]\)表示以\(i\)为左端点，用了\(2^j\)条线段，最远到哪里。然后从大到小贪心即可，类似于倍增找LCA的过程。代码：#include <bits/stdc++.h>using namespace std;...
2019-06-26 15:37:00
93
转载 AtCoder Beginner Contest 128 F - Frog Jump
题意有一只青蛙，有\(0, 1, \cdots, N - 1\)个荷叶。每个荷叶上有权值\(s_i\)。选定\(A\), \(B\)，初始分数为\(0\)。当前位置为\(x\)：对于\(y = x + A\)：如果\(y = N - 1\)，游戏结束。如果\(y \neq N - 1\)，但是\(y\)这个荷叶存在，那么分数增加\(s_i\)，并且这片荷叶消失。如果\(...
2019-05-27 12:35:00
179
转载 Codeforces 1151F Sonya and Informatics
题意：有一个数列，只有\(0\)和\(1\)，每一次操作选择两个数交换位置，求\(k\)次操作之后这个数列为非递减数列的概率是多少思路：假设一共有\(m\)个\(0\)，和\(n - m\)个\(1\)\(f[i][j]\)表示到第\(i\)个操作，前\(m\)个数字中有\(j\)个\(1\)的方案数有以下转移：前m个数字随便取两个交换，或者后(n - m)个数字随便取两个...
2019-04-24 22:04:00
142
转载 Atcoder Tenka1 Programmer Contest 2019 E - Polynomial Divisors
题意：给出一个多项式，问有多少个质数\(p\)使得\(p\;|\;f(x)\)，不管\(x\)取何值思路：首先所有系数的\(gcd\)的质因子都是可以的。再考虑一个结论，如果在\(\bmod p\)意义下，多项式中存在\((x^p - x)\)这个因式，那么这个质数\(p\)也是可以的显然\(p \leq n\)，那么我们只要枚举每个\(\leq n\)的质数，做模\(p\)意...
2019-04-22 16:06:00
113
转载 Atcoder Tenka1 Programmer Contest 2019 D Three Colors
题意：有\(n\)个石头，每个石头有权值，可以给它们染'R', 'G', 'B'三种颜色，如下定义一种染色方案为合法方案：所有石头都染上了一种颜色令\(R, G, B\)为染了'R', 染了'G', 染了'B'的所有石头的权值和，存在一个三角形的三边为\(R, G, B\)求合法方案数模\(998244353\)思路：考虑总方案数为\(3^n\)，我们考虑怎么求出不合法的...
2019-04-22 14:52:00
146
转载 Codeforces 1146E Hot is Cold
题意：给出一个序列，有两种操作：\(>\;x\) 将大于\(x\)的数全都取负\(<\;x\) 将小于\(x\)的数全都取负最后输出序列中的所有数最后的状态思路：我们先考虑对于一个数来说，它最后的状态只取决于它初始的时候是哪个数，而跟它所处的位置无关。我们注意到序列中的数的范围是\([-10^{5}, 10^5]\)，那么我们只需要处理出每个数在经过\(q\...
2019-04-21 20:38:00
98
转载 ZOJ 3820 Building Fire Stations
题意：一棵树中，选取两点，使得(其他点到这两点的距离的最小值)的最大值最小思路：考虑只选取一点的情况，那么显然选取直径的中点即为答案。首先考虑选取的两点肯定在直径上，因为假如不在直径上，那么把点往直径上移动，不会使得答案变得更劣。再考虑选取两点，假如我们将树按照树的直径的中点分成两段，那么肯定是一边放一点。因为假如两个点都在一边的话，答案肯定是\(\frac{len}{2}\...
2019-04-07 19:24:00
80
转载 ZOJ 3822 Domination
题意：有一个\(n * m\)的棋盘，有一个人每天随机再一个空位上放一个棋子，问空棋盘变成每一行每一列都至少有一枚棋子的棋盘的期望天数是多少？思路：\(dp[i][j][k]\)表示\(i\)行至少有一枚棋子，\(j\)列至少有一枚棋子，已经放了\(k\)枚棋子的概率是多少.那么\(dp[i][j][k]\)可从以下四种状态转移过来：\(dp[i - 1][j][k - 1]...
2019-04-07 19:13:00
78
转载 HDU 6390 GuGuFishtion
题意：计算：\[\sum\limits_{a = 1}^{m}\sum\limits_{b = 1}^{n} \frac{\varphi(ab)}{\varphi(a)\varphi(b)} (\bmod p)\]思路：考虑算术基本定理和\(\varphi(x)\)函数积性将式子化简：令\(a = p_1^{t_1}p_2^{t_2} \cdots p_n^{t_n}\)，\(...
2019-04-07 16:14:00
105
转载 ZOJ 3949 Edge to the Root
题意：在一棵树中，可以从根节点往其他节点加一条边，使得根节点到其他所有节点的距离和最小，输出最小的距离和。思路：我们考虑在加的一条边为$1 \to v$，那么在树上从$1 \to v$的路径上，如果有一个点$y$到$v$比到$1$更近，那么这个点$y$的子树里的所有点都到$v$更近。那么我们找到离根最近的点$y$，那么$y$子树中的所有点都是到$v$更近。...
2019-04-05 10:30:00
68
转载 Codeforces 1144G Two Merged Sequences
题意：将一个序列分成两个序列，两个序列中元素的相对顺序保持和原序列不变，使得分出的两个序列一个严格上升，一个严格下降。思路：我们考虑每个元素都要进入其中一个序列。那么我们维护一个上升序列和一个下降序列，对于当前元素$i$：如果它只能确定的进入一个序列，那么就让它进入。如果它一个序列也进不去，那么答案就是'NO'。如果它两个序列都可以进去，那么判断它...
2019-04-01 13:45:00
209
转载 PTA 团体程序设计天梯赛 L3-020 至多删三个字符
$f[i][j]$表示到第$i$个字符，已经删去了$j$个字符的方案数。显然的转移：$f[i][j] = f[i - 1][j] + f[i - 1][j - 1]$但是这样会有重复，我们考虑什么情况会重复。比如说：'aabab'中的'bab'，我们删去'ba'，得到'aab'，删去'ab'得到'aab'，两者是相同的1 2 3 4 5a a b a b...
2019-03-23 17:14:00
240
转载 BZOJ 5102: [POI2018]Prawnicy
考虑最优解的集合中一定有一个$l$最大的，我们就去枚举左端点，把所有$l$小于等于它的全丢进堆里，取前$k$个即可。 1 #include <bits/stdc++.h> 2 using namespace std; 3 4 #define N 1000010 5 #define fi first 6 #define se secon...
2019-03-21 20:00:00
75
转载 BZOJ 1045: [HAOI2008] 糖果传递
我们令$x_i$表示第$i$个人传递给第$i + 1$个人的糖果数量，那么有：$$x_n - x_1 = \overline{a} - a_1$$$$x_1 - x_2 = \overline{a} - a_2$$$$\cdots$$$$x_{n - 1} - x_n = \overline{a} - a_n$$那么求等式两边求前缀和有：$$x_n - x_...
2019-03-21 17:21:00
70
空空如也
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人