6 ciociooo

尚未进行身份认证

暂无相关描述

等级
TA的排名 2w+

【Amritapuri 2009】 Find the Number

【题目大意】给定k个数p1,p2,,,pk,给定n,求第n大的数,满足有且仅有一个序列p中的数整除它。给定的p两两互质。(k32,25)【分析】二分答案+容斥判定其实看到k的范围就应该想到枚举子集来容斥了。【题目】/*Ciocio'sOiTemplate*/#include#include#include#include#inc

2014-03-10 19:11:30

【SGU 275】 To xor or not to xor

【题目大意】给定一个非负整数序列a1,a2,,,an(118)。要求选出其的一个非空子集,使得异或和最大。求最大异或和。【分析】先给出算法,再简略说明正确性。从高到底枚举每一个二进制位L。1.找出第L位为1的数ai,如果找到则转2,否则转4.2.若ans的第L位为0,ans^=ai。3.使所有第L位为1的数aj^=ai。4.枚举下一个二进制位。

2014-03-10 18:58:19

【NOI2003】 editor

【题目大意】要求一种数据结构,能够支持(1)在某个位置插入长度为n的字符串(2)删除从某个位置开始的长度为n的字符串(3)输出从某个位置开始的长度为n的字符串【分析】块状链表很裸的一道题,练练手。要注意几点细节:(1)空间可以循环使用(2)注意随时保证复杂度,即合并小区间【代码】#include#include#include

2014-03-04 16:18:17

【BZOJ 1880】 Elaxia的路线

【分析】我们分别从两个起点,两个终点,做四次最短路。然后我们可以知道哪些点和边是两人都经过的,并且按照经过的次序使边变为有向的。这样就构成了一个DAG。毫无疑问,我们要求的是这个DAG的最长路。用拓扑排序+DP即可完成。(PS:不知道标解是怎样,感觉我的做法很奇葩,但是在BZOJ上排rank4)【代码】#include#include#inclu

2014-02-25 19:36:19

【BZOJ 1975】 魔法猪学院

【分析】很明显是求k短路,我们用A*优化的Spfa来实现。先预处理Dist[i]表示当前点到终点的最短距离。然后优先队列中的关键字为dis+Dist[i],每次取出最小的关键字的i。用它的dis更新它可以到的点的dis,然后放入优先队列。当终点第k次出队的时候,就是到终点的k短路。【代码】#include#include#include#includ

2014-02-25 19:27:09

【PYC#1 欢乐赛】 题解

【题目地址】点击打开链接【分析们】【T-1】树状数组+Trie树【T-2】首先显然这是个堆,这个堆以位置为关键字,且形状固定。我们要做的就是将数字1~N填入堆中,并且令这些数字也满足堆性质。考虑我们有一个以x为根的堆,有i个数字可以填。我们用M[i]表示以i为根的堆的结点个数,可以逆序O(N)求得。用f[i]表示有i个数的方案数。我们得到一个

2014-02-23 15:57:00

【KpmCup#0 省选模拟赛】题解

【题目地址】【T-1】很明显的差分约束系统,判负环。但是裸的要超时,我们注意到一个负环必定在一个强连通分量中。于是我们先求出SCC,再判负环。只需要判断入队次数大于sqrt(N)即可,虽然这样是有反例的,但大多数数据是能过的。【T-2】斜率优化dp我们可以得到一个dp方程:      f[i]=min{f[j]+sigma(b[k]*(i

2014-02-20 16:45:11

【POJ 3469】 Dual Core CPU --最小割

【题目地址】点击打开链接【分析】这种题应该一看就是最小割的题目。然后我们考虑这样建图:1.S向每个任务连一条容量为A[i]的边。2.每个任务向T连一条容量为B[i]的边。3.如果输入u,v,w。那么u向v连容量w的边,v向u连容量w的边。那么如果任务a,b是由不同的cpu完成的,即各自分属S集和T集。那么割边集必然包含连接a,b的边。【代码】

2014-02-19 19:08:29

【HDU 1569】 方格取数2 --最大点权独立集

【题目大意】给你一个m*n的格子的棋盘,每个格子里面有一个非负数。从中取出若干个数,使得任意的两个数所在的格子没有公共边,就是说所取数所在的2个格子不能相邻,并且取出的数的和最大。(n,m【分析】将图黑白染色,然后按照矛盾关系建成二分图。那么求一个最大点权独立集即可。建图:i+j为奇数的与S节点相连,边的权值为棋盘上对应位置的值。i+

2014-02-19 18:58:37

【UVa 10780】 Again Prime? No time.

【题目大意】给定两个正整数N,M。求一个最大的正整数k,使得Mk|N!【分析】直接将N!和M的质因子分解,然后比较指数即可。N!的质因子分解式:  设N!=p1a1 ×p2a2 ×p3a3×××pkak那么pi的指数ai=sigma(N/(pij)) pij【代码】#include#include#include#inc

2014-02-18 13:21:29

【HNOI2012】 永无乡

【题目地址】点击打开链接【分析】平衡树的启发式合并,可以证明是O(nlogn)的。【代码】#include#include#include#include#include#include#includeusingnamespacestd;#definerep(i,a,b)for(inti=(a);i<=(b);++i)#

2014-02-17 17:14:54

【CTSC 2008】 网络管理 --树链剖分+树状数组+Trie树

【题目大意】给定一颗点上带权的树,每次可以修改某点的权值,或者询问两点u,v树上唯一路径的第k大权值。【分析】这类树上路径问题直接轻重权树链剖分就好啦。。但是是询问第k大,所以我们用一个树状数组套Trie树维护区间权值即可。。注意用BFS来剖分避免爆栈【代码】#include#include#include#include#inclu

2014-02-15 23:23:54

【POJ 1741】 Tree --点分治

【题目大意】       给定一棵N个节点、边上带权的无向无根树,再给出一个K,询问有多少个数对(i,j)满足i【数据规模】多组测试数据,每组数据满足N≤10000,1≤边上权值≤1000,1≤K≤10^9。【出处】楼天城男人必做8题之一……【分析】很显然有个暴力算法:从每个点出发遍历整棵树,统计数对个数。也很显然时间复杂度O(N^2),要TLE。

2014-02-14 15:41:18

【BZOJ 2818】 gcd

Description给定整数N,求1数对(x,y)有多少对.Input一个整数NOutput如题SampleInput4SampleOutput4HINThint对于样例(2,2),(2,4),(3,3),(4,2)1【分析】       设有x,y满足条件,有(x,y)=p,p

2014-02-14 00:34:06

Splay维护区间

Description给你一个长度为N的序列{ai}和M个操作 1.查询第k个数的值 2.将第k个数增加d 3.查询一段区间的和 4.查询一段区间的最大值 5.将一段区间镜面翻转(例如序列{1,2,3,4,5,6},将从2到5的区间翻转后得到序列{1,5,4,3,2,6}) 对于除操作2,5以外的操作,输出相应的答案Input第一行两个正整数N,M 第二行N

2014-02-11 22:18:57

【ZJOI2013 DAY1】K大数查询 --树套树水题

Description时限:2s 有n个位置和m个操作。操作有两种,每次操作如果是1abc的形式,表 示往第a个位置到第b个位置每个位置加入一个数c。如果操作形如2abc的形 式,表示询问从第a个位置到第b个位置,第c大的数是多少。Input第一行两个数n,m。意义如题目描述。 接下来m行每行形如1abc或者2abc如题目

2014-02-08 23:55:54

zbrka

Description考虑一个由N个整数构成的数列,其中1到N都在数列中出现了恰好一次。 在这个数列中从左到右任取两个数,如果前者比后者大,那么这对数就是一个逆序对。 而整个数列的逆序数就是其中所有逆序对的总数。 例如,数列(1,4,3,2)的逆序数为3,因为存在三个逆序对:(4,3),(4,2)和(3,2)。 写一个程序,计算有多少长度为N的这种数列,使它的逆序数恰为C。

2014-02-06 10:50:46

【Usaco Jan08 Gold】电话网络 --树型dp

DescriptionFarmerJohn决定为他的所有奶牛都配备手机,以此鼓励她们互相交流。不过,为此FJ必须在奶牛们居住的N(1所有草地中只有N-1对是相邻的,不过对任意两块草地A和B(1请你帮FJ计算一下,为了建立能覆盖到所有草地的通信系统,他最少要建多少座无线电通讯塔。Input*第1行:1个整数,N *第2..N行:每行为2个用空格隔开的整数

2014-02-04 19:29:54

【JLOI2013】删除物品 --树状数组

Description箱子再分配问题需要解决如下问题: (1)一共有N个物品,堆成M堆。 (2)所有物品都是一样的,但是它们有不同的优先级。 (3)你只能够移动某堆中位于顶端的物品。 (4)你可以把任意一堆中位于顶端的物品移动到其它某堆的顶端。若此物品是当前所有物品中优先级最高的,可以直接将之删除而不用移动。 (5)求出将所有物品删除所需的最小步数。删除操作不计入步数之

2014-02-04 18:55:52

TopCoder SRM 607 题解

。。。第一次进div1,就一道都没有搞出来,第一题理解错了题意,第二题乱搞没有成功,第三题没看。果然深夜+感冒不是适合刷题的模式啊,不过幸好还保持在blue。最后看了看WJMZBMR神犇的代码,表示自己果然傻逼,连第一题这样的傻逼题都没A。250pt:分奇数和偶数长度分别讨论,然后直接枚举中心和长度计算即可。。。(一开始理解错题意,以为不是按顺序拼凑,对出题人只能呵呵,明

2014-02-03 22:30:29

查看更多

勋章 我的勋章
    暂无奖章