这次题目真的没啥好写的了…我也真的郁闷死了…
第一题,朴素就可以AC掉.我写了一个用Splay维护状态的DP,竟然没写错…第二题,也是朴素就可以AC掉.不过我的朴素写的和人家的C++程序几乎一模一样,还是TLE一个点…我都无语了…第三题,一个简单的贪心.结果我贪心时不知道想什么呢,还用堆维护…堆差点写错了,还好还好…第四题,floyd,也差点写错了…
总体还好,错了一个点,Gold能不能进还不知道…希望不能,不然我就没有小号用了…
这次比赛总结三点:
1.注意细节处的时间复杂度(ansistring的问题,必要时加上var传递的问题,不要随便用集合的问题)2.floyd要写对3.堆要写熟
真的无语了…我rp怎么那么低…
阅读(111 次)
这个blog好几天没更新了,这几天光忙着期中考试,也没做啥题目.就在boss那儿做了一道很弱智的搜索,我都不敢发上来,肯定被bs=.=…
刚看了一下SDOI的题目,Day 1和Day 2的难度不成比例…Day 2要难很多.下面给Day 1随便写写题解吧. Day 2刚看了一下,三道题没有一个能AC,不过100分还是可以的.等都会做了再发solution.
Day 1第一题,本以为要写一个三维线段树,结果发现离散化就可以AC.想到了USACO那道题,总是把离散化的题目想麻烦…没什么可说的.
Day 1第二题,就是求1~n-1里的互质数对个数再加2.用到欧拉函数.欧拉函数刚在<什么是数学>上看过,记忆犹新.具体求法不多说.
Day 1第三题,一个线段树解决问题.注意线段树上的叶子节点分为两种,一种代表一个整点,一种代表一个开区间.比如[1, 2]就需要拆成:[1, 1], (1, 2), [2, 2]三个区间,对应线段树上三个叶子节点.程序会比较ws,容易错.
Day 1满分似乎不太难也不太容易,第三题考察代码准确性而已. Day 2我估计自己能做100分,总共300~400分.应该还算不错吧…
阅读(171 次)
矩形切割的题目,我不会矩形切割啊(或者说会但是写出来很恶心),于是写了个神奇的二维二叉单层线段树(不是n棵树,是二叉树,而且不是树套树).这东西单次操作的复杂度应该是O((logn)^2),但是竟然比O(nlogn)的还慢…无语了我都…难道这东西常数比n棵线段树大得多?大到了几千的级别?!囧.
不过还是AC了,内存好大.矩形切割其实最不错=.=,不过没怎么写过.不打算学,线段树也挺好的.
{ SGU 177; Square - sqybi’s code - 线段树}//for my winstyprogram sgu177_sqybi; const nn = 1000;
type treeNode = record x1, y1, x2, y2: integer; c: longint; lazy: boolean; end;
var tree: array[1..nn*nn*4]of treeNode; n, m, i, x1, y1, x2, y2, z: longint; ch: char;
procedure init(x, x1, y1, x2, y2: longint); […]
庆祝一下,这道题AC之后得到了宝贵的0.4分,于是以4.4分的成绩拿到了1000名…整1000名啊…一个不差…截图就不发了…
这道题是一道挺弱智的DP,和冰峰文有些类似,比那个还要简单.dset[l, r]表示从l到r这一段是不是一个set,而dlist[l, r]表示l到r是不是list.然后转移的时候考虑全就可以.其中判断是set,除了特殊情况以外,只要判断l+1到r-1是不是list就行.但注意如果a[l],a[r]不是’{’和’}’,一定不是set.判断是list的复杂些,除了特殊情况(就是atom的情况),还需要判断这一段是不是set(set也是一个list).然后枚举中间的每一位,如果某一位是’,’,那么看它两侧的串是不是两个list,是的话就说明l到r也是list.
实现不难,不过写错了一点,把l+1打成了l+r.winsty说的没错,一定要小心啊…刷1Y率是关键…
{ SPOJ 384; Any fool can do it; FOOL - sqybi’s code - DP}program fool_sqybi; const nn = 200;
var a: string; times, cases, n: longint; dset, dlist: array[1..nn, 1..nn]of longint;
procedure flist(l, r: longint); forward;
procedure fset(l, r: longint); begin if l = r then begin dset[l, r] := […]
题目描述看这段聊天记录:
Killa.sqybi 22:29:21就是说…两排点Killa.sqybi 22:29:38左边那排每个点都有一条边连向右边那排的某个点Killa.sqybi 22:29:45然后每个点有一些权值Killa.sqybi 22:30:05选取一些边Killa.sqybi 22:30:15然后这些边上的点组成一个集合Killa.sqybi 22:30:38要求这个集合的权值之和不能超过PKilla.sqybi 22:30:45问最多选取几个左边的点
看起来很简单的题啊…我刚开始想用网络流,结果问MaShuo,他说是DP…然后我就突然想到怎么做了…
Killa.sqybi 23:39:14首先啊..把所有左边的点按照连到右边点的顺序重新排序Killa.sqybi 23:39:55然后d[i,j]表示排序后左边前i个点选j个的最小花费Killa.sqybi 23:39:57和p比一下..
实现上还有一些小的注意事项,比如有的右边的点和左边的任意一个点没有连边,所以f()里面处理i=j的情况要注意.
WA on 1,8,10,11,11…第六次submit,AC了…
{ SGU 304; Mars Stomatology - sqybi’s code - DP}//for my winstyprogram sgu304_sqybi; const nn = 600; mm = 600;
var n, m, p, i, j, t, ans, ansx, edgeNum, x, y, temp: longint; a, c, r, next, adj, adjr: array[1..nn]of longint; […]
Liked it here?
Why not try sites on the blogroll...