Dylan's Blog
0%

Posted on Edited on In

7月26日 Educational Codeforces Round 47 题目链接：http://codeforces.com/contest/1009

A - Game Shopping & B - Minimum Ternary String

简单，不讲。。。

C - Annoying Present

思路： 其实也比较水。。。首先参数$x$对答案的贡献是不会变的，根据一些小学数学知识可以知道：当$d$为正时，选取的位置越靠边贡献越大；当$d$为负时，选取的位置越靠中间贡献越大。因此分类讨论一下就好了。

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include <bits/stdc++.h>
#define LL long long
using namespace std;

LL ans, n, m, x, d;;

int main()
{
    scanf("%lld%lld", &n, &m);
    for(int i=1; i<=m; i++)
    {
        scanf("%lld%lld", &x, &d);
        ans+=n*x;
        if(d>0) ans+=(n-1)*n/2*d;
        else
        {
            if(n&1) ans+=(n/2)*(n/2+1)*d;
            else ans+=n*n/4*d;
        }
    }
    printf("%lf\n", (double)ans/n);
}

D - Relatively Prime Graph

思路： 虽然是构造一张图，其实和图论没有什么关系。。。

看懂题意以后可以发现你就是要在$1-n$内找出$m$对互素的数，于是可以暴力枚举，知道枚举出$m$对数。因为这是实在是太暴力了，比赛时还在怀疑算法不够优秀。其实互质数对的分布是玄学的，所以一般是不好卡你暴力的，再加上CF的神机，放心的打就好了。（实测46ms) 代码：

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

int n, m, cnt;
pair<int, int> ans[100005];

int gcd(int x, int y) {return y==0 ? x : gcd(y, x%y);}

void solve()
{
    for(int i=1; i<=n; i++)
    {
        for(int j=i+1; j<=n; j++)
            if(gcd(i, j)==1)
            {
                ans[++cnt].first=i; ans[cnt].second=j;
                if(cnt==m) return;
            }
    }
}

int main()
{
    scanf("%d%d", &n, &m);
    if(m<n-1)
    {
        printf("Impossible\n");
        return 0;
    }
    solve();
    if(cnt<m) printf("Impossible\n");
    else
    {
        printf("Possible\n");
        for(int i=1; i<=m; i++) printf("%d %d\n", ans[i].first, ans[i].second);
    }
}

E - Intercity Travelling

思路： 一看题目，哇，和JXOI的风格好像的QVQ，都是小清新的期望计数题。虽然是期望，不过同样是套了期望的说法的一些计数类问题。

首先想到$n^2$的暴力DP，先处理前缀和。设$g[i]$为有多少种方法到达$i$点，$f$就是答案所求的东西，那么DP的方法就如下面代码所示：

1
2
3
4
5
6
7
8
9
10
11
12
g[0]=1;
for(int i=1; i<=n; i++)
{
    scanf("%lld", &a[i]);
    a[i]=(a[i]+a[i-1])%p;
}
for(int i=1; i<=n; i++)
    for(int j=0; j<i; j++)
    {
        f[i]=(f[i]+f[j]+a[i-j]*g[j])%p;
        g[i]=(g[i]+g[j])%p;
    }

然后我们打表发现$g[i]$就是$2^{i-1}$，又发现$f[i]$只由$a$中的元素组成，且组成方法与$a$中元素的值无关。于是再次打表，打出$f[i]$由$a$中的元素怎么构成，于是发现其中$h[n+1-i]$为构成$f[n]$(即答案)中$a[i]$的系数。即： 代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include <bits/stdc++.h>
#define LL long long
#define MAXN 1000006
#define p 998244353
using namespace std;

LL n, ans, h[MAXN], g[MAXN], a[MAXN], sum[MAXN];

int main()
{
    scanf("%lld", &n);
    g[1]=g[0]=1;
    for(int i=2; i<=n; i++) g[i]=(g[i-1]*2)%p;
    for(int i=1; i<=n; i++) scanf("%lld", &a[i]), a[i]=(a[i]+a[i-1])%p;

    for(int i=1; i<=n; i++)
    {
        h[i]=(sum[i-1]+g[i-1])%p;
        sum[i]=(sum[i-1]+h[i])%p;
    }
    for(int i=1; i<=n; i++) ans=(a[i]*h[n-i+1]+ans)%p;
    printf("%lld\n", ans%p);
}

F - Dominant Indices

思路： 一直没有学树上启发式合并。膜题解发现要用这种操作，于是学了一下。个人理解就是遍历每个节点，然后从每个节点再开始另一个搜索，处理出该节点子树的信息，这样显然最坏是$O(N^2)$的。然而我们可以从先遍历节点，回溯时保留父亲节点重儿子的信息，这样从父亲节点开始的另一个搜索就可以不用搜重儿子。于是我们保证了时间复杂度在$O(logn)$。

这道题也是类似，要求子树重节点最多的那一层，于是就按照启发式合并去做就好了。 代码：

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

int n, cnt, maxnum, maxans, siz[MAXN], head[MAXN], dep[MAXN], ans[MAXN], num[MAXN], tag[MAXN];

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

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

void dfs1(int x, int fa)
{
    siz[x]=1;
    for(int i=head[x]; i; i=edge[i].next)
    {
        int to=edge[i].to;
        if(to==fa) continue;
        dep[to]=dep[x]+1;
        dfs1(to, x);
        siz[x]+=siz[to];
    }
}

void update(int x)
{
    if(num[dep[x]]>maxnum) maxnum=num[dep[x]], maxans=dep[x];
    if(num[dep[x]]==maxnum && dep[x]<maxans) maxans=dep[x];
}

void add(int x, int fa, int op)
{
    num[dep[x]]+=op;
    update(x);
    for(int i=head[x]; i; i=edge[i].next)
    {
        int to=edge[i].to;
        if(to==fa) continue;
        add(to, x, op);
    }
}

void dfs2(int x, int fa, int keep)
{
    int maxson=-1, maxsize=0;
    for(int i=head[x]; i; i=edge[i].next)
    {
        int to=edge[i].to;
        if(to==fa) continue;
        if(siz[to]>maxsize) maxson=to, maxsize=siz[to];
    }

    for(int i=head[x]; i; i=edge[i].next)
    {
        int to=edge[i].to;
        if(to==fa || to==maxson) continue;
        dfs2(to, x, 0);
    }
    if(maxson!=-1) dfs2(maxson, x, 1);

    num[dep[x]]++;
    update(x);
    for(int i=head[x]; i; i=edge[i].next)
    {
        int to=edge[i].to;
        if(to==fa || to==maxson) continue;
        add(to, x, 1);
    }
    ans[x]=maxans;

    if(keep==0)
    {
        num[dep[x]]--;
        update(x);
        for(int i=head[x]; i; i=edge[i].next)
        {
            int to=edge[i].to;
            if(to==fa) continue;
            add(to, x, -1);
        }
        maxnum=maxans=0;
    }
}

int main()
{
    scanf("%d", &n);
    for(int i=1; i<n; i++)
    {
        int x, y;
        scanf("%d%d", &x, &y);  
        addedge(x, y);
        addedge(y, x);
    }
    dfs1(1, 0);
    dfs2(1, 0, 1);
    for(int i=1; i<=n; i++) printf("%d\n", ans[i]-dep[i]);
}

Posted on Edited on In

问题描述：

有一个球形空间产生器能够在$n$维空间中产生一个坚硬的球体。现在，你被困在了这个$n$维球体中，你只知道球面上$n+1$个点的坐标，你需要以最快的速度确定这个$n$维球体的球心坐标，以便于摧毁这个球形空间产生器。

输入：

第一行是一个整数$n(1<=N=10)$。接下来的$n+1$行，每行有$n$个实数，表示球面上一点的$n$维坐标。每一个实数精确到小数点后6位，且其绝对值都不超过20000。

输出：

有且只有一行，依次给出球心的$n$维坐标，两个实数之间用一个空格隔开。每个实数精确到小数点后3位。数据保证有解。

思路：

这应该是比较裸的高斯消元了。球心到$n+1$个点距离相等，那么我们把距离当作常量就有$n+1$个方程。把常量减去后就剩下$n$个方程$n$个未知数，这时我们就可以用高斯消元了。

方程我就不列出来了(懒)，然后因为方程保证有解，所以代码还是比较容易打的。

代码：

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
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <map>
#define MAXN 20
#define eps 1e-8
using namespace std;

int n;
double a[MAXN][MAXN], b[MAXN], c[MAXN][MAXN];

int main()
{
    scanf("%d", &n);
    for(int i=1; i<=n+1; i++)
        for(int j=1; j<=n; j++) scanf("%lf", &a[i][j]);
    for(int i=1; i<=n; i++)
        for(int j=1; j<=n; j++)
        {
            c[i][j]=2*(a[i][j]-a[i+1][j]);
            b[i]+=a[i][j]*a[i][j]-a[i+1][j]*a[i+1][j];
        }

    for(int i=1; i<=n; i++)
    {
        for(int j=i; j<=n; j++)
            if(fabs(c[j][i])>eps)
            {
                for(int k=1; k<=n; k++) swap(c[i][k], c[j][k]);
                swap(b[i], b[j]);
            }
        for(int j=1; j<=n; j++)
            if(i!=j)
            {
                double rate=c[j][i]/c[i][i];
                for(int k=i; k<=n; k++) c[j][k]-=c[i][k]*rate;
                b[j]-=b[i]*rate;
            }
    }
    for(int i=1; i<n; i++) printf("%.3lf ", b[i]/c[i][i]);
    printf("%.3lf\n", b[n]/c[n][n]);
}

Posted on Edited on In

问题描述：

石头游戏在一个n行m列的方格阵上进行。每个格子对应了一个编号在0~9之间的操作序列。操作序列是一个长度不超过6且循环执行、每秒执行一个字符的字符串。它包括： 1. 数字0~9：拿0~9个石头到该格子。 2. NWSE：把这个格子内所有的石头推到相邻的格子。 3. D：拿走这个格子的石头。

石头游戏的问题是：当这个石头游戏进行了t秒之后，所有方格中最多的格子有多少个石头。

输入：

第一行三个整数n, m, t, act。 接下来n行，每行m个字符，表示每个格子对应的操作序列。 最后act行，每行一个字符串，表示从0开始的每个操作序列。

输出：

一个整数：游戏进行了t秒之后，所有方格中最多的格子有多少个石头。

思路：

这种矩阵加速递推的题重点是建模和构造矩阵。好有趣啊。。

我们可以将方格阵的两位压到一维上，那么状态矩阵$f$就是一个$1*nm$的矩阵。因为操作序列的长度不超过6，所以操作最多60次一个循环，因此我们可以对于每一次设计一个转移矩阵。然后转移矩阵$a$的构造方法是： 1. 如果位置$i,j$的操作为”WENS”，那么我们就令$a[pos(i,j)][pos(i’,j’)]=1$。其中$i’,j’$为操作的对应位置。 2. 如果位置$i,j$的操作为数字$x$，那么我们就令$a[0][pos(i,j)]=x$。 3. 另外我们要保证$a[0][0]=1$

这样我们就是把状态矩阵$f[0]$当成了石头来源，$a[0][0]=1$保证了$f[0]=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
65
66
67
68
69
70
71
72
73
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#define MAXN 100
#define LL long long
#define pos(i, j) (i-1)*m+j
using namespace std;

int n, m, t, act, len[MAXN], op[MAXN][MAXN];
LL maxn, ans[MAXN][MAXN], a[MAXN][MAXN][MAXN], b[MAXN][MAXN];
char opt[MAXN][MAXN];

void init()
{
    ans[0][0]=1;
    for(int i=0; i<=pos(n, m); i++) b[i][i]=1;
    for(int i=0; i<60; i++) a[i][0][0]=1;
}

void mul(LL x[MAXN][MAXN], LL y[MAXN][MAXN])
{
    LL c[MAXN][MAXN];
    memset(c, 0, sizeof(c));
    for(int i=0; i<=n*m; i++)
        for(int j=0; j<=n*m; j++)
            for(int k=0; k<=n*m; k++) c[i][j]+=x[i][k]*y[k][j];
    memcpy(x, c, sizeof(c));
}

void ksm(int y)
{
    while(y)
    {
        if(y&1) mul(ans, b);
        mul(b, b); y>>=1;
    }
}

int main()
{
    scanf("%d%d%d%d", &n, &m, &t, &act);
    init();
    for(int i=1; i<=n; i++)
        for(int j=1; j<=m; j++) scanf("%1d", &op[i][j]);
    for(int i=0; i<act; i++)
    {
        scanf("%s", opt[i]);
        len[i]=strlen(opt[i]);
    }
    for(int k=0; k<60; k++)
    {
        for(int i=1; i<=n; i++)
            for(int j=1; j<=m; j++)
            {
                char act=opt[op[i][j]][k%len[op[i][j]]];
                if(act=='E' && j<m) a[k][pos(i, j)][pos(i, j+1)]=1;
                if(act=='N' && i>1) a[k][pos(i, j)][pos(i-1, j)]=1;
                if(act=='W' && j>1) a[k][pos(i, j)][pos(i, j-1)]=1;
                if(act=='S' && i<n) a[k][pos(i, j)][pos(i+1, j)]=1;
                if(act>='0' && act<='9')
                {
                    a[k][pos(i, j)][pos(i, j)]=1;
                    a[k][0][pos(i, j)]=act-'0';
                }
            } 
        mul(b, a[k]);
    }
    ksm(t/60);
    for(int i=0; i<t%60; i++) mul(ans, a[i]);
    for(int i=1; i<=n*m; i++) maxn=max(maxn, ans[0][i]);
    printf("%lld\n", maxn);
}

Posted on Edited on In

问题描述：

你需要求出$A^B$的所有约数之和。

输入：

只有两个数A，B $(1<=A,B<=5*10^7)$

输出：

一个数，约数之和($mod 9901$)

思路：

一开始不知道算术基本定理时看得比较懵逼。。。后面才发现是傻逼题。。

首先任何大于1的正整数$N$都可以分解成$ N =p_1^{c_1}p_2^{c_2}p_3^{c_3}···p_m^{c_m} $的形式，其中$c_i$为正整数，$p_1<p_2<p_3<···<p_m$且$p_i$均为质数。根据这个我们可以有个推论就是$N$的正约数之和为$ \prod_{i=1}^m (\sum_{j=0}^{c_i} p_i ^j) $。

这样就很容易得得出这题的答案:$ ans= \prod_{i=1}^m (\sum_{j=0}^{c_i*B} p_i ^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
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cmath>
#define MAXN 1000005
#define mod 9901
#define LL long long
using namespace std;

LL a, b, c[MAXN][2], ans=1, cnt;

void div(LL num)
{
    for(int i=2; i*i<=num; i++)
        if(num%i==0)
        {
            c[++cnt][0]=i;
            while(num%i==0) c[cnt][1]++, num/=i;
        }
    if(num!=1) c[++cnt][0]=num, c[cnt][1]=1;
}

LL ksm(LL x, LL y)
{
    LL ans=1;
    while(y)
    {
        if(y&1) ans=(x*ans)%mod;
        x=(x*x)%mod; y>>=1;
    }
    return ans;
}

LL sum(LL x, LL y)
{
    if(y==0) return 1;
    if(y&1) return (1+ksm(x, y/2+1))*sum(x, y/2)%mod;
    else return ((1+ksm(x, y/2+1))*sum(x, y/2-1)+ksm(x, y/2))%mod;
}

int main()
{
    while(scanf("%lld%lld", &a, &b)!=EOF)
    {
        div(a);
        for(int i=1; i<=cnt; i++) ans=sum(c[i][0], c[i][1]*b)*ans%mod;
        printf("%lld\n", ans);
    }
}

Posted on Edited on In

问题描述：

给你一组形如下图的方程组： EXCRT

你需要解出最小的$x$。

输入：

有多组数据，每组数据以$n$开始，表示有$n$个方程组 接下来n行分别表示$a_1$，$m_i$

输出：

输出最小的$x$

思路：

这就是扩展中国剩余定理的模板题了。如果$m_i$都两两互质，那么就是直接中国剩余定理就好了。但这里$m_i$是随机的，所以要用到一些其他的处理手法。

这里我们可以先用扩展欧几里得求出第一组方程：$x+y*m_1=a_1$。这样，我们得到了一组通解$x=x_0+t*m_1$。我们利用这组通解带入第二组方程，得到：变形为：于是我们得到了另一个线性同余方程，并且可以解出$t$的通解。利用这个通解又可以代入下一个方程。于是我们可以这样推出整个方程的解。

用数学归纳法再严谨地说一遍做法：设已经求出了$k$组方程，$ m_0= \prod_{i=1}^{k} m_i$，前$k$组方程的通解为$x=x_0+t*m_0$。那么我们可以将通解代入第$k+1$组方程中，得到 再利用扩展欧几里得解出新方程的通解。于是，我们可以利用$n$次扩展欧几里得解出计算出答案。

代码：

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

LL n, a[10000005], r[10000005];

LL exgcd(LL a, LL b, LL &x, LL &y)
{
    if(b==0)
    {
        x=1; y=0;
        return a;
    }
    LL d=exgcd(b, a%b, x, y);
    LL z=x; x=y; y=z-y*(a/b);
    return d;
}

LL solve()
{
    LL x=0, y=0, x0=0, m0=1;
    for(int i=1; i<=n; i++)
    {
        LL d=exgcd(m0, a[i], x, y);
        if((r[i]-x0)%d) return -1;
        x=(r[i]-x0)/d*x%a[i];
        x0=(x0+x*m0)%(m0/d*a[i]);
        m0=m0/d*a[i];
    }
    return (x0+m0)%m0;
}

int main()
{
    while(scanf("%lld", &n)!=EOF)
    {
        for(int i=1; i<=n; i++) scanf("%lld%lld", &a[i], &r[i]);
        printf("%lld\n", solve());
    }
}