题目描述

题目地址:COGS

这题真是蛇,调一晚上。。码力太弱了qwq

思路

本来以为这跟HAOI2016的食物链一样,但是在WA了一次后注意到食物链计算的是经过某点的路径条数,而本题是经过某边的路径条数。

DP 方程

为了求出经过某一条边的的路径条数,可以这样:

设$f(u,v)$是经过边$u,v$的路径条数,$dp(u)$为从源点到$u$的路径条数,$rdp(v)$为从$v$到终点的路径条数,则有
$f(u,v)=dp(u)\times rdp(v)$
最后的答案就是$\max{f(u,v)} u,v\in G$

为了实现这个操作,我们先正常建图,求出$rdp(u)$,再反向建图,求出$dp(v)$,最后对于每一条边都合并一下答案即可。

阅读全文

A题

题目描述

原题地址:Codeforces

题意:判断回文时间。

解决方案

先搞出来一个判断回文的函数,然后枚举分钟。

阅读全文

题目描述

原题地址:COGS

一句话题意:二维的分组背包

DP方程

状态定义

令$f(i,j,k)$为在前$i$个箱子中取药,使得生命值为$j$,精神值为$k$ 。

令第$i$瓶药造成的生命值伤害是$pain(i)$,精神伤害是$san(i)$,痛苦值为$suff(i)$。

阅读全文
hexo-hey真是太好用了!! 测试公式:$a^2+b^2=c^2$ Blog迁移至我的VPS上,域名不变

[COGS 131][USACO Mar08] 奶牛渡河

题目地址:COGS

DP方程

令$dp(i)$为前$i$头牛渡河的最短时间,$m(i)$为一次带$i$头牛过河所花费的时间,则有方程:
$$
dp(i)=\min_{2\leq 2j\leq i}{dp(j)+dp(i-j)+m(0),m(i)}
$$

对方程的解释

$2\leq 2j\leq i$等价于$1\leq j\leq i-j$ ,即枚举与前面的牛分成一组过河所需时间,然后取最小值

阅读全文

题目描述

问题:题目地址中文版

思路

注意到$a,b\leq 60$,所以预处理出所有$x^a,y^b$存起来,然后两两求和,去重, 然后处理一下得到答案。

坑点

  1. 开unsigned long long

  2. while (num <= 1e18)
       num = num * x
    

    这样写是不符合基本法的,会溢出掉的

阅读全文

题目描述

问题:题目地址

Vladik often travels by trains. He remembered some of his trips especially well and I would like to tell you about one of these trips:

阅读全文

什么是主席树

主席树:可持久化线段树,特点是每次修改都新建一颗新树,由于单点修改最多影响$\log n$个节点,因此只需要新建一条链,挂在原树上

问题:[COGS 2554][福利]可持久化线段树 RMQ问题的可持久化版本

这是一道板子题,但是此题没有体现主席树的经典应用,代码如下:

阅读全文

普通的快速幂

问题[COGS 1433]圣庙里的汉诺塔

计算$a^b\mod m$,其中$0\leq a,b\leq10^{16}$。

我们可以写出如下的暴力求幂程序,复杂度$O(n)$:

typedef long long ll;
ll pow_mod(ll a,ll b,ll m)
{
  	ll ans=1;
  	while(b--)
      	ans=(ans*a)%m;
  	return ans;
}

不过注意到对于任意正整数k,我们都可以拆成至多$log k$个二进制下的1,所以我们可以计算出$a^{2^0},a^{2^1},a^{2^2},\cdots$(可以递推出来),然后再用$\log b$次乘法将其合并起来,复杂度为$O(\log n)$,代码如下:

ll fast_pow_mod(ll a,ll b,ll m)
{
    ll ans=1;
  	while(b)
    {
      	if(b&1)
          	ans*=a;
      	a*=a;
      	b>>=1;
    }
  	return ans;
}

由快速幂魔改的快速乘

问题:[COGS 2037]Asm.def大点兵

由于$a\times b$可能溢出,因此不能直接乘起来再取膜,考虑到一个事实:
$$
a^b=
\begin{cases}

1 & b=0 \\
\underbrace { a \times \cdots \times a }_b & b \ge 1

\end{cases}
$$
$$
a\times b=
\begin{cases}
0&b=0
\underbrace{a+\cdots+a}_b&b\not=0
\end{cases}
$$
所以我们把上面的代码稍微改一改就好了:

阅读全文
如题,Blog迁移至Github Pages,因为我懒233 测试一下公式: $$ \begin{cases} dp\left(1\right)=1 \ dp\left(i\right)=\sum_{j\in\left[max(i-r,1),i-l\right]&h(j)\in\left[h(i)-t,h(i)+t\right]}dp(j) \end{cases} $$ $$ \begin{cases} dp(i)=1&outdgree(i)=0\ dp(i)=\max{dp(j)}+outdgree(i)&(i,j)\in E \end{cases} $$ 看起来Katex跑的不错嘛2333 UPDATE 2017/5/29 添 阅读全文