解题报告模板POJ1000 : A + B Problem

POJ1000 : A + B Problem

(这里要写来源OJ和题号,如果是小众OJ(即Vjudge上测不了的OJ),在这里附上题目的测试数据(如果能搞的到),(或生成器,同时提供边界数据)包)

题目链接

给定两个数,求它们的和

要求复杂度:O(ab)

,(如果是根据题目限制推出的做法,最好附上题目要求的复杂度)

(如果题目特别好懂,这一步可以直接写翻译的题面,如果这一题考阅读理解(模拟题),就自己把握一下写什么)

做法1

利用网络流,可以从原点S

到汇点T

连容量为a和b的两条边,求最大流即可

复杂度 O(1)

(写一下题目的坑点,如“此题十分变态,倍增的SA不能过,得用DC3或者SAM”,考虑到能力上的差别,慎用小众的缩写(自己衡量))

(可以附上AC代码,也可以附上Github上的链接,但最好写一下效率,语言嘛,看心情,反正集训队里大多是C++) (如果是计算几何题目,考虑到模版很长,在贴代码的时候可以考虑贴核心代码,像点、线、圆之类的定义就不必重复了,直接写成Point Vector Line, Circle之类一眼就能看出来的名字就好)

Time: 15 ms Memory: 768 K

#include
using namespace std;
int main()
{
int a, b;
cin >> a >> b;
cout << a + b << endl; return 0; } (略,表示可以把想到的其它做法(未必最优)写出来,最好分析一下复杂度,如果有空间复杂度的分析更好(针对数据结构题))

树上点分治

这几天一直想完成之前的点分治,但都在写其他题,今天终于写完了点分治,怕忘,就写一下博客。

【引言】

由于树具有一般的图没有的特点,所以在竞赛中的应用更广。

在一些树上路径问题中,暴力求解时间复杂度过高,往往需要一些更为高效的算法,点分治就是其中之一。

【思想】

在树上,取一个点,对于询问计算所有经过这个点的情况,再递归下去处理每一棵子树的情况。因为是递归处理,为了使递归的次数更少,一般都是要取使以其为根,所有子树中节点最多的子树拥有的节点最少,称这个点为“重心”。

重心求法如下:

(1)任取一个根,dfs一次求出每个节点的子树大小。

(2)记录每一个点最大子树的节点数。

(3)最大子树的节点最少的点便是重心

代码如下:


1
2
3
4
5
6
7
8
9
10
11
12
13
14
[cce_cpp]
void Getroot(int x, int fa)  {
    son[x] = 1;
    Max[x] = 0;
    int next;
    for (int i = last[x]; i ;i = e[i].last)
        if (!use[next = e[i].t] && next != fa)  {
            Getroot(next, x);
            son[x] += son[next];
            Max[x] = max(Max[x], son[next]);
        }
    Max[x] = max(Max[x], Son - son[x]);//因为这个点不一定是根,要计算它上的节点数,用树的大小减去(它的子节点数+1)即可
    if (Max[x] < Max[root]) root = x;
}
[/cce_cpp]

时间复杂度O(n)。

求出重心接下来就要解决问题了
(1)关于询问,以重心为根,求出所有经过当前重心的情况(即子节点1-->重心-->子节点2)。因为为了节省时间,是把所有子节点的情况一起算,如果两个子节点来自同一棵子树,那肯定是不行的,所以还要减去所以来自同一棵子树的子节点的情况。
(2)标记重心
(3)递归用相同的方法处理每一棵子树。
代码如下:


1
2
3
4
5
6
7
8
9
10
11
12
13
void sol(int x)  {
    root = 0;
    Getroot(x, 0);
    use[root] = 1;
    ans += Cal(root, 0);
    int next;
    for (int i = last[root]; i ;i = e[i].last)
        if (!use[next = e[i].t])  {
            ans -= Cal(next, e[i].val);
            Son = son[next];
            sol(next);
        }
}

点分治的思想基本上如上所述。

【例题】

继续阅读树上点分治

【HNSDFZ】IQ 测试

给出一个初始序列a,求对于每个询问序列b是否能通过初始序列删除一些数得来。

数据范围1<=ai,bi<=1000000,ΣL<=1000000,n,m<=1000000

题解:

这题目一看还挺简单的,即判断b的每个元素是否在a中按顺序出现,可以贪心求解,对于b的第i个元素,假设前  i - 1个元素已经在a中找到,b[i-1]在a中的位置为t,则为了能够找出答案,我们取的一定要是b[i-1]这个数在t后面第一次出现的位置。也就是对于每个询问的数取最前面能取的位置。

上面的方法时间复杂度是O(n^2)的,需要想个更优的解法。由于我们上面的贪心方法是正确的,我们可以从优化贪心入手,在上面的贪心中,是用枚举的方法来找第一个出现的位置,于是可以想到用链表来储存位置,对于一个数bi,可以开链表指向后一个与它值相同的数的位置,这样可以优化不少时间。这个方法对于随机的数据是可以过的。

注意这题数据范围ΣL<=1000000 n,m<=1000000,假设有这样一组数据:
a = 1 1 1 1...1 5 1(...中有1000000个1)一共有300000个询问数组b ;每个b都是{1 5 1}

这样对于每次询问,链表优化相当于没有。

但由于每个数指向的下一个位置只有一个,所以可以用倍增来优化。

设一个next数组,next[i]表示bi后面第(2^i)个与它值相同的数的位置,则对于查找bi后面第x个与它相同的数的位置,可以把x拆成多个2^n的和

代码如下:
继续阅读【HNSDFZ】IQ 测试

【POJ2411】Mondriaan's Dream

题意:

给出n*m的方阵,求用1*2的小矩形铺满有几种情况。

题解:

这题可以用状压dp来解决,但现在我用的是轮廓线dp(状压dp的一种,但在这题中比状压dp更优)。

我们可以从左到右、从上到下把方阵分成n*m个阶段。由于小矩形是1 * 2的, 所以对于每个阶段的决策有影响的只有当前这一行和上一行的一些部分。而上面“#”的部分是已经确定的,对当前点没有影响

如:1 2 3 4 5

1      # # # # #

2      # # 1 1 1

3      0 0 ?

·······

把对于决策有影响的阶段称为轮廓线(如上图的11100)

于是,可以用2^(m -1)来枚举轮廓线的状态。(m < n)

1表示被覆盖,0表示没被覆盖。

设(i, j)为当前阶段,k为当前轮廓线的状态

则可以得到转移方程:
不放: 下一个状态 now =  (k << 1) & ( (1 << m)  -  1)
dp[cur][now] += dp[cur ^ 1][k];

条件k&(1 << (m - 1))[即 [i-1][j]一定要被覆盖]
向上放: 下一个状态 now = ( (k << 1) | 1) & ( (1 << m)  - 1)
dp[cur][now] += dp[cur ^ 1][k];

条件!(k&(1 << (m - 1)))[即 [i-1][j]一定没被覆盖]
向左放: 下一个状态 now = ((k << 1)|3)&((1 << m) - 1)
dp[cur][now] += dp[cur ^ 1][k];

条件k&(1 << (m - 1)) && !(k&1)[即 [i-1][j]一定要被覆盖,[i][j-1]一定不能被覆盖]

时间复杂度O(n*m*2^m),由于一个点的状态只由它前一个点的状态转移来,可以开滚动数组来存储答案,最后答案dp[cur][2^m-1]

代码如下:

继续阅读【POJ2411】Mondriaan's Dream

3634【HNSDFZ集训】B 君的教育

题意:

  求出一个满足Σpk=x+yi(kS)的非负整数序列。

题解:

  由于p=-1+i(这里i是虚数),所以其满足p^n=2[p^(n1)+p^(n2)](这个我也不知道为什么,请自行探索)

然后在发现在不考虑一个p^k最多只能用1次的情况下,可以用p^0p^1x+yi表示出来。然后根据上面推出来的这个式子,k从0开始,若p^k用了奇数次,就把它调整成1次,偶数次就调整成0次,如此向后,最终一定能得到解集。

关于c++中的complex

关于虚数i

代码如下: 继续阅读3634【HNSDFZ集训】B 君的教育