A.牛牛和牛可乐的赌约 #逆元 #快速幂

题目链接

题意

nn面骰子（点数分别从11到nn，掷出每面的概率为1n\frac{1}{n}），先让你投mm次骰子，如果全部投出点数为nn点面。你在计算输的概率，请输出分数p/q mod 1e9+7p/q\ mod\ 1e9+7。

分析

显然，P(输)=1−(1n)m=(n−1)mnm=1- (\frac{1}{n})^m=\frac{(n-1)^m}{n^m}，但注意题目要求你求出P(输)在mod 1e9+7mod\ 1e9+7意义下的值，故先对分子进行快速幂，再对分母nmn^m求出其逆元inv(nm)inv(n^m)。考虑到模数为质数，直接使用费马小定理+快速幂即可得到逆元。

费马小定理：若pp为素数，aa为正整数，且a、pa、p互质，则有ap−1≡1（mod p）a^{p-1}\equiv 1（mod\ p）。

由于逆元xx满足$a\times x \equiv 1(mod\ p)\ \Rightarrow\ a\times x \equiv a^{p-1}(mod\ p)\ \Rightarrow\ x\equiv a^{p-2}(mod\ p) $

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
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <map>
#include <queue>
#include <stack>
#include <string>
#include <cstring>
#include <vector>
#include <cmath>
#include <unordered_map>
using namespace std;
typedef long long ll;
const int MOD = 1e9 + 7;
const int MAXN = 55;
ll qpow(ll base, ll power, ll mymod){
    ll ans = 1;
    while(power > 0){
        if(power & 1)
            ans = ans * base % mymod;
        power >>= 1;
        base = (base * base) % mymod;
    }
    return ans;
}
ll Inv(ll a, ll mymod){
    return qpow(a, mymod - (ll)2, mymod);
}
int main() {
    int q;
    scanf("%d", &q);
    while(q--){
        ll n, m;
        scanf("%lld%lld", &n, &m);
        ll a = qpow(n, m, (ll)MOD);
        ll b = Inv(a, (ll)MOD);
        printf("%lld\n", ((ll)(a - 1) * b) % ((ll)MOD));
    }
}

B.牛牛和牛可乐的赌约2 #博弈论 #打表

题目链接

题意

一个棋盘游戏，棋盘左上角为(0,0)(0,0)，该棋盘在(x,y)(x, y)的位置有一棋子，你和BobBob轮流移动该棋子，可左移也可上移，可移动一格或者两格，直到不能在移动(即到达(0,0)(0,0))的那个人为输。

你第一个出手，若游戏过程中两个人都用最优策略，最后你是否能够获胜。

分析

感谢@秃头小白的文章讲解。

显然(0,0)(0,0)为必败态。而若(x,y)(x,y)周围(x−1,y)(x−2,y)(x,y−1)(x,y−2)(x−1,y)(x−2,y)(x,y−1)(x,y−2)存在一点为必败态，则该点是必胜态。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
for (int i = 1; i <= 45; i++) {
    for (int j = 1; j <= 45; j++) {
        bool ans = 1;
        //寻找必败点
        if (i > 2) ans &= vis[i - 2][j];
        if (j > 2) ans &= vis[i][j - 2];
        if (i > 1) ans &= vis[i - 1][j];
        if (j > 1) ans &= vis[i][j - 1];
        vis[i][j] = !ans;
    }
}
for (int i = 1; i <= 45; i++) {
    for (int j = 1; j <= 45; j++) {
        printf("%d ", vis[i][j]);
    }
    printf("\n");
}

通过打出P-N表格，我们就能观察本题隐藏的性质，注意到

该表格对3×33\times 3矩阵分形，预先处理3×33\times 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
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <map>
#include <queue>
#include <stack>
#include <string>
#include <cstring>
#include <vector>
#include <cmath>
#include <unordered_map>
using namespace std;
typedef long long ll;
const int MOD = 1e9 + 7;
const int MAXN = 55;
string str;
bool vis[MAXN][MAXN];
bool ans[4][4] = { 
    {0, 1, 1}, {1, 0, 1}, {1, 1, 0}
};
int main() {
    int q;
    scanf("%d", &q);
    while(q--){
        int i, j; scanf("%d%d", &i, &j);
        if(ans[i % 3][j % 3]) printf("yyds\n");
        else printf("awsl\n");
    }
}

C.单词记忆方法 #递归 #分治

题目链接

题意

每个字母都有一个权值，AA权值为11，BB权值为22，… 依次类推。现要你求出一个字符串所有字母的权值总和，注意该字符串存在括号及数字，如ABCABC、(ABC)2、HHHH、(H2)2、H4ABCABC、(ABC)2、HHHH、(H2)2、H4，形如化学式。

分析

其实这题就是CCF CSP201912-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
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <map>
#include <queue>
#include <stack>
#include <string>
#include <cstring>
#include <vector>
#include <cmath>
#include <unordered_map>
using namespace std;
string str;
ll vis[4], ans;
ll getDigit(int& lo, int hi){
    ll res = 0;
    while(lo <= hi && isdigit(str[lo]))
        res = res * (ll)10 + (ll)(str[lo++] - '0');
    return res == 0 ? 1 : res;
}
void Compute(int lo, int hi, ll val){
    if(lo == hi){
        ans += (val * (ll)(str[lo] - 'A' + 1));
        return;
    }
    val *= (ll)getDigit(lo, hi);
    for (int i = lo, j = i + 1; i <= hi; i = j, j++){
        if('A' <= str[i] && str[i] <= 'Z'){
            int tmp = j;
            Compute(i, j - 1, val * (ll)getDigit(tmp, hi));
        }
        else if(str[i] == '('){
            for (int cnt = 1; cnt != 0; j++){
                if(str[j] == '(') cnt++;
                else if(str[j] == ')') cnt--;
            }
            int tmp = j;
            Compute(i + 1, j - 1, val * (ll)getDigit(tmp, hi));
        }
    }
}
int main(){
    cin >> str;
    Compute(0, str.length(), 1);
    printf("%lld\n", ans);
}

D.位运算之谜

题目链接

题意

a+ba+b的值为xx，a&ba\&b的值为yy，首先需要判断能否有一组a,ba, b满足当前的情况，如果有，那么求出a xor ba\ xor\ b，否则输出−1-1

分析

实际上该题并不需要我们将a,ba,b的具体值求出来，我们知道异或和即是不进位的加法，我们现在知道a+ba+b的结果，又因为(a&b)<<1(a\&b)<<1模拟a+ba+b的进位。正常的加法运算a+b=a xor b+((a&b)<<1)a+b = a\ xor\ b+((a\&b)<<1)。

当a+b−((a&b)<<1)a+b - ((a \& b ) << 1)如果是负数，显然无法存在a,ba,b满足题意，因为a xor ba\ xor\ b一定不为负。另外，还有一个排除条件，由于**a&ba\&b与a xor ba\ xor\ b一定取反**，也就说两者按位与一定为00。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <map>
#include <queue>
#include <stack>
#include <string>
#include <cstring>
#include <vector>
#include <cmath>
#include <unordered_map>
using namespace std;
typedef long long ll;
ll x, y;
int main(){
    int q; scanf("%d", &q);
    while(q--){
        scanf("%lld%lld", &x, &y);
        ll ans = x - (ll)(y << 1);
        if(ans < 0 || ans & y) printf("-1\n");
        else if(ans >= 0) printf("%lld\n", ans);
    }
}

F.牛牛的健身运动 #三分思想

题目链接

题意

mm天中，牛牛选其中一天来锻炼。每天有nn件器材。第kk天的第ii种器材能够增加k∗ai+bik*a_i+b_i力量。由于某种原因，牛牛只能在当天选择所有器材中增加力量值最小的两件（且两件不能相同）。牛牛希望能够选择某一天，使得他增加力量值最大，现要你求出他最多增加的力量。

分析

每一天牛牛只能选择力量值最小的两件，也就说假定现在为第kk天，则他只能增加yk=min(k∗(ai+aj)+(bi+bj),1≤i,j≤n)y_k=min(k*(a_i+a_j)+(b_i+b_j), 1\leq i,j \leq n)力量值，显然需要枚举两两器材搭配取得这一最小值。

但牛牛又希望从所有天中的最小值yk(1≤k≤m)y_k(1\leq k \leq m)取得最大值，求给定区间的最大值，用三分查找的算法较为适合。

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
#include <string>
#include <cstring>
#include <cstdio>
#include <iostream>
#include <stack>
#include <queue>
#include <map>
#include <vector>
#include <deque>
#include <cmath>
#include <algorithm>
#include <unordered_map>
using namespace std;
typedef long long ll;
const int MAXN = 2e3 + 5;
int n, m;
ll a[MAXN], b[MAXN];
ll Check(int x) { //获得当天增加力量最小值
    ll mymin = 0x3f3f3f3f3f3f3f3f;
    for (int i = 1; i <= n; i++)
        for (int j = i + 1; j <= n; j++) 
            mymin = min(mymin, (a[i] + a[j]) * (ll)x + (b[i] + b[j]));
    return mymin;
}
int main() {
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i++) scanf("%lld%lld", &a[i], &b[i]);
    int lo = 1, hi = m;
    ll ans = -0x3f3f3f3f3f3f3f3f;
    while (lo + 10 < hi) { //缩小区间
        int mid1 = lo + (hi - lo) / 3;
        int mid2 = hi - (hi - lo) / 3;
        if (Check(mid1) <= Check(mid2)) lo = mid1;
        else hi = mid2;
    }
    for (int i = lo; i <= hi; i++) ans = max(ans, Check(i)); //在小区间枚举比较最值
    printf("%lld\n", ans);
    return 0;
}

G.牛牛和字符串的日常 #KMP

题目链接

题意

给定喜欢句子，如果今日读的书中某连续kk个字符恰好为喜欢句子的某个前缀，那么能够加kk分。然而每天只能注意到一次自己喜欢的句子（即只能加分一次），你需要尽可能找到加分高的句子。现要求nn天后总共最多能有多少分

分析

由数据规模可知只能满足O(n)O(n)或更低的算法。直接用KMP模板即可，求出模式串（即喜欢句子）最长匹配长度。

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 <algorithm>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <map>
#include <queue>
#include <stack>
#include <string>
#include <cstring>
#include <vector>
#include <cmath>
#include <unordered_map>
using namespace std;
typedef long long ll;
const int MOD = 1e9 + 7;
const int MAXN = 1e5 + 5;
int nextTable[MAXN];
void buildNext(string str){
    int comlen = nextTable[0] = -1;
    int len = str.length(), i = 0;
    while(i < (len - 1)){
        if(comlen == -1 || str[i] == str[comlen]){
            i++;
            comlen++;
            nextTable[i] = comlen;
        }
        else comlen = nextTable[comlen];
    }
}
int KMP(string str, string T){
    int i = 0, j = 0;
    int res = -1;
    while(i < (int)T.length() && j < (int)str.length()){
        if(j < 0 || T[i] == str[j]){
            i++; j++;
        }
        else j = nextTable[j];
        res = max(res, j); //需添加的语句，更新模式串最长匹配长度
    }
    return res;
}
int main(){
    string str; cin >> str; buildNext(str);
    int n, ans = 0; scanf("%d", &n);
    for (int i = 1; i <= n; i++){
        string tmp; cin >> tmp;
        ans += KMP(str, tmp);
    }
    printf("%d\n", ans);
}

H.上学要迟到了 #单源最短路径

题目链接

题意

你去学校的路是一条总共有nn个公交车站的直线，且车站之间距离相等，每个车站只有一种对应的公交车aia_i，且每个公交车只在对应站停下。而第ii种公交车到达其下一个对应车站所需时间为tit_i，且单向行驶（从左到右）。而走路可以任意方向走，但步行走一站需TT时间。你的家在ss，学校在tt，求到达学校最短时间。

分析

这题其实不难，但是要注意两个隐藏细节(wa了好多发)：

  • 虽然公交车是单向，但人步行可以双向！
  • 公交车从一个对应站到另一个对应站，无论距离多长，耗费时间固定！

接下来，给人步行路径建双向边，给每种车的途径站建单向边，用DijkstraDijkstra算法求出路径即可。

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
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <map>
#include <queue>
#include <stack>
#include <string>
#include <cstring>
#include <vector>
#include <cmath>
#include <unordered_map>
using namespace std;
typedef long long ll;
const int MOD = 1e9 + 7;
const int MAXN = 1e5 + 5;
typedef struct Edge{
    int to, w;
} Edge;
typedef struct qnode{
    int v, data;
    bool operator <(const qnode& r) const {
        return data > r.data;
    }
}qnode;
vector<Edge> H[MAXN]; 
int n, m, st, ed, t;
int cost[MAXN], lastPos[MAXN];
int dis[MAXN];
void dijkstra(){
    priority_queue<qnode> myque;
    for (int i = 1; i <= n; i++) dis[i] = 0x3f3f3f3f;
    dis[st] = 0;
    myque.push({st, 0});
    while(!myque.empty()){
        qnode tmp = myque.top(); myque.pop();
        int u = tmp.v, len = tmp.data;
        if(len != dis[u]) continue;
        for (int i = 0; i < H[u].size(); i++){
            int v = H[u][i].to, w = H[u][i].w;
            if(dis[u] + w < dis[v]){
                dis[v] = dis[u] + w;
                myque.push({v, dis[v]});
            }
        }
    }
}
int main(){
    cin >> n >> m >> st >> ed >> t;
    for (int i = 1; i <= m; i++) scanf("%d", &cost[i]);
    for(int i = 1, v; i <= n; i++){
        scanf("%d", &v);
        if(lastPos[v] != 0) H[lastPos[v]].push_back({i, cost[v]}); 
        lastPos[v] = i;//记录v车的上一站点
    }
    for (int i = 1; i <= n - 1; i++) H[i].push_back({i + 1, t});
    for (int i = n; i >= 2; i--) H[i].push_back({i - 1, t}); //双向边
    dijkstra();
    printf("%d\n", dis[ed]);
    return 0;
}


I.迷宫 #动态规划

题目链接

题意

n×m（n,m≤100）n\times m（n,m\leq 100）地图，每个点有权值aija_{ij}，现要你从(1,1)(1,1)走到(n,m)(n, m)，可以往右走或往下走，每经过一个点便可得到相应权值，对权值和mod 1e4+7mod\ 1e4+7。问你从不同方式走到(n,m)(n,m)能获得多少种权值和？

分析

如果暴力搜索的话，总共有Cm+nnC^n_{m+n}路径，估计时间复杂度为O(n!)O(n!)，显然要用DP。

注意到取模1e4+71e4+7，我们知道权值和最大可能为1e4+71e4+7，最小可能为11，说明我们可以把权值枚举出来的。但是我们不知道能取到这一区间的哪些值，所以需要DP下看看哪些模数对应的权值和是可达的。

于是定义dp[i][j][k]dp[i][j][k]表示，地图(i,j)(i,j)点，能否达到权值kk。接下来枚举地图上的每一点及其所有模数，转移可从上一行的点、上一列的点进行。

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
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <map>
#include <queue>
#include <stack>
#include <string>
#include <cstring>
#include <vector>
#include <cmath>
#include <unordered_map>
using namespace std;
typedef long long ll;
const int MOD = 1e4 + 7;
const int MAXN = 105;
int n, m, val[MAXN][MAXN];
bool dp[MAXN][MAXN][MOD + 5];
int main(){
    scanf("%d%d", &n, &m);
    for(int i = 1; i <= n; i++){
        for (int j = 1; j <= m; j++){
            int tmp; scanf("%d", &tmp);
            val[i][j] = tmp % MOD; //避免
        }
    }
    dp[1][1][val[1][1]] = 1;
    for (int i = 1; i <= n; i++){
        for (int j = 1; j <= m; j++){
            for (int k = 0; k < MOD; k++){ //枚举模数
                dp[i][j][k] |= dp[i - 1][j][((k - val[i][j]) % MOD + MOD) % MOD];
                dp[i][j][k] |= dp[i][j - 1][((k - val[i][j]) % MOD + MOD) % MOD];
            }
        }
    }
    int ans = 0;
    for (int k = 0; k < MOD; k++) ans += dp[n][m][k];
    printf("%d\n", ans);
}

J.树上行走 #并查集

题目链接

题意

给定nn个节点、n−1n-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
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <map>
#include <queue>
#include <stack>
#include <string>
#include <cstring>
#include <vector>
#include <cmath>
#include <unordered_map>
using namespace std;
typedef long long ll;
const int MOD = 1e9 + 7;
const int MAXN = 2e5 + 5;
int flag[MAXN], tot = 0, fa[MAXN];
int n, sz[MAXN], ans[MAXN];
int findSet(int x){
    if(x != fa[x]) fa[x] = findSet(fa[x]);
    return fa[x];
}
int main(){
    scanf("%d", &n);
    for (int i = 1, tmp; i <= n; i++){
        scanf("%d", &flag[i]);
        fa[i] = i;
    }
    for (int i = 1, u, v; i <= n - 1; i++){
        scanf("%d%d", &u, &v);
        if(flag[u] != flag[v]) continue; 
        int pu = findSet(u), pv = findSet(v);
        fa[pu] = pv; //同类型节点进行合并
    }
    int mymax = -1, cnt = 0;
    for (int i = 1; i <= n; i++) findSet(i); //一定要保证所有顶点的路径都压缩完！！！
    for (int i = 1; i <= n; i++){
        sz[fa[i]]++; //统计该类型节点组成的树规模
        mymax = max(mymax, sz[fa[i]]);
    }
    for (int i = 1; i <= n; i++){
        if(sz[fa[i]] == mymax) ans[++cnt] = i; //满足条件，加入答案
    }
    printf("%d\n", cnt);
    for (int i = 1; i <= cnt; i++) printf("%d ", ans[i]);
    return 0;
}