Dylan's Blog
0%

Posted on Edited on In

问题描述

给你 $n$ 个盒子，第 $i$ 个盒子中有 $a_i$ 枝花，同一盒子内花颜色相同，不同盒子内花颜色不同，你需要从中选出 $s$ 枝花，问你有多少中不同的方案。

输入

第一行两个数$n$，$s$ ($n \leq 20, s \leq 10^{14}$) 第二行 $n$ 个数，第 $i$ 个数表示 $a_i$ ($a_i \leq 10^{12}$)

输出

输出方案数对 $1000000007$ 取模的值

思路

这个就是多重集的组合数，当 $\forall a_i$ 都 $a_i>s$ 时根据「插板法」可以知道答案是 ${s+n-1} \choose {n-1}$。但当 $s$ 较大时，会有 $s>a_i$ 的情况出现，这时可以比较自然地想到利用容斥原理计算合法的方案数。我们可以枚举出现这种情况的集合 $S$，然后套上容斥，最终的答案就是：

需要注意的是计算组合数时，要用 Lucas 定理对组合数取模，防止爆 longlong。

对于这种组合问题，也可以从生成函数的角度去看，可以推出和上面一样的式子。我们将它的生成函数写出来：

然后利用等比数列求和公式化简为：

将原式后半部分泰勒展开：

这个式子的第 $x^s$ 项的系数就是我们要的答案。对于后半部分，它又是一个生成函数，根据它的组合意义我们同样根据「插板法」可以知道 $x^s$ 的系数是 ${s+n-1} \choose {n-1}$。而前半部分，我们可以将这 $n$ 项暴力拆分，并分别计算它对 $x^s$ 项系数的贡献。将这些加起来，就刚好与用容斥原理推出的式子一样。

代码

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
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <queue>
#include <vector>
#include <map>
#include <set>
#define MAXN 25
#define P 1000000007
#define INF 0x3f3f3f3f
#define rint register int
#define LL long long
#define LD long double
using namespace std;

int n, ans, inv[MAXN];
LL s, a[MAXN];

int comb(int x, int y)
{
    if(x<y) return 0;
    int ans=1;
    for(rint i=0; i<y; ++i)
    {
        ans=1LL*ans*(x-i)%P;
        ans=1LL*ans*inv[i+1]%P;
    }
    return ans;
}

int main()
{
    scanf("%d%lld", &n, &s);
    for(rint i=0; i<n; ++i) scanf("%lld", &a[i]);
    inv[0]=inv[1]=1;
    for(rint i=2; i<=n; ++i) inv[i]=1LL*inv[P%i]*(P-P/i)%P;
    for(rint sta=0; sta<(1<<n); ++sta)
    {
        LL num=s, cnt=0;;
        for(rint i=0; i<n; ++i)
            if((sta>>i)&1)
            {
                cnt++;
                num-=(a[i]+1);
            }
        if(cnt&1) ans=(ans-comb((num+n-1)%P, n-1)+P)%P;
        else ans=(ans+comb((num+n-1)%P, n-1))%P;
    }
    printf("%d\n", ans);
    return 0;
}

Posted on Edited on In

8月3日 Codeforces Round #501 题目链接：http://codeforces.com/contest/1015

A - Points in Segments & B - Obtaining the String

比较水，不说了。。。

C - Songs Compression

思路： 很显然是一个贪心，按照能够压缩的大小排个序，能够选的就尽量选。然后就好了。

代码：

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
#include <bits/stdc++.h>
#define LL long long
using namespace std;

int n, m;
LL tot;

struct A {int x, y;} a[1000005];

bool CMP(A x, A y) {return x.x-x.y>y.x-y.y;}

int main()
{
    scanf("%d%d", &n, &m);
    for(int i=1; i<=n; i++) scanf("%d%d", &a[i].x, &a[i].y);
    sort(a+1, a+n+1, CMP);
    for(int i=1; i<=n; i++) tot+=a[i].x;
    if(tot<=m) {printf("0\n"); return 0;}
    for(int i=1; i<=n; i++)
    {
        tot-=(a[i].x-a[i].y);
        if(tot<=m) {printf("%d\n", i); return 0;}
        if(i==n) printf("-1\n");
    }
}

D - Walking Between Houses

思路： 蛮有趣的题，类似于构造吧。

我们设当前可以走$k$步，要走$s$距离，我们就以$(s+k-1)/k$为基准值，每一步走的距离都尽量靠近这个值（其实我也不清楚为什么是对的，只是觉得数据不好卡这个算法）。然后注意要特判两种为NO的情况。

代码：

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
#include <bits/stdc++.h>
#define LL long long
using namespace std;

LL n, k, s;
int ans[1000000], cnt;

void dfs(int pos, LL k, LL s)
{
    if(k==0 && s==0) return;
    LL dis=(s+k-1)/k;
    if(pos-dis>=1) pos=pos-dis;
    else if(pos+dis<=n) pos=pos+dis;
    else
    {
        LL t1=n-pos, t2=pos-1;
        if(t1>t2) pos=n, dis=t1;
        else pos=1, dis=t2;
    }
    ans[++cnt]=pos;
    dfs(pos, k-1, s-dis);
}

int main()
{
    scanf("%lld%lld%lld", &n, &k, &s);
    if(s>k*(n-1) || k>s) {printf("NO\n"); return 0;}
    printf("YES\n");
    dfs(1, k, s);
    for(int i=1; i<=cnt; i++) printf("%d ", ans[i]);
}

E1 - Stars Drawing (Easy Edition)

思路： 这个数据范围比较小，就是毒瘤模拟。。。我们枚举每个星星的中心，然后选尽可能大的，这个贪心比较显然。所以这个总复杂度为$O(N^3)$的。

代码：

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
#include <bits/stdc++.h>
#define LL long long
#define MAXN 1005
using namespace std;

int n, m, cnt, maxlen, x[MAXN*MAXN], y[MAXN*MAXN], z[MAXN*MAXN];
bool vis[MAXN][MAXN];
char mmp[MAXN][MAXN];

void check()
{
    for(int i=1; i<=n; i++)
        for(int j=1; j<=m; j++)
            if(mmp[i][j]=='*' && !vis[i][j]) {printf("-1\n"); exit(0);}
}

void find(int px, int py, int len)
{
    bool flag=1;
    if(px-len<1 || py-len<1 || px+len>n || py+len>m) return;
    for(int i=py; i<=py+len; i++) if(mmp[px][i]!='*') {flag=0; break;}
    for(int i=py; i>=py-len; i--) if(mmp[px][i]!='*') {flag=0; break;}
    for(int i=px; i<=px+len; i++) if(mmp[i][py]!='*') {flag=0; break;}
    for(int i=px; i>=px-len; i--) if(mmp[i][py]!='*') {flag=0; break;}
    if(flag) maxlen=len;
    find(px, py, len+1);
}

int main()
{
    scanf("%d%d", &n, &m);
    for(int i=1; i<=n; i++) scanf("%s", mmp[i]+1);
    for(int px=1; px<=n; px++)
        for(int py=1; py<=m; py++)
        {
            maxlen=0;
            find(px, py, 1);
            if(maxlen)
            {
                x[++cnt]=px; y[cnt]=py; z[cnt]=maxlen;
                for(int i=py; i<=py+maxlen; i++) vis[px][i]=1;
                for(int i=py; i>=py-maxlen; i--) vis[px][i]=1;
                for(int i=px; i<=px+maxlen; i++) vis[i][py]=1;
                for(int i=px; i>=px-maxlen; i--) vis[i][py]=1;
            }
        }
    check();
    printf("%d\n", cnt);
    for(int i=1; i<=cnt; i++) printf("%d %d %d\n", x[i], y[i], z[i]);
}

E2 - Stars Drawing (Hard Edition)

思路： 这里可以用一个常规的优化，就是用$O(N^2)$的预处理，$O(N^2)$计算，答案来代替$O(N^3)$的普通算法。

不过预处理和计算都比较的巧妙。可以利用类似DP的方法算出每个位置上下左右有多少个连续的‘*’，那么星星最大的大小就是它们的最小值，于是预处理就是$O(N^2)$。

计算每个位置有没有星星覆盖可以利用前缀和的思想，对于位置在$x,y$且大小为$l$的星星，我们可以在$(x-l, y)$处打上$+1$的标记，在$(x+l+1, y)$打上$-1$的标记。类似的，也可以在$(x, y-l)$打上$+1$，$(x, y+l+1)$打上$-1$的标记。最后再扫一遍就可以确定星星的覆盖情况。

代码：

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

int n, m, up[MAXN][MAXN], down[MAXN][MAXN], left[MAXN][MAXN], right[MAXN][MAXN];
int cnt, tag1[MAXN][MAXN], tag2[MAXN][MAXN], x[MAXN*MAXN], y[MAXN*MAXN], z[MAXN*MAXN];
char mp[MAXN][MAXN];

int main()
{
    scanf("%d%d", &n, &m);
    for(int i=1; i<=n; i++) scanf("%s", mp[i]+1);
    for(int i=1; i<=n; i++)
        for(int j=1; j<=m; j++)
        {
            if(mp[i][j]=='*') up[i][j]=up[i-1][j]+1;
            if(mp[i][j]=='*') left[i][j]=left[i][j-1]+1;
        }
    for(int i=n; i>=1; i--)
        for(int j=m; j>=1; j--)
        {
            if(mp[i][j]=='*') down[i][j]=down[i+1][j]+1;
            if(mp[i][j]=='*') right[i][j]=right[i][j+1]+1;
        }
    for(int i=1; i<=n; i++)
        for(int j=1; j<=m; j++)
        {
            int l=min(min(up[i][j], down[i][j]), min(left[i][j], right[i][j]))-1;
            if(l<=0) continue;
            tag1[i-l][j]++; tag1[i+l+1][j]--;
            tag2[i][j-l]++; tag2[i][j+l+1]--;
            x[++cnt]=i; y[cnt]=j; z[cnt]=l;
        }
    for(int i=1; i<=n; i++)
        for(int j=1; j<=m; j++)
        {
            tag1[i][j]+=tag1[i-1][j];
            tag2[i][j]+=tag2[i][j-1];
            if(mp[i][j]=='*' && tag1[i][j]==0 && tag2[i][j]==0)
            {
                printf("-1\n");
                return 0;
            }
        }
    printf("%d\n", cnt);
    for(int i=1; i<=cnt; i++) printf("%d %d %d\n", x[i], y[i], z[i]);
}

Posted on Edited on In

问题描述：

给出一个有向无环的连通图，起点为$1$终点为$N$，每条边都有一个长度。绿豆蛙从起点出发，走向终点。

到达每一个顶点时，如果有$K$条离开该点的道路，绿豆蛙可以选择任意一条道路离开该点，并且走向每条路的概率为 $1/K$ 。

现在绿豆蛙想知道，从起点走到终点的所经过的路径总长度期望是多少？

输入：

第一行: 两个整数 $N$,$M$，代表图中有$N$个点、$M$条边 第二行到第$1+M$行: 每行3个整数$a,b,c$，代表从$a$到$b$有一条长度为$c$的有向边

输出：

从起点到终点路径总长度的期望值，四舍五入保留两位小数

思路：

这个的期望按照套路应该反着求，所以我们反向建边，从终点开始进行概率DP。对于DAG上的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
#include <bits/stdc++.h>
#define MAXN 200005
#define LL long long
using namespace std;

int n, m, cnt, head[MAXN], deg[MAXN],temp[MAXN];
double dis[MAXN];

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

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


void topsort()
{
    queue<int> q;
    q.push(n);
    while(!q.empty())
    {
        int tot=0;
        int x=q.front(); q.pop();
        for(int i=head[x]; i; i=edge[i].next)
        {
            int to=edge[i].to;
            dis[to]+=(dis[x]+edge[i].dis)/temp[to];
            //printf("%d %d %lf %lf!!!\n", x, to, temp[to], dis[to]);
            if(deg[to]<=0) continue;
            deg[to]--;
            if(!deg[to]) q.push(to);
        }
    }
}

int main()
{
    scanf("%d%d", &n, &m);
    for(int i=1; i<=m; i++)
    {
        int x, y, z;
        scanf("%d%d%d", &x, &y, &z);
        addedge(y, x, z);
    }
    memcpy(temp, deg, sizeof(deg));
    topsort();
    printf("%.2lf\n", dis[1]);
}

Posted on Edited on In

问题描述：

在1~N这N个数中，等概率地选取两个数l、r，如果l>r，则交换l、r。把信号中的第l个数到第r个数取出来，构成一个数列P。

A部分对话的密码是数列P的xor和的数学期望，B部分对话的密码是数列P的and和的期望，C部分对话的密码是数列P的or和的期望。你需要求出A，B，C三部分对话的密码。

输入：

第一行一个正整数N 第二行N个自然数

输出：

一行三个实数，分别表示xor和、and和、or和的期望，四舍五入保留3位小数

思路：

比较考验思维的一道题呢。因为操作都是位运算，所以我们可以分别考虑每一位的期望值，从而计算出对答案的贡献。我们把这$n$个数的第$i$位拿出来存在数组$b$中，$b[k]$就是第$k$个数的第$i$位。

一共有$n^2$种情况，选出长度为1区间的概率为$1/n^2$，选出其余区间的概率为$2/n^2$。我们可以先统计长度为1区间对答案的贡献，再计算其余区间的贡献。因为有三种操作，所以我们要对每一种操作分别计算：

  1. and操作：这个比较简单，我们从左到右枚举右端点，用last记录上一次0的出现位置。那么以$r$为右端点and值为1的区间有$(r-last-1)$个，然后乘上概率，再求和就可以求出这这一位的期望了。

  2. or操作：这个和上一个类似也比较容易，用last记录上一次1的出现位置。如果位置$r$的数为1，就有$r-1$个区间or值为1；如果位置为$r$为0，就有$last$个区间为1，不要忘了乘上概率。

  3. xor操作：这个稍微复杂，我们先前缀异或一下，然后分别记录位置$r$前前缀异或值的数量记为$cnt[0],cnt[1]$。设位置$r$的前缀异或值为$c[r]$，那么xor值为1的区间就有$cnt[c[r]^1]$个。类似的，我们也可以算出期望。

最后，我们对每一位对期望就一个和就可以算出答案了。

代码：

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
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#define LL long long
#define INF 1e18
#define LB long double
#define MAXN 2000005
using namespace std;

int n, a[MAXN], b[MAXN], c[MAXN];
LL ans[4];

LL getxor()
{
    LL sum=0, cnt[2]={0};
    memcpy(c, b, sizeof(b));
    for(int i=1; i<=n; i++) sum+=c[i];
    for(int i=1; i<=n; i++)
    {
        c[i]^=c[i-1];
        sum+=2*cnt[c[i]^1];
        cnt[c[i-1]]++;
    }
    return sum;
}

LL getand()
{
    LL sum=0, last=0;
    for(int i=1; i<=n; i++) sum+=b[i];
    for(int i=1; i<=n; i++)
    {
        if(b[i]==0) last=i;
        else sum+=2*(i-last-1);
    }
    return sum;
}

LL getor()
{
    LL sum=0, last=0;
    for(int i=1; i<=n; i++) sum+=b[i];
    for(int i=1; i<=n; i++)
    {
        if(b[i]==0) sum+=2*last;
        else sum+=2*(i-1), last=i;
    }
    return sum;
}

int main()
{
    scanf("%d", &n);
    for(int i=1; i<=n; i++) scanf("%d", &a[i]);
    for(int i=0; i<=30; i++)
    {
        for(int j=1; j<=n; j++) b[j]=(a[j]>>i)&1;
        ans[1]+=getxor()*(1<<i);
        ans[2]+=getand()*(1<<i);
        ans[3]+=getor()*(1<<i);
    }
    printf("%.3Lf %.3Lf %.3Lf", (LB)ans[1]/(1LL*n*n), (LB)ans[2]/(1LL*n*n), (LB)ans[3]/(1LL*n*n));
}

Posted on Edited on In

问题描述：

考虑一个边权为非负整数的无向连通图，节点编号为$1$到$N$，试求出一条从 $1$号节点到$N$号节点的路径，使得路径上经过的边的权值的 XOR 和最大。

路径可以重复经过某些点或边，当一条边在路径中出现了多次时，其权值在计算 XOR 和时也要被计算相应多的次数。

输入：

第一行包含两个整数$N(n<=50000)$和$M(m<=100000)$，表示该无向图中点的数目与边的数目。 接下来$M$行描述$M$条边，每行三个整数$S_i,T_i,D_i$，表示$S_i$与$T_i$之间存在一条权值为$D_i$的无向边（图中可能有重边或自环）

输出：

仅包含一个整数，表示最大的 XOR 和

思路：

这种玄学的做法自然的想不到的啦。。。

首先异或路径有一个很有趣的地方就是你可以“瞬移”到任何地方，严谨的说就是你从$x$到$y$，再从$y$回到$x$这一段路径对答案的贡献为0。所以你从1到n的路径可以看成是：一条1到n的简单路径加上图中的一些环。形象的说就是你可以瞬移到环上一点绕一圈再瞬移回来。

如果只有一条1到n的路径，我们就可以直接利用线性基求出它们的最大异或和就好了。但如果有多条路径该如何维护？其实这也很简(xuan)单(xue)，随意选任意一条就好了！！因为这多条路径其实是构成了多个环的，如果你选了一条使答案更小路径，那么你再选这个路径构成的环就好了。那条小的路径走了两遍，相当于你走了另一条路径。所以你可以随意选一条路径，同样用线性基维护就好了。

代码：

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

int n, m, cnt, tot, head[MAXN];
LL ans, dis[MAXN], cir[MAXN], base[MAXN];
bool vis[MAXN];

struct Edge {int next, to; LL dis;} edge[MAXN*2];

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

void insert(LL x)
{
    for(int i=62; i>=0; i--)
    {
        if(!(x>>i)) continue;
        if(!base[i])  {base[i]=x; break;}
        x^=base[i];
    }
}

void dfs(int x)
{
    vis[x]=1;
    for(int i=head[x]; i; i=edge[i].next)
    {
        int to=edge[i].to;
        if(!vis[to])
        {
            dis[to]=dis[x]^edge[i].dis;
            dfs(to);
        }
        else insert(dis[to]^edge[i].dis^dis[x]);
    }
}

int main()
{
    scanf("%d%d", &n, &m);
    for(int i=1; i<=m; i++)
    {
        int x, y; LL z;
        scanf("%d%d%lld", &x, &y, &z);
        addedge(x, y, z);
        addedge(y, x, z);
    }
    dfs(1);
    ans=dis[n];
    for(int i=62; i>=0; i--)
        if((ans^base[i])>ans) ans=ans^base[i];
    printf("%lld\n", ans);
}