Dylan's Blog
0%

Posted on Edited on In

8月12日 2018百度之星初赛 (B) 题目链接：http://bestcoder.hdu.edu.cn/contests/contest_show.php?cid=826

1001 - degree

思路： 一道比较简单的结论题吧。。。我们贪心地找出一个度数最多的点，当不考虑K时，我们可以将其他的联通块都接在这个点上。当我们考虑K时，我们就可以从联通块上拆下K个点，再接到度数最多的点上，注意一下有没有K个点够拆就好了。

代码：

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
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#define INF 0x3f3f3f3f3f
using namespace std;

int T, n, m, k, deg[200005];

int main()
{
    scanf("%d", &T);
    while(T--)
    {
        int maxd=0;
        memset(deg, 0, sizeof(deg));
        scanf("%d%d%d", &n, &m, &k);
        for(int i=1; i<=m; i++)
        {
            int x, y;
            scanf("%d%d", &x, &y);
            deg[x]++, deg[y]++;
            maxd=max(maxd, max(deg[x], deg[y]));
        }
        if(k>m-maxd) printf("%d\n", n-1);
        else printf("%d\n", n-m+maxd+k-1);
    }
}

1003 - odds

思路： 特别好的一道题吧。。。

我们可以把每个叶子节点到根的路径提出来，这样问题可以简化为：一个路径上有K条边，分别有权值$x_1, y_1, x_2, y_2····x_k,y_k$，其中$y_i>=x_i$的。你需要从中选$x$条边取$y_i$，其余边取$x_i$，使这些的乘积最大。根据题目要求，求这个的复杂度应该要在$O(nlogn)$以内的。

于是我们可以想到一个贪心的方法，对于这$K$条边，我们选其中$y_i*x_i$最大的x条边取$y_i$，其余的取$x_i$。证明也很简单：假如已经处理出了前$i-1$条边（$i$是应该大于$x$的，否则直接取$y_i$）乘积为$w$。我们考虑第$i$条边：如果第$i$条边取$x_i$，那么乘积为$w*x_i$；如果取$y_i$，那么我们就需要从前$x$条取$y$边中，选出一条边$j$，让它值变为$x_j$，这样乘积就为$w_i*y_i*(x_j/y_j)$。不难看出我们希望乘积尽可能大，那么就需要选$y_i*x_i$尽可能大的边。

有了这个贪心策略后，实现就不难了。用一个multiset动态维护路径上$y_i*x_i$前$x$大的边，同时计算出答案，回溯时要将答案和multiset复原。注意，千万不能对于每一个叶子节点都重新算一遍答案，我比赛时就是这样SB的都算一遍，然后T飞了，比完赛才反应过来。

代码：

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
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <queue>
#include <set>
#define MAXN 200005
#define p 1000000007
#define LL long long
using namespace std;

int T, n, k, cnt, head[MAXN];
LL ans[MAXN], inv[MAXN];

struct Edge {int next, to, dis;} edge[MAXN];
struct Node
{
    LL x, y;
    bool friend operator < (Node a, Node b)
    {
        return a.y*b.x<b.y*a.x;
    }
} node[MAXN];

multiset<Node> st;
multiset<Node>::iterator it;

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

void dfs(int x, LL val)
{
    int maxd=-1;
    for(int i=head[x]; i; i=edge[i].next) maxd=max(maxd, edge[i].dis);
    if(maxd==-1) ans[x]=val;
    for(int i=head[x]; i; i=edge[i].next)
    {
        node[i].x=edge[i].dis;
        node[i].y=maxd;
        Node top= *st.begin();
        LL tag=0, temp=val;
        if(st.size()<k)
        {
            tag=1;
            st.insert(node[i]);
            temp=temp*inv[200000]%p*node[i].y%p;
        }
        else if(top<node[i])
        {
            tag=2;
            st.erase(st.begin());
            st.insert(node[i]);
            temp=temp*inv[top.y]%p*top.x%p;
            temp=temp*inv[200000]%p*node[i].y%p;
        }
        else temp=temp*inv[200000]%p*node[i].x%p;
        dfs(edge[i].to, temp);
        if(tag==1)
        {
            it=st.lower_bound(node[i]);
            st.erase(it);
        }
        if(tag==2)
        {
            it=st.lower_bound(node[i]);
            st.erase(it);
            st.insert(top);
        }
    }
}

int main()
{
    inv[0]=inv[1]=1;
    for(int i=2; i<=200000; i++) inv[i]=inv[p%i]*(p-p/i)%p;
    scanf("%d", &T);
    while(T--)
    {
        cnt=0;
        memset(head, 0, sizeof(head));
        memset(ans, -1, sizeof(ans));
        scanf("%d%d", &n, &k);
        for(int i=1; i<n; i++)
        {
            int x, y, z;
            scanf("%d%d%d", &x, &y, &z);
            x++, y++;
            addedge(x, y, z);
        }
        dfs(1, 1);
        for(int i=1; i<=n; i++) if(ans[i]!=-1) printf("%lld\n", ans[i]);
    }
}

1004 - p1m2

思路： 二分应该能够很容易的看出来，对于二分值大的就计算一下正的贡献，小于二分值的计算负的贡献，判断正负贡献是否大于0。

代码：

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
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#define INF 0x3f3f3f3f3f
#define LL long long
using namespace std;

int T, n, x[300005], y[300005];

bool check(int mid)
{
    LL res=0;
    memcpy(y, x, sizeof(x));
    for(int i=1; i<=n; i++)
    {
        if(y[i]>mid+1) res+=(y[i]-mid)/2;
        if(y[i]<mid) res-=(mid-y[i]);
    }
    return res>=0;
}

int main()
{
    scanf("%d", &T);
    while(T--)
    {
        int ans=0;
        scanf("%d", &n);
        for(int i=1; i<=n; i++) scanf("%d", &x[i]);
        int l=0, r=1e8;
        while(l<=r)
        {
            int mid=(l+r)/2;
            if(check(mid)) ans=mid, l=mid+1;
            else r=mid-1;
        }
        printf("%d\n", ans);
    }
}

1006 - rect

思路： 题目有一句比较重要的话就是$x_i,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
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#define INF 0x3f3f3f3f3f
#define LL long long
using namespace std;

int T, n, m, k, deg[200005];

int main()
{
    scanf("%d", &T);
    while(T--)
    {
        int w, h, x, y;
        LL ans=0;
        scanf("%d%d%d", &w, &h, &n);
        for(int i=1; i<=n; i++)
        {
            scanf("%d%d", &x, &y);
            ans+=min(min(x, y), min(w-x, h-y));
        }
        printf("%lld\n", ans);
    }
}

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