题目大意就是从Y走到C经过*最少是多少,其中#不可走,P可传送至任何一个为P的地方,这题可以广搜,hdu给出的是最短路,下面是官方的解题报告
给出的地图中,Y为起点,C为终点,#点不能通过,可直接忽略。所有的P为互通的传送门,故可将所以的P看作同一个点。每个能通过的点可以向上下左右四个方向走,如果对应的方向可以通过,则连边,若要走到的点是*,则边权为通过的费用,否则边权为0。
连边后求Y到C的最短路即可。
我的代码
1 |
|
题目大意就是从Y走到C经过*最少是多少,其中#不可走,P可传送至任何一个为P的地方,这题可以广搜,hdu给出的是最短路,下面是官方的解题报告
给出的地图中,Y为起点,C为终点,#点不能通过,可直接忽略。所有的P为互通的传送门,故可将所以的P看作同一个点。每个能通过的点可以向上下左右四个方向走,如果对应的方向可以通过,则连边,若要走到的点是*,则边权为通过的费用,否则边权为0。
连边后求Y到C的最短路即可。
我的代码
1 | #include <algorithm> |
题目大意是有k个伞兵落到地面上,已知每个人落点的概率,有m个物资站,落地后要去最近的站。问如何安排这些物资站,使得伞兵落地后行走的期望距离的和最小。(所有落点最多1000个)。
显然是个dp题,我们可以先预处理下,对每个落点点求出他的概率总和,代表伞兵落在这点的权。可以直到物资站一定悬在伞兵落下的那些点上,所以我们就可以用dpij 表示前i个落地点中选择j个作为物资点,则很容易想到转移方程dpij=min(dpkj1+diski),其中j1=j+1, diski表示在[k,i]区间的落地点选则一个作为物资点所走距离最小值的期望(就是每点到物资点的距离乘该点概率的总和)。
现在关键就是求dis,其实我们注意到 假设对于[i,j],假设选取k作为物资点,则有
disij=∑kn=i(ak−an)pn+∑jn=k+1(an−ak)pn
而若选择k+1作为物资点,则有
dis‘ij=∑kn=i(ak+1−an)pn+∑jn=k+1(an−ak+1)pn
则相减并化简得
dis‘ij−disij=(ak1−ak)(∑kn=ipn−∑jn=k+1pn)=(ak1−ak)(sumik−sumk1j)
设tmp=dis‘ij−disij,sum可以很容易求出,这样很显然,当k增加时,tmp的值也在增加,所以,若选取k作为物资点,则要tmp≥0,否则我们可以选取k+1作为物资点,这样,可以对dis进行预处理,然后就可以得出答案
1 | #include <algorithm> |
这题就是一个矩阵分割,因为之前做过USACO上类似的一题,所以最开始就看了这题
矩阵分割,有多种情况,具体可以参考我的USACO 3.1.4 Shaping Regions 搜索+矩形切割
但这题略有不同,USACO上面是颜色覆盖,这里是颜色相加,所以对于相交的区域不能那个直接计算面积,还要继续递推直到最后一个矩形
但有一个问题,矩形太多,递推超时,注意到颜色只有三种,所以我们可以对颜色进行一次一次排序(让R,G,B顺序),如果到分割第t个矩形时,当前所加的颜色含有第t个矩形的颜色,则我们可以直接跳转到下一个颜色区域,这样就可以避免重复搜索
还有一个问题,就是颜色的处理,因为颜色的相加,可以用位运算来解决,R-1,G-2,B-4,这样就对颜色的相加转化成或运算,具体可看我的代码(刚用我的代码提交了下,发现不论时间还是空间排行暂时第一,第一次啊!)
1 | #include<iostream> |
可以知道对于任何数n都可以写成n=x+[y+z+…],则对于任意的一个x(0≤x<n),后面的式子有2n−x−1种写法
假设对于给定的k,题目要求的就是f+n
则对于x有两种可能
若x=k,则这2n−x−1个式子中,因为第一项就是k,所以每一个式子至少含有1个k,现在就看其余项中含有多少k,而其余项就是求f(n−x)
若x≠k相等,则第一项不含有k,就看其余项中含有含有多少k,依旧是求f(n−x)
注意到,当k>n是,f(n)=0
则可以得到
fn=∑n−1i=kfi+2n−k−1
于是可以求出通项公式
fn=(n−k+3)∗2n−k−2(n>k)
more >>官方解题报告
我们特判出n≤k的情况。
对于1≤k<n,我们可以等效为n个点排成一列,并取出其中的连续k个点。下面分两种情况考虑:第一种情况,被选出的不包含断电,那么有n−k−1种情况完成上述操作,剩下未被圈的点之间还有n−k−2个位置,可以在每个位置断开,所以共 (n−k−1)∗2n−k−2 种方法。
第二种情况,即被选出的包含端点,那么有两种情况,并且剩余共n−k−1个位置,所以共2∗2n−k−1种方法。
总计2×2n−k−1+(n−k−1)2n−k−2=(n−k−3)2n−k−1。
题目实际上就是求n−1∑i=0|imoda−imodb|
既然有取余,明显会有循环节,很显然循环节是lcm(a,b)
那就求出循环节部分的值再乘以循环的次数再加上其余部分就可以了
多校的时候a,b都取的int,WA了 后来才弄对
1 | #include <algorithm> |
实际上就是求的二分图最大匹配
1 | #include <iostream> |
dp题
1 | #include <algorithm> |
crontab是unix下设置周期性执行任务的工具,类似于windows的计划任务。当系统启动时会自动启动cron进程并后台运行,系统每分钟就启动一次cron服务并检查是否有可执行的任务,若有则会自动执行该任务。
Linux系统一般都默认安装有crond服务,可跳过该步
安装crond服务
1 | yum install vixie-cron #vixie-cron是cron主程序 |
启动crond服务
1 | service crond start |
查看crond服务是否启动
1 | service crond status |
设置开机启动
1 | chkconfig crond on |
很明显这题要求的是使等式 x+d=pmod23=emod28=imod33 成立的最小的x,注意x不能为0
注意,有几组特殊数据供参考
关于中国剩余定理,我理解的也不是很好,直接套的模板
1 | #include <iostream> |
tag:
缺失模块。
1、请确保node版本大于6.2
2、在博客根目录(注意不是yilia根目录)执行以下命令:
npm i hexo-generator-json-content --save
3、在根目录_config.yml里添加配置:
jsonContent: meta: false pages: false posts: title: true date: true path: true text: false raw: false content: false slug: false updated: false comments: false link: false permalink: false excerpt: false categories: false tags: true
2018-09-16
#算法竞赛入门经典训练指南#动态规划
2018-09-16
#算法竞赛入门经典训练指南#动态规划
2018-09-16
#算法竞赛入门经典训练指南#排序#计算几何#贪心
2018-09-16
#算法竞赛入门经典训练指南#动态规划#离散#二分
2018-09-16
#算法竞赛入门经典训练指南#深度优先搜索#递归
2018-09-16
#算法竞赛入门经典训练指南#二分#深度优先搜索
2018-09-16
#算法竞赛入门经典训练指南#动态规划#递归#状态压缩
2018-09-16
#算法竞赛入门经典训练指南#动态规划#状态压缩
2018-09-16
#算法竞赛入门经典训练指南#贪心#数论
2018-09-16
#最大公约数#数论
2018-09-16
#codeforces
2018-09-16
#codeforces
2018-09-16
#codeforces#矩阵#快速幂
2018-09-16
#codeforces#数论
2018-09-16
#AC自动机#kmp#字典树#字符串匹配#数据结构
2018-09-16
#素数#欧拉函数#筛选
2018-09-16
#矩阵#快速幂
2018-09-16
#burnside#polya
2018-09-16
#素性测试#素数
2018-09-16
#仙剑#感动
2018-09-16
#仙剑#感动#语录
2018-09-16
#深度优先搜索#素数#hdu
2018-09-16
#数据结构#hdu#并查集
2018-09-16
#字典树#数据结构#hdu
2018-09-16
#动态规划#hdu
2018-09-16
#kmp#hdu
2018-09-16
#数据结构#hdu#线段树
2018-09-16
#数论#hdu
2018-09-16
#hdu#优先队列
2018-09-16
#计算几何#hdu
2018-09-16
#AC自动机#kmp#数据结构#hdu
2018-09-16
#动态规划#hdu#背包问题
2018-09-16
#递归#矩阵#快速幂#hdu
2018-09-16
#hdu#枚举
2018-09-16
#数据结构#hdu#枚举#后缀数组#旋转
2018-09-16
#排序#hdu
2018-09-16
#递归#数论#hdu#卡特兰数
2018-09-16
#矩阵#快速幂#hdu
2018-09-16
#kmp#hdu
2018-09-16
#动态规划#hdu
2018-09-16
#hdu#广度优先搜索#最短路
2018-09-16
#动态规划#hdu
2018-09-16
#深度优先搜索#hdu#矩形#分治
2018-09-16
#递归#数论#hdu
2018-09-16
#最大公约数#数论#hdu
2018-09-16
#贪心#hdu#二分图#图论#最大匹配
2018-09-16
#动态规划#hdu
2018-09-16
#数据结构#并查集#算法
2018-09-16
#Linux#crontab
2018-09-16
#数论#poj#中国剩余定理
2018-09-16
#递归#poj#规律
2018-09-16
#动态规划#poj
2018-09-16
#数论#poj#同余方程#扩展欧几里得
2018-09-16
#最短路#图论#poj
2018-09-16
#动态规划#poj
2018-09-16
#poj#记忆化搜索
2018-09-16
#最短路#图论#poj#floyd
2018-09-16
#动态规划#字符串匹配#poj
2018-09-16
#数论#poj
2018-09-16
#动态规划#poj
2018-09-16
#枚举#poj#位运算#高斯消元
2018-09-16
#图论#poj#生成树#kruskal
2018-09-16
#图论#poj#prim#生成树
2018-09-16
#二分图#最大匹配#poj#匈牙利算法
2018-09-16
#最大公约数#数论#欧拉函数#poj#费马小定理
2018-09-16
#深度优先搜索#poj#搜索
2018-09-16
#图论#poj#最小覆盖点
2018-09-16
#动态规划#poj#DP
2018-09-16
#深度优先搜索#数论#poj#搜索
2018-09-16
#动态规划#poj#最长公共子序列
2018-09-16
#二分图#图论#最大匹配#poj
2018-09-16
#poj#记忆化搜索
2018-09-16
#枚举#poj#位运算#高斯消元
2018-09-16
#图论#poj#prim#生成树
2018-09-16
#并查集#最短路#图论#poj#生成树
2018-09-16
#poj#位运算#高斯消元
2018-09-16
#poj#中国剩余定理#同余方程#扩展欧几里得
2018-09-16
#数论#poj#排列#组合数学
2018-09-15
#素数#筛选#poj
2018-09-15
#数据结构#广度优先搜索#poj#搜索#队列
2018-09-15
#最短路#图论#poj#生成树
2018-09-15
#素数#枚举#poj
2018-09-15
#数论#poj#抽屉原理
2018-09-15
#素数#欧拉函数#poj
2018-09-15
#polya#poj#组合数学
2018-09-15
#数论#欧拉函数#poj
2018-09-15
#动态规划#poj
2018-09-15
#图论#poj#最小生成树
2018-09-14
#深度优先搜索#poj#搜索
2018-09-14
#数据结构#并查集#poj
2018-09-14
#递归#poj#高精度
2018-09-14
#递归#数论#poj
2018-09-14
#数论#素数#poj
2018-09-14
#最大公约数#数论#poj#扩展欧几里得#欧几里得
2018-09-14
#深度优先搜索#poj#搜索
2018-09-14
#矩阵#快速幂#poj#斐波那契数列
2018-09-14
#数论#欧拉函数#poj#法雷级数
2018-09-14
#枚举#poj#位运算#高斯消元
2018-09-14
#数论#矩阵#poj#分治
2018-09-14
#数据结构#广度优先搜索#poj#搜索
2018-09-14
#数论#poj#抽屉原理
2018-09-14
#动态规划#递归#记忆化搜索#usaco
2018-09-14
#poj#测试数据
2018-09-14
#枚举#usaco
2018-09-14
#枚举#规律#搜索#usaco
2018-09-14
#动态规划#字典树#数据结构#usaco
2018-09-14
#动态规划#usaco#二叉树
2018-09-14
#深度优先搜索#枚举#usaco
2018-09-14
#动态规划#usaco
2018-09-14
#图论#usaco
2018-09-14
#深度优先搜索#矩形#分治#usaco#矩形切割
2018-09-14
#字典树#usaco
2018-09-14
#动态规划#usaco#背包
2018-09-14
#数论#usaco#阶乘
2018-09-14
#组合数学#usaco
2018-09-14
#枚举#usaco
2018-09-14
#高斯消元#usaco
2018-09-14
#广度优先搜索#usaco#康托展开
2018-09-14
#usaco#spfa
2018-09-14
#usaco#欧拉回路
2018-09-14
#素数#zoj#反素数
2018-09-14
#矩形#zoj#归并排序#逆序对
2018-09-14
#最大公约数#数论#矩阵#数据结构#zoj