Dylan's Blog
0%

Posted on Edited on In

问题描述：

给你$n$块长度为$1-n$的木板，你需要将它们组成一个栅栏，并且在栅栏中木板是高低交错的（就是所有木板要么都比两边低，要么都比两边高）。

显然有很多构建栅栏都方案，于是给你一个整数$C$，你需要求出按照字典序排在第$C$个的构建方案。

输入：

第一行一个整数$K$，表示有$K$组数据 接下来$K$行每行两个整数$n, c$，表示一组数据（$n<=20，c<=2^{63}$）

输出：

对于每组数据你需要输出字典序大小第$C$个第构建方案。

思路：

特别好的一道计数类DP。这题不光要你统计方案数，还要在它第基础上求出排名为$C$第方案。

我们设$f[i][j][k]$为：用$i$块木板，最左端木板从小大排在第$j$位，比两边都低（$k=0$），或比两边都高（$k=1$）的方案数。这个状态设计得十分精妙，不是直接设最左端木板的高度，而是设在$i$块木板中的排名。这样既方便了状态的转移，也方便了后面找方案的过程。

状态转移方程比较好推：$f[i][j][0]=\sum_{p=j}^{i-1}f[i-1][p][1]$和$f[i][j][1]=\sum_{p=1}^{j-1}f[i-1][p][0]$。这样我们就得出了方案数，接下来求排名为$C$的方案就比较容易了。我们从左到右枚举木板长度，比较方案数与排名的关系，进而推出答案。

代码：

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
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <cstdio>
#define MAXN 25
#define LL long long
using namespace std;

int T, n;
LL c, f[MAXN][MAXN][2];
bool vis[MAXN];

void init()
{
    f[1][1][0]=f[1][1][1]=1;
    for(int i=2; i<=20; i++)
        for(int j=1; j<=i; j++)
        {
            for(int k=1; k<j; k++) f[i][j][1]+=f[i-1][k][0];
            for(int k=j; k<i; k++) f[i][j][0]+=f[i-1][k][1];
        }
}

int main()
{
    init();
    scanf("%d", &T);
    while(T--)
    {
        int pos1, pos2;
        memset(vis, 0, sizeof(vis));
        scanf("%d%lld", &n, &c);

        for(int i=1; i<=n; i++)
        {
            if(f[n][i][1]>=c) {pos1=i, pos2=1; break;}
            else c-=f[n][i][1];
            if(f[n][i][0]>=c) {pos1=i, pos2=0; break;}
            else c-=f[n][i][0];
        }
        printf("%d ", pos1);
        vis[pos1]=1;

        for(int i=n-1; i>=1; i--)
        {
            int rank=0; pos2^=1;
            for(int j=1; j<=n; j++)
            {
                if(vis[j]) continue;
                rank++;
                if((pos2==0 && j>=pos1) || (pos2==1 && j<=pos1)) continue;
                if(f[i][rank][pos2]>=c)  {pos1=j; break;}
                else c-=f[i][rank][pos2];
            }
            printf("%d ", pos1);
            vis[pos1]=1;
        }
        printf("\n");
    }
}

Posted on Edited on In

问题描述：

问你包含$n$个节点的无向联通图有多少个，其中节点的编号为$1-n$

输入：

有多组数据，输入以0结束 每组数据一个整数$n$表示有$n$个节点（$n<=50$）

输出：

每组数据一行，表示有$n$个节点的无向联通图的个数

思路：

计数类DP好难啊。。。根本想不到。。。

我们设$f[i]$为：包含$i$个节点的无向联通图的个数，那么答案就是$f[n]$。然后这个可以等价为所有无向图总数-无向不联通图的个数。无向图总数很容易求，为$2^{n*(n-1)/2}$，而无向不联通图的个数可以通过DP得到。

假设我们推出了$f[1]$到$f[i-1]$，我们现在要求包含$i$个节点的无向不联通图个数。我们设1号节点所在的联通大小为$j$，那么这个联通块就有$C_{i-1}^{j-1}$种选择节点的方案，对于每一种选择方案，联通块有$f[j]$种构成方法，并且联通块之外的点是可以任意连边的的，所以有$2^{(i-j)*(i-j-1)/2}*f[j]$种情况。于是最后我们可以得出转移方程：

最后也是最最毒瘤的一点就是这道题要用高精！！！

代码：

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
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <string>
#define MAXN 2505
#define LL long long
using namespace std;

int n;
string f[MAXN], pow[MAXN];

string add(string x, string y)
{
    string ans;
    int lenx=x.length(), leny=y.length();
    int numx[500]={0}, numy[500]={0};
    for(int i=0; i<lenx; i++) numx[lenx-i-1]=x[i]-'0';
    for(int i=0; i<leny; i++) numy[leny-i-1]=y[i]-'0';
    int maxl=max(lenx, leny);
    for(int i=0; i<maxl; i++)
    {
        numx[i]+=numy[i];
        numx[i+1]+=numx[i]/10, numx[i]%=10;
    }
    if(numx[maxl]) maxl++;
    for(int i=maxl-1; i>=0; i--) ans+=numx[i]+'0';
    return ans;
}

string sub(string x, string y)
{
    string ans;
    int lenx=x.length(), leny=y.length();
    int numx[500]={0}, numy[500]={0};
    for(int i=0; i<lenx; i++) numx[lenx-i-1]=x[i]-'0';
    for(int i=0; i<leny; i++) numy[leny-i-1]=y[i]-'0';
    int maxl=max(lenx, leny);
    for(int i=0; i<maxl; i++)
    {
        numx[i]-=numy[i];
        if(numx[i]<0) numx[i]+=10, numx[i+1]--;
    }
    while(numx[--maxl]==0 && maxl>0) ;
    for(int i=maxl; i>=0; i--) ans+=numx[i]+'0';
    return ans;

}

string mul(string x, string y)
{
    string ans;
    int numx[500]={0}, numy[500]={0}, numz[500]={0};
    int lenx=x.length(), leny=y.length();
    for(int i=0; i<lenx; i++) numx[lenx-i-1]=x[i]-'0';
    for(int i=0; i<leny; i++) numy[leny-i-1]=y[i]-'0';
    int maxlen=lenx+leny-1;
    for(int i=0; i<lenx; i++)
        for(int j=0; j<leny; j++) numz[i+j]+=numx[i]*numy[j];
    for(int i=0; i<maxlen; i++) numz[i+1]+=numz[i]/10, numz[i]%=10;
    if(numz[maxlen]) maxlen++;
    for(int i=maxlen-1; i>=0; i--) ans+=numz[i]+'0';
    return ans;
}

string div(string x, LL b)
{
    string ans;
    int lenx=x.length(), d=0;
    for(int i=0; i<lenx; i++)
    {
        ans+=(d*10+x[i]-'0')/b+'0';
        d=(d*10+(x[i]-'0'))%b;
    }
    for(int i=0; i<ans.size(); i++)
        if(ans[i]!='0') return ans.substr(i);
    return "0";
}

string change(LL x)
{
    string ans;
    int numx[500], lenx=0;
    while(x)
    {
        numx[lenx++]=x%10;
        x/=10;
    }
    for(int i=lenx-1; i>=0; i--) ans+=numx[i]+'0';
    return ans;
}

string comb(LL n, LL m)
{
    string sum="1";
    for(LL i=m+1; i<=n; i++) sum=mul(sum, change(i));
    for(LL i=1; i<=n-m; i++) sum=div(sum, i);
    return sum;
}

int main()
{
    pow[0]="1";
    for(int i=1; i<=1500; i++) pow[i]=mul(pow[i-1], change(2));
    for(int i=1; i<=50; i++)
    {
        f[i]=pow[i*(i-1)/2];
        for(int j=1; j<i; j++)
        {
            string temp="";
            temp=mul(mul(comb(i-1, j-1), f[j]), pow[(i-j)*(i-j-1)/2]);
            f[i]=sub(f[i], temp);
        }
    }
    while(scanf("%d", &n) && n) cout<<f[n]<<'\n';
}

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);
}