训练赛Day6-The 36th ACMICPC Asia Regional Beijing Site

训练赛Day6-The 36th ACM/ICPC Asia Regional Beijing Site

B - Eliminate Witches!

题目大意

【样例解释】

给你一个字符串：

walpurgis(charlotte(patricia,gertrud),elly,gisela)

如下图：

现在要你输出该树节点个数以及先序遍历，和遍历中的访问边的顺序。例如该样例输出如下：

6 
walpurgis 
charlotte 
patricia 
gertrud 
elly 
gisela 
1 2 
2 3 
3 2 
2 4 
4 2 
2 1 
1 5 
5 1 
1 6 
6 1

数据范围

多组输入T <= 20,每个字符串不超过50000个节点，且每个节点对应的字符串长度不超过10，所有输入字符串长度不超过1000000。

解题思路

暴力模拟，首先可以看出该树的先序遍历就是字符串的先后出现顺序，并且还可以发现树的节点个数就是字符串中’(‘的个数加’,’的个数在加一，也就是节点个数 = cnt[‘(‘] + cnt[‘,’] + 1。之后再暴力Dfs模拟先序遍历顺序以及回溯过程即可。

AC代码

#include<cstdio>
#include<cstring>
#include<cmath>
#include<cstdlib>
#include<algorithm>
#include<vector>
#include<map>
using namespace std;
const int maxn = 1000000;
int T, len, l, now, tot;
char s[maxn + 5];
char c[15];
vector<pair<int, int> >ans;
void solve() {
    int tot = -1;
    for(int i = 0; i < len; i++){
        if(s[i] >= 'a' && s[i] <= 'z')c[++tot] = s[i] ;
        else if(s[i] == ',') {
            if(tot >= 0) {
                c[++tot] = '';
                printf("%s
", c);
                tot = -1;
            }
        }
        else if(s[i] == '(') { 
            c[++tot] = '';
            printf("%s
", c);
            tot = -1;
        }
        else if(s[i] == ')') {
            if(tot >= 0) {
                c[++tot] = '';
                printf("%s
", c);
                tot = -1;
            }
        }
    }
    if(tot >= 0) {
        c[++tot] = '';
        printf("%s
", c);
    }
}
void Dfs(int fa) {
    while(l < len) {
        if(s[l] >= 'a' && s[l] <= 'z')++tot, l++;
        else if(s[l] == ',') {
            if(tot >= 0) {
                tot = -1;
                now++;
                ans.push_back(make_pair(fa, now));
                ans.push_back(make_pair(now, fa));
            }
            l++;
        }
        else if(s[l] == '(') { 
            tot = -1;
            now++;
            if(fa != 0)ans.push_back(make_pair(fa, now));
            l++;
            int tmp = now;
            Dfs(now);
            if(fa != 0)ans.push_back(make_pair(tmp, fa)); 
        }
        else if(s[l] == ')') {
            if(tot >= 0) {
                now++;
                ans.push_back(make_pair(fa, now));
                ans.push_back(make_pair(now, fa));
                tot = -1;
            }
            l++;
            return ;
        }
    }

}
int main() {
    scanf("%d", &T);
    while(T--) {
        ans.clear(); now = 0, l = 0, tot = -1;
        scanf("%s", s);
        len = strlen(s);
        int p = 0, i = 0;
        while(i < len) {
            if(s[i] == '(' || s[i] == ',')p++;
            i++;
        }
        printf("%d
", p + 1);
        solve();
        Dfs(0);
        for(int i = 0; i < ans.size(); i++)
            printf("%d %d
", ans[i].first, ans[i].second);
        printf("
");
    }
    return 0;
}

A，B两个人在玩一个游戏，即有n个球，球的标号是从1～n的，并且每个球有一个攻击力，攻击力的大小个球的标号有关，标号为i的球的攻击力等于 $2^{i - 1}$ 。现在游戏规则是这样的，A每次随机出一个球，并且每个球只能被随机到一次，且这个球会有50%的概率攻击A，同样也有50%的概率攻击B。A，B初始血量都是 $2^{n}$ 。每一轮过后，如果A的血量低于B的血量那么A就输了，否则当所有球都用完之后A还没有输的话，那么A就赢了，现在问你A赢的概率。要求以分数最简式的形式输出答案。

数据范围

多组输入T<=30，球的个数n<=500。

解题思路

首先我们可以知道 $2^{i} - 1 = 2^{0} + 2^{1} + \dots + 2^{i - 1}$ 。所以，假如B得了一个标号最大的球，那么不管之后怎么取A一定是赢的，而当B得了一个i号球，且i不等于n，那么之后A要赢的话之后一轮取到比i大的球都必须给B，也就是B取到球的标号是递增的，而我们可以知道n个球一共有 $n!$ 种取球的顺序，那么我们对于每一个排列顺序都可以知道A赢的概率，求出所有的排列的概率在求和即可求出A赢的概率。但是n有500那么大，如果照这个方法暴力显然不能写，但是通过打表打得n从1～10的几项发现，在未最简化的情况下，每一项的分母都是 $n! * 2^{n}$ ，而分子则呈现第i项的分子是第i-1项分子的2 * i - 1倍。看到分母应该就得想到显然得大整数写了，Java的大整数就行。

AC代码

import java.util.*;
import java.math.*;

public class Main {
    static BigInteger zo = new BigInteger("0");
    public static BigInteger Gcd(BigInteger x, BigInteger y) {
        if(x.remainder(y).compareTo(zo) == 0) return y;
        return Gcd(y, x.remainder(y));
    }
    public static void main(String []args) {
        Scanner cin = new Scanner(System.in);
        BigInteger [] fac = new BigInteger[505];
        BigInteger [] f = new BigInteger[505];
        BigInteger [] Pow = new BigInteger[505];
        fac[0] =new BigInteger("1");
        f[0] = new BigInteger("1");
        Pow[0] = new BigInteger("1");
        for (int i = 1; i <= 500; i++) {
            BigInteger val = BigInteger.valueOf(i);
            fac[i] = fac[i - 1].multiply(val);
            BigInteger v = BigInteger.valueOf(2 * i - 1);
            f[i] = f[i - 1].multiply(v);
            BigInteger w = new BigInteger("2");
            Pow[i] = Pow[i - 1].multiply(w);
        }
        int T = cin.nextInt();
        for (int cas = 1; cas <= T; cas++) {
            int n = cin.nextInt();
            BigInteger gcd = Gcd(f[n], fac[n].multiply(Pow[n]));
            System.out.println(f[n].divide(gcd).toString() + "/" + fac[n].multiply(Pow[n]).divide(gcd).toString());
        }
    }
}

懒得写了，放了队友代码。。。。

F - Machine scheduling

题目大意

n个数取r个分成小于等于m组的方案数，并且取出的r个数要求两两之间的差值必须大于等于k。

数据范围

$1 \leq n, r, k, m \leq 1000$ ,要求答案模 $10^{9} + 7$ 。

解题思路

首先将此题分成两部分分开求解，第一部分是n个数取r个满足要求的有多少个，第二部分是r个数分成m的方案数。因为两个问题相互独立，所以最后答案就是第一部分的方案数乘上第二部分的方案数。

首先看第二部分，是一个斯特林数，也可以看做是一个DP问题，S[i][j]代表前i个数分成j组的方案数，那么S[i][j]可以由S[i-1][j-1]转移过来，因为可以将第i个数单独作为第j组；S[i][j]也可以由S[i-1][j]转移过来，第i个数可以放在j组中的任意一组，所以总转移状态为 $S [i] [j] = S [i - 1] [j - 1] + S [i - 1] [j] * j$ 。所以第二部分总的方案数就是 $\sum_{j = 0}^{m} S [n] [j]$ 。

然后看第一部分，n个数取r个即有 $d = n - ((r - 1) * k + 1)$ 个空闲的数，因为这样保证了满足任意两个数差值大于等于k的条件，然后可以看做成r+d个数取r个数的方案个数。

最后两部分相乘取模即可。

AC代码

#include<cstdio>
#include<cstring>
#include<cmath>
#include<cstdlib>
#include<algorithm>
using namespace std;
typedef long long LL;
const int maxn = 1010;
const int Pt = 1e9 + 7;
int n, r, k, m;
LL c[maxn + 5][maxn + 5];
LL S[maxn + 5][maxn + 5];
void Init() {
    for(int i = 0; i <= maxn; i++)c[i][0] = 1;
    for(int i = 1; i <= maxn; i++)
        for(int j = 1; j <= i; j++)
            c[i][j] = (c[i - 1][j] + c[i - 1][j - 1]) % Pt;
    for(int i = 0; i <= maxn; i++)S[i][0] = 0LL, S[i][i] = 1LL; S[0][0] = 1LL;
    for(int i = 1; i <= maxn; i++)
        for(int j = 1; j <= i; j++)
            S[i][j] = (S[i - 1][j - 1] + S[i - 1][j] * j % Pt) % Pt;
}
int main() {
    Init();
    while(scanf("%d%d%d%d", &n, &r, &k, &m) != EOF) {
        int d = n - ((r - 1) * k + 1);
        if(d < 0)printf("0
");
        else {
            d += r; 
            LL res = 0LL;
            for(int i = 0; i <= m; i++) res = (res + c[d][r] * S[r][i] % Pt) % Pt;
            printf("%lld
", res);
        }
    }
    return 0;
}

G - Panda

题目大意

给你一个长度为n的且只包含字符’b’和’w’的字符串，然后m个操作，操作0代表查询区间[l,r]字符串”wbw”的个数（可以重叠），操作1代表修改第k个字符为ch。

数据范围

多组输入T<=100，n<=50000,m<=10000。

解题思路

可以发现每做一次修改只会影响到3个位置的值，因为查询较多，可以用树状数组维护前i个字符有多少个”wbw”串，并记下以第i个结尾是否有”wbw”，那么修改k位置的话，只需要先将k，k+1，k+2位置的答案先减掉，之直接修改字符串并判断k，k+1，k+2位置有无”wbw”串，有则更新答案。

AC代码

#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<algorithm>
using namespace std;
const int maxn = 50000;
char s[maxn + 5];
int c[maxn + 5];
int vis[maxn + 5];
int n, m;
int lowbit(int x) {
    return x & -x;
}
void add(int x, int y) {
    while(x <= maxn) {
        c[x] += y;
        x += lowbit(x);
    }
}
int sum(int x) {
    int res = 0;
    while(x > 0) {
        res += c[x];
        x -= lowbit(x);
    }
    return res;
}
int main() {
    int T, cas = 0; scanf("%d", &T);
    while(T--) {
        memset(vis, 0, sizeof(vis));
        memset(c, 0, sizeof(c));
        scanf("%d%d", &n, &m);
        scanf("%s", s + 1);
        for(int i = 1; i <= n - 2; i++) {
            if(s[i] == 'w' && s[i + 1] == 'b' && s[i + 2] == 'w') {
                vis[i + 2] = 1;
                add(i + 2, 1);
            }
        }
        printf("Case %d:
", ++cas);
        while(m--) {
            int op;
            scanf("%d", &op);
            if(op == 0) {
                int l, r;
                scanf("%d%d", &l, &r); l++, r++;
                printf("%d
", max(0, sum(r) - sum(l + 1)));
            }
            else {
                int l; char ch;
                scanf("%d %c", &l, &ch); l++;
                s[l] = ch;
                for(int i = l; i <= min(l + 2, n); i++) {
                    add(i, -vis[i]);
                    vis[i] = 0;
                }
                for(int i = max(1, l - 2); i <= l; i++) {
                    if(s[i] == 'w' && s[i + 1] == 'b' && s[i + 2] == 'w') {
                        add(i + 2, 1);
                        vis[i + 2] = 1;
                    }
                }
            }
        }
    }
}

J-Tourism Planning

题目大意

有n个人，m个景点，每个景点都需要门票，每去一个景点就需要花费对应的兴趣值，然后每个人去景点也会获得对应的兴趣值，并且特别的如果多个人在一个景点将会获得额外的兴趣值。现在要你求最大兴趣值和。如果不大于0则输出”STAY HOME”。

数据范围

$1 \leq N \leq 10, 1 \leq M \leq 10$ ,分别代表N个人和M个景点， $1 \leq P_{i} \leq 1000$ ，代表一个人去第i个地方需要花费的兴趣值， $1 \leq i \leq N, 1 \leq j \leq M, 1 \leq V_{i j} \leq 1000,$ 代表第i个人去第j个景点获得的兴趣值， $1 \leq i \leq N, 1 \leq j \leq N, 1 \leq B_{i j} \leq 1000,$ 代表i，j两个人在同一景点会产生的兴趣值。

解题思路

$d p [i] [s]$ 代表前i个景点在访问为s的状态下的最大兴趣值。那么它可以由第i-1的景点的状态转移过来，但是因为人数是不递增的，那么 $d p [i] [s] = m a x (d p [i - 1] [j] + c [i] [s]),$ 其中 $s \leq j \leq (1 << n) - 1,$ $c [i] [s]$ 代表第i个景点在s状态下的兴趣值，而 $c [i] [s]$ 的话，对每个状态找出哪些人访问了该景点，以及多个人之间的额外兴趣值。

具体见代码：

AC代码

#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<algorithm>
using namespace std;
const int INF = 1000000;
const int maxn = 2000;
int dp[15][maxn + 5], c[15][maxn + 5];
int p[15], v[15][15], b[15][15];
int n, m;
void Init() {
    for(int i = 1; i <= m; i++) {
        for(int s = 0; s < (1 << n); s++) {
            c[i][s] = 0;
            for(int j = 1; j <= n; j++) {
                if((1 << (j - 1)) & s) {
                    c[i][s] += (v[j][i] - p[i]);
                    for(int k = 1; k < j; k++) {
                        if((1 << (k - 1) & s))c[i][s] += b[j][k];
                    }
                }
            }
        }
    }
}
void solve() {
    int Max = -INF;
    for(int i = 1; i <= m; i++)
        for(int s = 0; s < (1 << n); s++)dp[i][s] = -INF;
    for(int i = 1; i <= m; i++) {
        for(int s = 0; s < (1 << n); s++) {
            for(int j = s; j < (1 << n); j++) {
                if((s & j) == s) {
                    dp[i][s] = max(dp[i][s], dp[i - 1][j] + c[i][s]);
                }
            }
            if(i == m)Max = max(Max, dp[m][s]);
        }
    }
    if(Max <= 0)printf("STAY HOME
");
    else printf("%d
", Max);
} 
int main() {
    while(~scanf("%d%d", &n, &m)) {
        if(n == 0 && m == 0)break;
        for(int i = 1; i <= m; i++)scanf("%d", &p[i]);
        for(int i = 1; i <= n; i++)
            for(int j = 1; j <= m; j++)
                scanf("%d", &v[i][j]);
        for(int i = 1; i <= n; i++)
            for(int j = 1; j <= n; j++)
                scanf("%d", &b[i][j]);
        Init();
        solve();
    }
    return 0;
}