文章列表
 
您正在查看 "oj题目 解题报告" 分类下的文章

2009-08-27 17:04

就是要去求次小生成树。

我的方法是基于 Prim 的,在计算最小生成树的时候顺便把 F[u][v] (最小生成树中 u 到 v 的唯一路径中最长边的权值),Closet[u] (最小生成树中离 u 最近的点) 计算出来。

然后枚举所有的存在的,不在最小生成树中的边 <u , v> ,用它去替换 f[u][v] 所对应的边。如果 w[u][v] == f[u][v] 那么说明不唯一,如果对于所有的 <u , v> , 均有 f[u][v] < w[u][v] ,

 
2009-08-23 23:19

好像是 NOI 之前知道这是一个很“秃”的 DP 题。。。今天以复习 Cpp 为目的做了做,结果一个美好的晚上就这么华丽的没了。。。

【题目大意】

一个不降的序列,长度 N <=500000,每个数为非负整数<=500000

你的操作是 dec (a[i]) ;
问最少的操作数,使得得到一个不降的序列,对于里面的每个数 b[i] 有(包括 i) >= k 个数 == b[i]。(就是说对于每个出现的数,他的出现

 
2009-07-24 17:38

一道是 SPOJ 的 GSS2 …… 两个月前参考 RGT 神牛的程序 AC 的,过了两个月又不知道为什么了。

这道题目先将询问的区间按照右端点排序,然后从左往右扫描一遍逐个回答。记 pre[i] 为 i 号点的那个数 dat[i] 左边最近的和它一样的数的位置,那么每次扫描到了 i ,就把 (pre[i] , i] 这一整个区间 + dat[i]

然后如果 i 点是某个询问的结束点,回答它。

 
2009-07-21 22:37

赵逸龙是神牛。。。

program         Round_Numbers ;
var     c       : array[0..31,0..31] of longint ;

function        calc (x : longint) : longint ;

 
2009-07-15 14:53

有这样一个经典的 NIM 组合游戏叫 staircase nim

就是说有 N 堆石子,两个人每次只能选择任意一堆 i (i > 0),从 i 中拿出任意 S 颗(S > 0)放入第 i - 1 堆中。无子可拿者为败 ~

这个问题,判断败局的条件是当前的所有奇数号堆的子数的 Nim 和为零,记这样的状态为 X

这个很好说明,因

 
2009-07-14 17:17

题意为,在一个 DAG 图顶点上面有几个棋子,YOU 和 I 轮流操作,每次操作就是找一个棋子往它能够移动的地方移动一格(沿着边到另外一个顶点),不能操作的人输。给出图以及每个棋子,问第一次操作的人有没有必胜策略。

这就是一个用 SG 函数解决的博弈题。

出度为零的点的 SG 值为 0,对于结点 I ,SG[I] = MEX (SG[SON[I]) {FOR ALL SON[I]},MEX就是在自然数集合中最小的不在SG[SON[I]]集合里面的数。

 
2009-07-12 19:28

题目的意思,就是给出N个 (N <= 10000) 带权值的区间 seg (a , b , w) ,以及一个范围 [ST , EN] (0 <= ST <= EN <= 86400) ,要求使用这些区间覆盖满每个点 ~ 并使得权值之和最小。权值均为非负数。输出最小花费或者给出无解信息。

首先将末端点 < ST 的区间去掉。区间按照右端点排序 ~

然后动态规划。

设 F[i] 表示在前 i 个区间里面选择且必

 
2009-07-12 10:44

终于捡起来了丢了三个月的后缀数组。

这道题目,就是后缀数组的基本运用。

若 S 为一个字符串,'+'是字符串中的连接运算,那么 T = S + S + ... + S 就是一个基于 S 的连续重复串,S 是 T 个一个基。显然对于一个 T,可能会有多个不同的基。题意就是给出一个串 ST ,求出这个串里面所有连续重复子串重复次数的最大值

【分析】

 
2009-07-06 23:41

题目的意思是说,给一些区间,每个区间有一个价值,要求选出若干个不相交的区间使得它们的价值之和最大 ~

区间个数 <= 10000

这道题目每个区间的坐标范围很大,需要离散化。。。首先离散化点,将所有的端点集中起来排序,确定每个区间离散化了之后的坐标。然后将每个区间按照右端点排序。最后 O (N) 的 DP 搞定 ~

要注意的是,输入所给出的不是端点的坐标,

 
2009-07-01 23:16

我现在的日子是越来越囧了。。。比如今天做 SGU 307,我知道了题目中的结论,然后我想把它证明出来。在草稿纸上面写了一点点就觉得写不下去了。于是只能打开打开Dev-Cpp去写它。

这道题目题意为,原来的 N * M 矩阵 A 是一个 0 1 矩阵。现在给出一个 (N-1) * (M-1) 的矩阵 B ,其中

B[I][J] = A[I][J] + A[I+1][J] + A[I][J+1] + A[I+1][J+1]

 
   
 
 
文章存档
 
     
 
最新文章评论
  

我也从来没有证明过,从来都是看别惹难道,
 

那个,请问,如果改成非递归怎么改……改半天改不出来啊…………谢谢……
 

崩溃了。。。哇哇哇 我操 TMGBL
 

Orz证明
 

能不能把数据发一份给我呢?谢谢467849453@qq.com
   
帮助中心 | 空间客服 | 投诉中心 | 空间协议
©2012 Baidu