本想在寒假期间写点什么的…无奈域名出了点问题…
导致这一个半月里面网站一直处于无法访问的状态…
想起以前积累的计算几何模板…想差不多可以整理下发出来…
不过充斥着define…以及define的奇怪用法…可以说完全是C语言风格的代码…
总之这是一个基于数组和define而不是类和template的模板…会有人看吗…
如果每段代码都注解出一步步怎么得到的话…工程浩大…
结果心血来潮…给几乎每段代码画了个图片…
蓝色是已知,红色是所求…
画了几个才发现…有些还真难用图片表达啊…
那么就开始吧…
昨天是ZOJ Monthly, August 2010
好久没做题了…N天前就看到这次月赛是东方专场…于是想着一定要去凑凑热闹…
不过最后还是只做了4个小时…最后一小时忙别的事情去了…
一看题数…居然有13题…
题号也变成了各种人物的名字了…
一上来是第阿求题…禁语吗……glob和regex的转换…看了下样例感觉不难…但是害怕有一堆要考虑的东西…
然后是第⑨题…算术教室…n个人围成一圈随机选取m个人,其中有9人是连着坐的概率是多少呢?…第一反应就是感觉是组合数方面的于是无视中…
然后看到已经有人过题了…第妖梦题…为大胃王幽幽子准备食物…第i天能准备bi份食物,但是要吃掉ai份食物…希望食物越新鲜越好…求各天准备多少食物…果然很水呢…从后往前扫一遍就可以了…
本想就看看题目娱乐下…结果一不小心手痒了…
于是敲了下…过了…
接着发现又一题有人过了…第四季题…黑白分明呢…用了Bad Apple影绘的图…
把24位点阵图转换成灰度然后再根据公式二值化…也很水…看到那句”All divisions are truncated divisions.”后就想…会有人栽在这里吧…后来真发现有个id是”一句All divisions are truncated divisions. 让我wa了10次，杯具了整个下午！！！”
但是敲了一下…在本地测试的时候用scanf(“#%2lx%2lx%2lx”,&r,&g,&b);来读入,结果本地测试死循环了…难道#也是特殊字符?于是改成了scanf(“%#%2lx%2lx%2lx”,&r,&g,&b);在本地测试通过了…可是交上去OLE了…难道编译器不同吗…
于是很郁闷的改成了scanf(“%s”,str);sscanf(str+1,”%2lX%2lX%2lX”,&r,&g,&b);
题目描述里面没说输出的9或者空格之间需要空格隔开…但是sample output里面却隔开了…于是改成没有空格隔开结果wa了…
最后再改回来有空格隔开的才AC…
接着看到第灵梦题有人过了…塞钱箱…说是第i天请人赛钱可以得到si元,但是如果这么做了,下一次请人赛钱的时间必须在xi天后,yi天前…求如果第一天请人赛钱的话,最多能得到多少钱…
稍微想了下,一个简单的dp而已…dp[i]表示第i天请人赛钱的话,从第i天开始最多能得到多少钱…转移时只要找xi天后,yi天前这段区间的dp值最大的即可…
然后一看规模…5万天…囧了…不过求区间最大值而已…解题报告虽然说用线段树…可当时我想到的却是rmq…
但是rmq是一次性的预处理的…于是就YY着改造了一下,依然沿袭rmq那种思路:分成logN层,每层有N个数,第i层的第j个数表示在[j,j+2^i-1]的范围内最大值是多少
然后从后往前边dp边insert,对于第i天来说,这天之后的每一天的dp值和rmq数组值都是已经得到了的,于是就能得到第i天的dp值,然后将这个值插入进rmq数组,更新第i个数的那logN层数字,总复杂度O(nlogn)
很快写好了…提交却下标越界…然后发现数组开小了- -|||…改后AC
在看解题报告的时候发现评论里有说Sparse Table什么的…原来我那方法叫这个名字啊…
接下来看到第辉夜题有人过…妹红要埋伏辉夜吗…题目是求一张图上从起点到终点之间的必经之路…也就是桥?…模板题吗…可惜我只有割点的模板…于是忽略了这题…
接下来看到第芙兰题有人过了…永夜抄吗……看到迷途竹林以为又是图论有关的…结果却不是这样…
一共有n个房间,第i个房间有xi个ITEM,每个是ai点,有yi个TIME,每个是bi点,每次去一个房间把所有这个房间的ITEM和TIME收完回到入口,直到所有房间的ITEM和TIME都收完…
拿一个点数是a的ITEM的时候可以得到IV分,并且TV增加a
拿一个点数是b的TIME的时候可以得到TV分,并且IV增加b
一开始IV和TV值为0,求最多能得到多少分
因为进一个房间后,该房间所有的ITEM和TIME都要收完,所以先考虑在一个房间内的情况,该按什么顺序收最好
小数据手动演算了一下,发现分数会增加IV*xi+TV*yi+u*ai+v*bi,并且u+v=xi*yi,并且对任何正整数的u,v搭配都总有一种顺序可以满足
于是得到了在第i个房间内最多分数会增加IV*xi+TV*yi+max{ai,bi}*xi*yi的结论,可见ai,bi和IV,TV是分离的,因此外面用一层状态压缩dp计算2^15个状态就可以了
dp[state]表示state的位为1的对应的房间已经去过的情况下,所得到的最大分数
并且这个情况下的IV和TV值是固定的,轻轻松松的上吧…
又看到第因幡题有人过…腹黑兔啊…看似公平的游戏却把规则定的自己总有必胜策略…想到东方夜神雪里面那个取硬币小游戏…轮流取1~3枚,取走最后一枚的人输…可是起始的硬币数量并不是随机的…而是4k+1…太囧了…玩了好几盘才发现原来这游戏是必输的…
回到这里…这次是类似孔明棋的小游戏…每次可以选一个棋子往4个方向之一跳,但是必须跳过别的棋子并且最终落在某个空格上,中间可以跳过连续多个棋子,被跳过的棋子都会被拿走…
给定初始棋局,问让铃仙和因幡谁先走可以使得因幡有必胜策略…
一看规模才5*5…想想2^25也不是什么大数字…加上有一句”It’s guaranteed that no more than 61.8% of them are ‘e’s.”…感觉状态会很少…于是直接暴力记录博弈状态…
第一次交忘记处理了选取的棋子是一排棋子中间的某个棋子的情况…改后AC
然后…第魔里沙题有人过…魔炮啊…是个计算几何…求往什么方向射可以打中最多点,魔炮的范围是个顶点为原点的抛物线
抛物线啊…想到每个点有个可被命中的角度范围,也就是魔炮的方向在这个范围内,这个点可以被打中,但是对不同距离的点而言,这个范围的大小是不一样的…
计算了下,二次系数是a的抛物线和半径为r的圆的交点
y坐标是: y=(sqrt(1+4*a*a*r*r)-1)/(2*a)
设上图中P点对应的极角为alpha,那么当魔炮中轴对着[alpha-theta, alpha+theta]区间中任意的极角时,P点就能被打中
这个theta值为: theta=atan(x/y) =atan(sqrt(y/a)/y)=atan(sqrt(1/y*a))
于是问题转换成了,找一个极角,使得它被最多的区间覆盖…而数据规模有3万个点…
脑中第一个闪现的是离散化+线段树…显然太麻烦了…
然后想起以前某些题…比如矩形求并之类的…貌似只要看左右边界判断出入就行…
于是想到了用这个方法就好,将区间变成端点,左端点标记为入,右端点标记为出,然后将所有端点按大小(这里是极角)排序
然后从前往后扫描,遇到标记为入的端点就当前覆盖区间数加一,遇到标记为出的端点就当前覆盖区间数减一,扫描一遍下来,取当前覆盖区间数的最大值…就是所需的答案daze
另外处理下跨边界相邻的情况,就是当区间在[0,2pi]的两边时,就多插入个小于0的那个入端点和大于2pi的那个出端点
然后…有别的事情…于是就看看题目然后不继续做了…
第极题…姬海棠也有啊…貌似是找最安全点…话说游戏里寅丸星的香蕉激光实在是太恶心了…但是这题目里面是射线…而且是曼哈顿距离?…直接傻眼了…点和线的曼哈顿距离?那是什么?怎么求?
第图书题…不动的大图书馆…题目是一共m种元素卡,一共有n种符文,每种元素卡上等概率出现这n种符文中的一种,求m种元素卡各取一张的话,有多少概率可以使得这些卡上的符文至少有l个是相同的…输出成既约分数…
又是组合数类的题目吗…
第咲夜题…时间的操作…哦不…这题是求表达式结果是某个类型的可能性个数?
题目很长呢…
第幽幽子题…赏花会啊…真好呢…
又是做食物…这次是第i天幽幽子会吃掉ai份食物…妖梦每天可以做L份食物,或者花一天时间锻炼自己使得L值增加1…求N天过后剩下的食物最多还有多少份…
这里或者这里是官方解题报告吧…
下面是我灵梦,芙兰,魔里沙题的代码…
最近在看Objective-c
虽说是c语言扩展出来的…可是这里面的对象甚至类本身却是动态的…
查了下貌似这叫反射?
倒是和不少脚本型的语言很像…
了解下语法之类的可以看看这里(这篇东西同时有中文版),Wiki上还有些和C++的对比
一点点看下来,一开始还没什么,感觉只是语法变了下
嗯…#include变成#import
创建类用@interface,还可以继承,不过只能继承一个父类
objective-c的方法名很有特点…并不是完整名称后面跟参数列表…而是两者交织起来…
虽然这样打字可能要多些(没有带提示功能的编辑器的话,很吃力…),但是阅读起来更加明晰,不会出现忘记第几个参数是什么作用的情况了
实现类在@implementation块内写
这里就有些舒服了,方法名直接复制到对应的implementation块中就可以开始写方法的内容了
用C++的时候,要把成员函数的声明复制过来,然后在返回类型和函数名之间加上”类名::”的东西,感觉很麻烦呢…
this变成了self,要调用父类的方法而自身却重载过了这个方法时,可以对super调用方法
用-的是对象的method,用+的是类的method,后者相当于C++的静态成员函数
id类型是万能的对象,就像void*,对id对象可以调用任何方法,只要它的本体有这个方法就可以,没有的话…就会产生异常
看到后面感觉越来越玄乎…难道一个对象里存了一个方法列表,并且方法名和参数类型都有吗?…
事实上就是这样没错…一个对象指针所指的是个这样的结构体(摘自objc.h)
typedef struct objc_object {
struct objc_class* class_pointer;
} *id;
实际对象在这个基础上后面还会跟上它的成员变量…
而这个objc_class呢,则是这样的结构(摘自objc.h)
struct objc_class {
MetaClass class_pointer; /* Pointer to the class’s
[...]
话说有快一个月没有写点什么了…
这段时间里也发生了各种事…
其中一个是EDA课程的大作业(用VHDL设计洗衣机芯片)…deadline是在7月9日(周五)…
而期末考试是在7月5日,7月7日,7月9日…EDA大作业心血来潮赶着在7月7日的时候就做好交了…不过也庆幸没有往后拖…
因为后来得了胃炎…7月9日的考试时真是煎熬啊…胃很难受,又饿着肚子又反胃…
EDA这门课结束了…VHDL语言的东西也不知道以后还会不会接触…写点什么纪念下吧…
VHDL是一种硬件描述语言…比如用来编写各种芯片…
课上用的环境是maxplus II…不过貌似落伍了?…
编写硬件真是和编写软件差很多…
基本上,VHDL中每条语句之间都是并发的,软件则是顺序执行的(当然多核多线程下可能有真正意义上的并发)…
因为软件每条指令背后都有个cpu时钟…指令之间有着先后顺序…
而VHDL则是用最基本的门电路构建一个从输入到输出的逻辑关系…不计信息传播速度的话,输出只在输入改变的时候改变…
那么…先说下VHDL的几个够用的语法吧…
首先,和C++中#include语句类似的是library
LIBRARY IEEE;
话说到现在也没太搞明白library后面跟的东西是从什么文件夹里找的…
vhdl中use是类似C++中的using的东西
USE IEEE.STD_LOGIC_1164.ALL;
USE IEEE.STD_LOGIC_UNSIGNED.ALL;
就像using namespace std;一样平常…
恩…对应C++的namespace的话应该是package了吧…
不过…我没有用过namespace,也没有用过package…不用管这些也挺够用的…
然后是元件(实体)的定义…一段vhdl程序就是用来做成一个元件的…就像C++中一个函数(感觉比起类来说更接近函数)
这个实体的定义是放在entity语句中的,其中主要是port语句定义端口名字和类型,就像C++中定义函数参数一样
ENTITY counter IS
PORT(clk,en,reset:IN STD_LOGIC;
target:IN STD_LOGIC_VECTOR(4 DOWNTO 0);
q:OUT STD_LOGIC);
–counter:clk来一个上升沿则内部计数器加一,直到内部计数器与target值相同时q端从0变成1
–en:1-enable,0-disable
–reset:0-nothing 1-reset to 0
END ENTITY counter;
这样定义了一个叫做counter的元件(实体)
其中clk,en,reset是输入端,并且都是1bit大小(STD_LOGIC是1个bit),也就是这三个端口分别占用一个引脚…
target也是输入端,但是有5bit大小,也就是它用了5个引脚,要指定是哪个引脚可以用下标,就像C++的数组一样
q是输出端,1bit大小
下面是注释…在vhdl中用–表示注释…
到这里,就像是C++中声明了一个函数,但是函数内容还没有
下面要用architecture来写这个元件内部结构了,相当于C++的函数体
ARCHITECTURE behav OF counter IS
–这里可以放内部信号的定义
–引用外部元件的定义也写在这里
BEGIN
–这里放代码(赋值语句)
END ARCHITECTURE behav;
内部信号类似于C++中函数体中的局部变量,作用域是整个元件(实体)内部
然后代码部分…是的…从根本上来说只有赋值语句…
连接电路的时候除了连连线之外还能做什么呢…
vhdl只是做这种连线的工作…
赋值语句是用
Project Euler
Problem 126 : C++,推公式,枚举
Problem 127 : C++,质因数的游戏
Problem 128 : C++,蜂窝坐标系,推导,素性判定
Problem 129 : C++,满世界的1,是有因子的
Problem 130 : C++,满世界的1,也有无聊的地方
下面是详细内容:
Project Euler
Problem 121 : C++,数学,概率
Problem 122 : C++,搜索剪枝
Problem 123 : C++,化简
Problem 124 : C++,模拟
Problem 125 : C++,枚举
下面是详细内容:
RSS订阅