Dylan's Blog
0%

Posted on Edited on In

问题描述：

给你一张由$T$条边构成的无向图，求起点$S$到终点$E$恰好经过$N$条边的最道路。（路径可以重复经过）

输入：

第一行包含4个整数$N$、$T$、$S$、$E$ （$N<=1000000，T<=100$，节点编号不超过1000） 接下来T行每行三个数$Len，I_1，I_2$ 表示$I_1 I_2$间有一条长度为$Len$的无向边

输出：

一个整数，起点$S$到终点$E$恰好经过$N$条边的最道路长度

思路：

将这个与矩阵加速递推联系起来确实需要对递推有很深的理解（需要很大脑洞）。。。

其实我们每进行一次递推就是多经过一条路径，然后每一次进行递推时都需要将所有点之间的距离初始化一下（如果不初始化就是普通的最短路，初始化了就是经过N条边的最短路）。

我们的递推可以利用类似Floyd的方式来实现。如果直接开$1000*1000$的矩阵复杂度显然会爆掉，于是我们考虑只有100条边，那么最多只有200个点是有用的，因此我们先离散化一下。最后按照套路利用矩阵快速幂优化一下递推就能够过了。

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
using namespace std;

int n, m, t, s, e, tot, sub[205], f[205][205], g[205][205];

struct A {int s, t, len;} a[205];

void mul(int x[205][205], int y[205][205])
{
    int ans[205][205];
    memset(ans, 0x3f, sizeof(ans));
    for(int k=1; k<=m; k++)
        for(int i=1; i<=m; i++)
            for(int j=1; j<=m; j++)
                ans[i][j]=min(ans[i][j], x[i][k]+y[k][j]);
    memcpy(x, ans, sizeof(ans));
}

int main()
{
    memset(f, 0x3f, sizeof(f));
    scanf("%d%d%d%d", &n, &t, &s, &e);
    sub[++tot]=s; sub[++tot]=e;
    for(int i=1; i<=t; i++)
    {
        scanf("%d%d%d", &a[i].len, &a[i].s, &a[i].t);
        sub[++tot]=a[i].s; sub[++tot]=a[i].t;
    }
    sort(sub+1, sub+tot+1);
    m=unique(sub+1, sub+tot+1)-sub-1;
    for(int i=1; i<=t; i++)
    {
        int x=lower_bound(sub+1, sub+m+1, a[i].s)-sub;
        int y=lower_bound(sub+1, sub+m+1, a[i].t)-sub;
        f[x][y]=min(f[x][y], a[i].len);
        f[y][x]=min(f[y][x], a[i].len);
    }
    memcpy(g, f, sizeof(g));
    n--;
    while(n)
    {
        if(n&1) mul(g, f);
        mul(f, f); n>>=1;
    }
    s=lower_bound(sub+1, sub+m+1, s)-sub;
    e=lower_bound(sub+1, sub+m+1, e)-sub;
    printf("%d\n", g[s][e]);
}

Posted on Edited on In

问题描述：

上帝手中有着N 种被称作“世界元素”的东西，现在他要把它们中的一部分投放到一个新的空间中去以建造世界。每种世界元素都可以限制另外一种世界元素，所以说上帝希望所有被投放的世界元素都有至少一个没有被投放的世界元素能够限制它，这样上帝就可以保持对世界的控制。

帝希望知道他最多可以投放多少种世界元素，你需要帮助上帝解决这个问题。

输入：

第一行是一个整数$N$，表示世界元素的数目。 第二行有$N$个整数$A_1, A_2, …, A_N$。$A_i$ 表示第$i $个世界元素能够限制的世界元素的编号。

输出：

一个整数，表示最多可以投放的世界元素的数目。

思路：

根据题意，我们可以发现限制关系是一个环加内向树森林，这道题就是一个基环树森林版本的“没有上司的舞会”。因此，这道题的DP转移方程很容易推出，难就难在如何处理基环树森林。

关于基环树上的树形DP我们在BZOJ1791 Island这题中提到过，用的是找出环然后破环为链的方法。然而这道题用这个方法就不好处理，于是我们可以用分类讨论，进行两次DP的方法处理。我们对于每棵基环树找出环上的任意一条边，先假设不用这条边的限制，那么就是一个直接的树形DP，为了方便我们把所有边反着建，把边所在的一个端点作为根节点，然后这样得出了答案一。再假设这条边的限制一定要用到，也是同样的DP只是要一个特判，这样得出的答案二。那么最终的答案就是两个答案中大的那一个。

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <cstring>
#define MAXN 1000006
using namespace std;

int n, cnt, ans, root, fa[MAXN], head[MAXN], f[MAXN][2];
bool vis[MAXN];

struct Edge {int next, to;} edge[MAXN];

void addedge(int from, int to)
{
    edge[++cnt].next=head[from];
    edge[cnt].to=to;
    head[from]=cnt; 
}

int find(int x)
{
    if(vis[x]) return x;
    vis[x]=1;
    return find(fa[x]);
}

void dfs(int x, int fa)
{
    f[x][0]=f[x][1]=0; vis[x]=1;
    for(int i=head[x]; i; i=edge[i].next)
    {
        int to=edge[i].to;
        if(to==root) continue;
        dfs(to, fa);
        f[x][0]+=max(f[to][0], f[to][1]);
    }
    if(x==fa) {f[x][1]=f[x][0]+1; return;}
    for(int i=head[x]; i; i=edge[i].next)
    {
        int to=edge[i].to;
        if(to==root) continue;
        f[x][1]=max(f[x][1], f[x][0]-max(f[to][1], f[to][0])+f[to][0]+1);
    }
}

int main()
{
    scanf("%d", &n);
    for(int i=1; i<=n; i++)
    {
        scanf("%d", &fa[i]);
        addedge(fa[i], i);
    }
    for(int i=1; i<=n; i++)
        if(!vis[i])
        {
            root=find(i);
            dfs(root, 0);
            int temp=max(f[root][0], f[root][1]);
            dfs(root, fa[root]);
            temp=max(f[root][0], temp);
            ans+=temp;
        }
    printf("%d\n", ans);
}

Posted on Edited on In

问题描述：

给你一个$h*w$的网格，其中有$n$个黑色的格子，它们的位置为$(x_i, y_i)$。你从左上角开始，每一步只能向左或者下移动，并且不能经过黑色格子，问你有多少种到达右下角的方案。

输入：

第一行给你三个数$h, w, n$（$1<=h, n<=10^5, 1<=n<=200$）

输出：

输出对$10^9+7$取模的方案数

思路：

感觉JXOI很喜欢考计数类DP，然而自己菜的一比。。。

首先我们就是要考虑如何设计一个状态，能够统计DP时的信息，并且能够根据这个状态不重不漏地进行DP（我觉得计数类DP就是这个难，状态转移反而容易一些）。因为黑色格子不多，所以我们的复杂度应该和黑色的格子有关。我们可以先将黑色格子按照横纵坐标排序，然后设$f[i]$为到达$i$个黑色格子且不经过前$i-1$个黑色格子的可能路径数。特别的，设$f[n+1]$的坐标为$(h+1, w+1)$，那么答案就是$f[n+1]$了。

接下来我们考虑如何计算和转移。我们可以先计算出到达第$i$个黑色格子所有路径，这个的数量为$C_{x_i+y_i-2}^{x_i-1}$，原因是一共要向下或向左走$x_i+y_i-2$步，然后其中要任选$x_i-1$步向左走。然后还要减去经过前面黑色格子的路径数，因此我们可以推出DP方程为: 还要特别注意的是如果$x_j>x_i$或者$y_j>y_i$时，这一项是不用减去的。

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
#include <bits/stdc++.h>
#define MAXN 300005
#define p 1000000007
#define LL long long
using namespace std;

int h, w, n;
LL f[MAXN], fac[MAXN], inv[MAXN];

struct Node {int x, y;} a[MAXN];

bool CMP(Node x, Node y)
{
    if(x.x==y.x) return x.y<y.y;
    else return x.x<y.x;
}

LL comb(LL n, LL m)
{
    return fac[n]*inv[n-m]%p*inv[m]%p;
}

void init()
{
    inv[0]=fac[0]=fac[1]=inv[1]=1;
    for(int i=2; i<=MAXN-5; i++)
    {
        fac[i]=(fac[i-1]*i)%p;
        inv[i]=inv[p%i]*(p-p/i)%p;
    }
    for(int i=2; i<=MAXN-5; i++) inv[i]=(inv[i]*inv[i-1])%p;
}

int main()
{
    init();
    scanf("%d%d%d", &h, &w, &n);
    for(int i=1; i<=n; i++) scanf("%d%d", &a[i].x, &a[i].y);
    sort(a+1, a+n+1, CMP);
    a[n+1].x=h; a[n+1].y=w;
    for(int i=1; i<=n+1; i++)
    {
        f[i]=comb(a[i].x+a[i].y-2, a[i].x-1);
        for(int j=1; j<i; j++)
        {
            if(a[j].x>a[i].x || a[j].y>a[i].y) continue;
            f[i]=(f[i]-f[j]*comb(a[i].x+a[i].y-a[j].x-a[j].y, a[i].x-a[j].x))%p;
        }
    }
    printf("%lld\n", (f[n+1]+p)%p);
}

Posted on Edited on In

问题描述：

在$N*M$的网格中有一个起始位置为$(x, y)$的robot。它每一步会随机的执行四个操作中一个：待在原地，向左，向右，向下（它是不能够移动到网格之外的）。然后问你它移动到第$N$行的步数期望值为多少。

输入：

第一行两个整数$N，M$，表示$N*M$的网格（$1<=n, m<=1000$） 第二行两个整数$x，y$，表示起始位置为$(x, y)$

输出：

输出到第$n$行的期望步数

思路：

这道题中的状态转移方程并不难想到。但是我们发现这些状态会相互影响，并且无法推出其中的任何一个。对于这种期望DP就要用到另一种套路“高斯消元”。

按照套路我们依然从后往前推，第$n$行的所有期望值都为0，我们把这个作为初值向前DP。对于每一行我们都能根据转移方程列出一个方程组，而且我们发现其中的每个方程只有2-3个变量（边界时为两个，其余为3个）。于是我们可以不用普通$O(N^3)$的高斯消元，而是可以YY出一个类似的$O(n)$的消元方法，然后对于每一行都进行一遍这个操作，总复杂度为$O(nm)$。

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <cstdio>
#include <string>
#define MAXN 1005
using namespace std;

int n, m, x, y;
double a[MAXN][5], g[MAXN], f[MAXN], w[MAXN];

void guass()
{
    for(int i=1; i<m; i++)
    {
        double rate=a[i+1][0]/a[i][1];
        a[i+1][0]-=a[i][1]*rate;
        a[i+1][1]-=a[i][2]*rate;
        w[i+1]-=w[i]*rate;
    }
    f[m]=w[m]/a[m][1];
    for(int i=m-1; i>=1; i--) f[i]=(w[i]-a[i][2]*f[i+1])/a[i][1];
}

int main()
{
    scanf("%d%d%d%d", &n, &m, &x, &y);
    for(int i=1; i<=m; i++)
    {
        g[i]=2;
        if(i>1) g[i]++;
        if(i<m) g[i]++;
        g[i]=1.0/g[i];
    }
    for(int i=n-1; i>=x; i--)
    {
        for(int j=1; j<=m; j++)
        {
            if(j!=1) a[j][0]=-g[j];
            a[j][1]=1-g[j];
            if(j!=m) a[j][2]=-g[j];
            w[j]=g[j]*f[j]+1;
        }
        guass();
    }
    printf("%lf\n", f[y]);
}

Posted on Edited on In

问题描述：

对于给定的整数$a，b，d$，有多少正整数对$x，y$，满足$x<=a，y<=b$并且$gcd(x,y)=d$

输入：

第一行包含一个正整数$n$，表示一共有$n$组数据$（1<=n<= 50000）$ 接下来$n$行，每行表示一个询问。每行三个正整数，分别为$a,b,d$（$1<=d<=a,b<=50000$）

输出：

对于每组询问，输出一个正整数，表示满足条件的整数对数

思路：

这是一个莫比乌斯反演的模版题，莫比乌斯反演虽然听起来很高级但内容还是比较好理解的。

首先是莫比乌斯函数$\mu(n)$，这是一个表示容斥系数的函数。它的定义是这样的：当n有相等的质因子$\mu(n)=0$；当n没有相等质因子且质因子个数为偶数$\mu(n)=1$；当$n$没有相等质因子且质因子个数为奇数$\mu(n)=-1$。

然后关于莫比乌斯反演有下面两个形式：我们设存在两个函数$F(n), f(n)$

形式一：如果满足条件 那么就有： 形式二：如果满足条件 那么就有： 关于证明，我这么菜自然是不懂的。

对于这道题，设$x=\lfloor a/d\rfloor$， $y=\lfloor b/d \rfloor$。显然可以将题目转化为求这样一个式子： 然后我们设$f(n)$为在范围内$gcd(i,j)=n$的的个数，设$F(n)$为在范围内$n|gcd(i,j)$的个数，因此 那么很显然，函数$f(d),F(n)$满足反演的第二种形式且$f(1)$就是我们所求答案。于是利用反演得到：

于是直接计算就是这样的（实测70分）:

1
2
for(int j=1; j<=min(a, b); j++) ans+=mob[j]*(a/j)*(b/j);
//注意这里的mob是未经前缀和处理的

然后可以发现$a/j, b/j$的取值是一段一段的，所以我们利用数论分块的方法进行优化。数论分块可以看这道题:BZOJ1257 余数之和，然后代码是这样的：

1
2
3
4
5
6
for(int l=1, r; l<=min(a, b); l=r+1)
{
    r=min(a/(a/l), b/(b/l));
    ans+=(mob[r]-mob[l-1])*(a/l)*(b/l);
}
//注意这里的mob是经过前缀和处理的

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <string>
#define MAXN 500005
#define LL long long
using namespace std;

int n, a, b, d, cnt, pri[MAXN], tag[MAXN], mob[MAXN];

void init()
{
    mob[1]=1;
    for(int i=2; i<=50000; i++)
    {
        if(!tag[i]) pri[++cnt]=i, mob[i]=-1;
        for(int j=1; j<=cnt && pri[j]*i<=50000; j++)
        {
            tag[i*pri[j]]=1;
            if(i%pri[j]==0) {mob[i*pri[j]]=0; break;}
            else mob[i*pri[j]]=-mob[i];
        }
    }
    for(int i=2; i<=50000; i++) mob[i]+=mob[i-1];
}

int main()
{
    init();
    scanf("%d", &n);
    for(int i=1; i<=n; i++)
    {
        int ans=0;
        scanf("%d%d%d", &a, &b, &d);
        a/=d; b/=d;
        for(int l=1, r; l<=min(a, b); l=r+1)
        {
            r=min(a/(a/l), b/(b/l));
            ans+=(mob[r]-mob[l-1])*(a/l)*(b/l);
        }
        printf("%dn", ans);
    }
}