ACZSH-CSDN博客

原创 Zju2492 A Dp Problem

给你一些一元一次方程，让你求出未知数的解，如果只有一个解则输出这个解，如果有无数个则输出"IDENTITY"（如 x=x）,无解则输出“IMPOSSIBLE”(如 x+2=x+3）。考虑等式两边也就是“=”两边，分别求出两边未知数项的系数和常数项，分别为，f1,d1,f2,d2,那么最后的答案就是(d2-d1)/(f1-f2)。（这个。。。大家应该都懂！！！）。处理系数有点恶心。

2013-11-06 19:35:24 700

原创 zju1093 monkey and banana 猴子和香蕉

有一班科学家正在设计一个测试猴子IQ的试验。他们把一只“banana”吊在天花板，而且同时给猴子一些箱子。如果猴子聪明的话，它们会把箱子一个个叠起来做成一个塔子来取得食物。科学家有n种箱子，而且每一种箱子都有好多个。第 i 种箱子有三维（xi,yi,zi)。箱子可以用它的任意一面作底面来摆放，也就是它的三维之中可以任选两条来做它的底面长和宽。科学家想确定箱子叠到最高的时候是可以到达天花板的。现在问

2013-11-06 19:27:23 901

原创 Pku2406 Power Strings

求一个字符串由多少个重复的子串连接组成，例如ababab由3个ab连接而成，因此答案为3，又例如abcd由1个abcd连接而成，因此答案为1。我们要求最小的重复周期，可以想到，设n为s串的长度，如果n mod (n-next[n])=0,那么最小周期就是(n-next[n]),答案便是n div (n-next[n])。证明一下，设S=s1s2s3s4s5s6s7s8s9,假设ne

2013-11-06 19:22:44 603

原创 [Poi0504]Piggy Banks小猪存钱罐（并查集）

Byteazar 有 N 个小猪存钱罐. 每个存钱罐只能用钥匙打开或者砸开. Byteazar 已经把每个存钱罐的钥匙放到了某些存钱罐里. Byteazar 现在想买一台汽车于是要把所有的钱都取出来. 他想尽量少的打破存钱罐取出所有的钱,问最少要打破多少个存钱罐. 不多说了，并查集求连通块个数即可。CODE:var fa:array[0..1000000

2013-11-06 10:52:31 1142

原创 zju1942Frog（并查集）

有一只叫做Freddy的青蛙坐在湖中央的一块石头上，突然间他发现另一只青蛙（她的名字是Fiona）坐在另一颗石头上。他想要过去找她，但是因为湖水很脏，到处充满着游客的防晒油，所以他决定用跳的，而不要用游的。不妙的是Fiona的石头离他的距离超出他所能跳的范围。因此Freddy考虑利用其它的一些石头当作中继站，因此他就可以跳比较小的距离（或许要跳许多次）去找Fiona。要这样子连续的

2013-11-06 10:49:50 927

原创黑魔法师之门（并查集）

applepi被囚禁的地点只有一扇门，当地人称它为“黑魔法师之门”。这扇门上画着一张无向无权图，而打开这扇门的密码就是图中【每个点的度数大于零且都是偶数】的子图的个数对1000000009取模的值。此处子图 (V, E) 定义为：点集V和边集E都是原图的任意子集，其中E中的边的端点都在V中。　　但是Vani认为这样的密码过于简单，因此门上的图是动态的。起初图中只有N个顶点而没有边。Va

2013-11-06 10:28:39 1026

原创 [Usaco2011 Nov]Cow Steeplechase奶牛越野跑

题目大意：给出N平行于坐标轴的线段，要你选出尽量多的线段使得这些线段两两没有交点（顶点也算），横的与横的，竖的与竖的线段之间保证没有交点，输出最多能选出多少条线段。（NInput3 4 5 10 5 6 2 6 12 8 3 8 5 Output2我们将横的线段和竖的线段分开，如果某条横的线段与竖的线段有焦点，就将他们连边。最后的答案表示最大独立集。CODE

2013-10-31 11:26:17 731

原创 [SCOI2009]生日礼物

小西有一条很长的彩带，彩带上挂着各式各样的彩珠。已知彩珠有N个，分为K种。简单的说，可以将彩带考虑为x轴，每一个彩珠有一个对应的坐标(即位置)。某些坐标上可以没有彩珠，但多个彩珠也可以出现在同一个位置上。小布生日快到了，于是小西打算剪一段彩带送给小布。为了让礼物彩带足够漂亮，小西希望这一段彩带中能包含所有种类的彩珠。同时，为了方便，小西希望这段彩带尽可能短，你能帮助小西计算这个最短的长度么？彩带的

2013-10-29 14:15:50 700

原创 [Usaco 2011 Dec]Umbrellas for Cows

题面：今天是下雨天！FJ的N （ 1 只能说这题比较坑了，跟[USACO 2012 Dec]Wifi Setup比较像，好像此题比那题先出。。坑在哪里呢。就是比方说遮住10个点的伞可能比遮住9个点的伞要便宜（不知道是不是盗版），所以就不能直接按距离做，这里我做了一个处理，就是如果小的伞要比大的伞贵，就把小的伞的价格变成大的伞的价格，这样就可以直接按照距离做了，可以保证答案的最优

2013-10-29 11:08:31 780 2

原创 Ural1024 Permutations

Input Input In the first line of the standard input an only natural number N (1 <= N <= 1000) is contained, that is a number of elements in the set that is rearranged by this permutation. In the

2013-10-29 10:51:33 522

原创阶梯教室的利用（DP）

阶梯教室设备利用我们现有许多演讲要在阶梯教室中举行。每一个演讲都可以用唯一的起始和终止时间来确定，如果两个演讲时间有部分或全部重复，那么它们是无法同时在阶级教室中举行的。现在我们想要尽最大可能的利用这个教室，也就是说，我们需要在这些演讲中选择一些不重复的演讲来举行使得他们用的总时间尽可能的长。我们假设在某一演讲结束的瞬间我们就可以立即开始另一个演讲。任务：请写一

2013-10-29 10:36:17 972

原创国家集训队树（罗雨屏）（线段树+2K父亲+dfs序）

中国国家队训练问题描述　　给定一棵大小为 n 的有根点权树,支持以下操作: 　　• 换根　　• 修改点权　　• 查询子树最小值 Input 　　第一行两个整数 n, Q ,分别表示树的大小和操作数。　　接下来n行,每行两个整数f,v,第i+1行的两个数表示点i的父亲和点i的权。保证f < i。如果f = 0,那么i为根。输入数据保证只有

2013-10-28 16:29:29 1344 1

原创暴力摩托（并查集）

英雄最喜欢玩暴力摩托，一个通宵之后，总算过了全关！正当他为自己的成绩洋洋得意的时候却发现居然还有一个特别的附加关！华英雄虽然累得眼睛都睁不开了，但是他还是决定再试一试！这一关与以前的关不同，包含有N个站，之间连了M条双向的通路！但每条路都规定了一个Speed值，在这条路上必须以这个速度前进！所以在前进的时候要频繁的调整速度，这对鱼类来说是很痛苦的，所以华英雄决定尽量使调整的幅度小一些，也就是

2013-10-28 16:08:23 998

原创 USACO 接苹果

今天刷了终于又刷到这道水题了，看到这道题，果断DP，我们用F[I,J,K] （K=1 .. 2)表示当前到了第I分钟，移动了J次，并且现在处在k号树下所能接到的最大苹果数。很容易想到转移方程：用A[I]表示第I分钟落下苹果的树的编号。 1: A[I]=1, F[I,J,1]=MAX(F[I-1,J,1],F[I-1,J-1,2])+1;

2013-10-28 16:01:15 709

小Z的OI之家