MaverickFW-CSDN博客

原创【高斯消元】GYM-102426A 题解

题意：T组 n个m维的向量判线性相关思路：裸的高消，考场的时候因为没有非异或的高消板子和精度问题卡了半天，所以写个方便整理板子。#include<bits/stdc++.h>#define clr(x) (x, 0, sizeof x)using namespace std;const int maxn = 15;const int maxm = 5;int T,n,m;double tmp,c[maxn][maxn];int main() { scanf("%

2021-03-15 15:27:02 203

原创 NOIPの模板总结

数论GCDEXGCDLUCAS扩展LUCASCRT扩展CRT排列组合卡特兰数错排斯特林数快速幂矩阵快速幂筛法线性筛高斯消元线性基图论最短路floyddijkstraSPFA差分约束系统最短路径树二分图匈牙利二分图染色find union

2017-11-09 18:33:30 579

原创 Codeforces 875B Sorting the Coins 题解

B. Sorting the Coins time limit per test1 second memory limit per test512 megabytes inputstandard input outputstandard output Recently, Dima met with Sasha in a philatelic store, and since then th

2017-11-03 19:19:16 656

原创 Codeforces 875A Classroom Watch 题解

A. Classroom Watch time limit per test1 second memory limit per test512 megabytes inputstandard input outputstandard output Eighth-grader Vova is on duty today in the class. After classes, he went

2017-11-03 19:12:19 568

原创 Codeforces 875C National Property 题解

C. National Property time limit per test1 second memory limit per test512 megabytes inputstandard input outputstandard output You all know that the Library of Bookland is the largest library in th

2017-11-03 19:09:00 590

原创 Codeforces 876B Divisiblity of Differences 题解

B. Divisiblity of Differences time limit per test1 second memory limit per test512 megabytes inputstandard input outputstandard output You are given a multiset of n integers. You should select exa

2017-11-03 19:02:22 334

原创 Codeforces 876A Trip For Meal 题解

A. Trip For Meal time limit per test1 second memory limit per test512 megabytes inputstandard input outputstandard output Winnie-the-Pooh likes honey very much! That is why he decided to visit his

2017-11-03 18:55:16 371

原创【BZOJ2744】【二分图】[HEOI2012]朋友圈题解

Description在很久很久以前，曾经有两个国家和睦相处，无忧无虑的生活着。一年一度的评比大会开始了，作为和平的两国，一个朋友圈数量最多的永远都是最值得他人的尊敬，所以现在就是需要你求朋友圈的最大数目。两个国家看成是AB两国，现在是两个国家的描述： 1. A国：每个人都有一个友善值，当两个A国人的友善值a、b，如果a xor b mod 2=1，那么这两个人都是朋友，否

2017-11-01 21:42:51 478

原创【BZOJ3401】【单调栈】[Usaco2009 Mar]Look Up 仰望题解

Description约翰的N(1≤N≤105)头奶牛站成一排，奶牛i的身高是Hi(l≤Hi≤1,000,000)．现在，每只奶牛都在向后看齐．对于奶牛i，如果奶牛j满足i#include <bits/stdc++.h>#define LL long long#define clr(x) memset(x, 0, sizeof x)#define ms(a, x) memset(x, a,

2017-11-01 21:39:02 561

原创【BZOJ2761】【hash】[JLOI2011]不重复数字题解

Description给出N个数，要求把其中重复的去掉，只保留第一次出现的数。例如，给出的数为1 2 18 3 3 19 2 3 6 5 4，其中2和3有重复，去除后的结果为1 2 18 3 19 6 5 4。Input输入第一行为正整数T，表示有T组数据。接下来每组数据包括两行，第一行为正整数N，表示有N个数。第二行为要去重的N个正整数。Output对于每组数据，输出一行，为去重后剩下的数

2017-11-01 21:37:55 541

原创【BZOJ1053】【DFS】【打表】[HAOI2007]反素数ant 题解

Description　　对于任何正整数x，其约数的个数记作g(x)。例如g(1)=1、g(6)=4。如果某个正整数x满足：g(x)>g(i) 0#include using namespace std;int n,num[100];int main() { num[1] = 1396755360; num[2] = 1102701600; nu

2017-11-01 21:36:06 365

原创【BZOJ2142】【扩展lucas】礼物题解

Description一年一度的圣诞节快要来到了。每年的圣诞节小E都会收到许多礼物，当然他也会送出许多礼物。不同的人物在小E 心目中的重要性不同，在小E心中分量越重的人，收到的礼物会越多。小E从商店中购买了n件礼物，打算送给m个人，其中送给第i个人礼物数量为wi。请你帮忙计算出送礼物的方案数（两个方案被认为是不同的，当且仅当存在某个人在这两种方案中收到的礼物不同）。由于方案数可能会很大，你

2017-11-01 21:33:33 413

原创【BZOJ4565】【状压DP】【区间DP】[Haoi2016]字符合并题解

Description有一个长度为 n 的 01 串，你可以每次将相邻的 k 个字符合并，得到一个新的字符并获得一定分数。得到的新字符和分数由这 k 个字符确定。你需要求出你能获得的最大分数。 Input第一行两个整数n，k。接下来一行长度为n的01串，表示初始串。接下来2k行，每行一个字符ci和一个整数wi，ci 表示长度为k的01串连成二进制后按从小到大顺序得到的第i种合并方案得到的新字

2017-11-01 21:31:21 517

原创【BZOJ2125】【仙人掌】最短路题解

Description给一个N个点M条边的连通无向图，满足每条边最多属于一个环，有Q组询问，每次询问两点之间的最短路径。Input输入的第一行包含三个整数，分别表示N和M和Q 下接M行，每行三个整数v，u，w表示一条无向边v-u，长度为w 最后Q行，每行两个整数v，u表示一组询问Output输出Q行，每行一个整数表示询问的答案Sample Input9 10 21 2 11 4 13 4 12 3

2017-11-01 21:29:07 519

原创【BZOJ2073】【状压DP】[POI2004]PRZ 题解

Description一只队伍在爬山时碰到了雪崩,他们在逃跑时遇到了一座桥,他们要尽快的过桥. 桥已经很旧了, 所以它不能承受太重的东西. 任何时候队伍在桥上的人都不能超过一定的限制. 所以这只队伍过桥时只能分批过,当一组全部过去时,下一组才能接着过. 队伍里每个人过桥都需要特定的时间,当一批队员过桥时时间应该算走得最慢的那一个,每个人也有特定的重量,我们想知道如何分批过桥能使总时间最少. Inp

2017-11-01 21:19:27 450

原创【BZOJ2783】【DFS】[JLOI2012]树题解

Description 在这个问题中，给定一个值S和一棵树。在树的每个节点有一个正整数，问有多少条路径的节点总和达到S。路径中节点的深度必须是升序的。假设节点1是根节点，根的深度是0，它的儿子节点的深度为1。路径不必一定从根节点开始。 Input 第一行是两个整数N和S，其中N是树的节点数。第二行是N个正整数，第i个整数表示节点i的正整数。接下来的N-1行每行是2个整数x

2017-11-01 21:15:12 310

原创【BZOJ1419】【期望DP】Red is good 题解

Description桌面上有R张红牌和B张黑牌，随机打乱顺序后放在桌面上，开始一张一张地翻牌，翻到红牌得到1美元，黑牌则付出1美元。可以随时停止翻牌，在最优策略下平均能得到多少钱。 Input一行输入两个数R,B,其值在0到5000之间 Output在最优策略下平均能得到多少钱。 Sample Input5 1 Sample Output4.166666 HINT输出答案时,小数点后第六

2017-11-01 21:12:52 460

原创【BZOJ4726】【树形期望DP】[POI2017]Sabota? 题解

Description某个公司有n个人, 上下级关系构成了一个有根树。其中有个人是叛徒(这个人不知道是谁)。对于一个人, 如果他下属(直接或者间接, 不包括他自己)中叛徒占的比例超过x，那么这个人也会变成叛徒，并且他的所有下属都会变成叛徒。你要求出一个最小的x，使得最坏情况下，叛徒的个数不会超过k。 Input第一行包含两个正整数n,k(1<=k<=n<=500000)。接下来n-1行

2017-10-29 18:20:18 477

原创【BZOJ1477】【扩展欧几里得】青蛙的约会题解

Description两只青蛙在网上相识了，它们聊得很开心，于是觉得很有必要见一面。它们很高兴地发现它们住在同一条纬度线上，于是它们约定各自朝西跳，直到碰面为止。可是它们出发之前忘记了一件很重要的事情，既没有问清楚对方的特征，也没有约定见面的具体位置。不过青蛙们都是很乐观的，它们觉得只要一直朝着某个方向跳下去，总能碰到对方的。但是除非这两只青蛙在同一时间跳到同一点上，不然是永远都不可能碰面的。为了帮

2017-10-20 19:22:41 373

原创【BZOJ3884】【欧拉函数】上帝与集合的正确用法题解

#include <iostream>#include <cstdio>#include <cstring>#include <string>#include <set>#include <queue>#include <algorithm>#include <vector>#include <cstdlib>#include <cmath>#include <ctime>#i

2017-10-18 18:46:46 314

原创【BZOJ4403】【lucas】【组合数】序列统计题解

Description给定三个正整数N、L和R，统计长度在1到N之间，元素大小都在L到R之间的单调不降序列的数量。输出答案对10^6+3取模的结果。Input输入第一行包含一个整数T，表示数据组数。第2到第T+1行每行包含三个整数N、L和R，N、L和R的意义如题所述。 1≤N,L,R≤10^9，1≤T≤100，输入数据保证L≤R。 Output输出包含T行，每行有一个数字，表示你所求出的答案

2017-10-18 16:01:28 327

原创【BZOJ1977】【MST】【LCA】[BeiJing2010组队]次小生成树 Tree 题解

Description小 C 最近学了很多最小生成树的算法，Prim 算法、Kurskal 算法、消圈算法等等。正当小 C 洋洋得意之时，小 P 又来泼小 C 冷水了。小 P 说，让小 C 求出一个无向图的次小生成树，而且这个次小生成树还得是严格次小的，也就是说：如果最小生成树选择的边集是 EM，严格次小生成树选择的边集是 ES，那么需要满足：(value(e) 表示边 e的权值) ∑e∈EMv

2017-10-15 21:10:02 330

原创【BZOJ3732】【MST】【LCA】Network 题解

Description给你N个点的无向图 (1 <= N <= 15,000)，记为：1…N。图中有M条边 (1 <= M <= 30,000) ，第j条边的长度为： d_j ( 1 < = d_j < = 1,000,000,000).现在有 K个询问 (1 < = K < = 20,000)。每个询问的格式是：A B，表示询问从A点走到B点的所有路径中，最长的边最小值是多少？Inpu

2017-10-15 21:04:45 274

原创【BZOJ1084】【杂题DP】[SCOI2005]最大子矩阵题解

Description　　这里有一个n*m的矩阵，请你选出其中k个子矩阵，使得这个k个子矩阵分值之和最大。注意：选出的k个子矩阵不能相互重叠。Input　　第一行为n,m,k（1≤n≤100,1≤m≤2,1≤k≤10），接下来n行描述矩阵每行中的每个元素的分值(每个元素的分值的绝对值不超过32767)。Output　　只有一行为k个子矩阵分值之和最大为多少。Sample Input3 2 2

2017-10-13 21:59:17 475

原创【BZOJ1083】【MST】[SCOI2005]繁忙的都市题解

Description　　城市C是一个非常繁忙的大都市，城市中的道路十分的拥挤，于是市长决定对其中的道路进行改造。城市C的道路是这样分布的：城市中有n个交叉路口，有些交叉路口之间有道路相连，两个交叉路口之间最多有一条道路相连接。这些道路是双向的，且把所有的交叉路口直接或间接的连接起来了。每条道路都有一个分值，分值越小表示这个道路越繁忙，越需要进行改造。但是市政府的资金有限，市长希望进行改

2017-10-13 21:50:27 354

原创【BZOJ2460】【贪心】【拟阵】【高斯消元】[BeiJing2011]元素

Description相传，在远古时期，位于西方大陆的 Magic Land 上，人们已经掌握了用魔法矿石炼制法杖的技术。那时人们就认识到，一个法杖的法力取决于使用的矿石。一般地，矿石越多则法力越强，但物极必反：有时，人们为了获取更强的法力而使用了很多矿石，却在炼制过程中发现魔法矿石全部消失了，从而无法炼制出法杖，这个现象被称为“魔法抵消” 。特别地，如果在炼制过程中使用超过一块

2017-10-13 08:06:19 377

原创【BZOJ3105】【拟阵】【高斯消元】【贪心】[cqoi2013]新Nim游戏题解

Description传统的Nim游戏是这样的：有一些火柴堆，每堆都有若干根火柴（不同堆的火柴数量可以不同）。两个游戏者轮流操作，每次可以选一个火柴堆拿走若干根火柴。可以只拿一根，也可以拿走整堆火柴，但不能同时从超过一堆火柴中拿。拿走最后一根火柴的游戏者胜利。本题的游戏稍微有些不同：在第一个回合中，第一个游戏者可以直接拿走若干个整堆的火柴。可以一堆都不拿，但不可以全部拿走。第二回合也一样，第二个

2017-10-12 22:08:00 325

原创【BZOJ4562】【拓扑排序】【DP】[Haoi2016]食物链题解

Description如图所示为某生态系统的食物网示意图，据图回答第1小题现在给你n个物种和m条能量流动关系，求其中的食物链条数。物种的名称为从1到n编号 M条能量流动关系形如 a1 b1 a2 b2 a3 b3 …… am-1 bm-1 am bm 其中ai bi表示能量从物种ai流向物种bi,注意单独的一种孤立生物不算一条食物链 Input第一行两个整数n和m,接下来m

2017-10-12 20:39:59 827

原创【BZOJ2095】【最大流】[Poi2010]Bridges 题解

DescriptionYYD为了减肥，他来到了瘦海，这是一个巨大的海，海中有n个小岛，小岛之间有m座桥连接，两个小岛之间不会有两座桥，并且从一个小岛可以到另外任意一个小岛。现在YYD想骑单车从小岛1出发，骑过每一座桥，到达每一个小岛，然后回到小岛1。霸中同学为了让YYD减肥成功，召唤了大风，由于是海上，风变得十分大，经过每一座桥都有不可避免的风阻碍YYD，YYD十分ddt，于是用泡芙贿赂了你，希望你

2017-10-12 20:38:20 378

原创浅谈子集系统、拟阵与贪心

拟阵前先谈另一个东西，子集系统。子集系统是一个有序二元组M=(S，L)，它必须满足以下3个条件： 1.S是一个有限集。 2.L是S的一些子集构成的有限非空子集。 3.遗传性：对∀B∈L，∀A⊆B，有A∈L（可知θ必须是L的元素）。 S中每个元素被赋予一个正值w(s)。举个例子，一个带权无向图G的边集为E，它的所有生成森林集合为J，则(E，J)为一个子集系统。独立集对于U⊆S，如果

2017-10-11 20:02:45 1658

原创【BZOJ2456】【杂题】mode 题解

Description给你一个n个数的数列，其中某个数出现了超过n div 2次即众数，请你找出那个数。Input第1行一个正整数n。第2行n个正整数用空格隔开。Output一行一个正整数表示那个众数。Sample Input53 2 3 1 3Sample Output3HINT100%的数据，n<=500000，数列中每个数<=maxlongint。卡内存，解法很简单，就是将不同的数抵消，

2017-10-11 18:48:15 436

原创关于贪心算法的研究

关于贪心算法的研究[摘要] 本文对贪心算法进行较详细的研究。第一部分明确其基本概念，第二部分介绍常见的贪心模型，第三部分给出常用的贪心证明方式，第四部分介绍贪心的经典算法，第五部分与其他算法进行比较，最后总结贪心算法的优劣性、竞赛应用及前景。 [关键词] 贪心算法、Prim、kruskal、Dijkstra、Huffman、拟阵、证明贪心算法是在信息学竞赛中一个常用的重要算法。在许多的经典算法中

2017-10-11 14:48:43 8546 1

原创【BZOJ3812】【状压DP】【容斥原理】主旋律题解

Description响应主旋律的号召，大家决定让这个班级充满爱，现在班级里面有 n 个男生。如果 a 爱着 b，那么就相当于 a 和 b 之间有一条 a→b 的有向边。如果这 n 个点的图是强联通的，那么就认为这个班级是充满爱的。不幸的是，有一些不好的事情发生了，现在每一条边都可能被摧毁。我作为爱的使者，想知道有多少种摧毁的方式，使得这个班级任然充满爱呢？（说人话就是有多少边的子集删去之后

2017-10-11 09:40:08 449

原创 Codeforces Round #438 C. Qualification Rounds 题解

C. Qualification Rounds time limit per test2 seconds memory limit per test256 megabytes inputstandard input outputstandard output Snark and Philip are preparing the problemset for the upcoming pre

2017-10-10 22:04:18 327

原创 Codeforces Round #438 B. Race Against Time 题解

B. Race Against Time time limit per test2 seconds memory limit per test256 megabytes inputstandard input outputstandard output Have you ever tried to explain to the coordinator, why it is eight ho

2017-10-10 22:03:03 244

原创【模拟】Codeforces Round #438 A. Bark to Unlock 题解

A. Bark to Unlock time limit per test2 seconds memory limit per test256 megabytes inputstandard input outputstandard output As technologies develop, manufacturers are making the process of unlocki

2017-10-10 22:00:52 551

原创【DP】【拓扑排序】road 题解

给一个图，从一个入度为零的点到一个出度为零的点，求点权和最大。跑dp的同时也要跑拓扑排序，dp[i]表示从一个入度为0的点到i位置的最大分数。然后将i之后的点全部入度减1，接着进行dp。#include <iostream>#include <cstdio>#include <cstring>#include <string>#include <set>#include <queue>#

2017-10-10 20:12:23 460

原创【DP】【单调栈】question 题解

给一个01矩阵，求1覆盖的最大矩形面积。统计每一个位置高度，单调栈维护，顺着跑一遍。#include <iostream>#include <cstdio>#include <cstring>#include <string>#include <set>#include <queue>#include <algorithm>#include <vector>#include <cst

2017-10-10 20:07:40 257

原创【状压DP】chess 题解

给出一个n*m的01矩阵，里面为0的点不能放旗子，两个相邻的格子不能放旗子，求放法种数。 n,m<12裸的状压DP，15行，每行一个12位01串表示。check就与一下。#include <iostream>#include <cstdio>#include <cstring>#include <string>#include <set>#include <queue>#include

2017-10-10 20:01:48 285

原创【DP】【01背包】【完全背包】Birthday 题解

n个物品m元钱，每个物品给出单价、权值以及第一次购买时赠送的权值其实就是01背包和完全背包套一起，解法其实写一个背包判一个也可以过#include <iostream>#include <cstdio>#include <cstring>#include <string>#include <set>#include <queue>#include <algorithm>#include

2017-10-10 19:57:54 313

空空如也

空空如也