牛客小白月赛&&艾教习题总结

管道取珠

输入

第一行包含两个整数n, m，分别表示上下两个管道中球的数目。 第二行为一个AB字符串，长度为n，表示上管道中从左到右球的类型。其中A表示浅色球，B表示深色球。 第三行为一个AB字符串，长度为m，表示下管道中的情形。

输出

仅包含一行，即为 Sigma(Ai^2) i从1到k 除以1024523的余数。

输入示例

2 1
AB
B

输出示例

5

数据规模及约定

约30%的数据满足 n, m ≤ 12；
约100%的数据满足n, m ≤ 500。

题解

这题思路比较妙，我们需要先想想 ∑ai2 有什么意义。如果我们构造出这样一个游戏场景，即两个人同时玩两份同样的如题目所述的管道取珠的游戏，那么这两个人游戏结束后取到的珠子颜色序列一模一样的方案数就是题目里要求的答案。

令这两个人分别是 p1 和 p2。于是设 f[i][j][k] 表示 p1 取了第二个管道中的前 i 个珠子，第一个管道中的前 j 个珠子；p2 取了第一个管道的前 k 个珠子，这个状态下颜色序列相同的方案数，转移显然。

注：n为12以内一般是阶乘的题，n为30以内可以考虑状态压缩，莫队，线段树等各种情况，50左右选择二分，100以上需要另想方法。

问号猜数

有一堆数按照递增的顺序排列，然而这些数的某些位我们并不知道，我们知道的只是这些数是从小到大排列的，现在依次给出这些数，不知道的位用？表示。我们需要猜这个数能满足递增条件的最小数。例如：

??

1?

?1

???

?99

?9?

?4?5

第一个数是10，第2个11，第3个21，第4个100，第5个199，第6个290，第7个1405。

题解

用贪心虽然比较快，但代码不容易写，须考虑情况挺多。因此我们分析一下。首先n<=6，代表最大位数是6，也就是说最大的数也就是百万位。因此直接从1枚举，另设指针指向第1个数，每枚举到某个数满足该指针指向的数，则将指针指向下一个数，然后继续枚举，因此扫描一遍之后就得到所有的答案了。

接下来，假如n<=15，由于数是递增的，则将枚举用二分来完成。假如n>=100，这时再考虑贪心。

取牌去牌

有n张牌，每个牌有一个a属性和1个b属性，第i张牌的属性为ai，bi。现在每次从牌中选两张牌ii.j，得到一个ai bj + bi aj的分数，然后从这两张牌中去掉1张牌。经过n-1次操作之后就剩1张牌了。问经过n-1次操作后得到的最大的分数和是多少。

题解

主要是删除牌的问题。但是假如我们将每张牌看成1个结点，属性的乘积得到的分数为1条路径，那么n张牌构成了n个结点n*（n-1）/2条边的强联通无向图，那么只需求每次分数最大的最小生成树即可。

铁索连环

有n个数，现在有m次查询，每次查询[l,r]范围所有不同的数。假设n很大

题解

我的思路是打表记录上一个相同元素的位置，比如a[1-10]=1,2,4,3,2,4,5,6,3,4,那么b[1-10]=0,0,0,0,2,3,0,0,4,6。这样l，r的范围内只需扫描1遍即可，扫到0结果加1，扫到非0的数看该下标是否 < l，是则加1，否则不处理。时间复杂度是0mn。

艾教的方法不是很懂，不过举了一个例子，假如(3(3(3(3(3)))))，查询范围为括号所示，那么只需将第5个3赋为1，其他3赋为0即可。看起来最后就像一条链子捆绑着相同的元素。

狭路相逢

有一个图，每条路上都有强盗，每个节点都有驴友，假如到某条路上，该路上的强盗抢劫你的条件是强盗人数大于等于你们人数。你们每经过一个节点可以拉驴友入伍结伴而行，问（忘记问什么了，尴尬~QAQ~）

题解

并查集

区间gcd

给定l，r，问多少种gcd(l,r)==gcd(l2.r2)

题解

1、两个条件，从1到n，最大公约数呈递减阶梯式。

2、gcd(gcd（a,b）,gcd(c,d))==gcd(a,d)

根据性质2可以用st表列出范围内l，r的最大公约数，即1，n最大公约数

根据性质1，二分求解

信号误差

艾教给女朋友传情发信号，信号是01串（16位）组成的字母，但是有情敌的干扰，途中可能至多会有两位进制会发生改变。问如何设置01串才能无视干扰准确将信号传给女盆友。例如1111111111111111，那么该2个1也是比0多，所以无视干扰。但每次只能处理一个字母，效率太慢。

题解

图论。将距离2以内的所有结点全部连起来。贪心选取结点，可以直接选择第一个结点开始。

牛客小白月赛

音标

题目描述

我们规定元音字母有a、e、i、o、u，并且规定半元音字母y也是元音字母。

Cwbc在学习英语，XHRlyb为了让Cwbc的记忆更加深刻，于是她让Cwbc把每个字符串的所有字母都变成一个恰好**不大于它本身的小写元音字母**。

输入描述:

输入数据有多行，每行有一个仅包含小写字母的字符串。

输出描述:

输出数据应有多行，每行有一个变化后的字符串。

示例1

输入

aeiou

输出

aeiou

说明

元音字母变为一个恰好不大于它本身的字母，也就是元音字母本身

示例2

输入

bfjpv

输出

aeiou

说明

输入样例是由元音字母a、e、i、o、u的后一个字母组成，每个字母变为一个恰好不大于它本身的字母，也就是a、e、i、o、u。

备注:

每行字符串长度不超过2×105，字符串总长度不超过106。

代码

upper_bound的应用

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
char s[210000];
char a[]="aeiouy";
int main()
{
    while(cin>>s)
    {
        for(int i=0;s[i];i++)
        {
            s[i]=a[upper_bound(a,a+6,s[i])-a-1];
        }
        puts(s);
    }
}

躲藏

题目描述

XHRlyb和她的小伙伴Cwbc在玩捉迷藏游戏。
Cwbc藏在多个不区分大小写的字符串中。
好奇的XHRlyb想知道，在每个字符串中Cwbc作为子序列分别出现了多少次。
由于Cwbc可能出现的次数过多，你只需要输出每个答案对2000120420010122取模后的结果。
聪明的你在仔细阅读题目后，一定可以顺利的解决这个问题！

输入描述:

输入数据有多行，每行有一个字符串。

输出描述:

输出数据应有多行，每行表示一个答案取模后的结果。

示例1

输入

Cwbc

输出

1

说明

Cwbc作为子序列仅出现了1次。

示例2

输入

acdcecfwgwhwibjbkblcmcnco

输出

81

说明

Cwbc作为子序列出现了34=81次。

备注:

每行字符串长度不超过2×105，字符串总长度不超过106。

代码

一个memset导致超时，也是够无语。时间复杂度4 On，加上memset是5 On，就差1个On就超时。

#include<stdio.h>
#include<ctype.h>
char str[200010];
long long dp[5][200010];
int main() {
	int i;
	while (scanf("%s", str + 2) != EOF) {
		dp[1][0] = 'c', dp[2][0] = 'w', dp[3][0] = 'b',dp[4][0] = 'c';
		for (i = 2; str[i]; i++) {
			dp[0][i] = 1;
			str[i] = tolower(str[i]);
			for (int k = 1; k < 5; k++) {
				dp[k][i] = dp[k][i - 1];
				if (str[i] == dp[k][0]) {
					dp[k][i] += dp[k - 1][i];
					dp[k][i] %= 2000120420010122;
				}
			}
		}
		printf("%lld\n", dp[4][i - 1]);
	}
	return 0;
}

博弈

博弈双方都是绝顶聪明的，并且XHRlyb先手，请你来帮XHRlyb预测这一局游戏谁会获胜。

如果博弈双方谁也无法取胜，那么判定为平局。

输入描述:

输入数据有多行，每行有三个正整数，l，r，k。

输出描述:

输出数据应有多行，如果这一局XHRlyb获胜，那么请输出XHRlyb；如果Cwbc获胜，请输出Cwbc；如果两人平局，请输出Draw。

示例1

输入

1 3 2

输出

XHRlyb

示例2

输入

1 4 2

输出

Cwbc

备注:

1 ≤ l ≤ r ≤ 105。
1 ≤ k ≤ 100。
1 ≤ T ≤ 1000。

代码

水dp，l，r写反了，一直报错

#include<iostream>
#include<cstring>
#include<cmath>
using namespace std;
int dp[100005];
int sum[100005];
int main() {
	int l, r, k;
	while (cin >> l >> r >> k) {
		memset(dp, 0, sizeof(dp));
		memset(sum, 0, sizeof(sum));
		if (k == 1) {
			cout << "Draw" << endl;
			continue;
		}
		for (int i = 1; i < k; i++) {
			dp[i] = 1;
			sum[i] = (sum[i - 1] + 1);
		}
		for (int i = k; i <= r; i++) {
			dp[i] = (dp[i / k] * k + 1);
			sum[i] = (sum[i - 1] + dp[i]);
		}
		if (abs(sum[r] - sum[l - 1]) % 2 == 1)
			cout << "XHRlyb" << endl;
		else
			cout << "Cwbc" << endl;
	}
	return 0;
}