- 博客(270)
- 收藏
- 关注
RSS订阅原创 [KM算法 O(n^ 3) ] 带权二分图最大匹配
奔小康赚大钱Time Limit: 1000/1000 MS (Java/Others)Memory Limit: 32768/32768 K (Java/Others)Total Submission(s): 18257Accepted Submission(s): 7702Problem Description传说在遥远的地方有一个非常富裕的村落,有一天,村长...
2019-11-05 20:09:48
250
原创 [2-SAT] 输出路径 POJ3683 Priest John's Busiest Day
Priest John's Busiest DayTime Limit:2000MS Memory Limit:65536K Total Submissions:13255 Accepted:4495 Special Judge DescriptionJohn is the only priest in his town. S...
2019-10-30 21:00:43
176
原创 [DAG支配树(拓扑排序+LCA)] HDU6604 Blow up the city
Blow up the cityTime Limit: 5000/5000 MS (Java/Others)Memory Limit: 131072/131072 K (Java/Others)Total Submission(s): 742Accepted Submission(s): 393Problem DescriptionCountry A and B ...
2019-09-21 20:37:42
356
转载 约瑟夫环 n, k 第 m 个出圈
ACM-ICPC 2018 沈阳赛区现场赛 K. Let the Flames Begin （约瑟夫环问题）题目链接：题意：有 n 个人围成一个圈，从 1 开始报到第 k 个人出环，问第 m 个出环的人是谁，n、m、k <= 1e18 且 min（m，k）<= 2e6。题解：容易得出O（m）的递推公式 f[n][m] = （f[n-1][m-1] + k - 1）% n +...
2019-09-08 20:00:50
459
原创 [硬核线段树] 2018CCPC吉林I.lovers
LoversTime Limit: 25000/15000 MS (Java/Others)Memory Limit: 262144/262144 K (Java/Others)Total Submission(s): 351Accepted Submission(s): 104Problem DescriptionThe Fool comes to a cros...
2019-07-17 18:25:28
287
原创 [序列自动机+倍增] 查询是否存在一个给出的全排列的循环右移是给定区间的子序列 CF1143E
E. Lynyrd Skynyrdtime limit per test2 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard outputRecently Lynyrd and Skynyrd went to a shop where Lynyrd bought ...
2019-05-15 16:32:39
297
原创 [DP + 序列自动机] 修改子串并询问原串中是否包含子串 CF1150D
D. Three Religionstime limit per test3 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard outputDuring the archaeological research in the Middle East you foun...
2019-05-10 15:39:28
169
原创 [倍增] 将带权树分割为数量最少的链 CF1059E
E. Split the Treetime limit per test2 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard outputYou are given a rooted tree onnnvertices, its root is the ver...
2019-04-30 12:46:28
209
原创 [tarjan + lca] 动态加边求桥
D - NetworkPOJ - 3694A network administrator manages a large network. The network consists of N computers and M links between pairs of computers. Any pair of computers are connected directly or ...
2019-04-19 13:53:47
249
原创 [tarjan缩点 + 割点 / 割边 + 重边] 无向图求割点
#include <iostream>#include <cstdio>#include <cmath>#include <stack>#include <cstring>#define ll long long#define db doubleusing namespace std;const int mn = ...
2019-04-15 20:34:58
406
原创 [tarjan模板] 需要几个点覆盖整张图+需要增加几条边 使全图强联通
A - Network of SchoolsPOJ - 1236A number of schools are connected to a computer network. Agreements have been developed among those schools: each school maintains a list of schools to which it d...
2019-04-15 16:01:57
113
原创 [拓扑排序] 横纵涂色 ZOJ3780
E - Paint the Grid AgainZOJ - 3780Leo has a grid withN×Ncells. He wants to paint each cell with a specific color (either black or white).Leo has a magical brush which can paint any row wit...
2019-04-12 17:52:23
122
原创 [状压DP] 每个人排在不同位置有不同贡献 求队伍贡献值一定的方案数 ZOJ3777
B - Problem ArrangementZOJ - 3777The 11th Zhejiang Provincial Collegiate Programming Contest is coming! As a problem setter, Edward is going to arrange the order of the problems. As we know, the...
2019-04-11 20:43:27
130
原创 [NIM博弈变形] A在部分堆中只能取奇数 另一部分只能取偶数 B任取 ZOJ3964
G - Yet Another Game of StonesZOJ - 3964Alice and Bob are playing yet another game of stones. The rules of this game are as follow:The game starts withnpiles of stones indexed from 1 ton. T...
2019-04-11 12:54:20
230
原创 [组合数递推公式] RGB游戏 ZUFE2019校赛D
问题 D: D - RGB游戏时间限制:1 Sec内存限制:256 MB提交:35解决:6[提交][状态][讨论版]题目描述三水最近发明了一个RGB游戏：有 n 个方格，编号为从 1 到 n，它用七种颜色的颜料给方格上色，每个 方块只能涂一种颜色。总的分值是这 n 个方块得分之和，如果方块被涂成红色，则方块的得分为 2，如 果方块被涂成蓝色则为 3，如果方块被涂...
2019-03-18 16:20:57
230
原创 [最大独立集 = 补图的最大团] E. Helping Hiasat CF1105E
E. Helping Hiasattime limit per test2 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard outputHiasat registered a new account in NeckoForces and when his fri...
2019-03-12 21:14:13
184
原创 [线段树+欧拉函数+状态压缩] 区间修改 求区间积的欧拉函数 CF1114F
F. Please, another Queries on Array?time limit per test5.5 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard outputYou are given an arraya1,a2,…,ana1,a2,…,a...
2019-02-28 19:37:02
326
原创 [交互式+随机] 询问求等差数列 CF1114E
E. Arithmetic Progressiontime limit per test2 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard outputThis is an interactive problem!An arithmetic progress...
2019-02-27 16:32:43
190
原创 [区间DP] 选择区间改变颜色使同色 n = 5000 CF1114D
D. Flood Filltime limit per test2 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard outputYou are given a line of nn colored squares in a row, numbered from ...
2019-02-26 13:51:19
247
原创 [分解质因数/阶乘素因子的幂] C. Trailing Loves (or L'oeufs?) CF1114C
C. Trailing Loves (or L'oeufs?)time limit per test2 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard outputThe number "zero" is called "love" (or "l'oeuf" t...
2019-02-25 19:37:47
357
原创 【对偶问题 + 三分】C. Freelancer's Dreams
C. Freelancer's Dreamstime limit per test2 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard outputMikhail the Freelancer dreams of two things: to become a c...
2019-02-19 23:48:35
186
原创 【线段树区间更新】2018CCPC-Wannafly Winter Camp Day5 Div1 I
https://www.zhixincode.com/contest/20/problem/I?problem_id=304Sorting已经提交已经通过46.43%Total Submission：28Total Accepted：13题目描述 你有一个数列a1,a2,…,ana_1, a_2, \dots, a_na1,a2,…,an，你要模拟一个类似于快...
2019-01-25 15:25:47
208
原创 [单调队列] 求固定大小矩阵内最大最小值 洛谷P2216
题目描述有一个a*b的整数组成的矩阵，现请你从中找出一个n*n的正方形区域，使得该区域所有数中的最大值和最小值的差最小。输入输出格式输入格式： 第一行为3个整数，分别表示a,b,n的值第二行至第a+1行每行为b个非负整数，表示矩阵中相应位置上的数。每行相邻两数之间用一空格分隔。 输出格式： 仅一个整数，为a*b矩阵中所有“n*n正方形区域中的最大整数和最小整...
2019-01-16 17:05:52
507
原创 [单调队列] 滑动窗口 求长度为m区间内最小值 洛谷P1440
题目描述一个含有n项的数列(n<=2000000)，求出每一项前的m个数到它这个区间内的最小值。若前面的数不足m项则从第1个数开始，若前面没有数则输出0。输入输出格式输入格式： 第一行两个数n，m。第二行，n个正整数，为所给定的数列。 输出格式： n行，第i行的一个数ai，为所求序列中第i个数前m个数的最小值。 输入输出样例输入样例#1： ...
2019-01-15 21:12:37
513
原创 【树状数组套动态开点线段树】求动态逆序对 洛谷P3157
题目描述对于序列A，它的逆序对数定义为满足i<j，且Ai>Aj的数对(i,j)的个数。给1到n的一个排列，按照某种顺序依次删除m个元素，你的任务是在每次删除一个元素之前统计整个序列的逆序对数。输入输出格式输入格式： 输入第一行包含两个整数n和m，即初始元素的个数和删除的元素个数。以下n行每行包含一个1到n之间的正整数，即初始排列。以下m行每行一个正整数，依次为每次删...
2019-01-14 01:11:27
191
原创 【主席树/分块前缀】求矩阵中最少几个数之和≥给定数 洛谷P2468
题目描述幸福幼儿园B29班的粟粟是一个聪明机灵、乖巧可爱的小朋友，她的爱好是画画和读书，尤其喜欢Thomas H. Cormen的文章。粟粟家中有一个R行C列的巨型书架，书架的每一个位置都摆有一本书，上数第i行、左数第j列摆放的书有Pi,j页厚。粟粟每天除了读书之外，还有一件必不可少的工作就是摘苹果，她每天必须摘取一个指定的苹果。粟粟家果树上的苹果有的高、有的低，但无论如何凭粟粟自己的个头...
2019-01-13 00:16:01
119
原创 [主席树] 静态区间第k小 洛谷P3834
题目背景这是个非常经典的主席树入门题——静态区间第K小数据已经过加强，请使用主席树。同时请注意常数优化题目描述如题，给定N个整数构成的序列，将对于指定的闭区间查询其区间内的第K小值。输入输出格式输入格式：第一行包含两个正整数N、M，分别表示序列的长度和查询的个数。第二行包含N个整数，表示这个序列各项的数字。接下来M行每行包含三个整数l, r, kl,r,k...
2019-01-11 18:39:30
273
原创 【DP】Rabbit的工作(1) 牛客练习赛36B
链接：https://ac.nowcoder.com/acm/contest/328/B来源：牛客网 Rabbit的工作(1)时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 32768K，其他语言65536K64bit IO Format: %lld题目描述Rabbit大学毕业后找到了一份实习工作，如果实习通过她就转正了。实习期共有N天，其中有几天公司集体放...
2019-01-05 23:04:09
239
原创 [二分] L. Berland University CFcontest/1090/L
#include <bits/stdc++.h>#define ll long longusing namespace std;ll t, n, a, b, k;ll w1, w2;bool check(ll x){ ll p = min(x, a), q = min(x, b); ll sz = p * w1 + q * w2; // 最多上的课 x人总数 ...
2018-12-12 17:37:16
192
原创 D. Similar Arrays CFcontest/1090/D
未出现的关系中任选一组 第一种两格填1和2, 第二种两格填1, 其他数字任填相当于把第一种的2改成1小于关系不影响, 大于关系仅原2 > 1, 该关系不给出, 无影响#include <bits/stdc++.h>using namespace std;const int mn = 1e5 + 10;bool vis[mn];vector<int&...
2018-12-12 16:13:54
205
原创 [01背包] J. Streets and Avenues in Berhattan CF1070 J
#include <bits/stdc++.h>using namespace std;const int mn = 30010, mk = 2e5 + 10;char ch[mk];bool dp[mn];int cnt[30];int main(){ int T; cin >> T; while (T--) { memset(cnt, ...
2018-12-11 12:10:37
183
原创 [二分] E. Getting Deals Done CFcontest1070E
#include <bits/stdc++.h>#define ll long longusing namespace std;const int mn = 2e5 + 10;int n, m;ll t;int p[mn], xu[mn];bool check(int x){ int lim = xu[x]; // 至少需要xu[x]的能力完成x个,大于xu...
2018-12-10 20:56:18
197
原创 [BFS] 求一定数位和的D的最小倍数 CFcontest1070A
余数500 * 数位和5000 = 25w种情况BFS先达到该种状态的一定数值最小#include <bits/stdc++.h>using namespace std;struct node{ int num, yu, sum;};queue<node> que;node fr[520][5020];bool vis[520][5020];...
2018-12-10 18:27:48
198
原创 构造对战矩阵 2018icpc青岛F https://vjudge.net/contest/274486#problem/F
#include<bits/stdc++.h>using namespace std;int p[2010][2010];void dabiao(){ p[1][1] = 1; for (int t = 1; t <= 1000; t *= 2) { for (int i = 1; i <= t; i++) for (int j = 1...
2018-12-06 19:05:29
373
原创 和最大子矩阵 ZUFEOJ
问题 H: 吃西瓜时间限制: 1 Sec 内存限制: 256 MB提交: 8 解决: 6[提交][状态][讨论版][命题人:外部导入]题目描述 【问题描述】老胡买了是长方体形的西瓜来犒劳大家....这块西瓜长m厘米,宽n厘米,高h厘米.他发现如果把这块西瓜平均地分成m*n*h块1立方厘米的小正方体,那么每一小块都会有一个营养值(可能为负,因为西瓜是有可能坏掉的,但是...
2018-12-04 19:55:47
198
原创 [二分+贪心] Kayaking Trip CFgym 101572 K
#include <bits/stdc++.h>using namespace std;const int mn = 3e5 + 10;int sum, cnt;int num[5], s[5], c[mn];struct Node{ int a, b, ts;} node[10];int tnum[5];bool check(int m...
2018-12-03 21:18:37
232
原创 [map] 求多向量交点数量 CF975D
D. Ghoststime limit per test2 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard outputGhosts live in harmony and peace, they travel the space without any pur...
2018-12-01 21:08:56
269
原创 [概率01背包] D - Just another Robbery LightOJ - 1079
As Harry Potter series is over, Harry has no job. Since he wants to make quick money, (he wants everything quick!) so he decided to rob banks. He wants to make a calculated risk, and grab as much mone...
2018-11-26 19:19:44
173
原创 [概率DP] C - Race to 1 Again LightOJ - 1038
Rimi learned a new thing about integers, which is - any positive integer greater than 1 can be divided by its divisors. So, he is now playing with this property. He selects a number N. And he calls th...
2018-11-26 15:36:10
130
原创 [概率DP] B - Discovering Gold LightOJ - 1030
You are in a cave, a long cave! The cave can be represented by a 1 x N grid. Each cell of the cave can contain any amount of gold.Initially you are in position 1. Now each turn you throw a perfect 6...
2018-11-26 14:21:23
187
空空如也
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人