2
5
2016
0

【实力娱乐】黑白棋AI设计(定期不更新)

寒潮五天实力颓到年级200+,感觉整个人都GG了。

隔膜传送门天梯传送门

大概是这么个意思,目前Rank18

采用战术:

alpha-beta搜索

鬼畜局面估价,包括散度、行动力判定,辣鸡边角攻防以及根本不是余裕手的余裕手判定

开局、中局、终局特殊处理。

不贴代码,求组队娱乐

Category: HDU | Tags:
1
22
2016
0

【枚举+二分】BZOJ 3061: [Usaco2013 Feb]Partitioning the Farm

大家好我又回来颓了。

期末受寒潮影响考完语文政治暂停五天复(kuang)习(huan),回去继续考(bao)试(ling)

3061: [Usaco2013 Feb]Partitioning the Farm

Time Limit: 10 Sec  Memory Limit: 128 MB

Description

 FJ的农场是n*n(2<=n<=15)的,每块地里有若干头牛,FJ最多能建K(1<=k<=2n-2)条篱笆,而这些篱笆只能沿着每块地的边缘建。建完篱笆之后,牛被分成了若干群。FJ想使得这些群中牛最多的那个群的牛尽量少。请输出满足FJ要求的情况下的牛最多的那个群有多少头牛。

Category: BZOJ | Tags: 二分 枚举
11
1
2015
1

【取模+枚举】NOIP2014 T6 解方程

CODEVS 3732: [NOIP2014]解方程

Time Limit: 1 Sec  Memory Limit: 128 MB

Description

Input

输入共n+2行。

第一行包含2个整数n、m,每两个整数之间用一个空格隔开。

接下来的n+1行每行包含一个整数,依次为a0,a1,a2,……,an

Output

第一行输出方程在[1, m]内的整数解的个数。

接下来每行一个整数,按照从小到大的顺序依次输出方程在[1, m]内的一个整数解。

Hint

 

【数论噩梦系列】%%%数学省队同桌

Category: NOIP | Tags: 数论 枚举 模意义
11
1
2015
0

【map预处理+倍增优化傻逼模拟】

CODEVS 1199: 开车旅行

Time Limit: 1 Sec  Memory Limit: 128 MB

Description

小A和小B决定利用假期外出旅行,他们将想去的城市从1到N 编号,且编号较小的城市在编号较大的城市的西边,已知各个城市的海拔高度互不相同, 记城市 i的海拔高度为Hi,城市 i 和城市 j 之间的距离 d[i,j]恰好是这两个城市海拔高度之差的绝对值,即 d[i, j] = |Hi − Hj|。

旅行过程中,小A 和小B轮流开车,第一天小A 开车,之后每天轮换一次。他们计划选择一个城市 S 作为起点,一直向东行驶,并且最多行 驶 X 公里就结束旅行。小 A 和小B的驾驶风格不同,小 B 总是沿着前进方向选择一个最近的城市作为目的地,而小 A 总是沿着前进方向选择第二近 的城市作为目的地(注意:本题中如果当前城市到两个城市的距离相同,则认为离海拔低的那个城市更近)。如果其中任何一人无法按照自己的原则选择目的城市, 或者到达目的地会使行驶的总距离超出X公里,他们就会结束旅行。

在启程之前,小A 想知道两个问题:

1.对于一个给定的 X=X0,从哪一个城市出发,小 A 开车行驶的路程总数与小 B 行驶的路程总数的比值最小(如果小 B的行驶路程为0,此 时的比值可视为无穷大,且两个无穷大视为相等)。如果从多个城市出发,小A 开车行驶的路程总数与小B行驶的路程总数的比值都最小,则输出海拔最高的那个 城市。

2.对任意给定的 X=Xi和出发城市 Si,小 A 开车行驶的路程总数以及小 B 行驶的路程总数。

Input

第一行包含一个整数 N,表示城市的数目。

第二行有 N 个整数,每两个整数之间用一个空格隔开,依次表示城市 1 到城市 N 的海拔高度,即H1,H2,……,Hn,且每个Hi都是不同的。

第三行包含一个整数 X0。

第四行为一个整数 M,表示给定M组Si和 Xi。

接下来的M行,每行包含2个整数Si和Xi,表示从城市 Si出发,最多行驶Xi公里。

Output

输出共M+1 行。

第一行包含一个整数S0,表示对于给定的X0,从编号为S0的城市出发,小A开车行驶的路程总数与小B行驶的路程总数的比值最小。

接下来的 M 行,每行包含 2 个整数,之间用一个空格隔开,依次表示在给定的 Si和Xi下小A行驶的里程总数和小B 行驶的里程总数。

 

先黑一个:开军旅行

Category: NOIP | Tags: map 倍增 NOIP 模拟
10
22
2015
1

【KMP+DP】 ZHOJ模拟赛34 T1压缩

1397: 【NOIP2014模拟赛No.34】压缩

时间限制: 1 Sec  内存限制: 512 MB

题目描述

我们定义一种压缩方法。首先将字符串分成若干个部分。对于每个部分,我们找出其最短的循环节。每个部分的循环节拼起来就是压缩后的字符串。
给定一个字符串,长度为n。请求出这个字符串可以被压缩成的最短长度。

输入

输入数据仅有一行,包含一个字符串。保证字符串只含有小写英文字母。

输出

输出一行,包含一个整数,代表答案。

样例输入

bababacacac

样例输出

5 

提示

一种可行的方法是 bababa|c|acac,压缩后得到 bacac,长度为 5。


对于 20%的数据,n≤10。

对于 40%的数据,n≤100。

对于 80%的数据,n≤1000。

对于 100%的数据,n≤5000。

 

选拔爆0,233333333

听字符串大师ZNZ讲解以后突然想来水一发

Category: 魔泥赛 | Tags: KMP DP
10
18
2015
1

【树链剖分+线段树】NOI2015 软件包管理器

4196: [Noi2015]软件包管理器

Time Limit: 10 Sec  Memory Limit: 512 MB

Description

 Linux用户和OSX用户一定对软件包管理器不会陌生。通过软件包管理器,你可以通过一行命令安装某一个软件包,然后软件包管理器会帮助你从软件源下载软件包,同时自动解决所有的依赖(即下载安装这个软件包的安装所依赖的其它软件包),完成所有的配置。Debian/Ubuntu使用的apt-get,Fedora/CentOS使用的yum,以及OSX下可用的homebrew都是优秀的软件包管理器。

你决定设计你自己的软件包管理器。不可避免地,你要解决软件包之间的依赖问题。如果软件包A依赖软件包B,那么安装软件包A以前,必须先安装软件包B。同时,如果想要卸载软件包B,则必须卸载软件包A。现在你已经获得了所有的软件包之间的依赖关系。而且,由于你之前的工作,除0号软件包以外,在你的管理器当中的软件包都会依赖一个且仅一个软件包,而0号软件包不依赖任何一个软件包。依赖关系不存在环(若有m(m≥2)个软件包A1,A2,A3,…,Am,其中A1依赖A2,A2依赖A3,A3依赖A4,……,Am−1依赖Am,而Am依赖A1,则称这m个软件包的依赖关系构成环),当然也不会有一个软件包依赖自己。
现在你要为你的软件包管理器写一个依赖解决程序。根据反馈,用户希望在安装和卸载某个软件包时,快速地知道这个操作实际上会改变多少个软件包的安装状态(即安装操作会安装多少个未安装的软件包,或卸载操作会卸载多少个已安装的软件包),你的任务就是实现这个部分。注意,安装一个已安装的软件包,或卸载一个未安装的软件包,都不会改变任何软件包的安装状态,即在此情况下,改变安装状态的软件包数为0。
 

Input

输入文件的第1行包含1个正整数n,表示软件包的总数。软件包从0开始编号。

随后一行包含n−1个整数,相邻整数之间用单个空格隔开,分别表示1,2,3,…,n−2,n−1号软件包依赖的软件包的编号。
接下来一行包含1个正整数q,表示询问的总数。
之后q行,每行1个询问。询问分为两种:
install x:表示安装软件包x
uninstall x:表示卸载软件包x
你需要维护每个软件包的安装状态,一开始所有的软件包都处于未安装状态。对于每个操作,你需要输出这步操作会改变多少个软件包的安装状态,随后应用这个操作(即改变你维护的安装状态)。
 

Output

输出文件包括q行。

输出文件的第i行输出1个整数,为第i步操作中改变安装状态的软件包数。
 

本子OJ传送门

2天学个树剖来水一水= =

Category: NOI | Tags: 树链剖分 线段树
10
15
2015
1

【区间第K大带修改】BZOJ3196 2B平衡树

Description

您需要写一种数据结构(可参考题目标题),来维护一个有序数列,其中需要提供以下操作:
1.查询k在区间内的排名
2.查询区间内排名为k的值
3.修改某一位值上的数值
4.查询k在区间内的前驱(前驱定义为小于x,且最大的数)
5.查询k在区间内的后继(后继定义为大于x,且最小的数)

Input

第一行两个数 n,m 表示长度为n的有序序列和m个操作
第二行有n个数,表示有序序列
下面有m行,opt表示操作标号
若opt=1 则为操作1,之后有三个数l,r,k 表示查询k在区间[l,r]的排名
若opt=2 则为操作2,之后有三个数l,r,k 表示查询区间[l,r]内排名为k的数
若opt=3 则为操作3,之后有两个数pos,k 表示将pos位置的数修改为k
若opt=4 则为操作4,之后有三个数l,r,k 表示查询区间[l,r]内k的前驱
若opt=5 则为操作5,之后有三个数l,r,k 表示查询区间[l,r]内k的后继

Output

对于操作1,2,4,5各输出一行,表示查询结果

Sample Input

9 6
4 2 2 1 9 4 0 1 1
2 1 4 3
3 4 10
2 1 4 3
1 2 5 9
4 3 9 5
5 2 8 5

Sample Output

2
4
3
4
9

学了树套树来水一水= =

Category: BZOJ | Tags: 树套树 线段树 平衡树
9
4
2015
0

【轮廓线状压DP+伪BFS】Codevs 1050 棋盘染色2

Codevs传送门

题意:给定5*n的黑白棋盘,要求将最少的白格染黑,使黑色块相联通。

Category: Codevs | Tags: 轮廓线状压DP BFS
8
30
2015
1

【二分+罗干】Fitting boxes[Codeforces KTU Programming Camp (Day 2) Aug/30/2015 ]

CF传送门

人话:

两个长宽为整数的矩形,判断它们是否能包含。

Category: Codeforces | Tags: 二分 几何
8
30
2015
0

【缩点+优先队列+罗干】花式把妹

 花式把妹

【问题描述】

	保镖SHC有n个妹子(妹子1到n编号),某些妹子与某个对应的妹子(单向)关系非常好,只要SHC搞
定了这个妹子,也能顺手搞定那个对应的妹子。每个妹子颜值不同,当这个妹子被搞定后就能SHC的后宫群总
颜值会增加对应颜值。现在。SHC作为外貌协会会长,他想手动搞定k个妹子,来为他的后宫群增加最多的颜值。

【输入格式】

	第1行两个整数 n、k。
	接下来n行每行两个整数a[i]、b[i]。a[i]表示第i个妹子非常要好的妹子,如果a[i]为0,则表示
这个妹子非常高贵冷艳,没有要好的妹子。b[i]表示这个妹子的颜值。

【输出格式】

	仅一个数,表示保镖SHC后宫群增加最多的颜值。

魔泥赛(题面已修改),场上只能乱搞。。。

Category: HDU | Tags: 缩点 优先队列 伪树剖

Host by is-Programmer.com | Power by Chito 1.3.3 beta | Theme: Aeros 2.0 by TheBuckmaker.com