这次的模拟赛比较简单。
150 T1:100 T2:30 T3:0 T4:20
T1:
【题目描述】
给定两个字符串a,b,从a中选一段前缀,b中选一段后缀(前后缀都可以为
空),并将选出的后缀拼在选出的前缀后面。
你需要求出有多少种本质不同的串(可以为空)
场上思路:
上来直接敲了个扩展kmp,仔细读题后发现这道题和kmp半毛钱关系没有,浪费了20min。
很容易发现,挨个枚举不同的串显然不是正解,而串的总数又是两串长度之积。所以只需要求出重复的串的数量就可以了
思考,看样例找规律,将b串反转后与a串逐个匹配,相同的字母对应了一个重复的串,发现能过样例,自己思考后发现假了,没有判断所有重复的串
又仔细观察
如下两个串
abccb
babac
从b考虑,以b为节点的重复的串和两串中b的位置没有直接联系。
如ab abccbab等,而以b为节点的重复的串数量恰好是2*2=4.多尝试几次发现确实如此。
于是我们开桶,存一下每个串中每个字母一共出现了几次,然后把两串中相同字母相乘,与总串数做差,就是答案
using namespace std;
const int maxn = 1e6+10;
char a[maxn],b[maxn];
long long t1[30],t2[30];
long long n1 = 1,n2 = 1;
long long ans;
int main(){
freopen("nan.in","r",stdin);
freopen("nan.out","w",stdout);
cin>>a+1;
cin>>b+1;
while(a[n1] != '\0') n1++;
while(b[n2] != '\0') n2++;
ans = n1*n2;
n1--,n2--;
for(int i = 1;i <= n1;i++){
if('a'<=a[i]&&a[i]<='z') t1[a[i]-'a'+1]++;
}
for(int i = 1;i <= n2;i++){
if('a'<=b[i]&&b[i]<='z') t2[b[i]-'a'+1]++;
}
for(int i = 1;i <= 26;i++) ans -= t1[i]*t2[i];
cout<<ans;
fclose(stdin);
fclose(stdout);
return 0;
}
T2
【题目描述】
有n个砝码,每个砝码都有初始重量ai。Q次操作,每次操作有下列两种:
•1,l,r,x:表示把l到r的所有ai变成x
•2,l,r,x:查询l到r的所有砝码,每个砝码可以用无数次,是否能称出重量x
ai和所有的x都不大于m。
保证ai和所有操作1的x总共最多不超过10种数字。
注意砝码只能放在同一侧。
【输入格式】
从文件weight.in中读入数据。
第一行三个整数n,m,Q。
接下来一行n个整数ai。
接下来Q行每行四个整数opt,l,r,x表示一次操作。opt=1表示操作1,opt=2
表示操作2。
【输出格式】
输出到文件weight.out中。
对于每个2操作。输出一行‘Yes’或者‘No’表示能否称出重量x。
【样例输入1】
3 3
1 2 3
2 1 3 2
1 1 3 3
2 1 3 2
【样例输出1】
Yes
No
场上写了个分块,挂了,暴力分。主要是这题没给大样例,我能有暴力分其实已经很奇迹了qwq
T3
T4
考场上只打了暴力,20分,给的挺多
从每个敌人出发打一遍最短路径? 因为是一棵树,所以直接BFS,最后统计每个点的最小距离取所有点最小距离的最大值为答案。