题目点击这里 题目大意:有T组数据,每组数据给出N和K,求N的自然数和分解中,每个数不小于K的方案总数(分解方案有序,也就是说3=1+2和3=2+1是两种方案)。 首先可以想想DP的方程。 f[i]表示c(i,K)(定义与题目相同)的值,那…
呼,鼓捣了好几个中午+一节信息课终于把这个搞定了,这里尝试写一写看看有没有人用得上。 这个,我在前几天更换了一个新的主题,看到这个主题是支持特色图像的(说的像原来那个不支持一样),然后就想像黄学长一样搞个随机特色图像,然后发现他那个是主题自…
题目点击这里 首先可以想到DP的方法:令f[i]表示前i天的最小花费,那么可以得到递推方程 f[i]=min{f[j]+c[j+1,i]+k}(0<=j<i) 其中c[i,j]表示从第i天到第j天走同一条最短路径的成本。 由于天…
题目点击这里 题目大意:给定一个矩阵A,求A+A^2+A^3+...+A^N的值mod m。
题目点击这里 其实就是小学数学题啦~没什么好说的,直接求不方便,可以先求出所有的方案数为M^N,然后不会越狱的方案数为M*(M-1)^(N-1),相减就可以,当然由于数据稍微有点大,所以需要用快速幂来搞定。 代码: var p,q,ans:…
算是挺简单的题目 题目点击这里 看上去很像数据结构题目(虽然的确是),由于操作数不超过20W,所以最终数列中的元素数量都不会超过20W,所以可以开一个20W长的线段树,一开始全是0,这样插入就只要依次插入就可以,查询就要记录当前数列中的元素…
第一道斜率优化DP~ 题目点击这里 朴素的DP方程是比较容易想到的(想不到的话说明基本功还不够,多做一点简单DP题目吧):F[i]表示前i个玩具装好的最小花费,则: F[i]=min(F[j]+(SUM[i]-SUM[j]+i…
题目点击这里 题目很好理解就是一道最小割的题目,但是俗话说得好,“看到100就要想到网络流”。然而这道题目N和M都是1000的,所以直接上最大流算法似乎是不太可行的。 这里就要充分利用这题里面的图的特点了。 可以发现,在这个图里面: 任意两…
其实我在不久之前还以为有向图的强连通分量算法是和无向图的双联通分量算法是一样的呢。。。打的时候发现有点不对劲,的确有向图强连通分量的tarjan是要稍微麻烦一点的。。。 代码: var a,next,v,low,dfn,st,be:arra…
题目点击这里 算是图论的比较简单的综合题目。 这怎么看都是单源点最长路啦~但由于路径会有环出现,所以我们就要先用tarjan缩点,这样处理后的图就是一个有向无环图,重新建图后用改造后的spfa就可以啦。 代码: var a,next,v,l…
最后一次正经参加NOIP了啊。。。 DAY1 早上到学校还算早,然后简单miu了几眼以前写的博客的一些模板,然而并没有用到。 进机房(我讨厌二号位,一号位都好啊),每次校本课程都在这里所以很熟悉,发现只有逗比ABC就只好装个搜狗,然后今年竟…
有段时间没有写了,NOIP就快来了,弄点DP题目做做吧。 【bzoj1270】[BeijingWc2008]雷涛的小猫 题目是权限题,不过NOI题库可以交。 很容易想到朴素DP方程: 设f[i,j]为前i棵树,高度为j时能得到的最多柿子数量…
一年半以前的古老代码了,现在拿出来可能以后用得上,方便找。 var s,y:array[1..1048576]of int64; n,m,i,k,a,b:longint; c:int64; procedure update&…
好吧,作为倒数第二次参加NOIP,这次可是有相当重要的意义的(吧)。 考前还是看去年找到的复习资料,毕竟那个已经很全了。 凭借着往年的记忆找到了省实,来的时间刚刚好,到了之后看了下试室位置之后差不多就上去了。 (以下时间是当时…
前段时间学习了一下凸包,网上主要用的是Graham扫描法,但是dwj说Andrew其实会好一点。然后我自己也看了这两种算法,感觉Andrew其实是后者的改进版,虽然没那么容易理解。 Andrew的算法流程大概如下: 1、把所有的点按照横坐标…
更多...
加载中...