4 MaverickFW

尚未进行身份认证

我要认证

It's Maverick

等级
TA的排名 2w+

NOIPの模板总结

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

2017-11-09 18:33:30

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

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

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

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

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

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

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

2017-11-01 21:42:51

【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

【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

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

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

2017-11-01 21:36:06

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

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

2017-11-01 21:33:33

【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

【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

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

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

2017-11-01 21:19:27

【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

【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

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

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

2017-10-29 18:20:18

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

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

2017-10-20 19:22:41

【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

【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

查看更多

勋章 我的勋章
  • 持之以恒
    持之以恒
    授予每个自然月内发布4篇或4篇以上原创或翻译IT博文的用户。不积跬步无以至千里,不积小流无以成江海,程序人生的精彩需要坚持不懈地积累!