上海2022年12月月赛乙组

上海2022年12月月赛乙组"/>

上海2022年12月月赛乙组

上海2022年12月月赛乙组

T1 拼接单词

题目描述

给定两个单词 a a a 和 b b b，取 a a a 的一个前缀，再取 b b b 的一个后缀，就可以拼成一个新的单词。比如 a = tree a=\text{tree} a=tree， b = heap b=\text{heap} b=heap，则 treap = tr + eap \text{treap}=\text{tr}+\text{eap} treap=tr+eap 就是一个新的单词。

对于给定的 a a a 和 b b b，请计算它们可以拼出多少种不同的单词？注意拼接的时候， a a a 与 b b b 至少要出一个字母。

输入格式

• 第一行：一个仅有小写字母构成的字符串，表示前缀的来源 a a a
• 第二行：一个仅有小写字母构成的字符串，表示后缀的来源 b b b

输出格式

单个整数：表示新造单词的数量。

数据范围

记 a a a 的长度为 n n n， b b b 的长度为 m m m

• 对 30 % 30\% 30% 的数据， n , m ≤ 100 n,m \leq 100 n,m≤100；
• 对 60 % 60\% 60% 的数据， n , m ≤ 1000 n,m\leq 1000 n,m≤1000；
• 对 100 % 100\% 100% 的数据， 1 ≤ n , m ≤ 100 , 000 1 \leq n,m \leq 100,000 1≤n,m≤100,000。

样例数据

输入:

ab
ba

输出:

3

说明:

abba
aba
aa

输入:

tree
heap

输出:

14

分析：

暴力：

#include<bits/stdc++.h>
using namespace std;
string a,b;
set<string>jlt;//set
int main(){cin>>a>>b;int n=a.length(),m=b.length();string s1,s2;for(int i=0;i<n;++i){s1+=a[i];s2="";for(int j=m-1;j>=0;--j){s2=b[j]+s2;string st=s1+s2;jlt.insert(st);}}cout<<jlt.size()<<endl;return 0;
}

MATH：

如 a b c abc abc 和 d e f def def 两字符串，共能组成 3 × 3 3\times 3 3×3 个不同的新造词。

再如 a b c abc abc 和 a d c adc adc 两字符串，由于 a [ 0 ] a[0] a[0] 和 b [ m − 1 ] b[m-1] b[m−1] 是必须取到的，所以共能组成 3 × 3 3\times 3 3×3 个新造词。
再如 t r e e tree tree 和 h e a p heap heap 两单词， t r + e a p = t r e + a p , t r e + e a p = t r e e + a p tr+eap=tre+ap,~tre+eap=tree+ap tr+eap=tre+ap, tre+eap=tree+ap ，所以共能组成 4 × 4 − 2 = 14 4\times 4-2=14 4×4−2=14 个新造词。
再如 t e a r tear tear 和 h e a p heap heap 两单词， t + e a p = t e + a p = t e a + p t+eap=te+ap=tea+p t+eap=te+ap=tea+p ，所以共能组成 4 × 4 − 2 = 14 4\times 4-2=14 4×4−2=14 个新造词。

对于两字符串 a , b a,b a,b 除去 a [ 0 ] , b [ m − 1 ] a[0],b[m-1] a[0],b[m−1] ，如果没有字母相同，则可以组成 n × m n\times m n×m 个新造词。
对于两字符串 a , b a,b a,b 除去 a [ 0 ] , b [ m − 1 ] a[0],b[m-1] a[0],b[m−1] ，有相同字母但没有相同子串（指长度大于 1 1 1 ），可以组成 n × m − Σ i = 0 25 v h 1 [ i ] × v h 2 [ i ] n\times m-\Sigma_{i=0}^{25}vh1[i]\times vh2[i] n×m−Σi=025​vh1[i]×vh2[i] 个新造词，其中 v h 1 [ i ] vh1[i] vh1[i] 表示字符串 a a a 中出现了多少个字母 char ( i + ′ a ′ ) \text{char}(i+{'}a{'}) char(i+′a′) （除 a [ 0 ] a[0] a[0] ）， v h 2 [ i ] vh2[i] vh2[i] 即为字符串 b b b 的哈希表。

对于两字符串 a , b a,b a,b 除去 a [ 0 ] , b [ m − 1 ] a[0],b[m-1] a[0],b[m−1] ，有相同子串，同样可以组成 n × m − Σ i = 0 25 v h 1 [ i ] × v h 2 [ i ] n\times m-\Sigma_{i=0}^{25}vh1[i]\times vh2[i] n×m−Σi=025​vh1[i]×vh2[i] 个新造词。

证明：

两个字符串 t r e e , h e a p tree,heap tree,heap ，因为 t r + e a p = t r e + a p tr+eap=tre+ap tr+eap=tre+ap ，所以可以类比到所有情况：两个相同字母，取前舍后和取后舍前为同一种新造词，所以 a n s − = 1 ans-=1 ans−=1 ，若有多个相同字母，则组合可得 a n s − = v h 1 [ ] × v h 2 [ ] ans-=vh1[~]\times vh2[~] ans−=vh1[ ]×vh2[ ] 。

（以下论证并不必要）
以下只是当时的一些思考，并不必要
两个字符串 t e a r , h e a p tear,heap tear,heap ，因为 t + e a p = t e + a p = t e a + p t+eap=te+ap=tea+p t+eap=te+ap=tea+p ，所以可以类比到所有情况：两子串 s t st st 相同（即为所举例子中的 e a ea ea ），从第 0 0 0 个字母断开（即为所举例子中的 t + e a p t+eap t+eap ，子串全在字符串 b b b 中）、从第 1 1 1 个字母断开（即为所举例子中的 t e + a p te+ap te+ap ，子串的第一个字母在字符串 a a a 中，其余都在字符串 b b b 中）、 ⋯ \cdots ⋯ 、从第 s t . l e n g t h ( ) st.length() st.length() 个字母断开（即为所举例子中的 t e a + p tea+p tea+p ，子串全在字符串 a a a 中）所得的新单词为同一种新造词，所以有 a n s − = s t . l e n g t h ( ) ans-=st.length() ans−=st.length() ，但是并不完全。
如果该子串没有相同字母，则有 a n s − = s t . l e n g t h ( ) ans-=st.length() ans−=st.length() ，即 a n s − = v h 1 [ ] × v h 2 [ ] ans-=vh1[~]\times vh2[~] ans−=vh1[ ]×vh2[ ] （子串部分也可和其余部分中的相同字母组合）；如果该子串有相同字母， a n s ans ans 还需减掉子串中的重复字母组合后的数量，如字符串 t e e a , e e a p teea,eeap teea,eeap ，其中 [ t e + e e a p = t e e + e a p ] , [ t + e e a p = t e + e a p = t e e + a p = t e e a + p ] , [ t + e a p = t e + a p ] ~[te+eeap=tee+eap],~[t+eeap=te+eap=tee+ap=teea+p],~[t+eap=te+ap]  [te+eeap=tee+eap], [t+eeap=te+eap=tee+ap=teea+p], [t+eap=te+ap] ，可以看到结果并非 ( a n s − s t . l e g n t h ( ) ) = 13 (ans-st.legnth())=13 (ans−st.legnth())=13 ，而是 ( a n s − v h 1 [ ] × v h 2 [ ] ) = 11 (ans-vh1[~]\times vh2[~])=11 (ans−vh1[ ]×vh2[ ])=11 ，问题就出在前后两个中括号内，即问题出在重复新造词的长度上，并非只有长度为 n + m − s t . l e g n t h ( ) n+m-st.legnth() n+m−st.legnth() 的新造词会出现重复，即子串不一定要正好取全：
如所举例子，令 s t . l e n g t h ( ) = l e n , n + m − l e n = f n st.length()=len,~n+m-len=fn st.length()=len, n+m−len=fn ，如中括号 1 1 1 内，如果字符串 a a a 多向后选择一个字母，则长度 + 1 +1 +1 ，枚举直到当前的字母 e e e 结束，共有两种， a n s − = 1 ans-=1 ans−=1 ，由此可以推广到全部。
所以本质上又成为了组合。

#include<bits/stdc++.h>
using namespace std;
#define ll long long
string a,b;
ll vh1[26],vh2[26];
ll ans=0;
int main(){cin>>a>>b;ll n=a.length(),m=b.length();ans=n*m;for(int i=1;i<n;++i)++vh1[a[i]-'a'];for(int i=0;i<m-1;++i)++vh2[b[i]-'a'];for(int i=0;i<26;++i)ans-=vh1[i]*vh2[i];cout<<ans<<endl;return 0;
}

T2 八进制小数

题目描述

给定一个八进制的纯小数（不含循环节），输出它的十进制表示。

例如 ( 0.1 ) 8 = ( 0.125 ) 10 (0.1)_{8}=(0.125)_{10} (0.1)8​=(0.125)10​， ( 0.35 ) 8 = ( 0.453125 ) 10 (0.35)_8=(0.453125)_{10} (0.35)8​=(0.453125)10​

输入格式

一个数字序列：表示一个八进制数字的小数部分

输出格式

一个数字序列：表示给定数字的十进制的小数部分

数据范围

设 n n n 表示输入序列的长度

• 对于 30 % 30\% 30% 的数据， n ≤ 5 n\leq 5 n≤5
• 对于 60 % 60\% 60% 的数据， n ≤ 50 n\leq 50 n≤50
• 对于 100 % 100\% 100% 的数据， n ≤ 500 n\leq 500 n≤500

样例数据

输入:

1

输出:

125

输入:

35

输出:

453125

分析：

暴力高精度。

#include<bits/stdc++.h>
using namespace std;
string s;
struct nod{short a[2010];//最大长度在1500左右nod(){memset(a,0,sizeof(a));}nod operator =(const string s){a[0]=s.length();for(int i=1;i<=s.length();++i)a[i]=s[i-1]-'0';return *this;}nod operator +(const nod x){nod ans;for(int i=max(a[0],x.a[0]);i>=1;--i){ans.a[i]+=a[i]+x.a[i];ans.a[i-1]+=ans.a[i]/10;ans.a[i]%=10;}ans.a[0]=max(a[0],x.a[0]);while(ans.a[0]>=1&&ans.a[ans.a[0]]==0)//删除后缀0--ans.a[0];return ans;}nod operator *(const nod x){nod ans;for(int i=1;i<=a[0];++i)for(int j=1;j<=x.a[0];++j)ans.a[i+j]+=a[i]*x.a[j];ans.a[0]=a[0]+x.a[0];for(int i=ans.a[0];i>=1;--i){ans.a[i-1]+=ans.a[i]/10;ans.a[i]%=10;}while(ans.a[0]>=1&&ans.a[ans.a[0]]==0)--ans.a[0];return ans;}nod operator *(const short x){nod ans;for(int i=1;i<=a[0];++i)ans.a[i]=a[i]*x;for(int i=a[0];i>=1;--i){ans.a[i-1]+=ans.a[i]/10;ans.a[i]%=10;}ans.a[0]=a[0];while(ans.a[0]>=1&&ans.a[ans.a[0]]==0)--ans.a[0];return ans;}string str(){string s="";for(int i=1;i<=a[0];++i)s+=a[i]+'0';return s;}friend ostream& operator <<(ostream& out,nod x){out<<x.str();return out;}
};
int main(){cin>>s;int pos=-1;for(int i=s.length()-1;i>=0;--i){if(s[i]!='0')break;pos=i;}if(pos!=-1)s.erase(pos);nod ini;ini.a[0]=3,ini.a[1]=1,ini.a[2]=2,ini.a[3]=5;nod r[s.length()+2];r[1]=ini;for(int i=2;i<=s.length();++i)r[i]=r[i-1]*ini;//r数组是每一位的权值nod ans[s.length()+2];for(int i=1;i<=s.length();++i)ans[i]=r[i]*(s[i-1]-'0');nod fn;for(int i=1;i<=s.length();++i)fn=fn+ans[i];cout<<fn<<endl;return 0;
}

T3 树的最长路

题目描述

给定一棵 n n n 个结点的树， 1 1 1 号点为根，树上相邻两点之间的距离均为 1 1 1。请为树上每个点求出距离最远的点，并输出这些最长路的距离。

输入格式

• 第一行：单个整数表示 n n n；
• 第二行： n − 1 n-1 n−1 个整数表示 p 2 p_2 p2​ 到 p n p_n pn​， p i p_i pi​ 表示 i i i 号点父亲的编号，保证有 1 ≤ p i < i 1\leq p_i<i 1≤pi​<i。

输出格式

• n n n 个整数：表示从第 i i i 个点出发的最长路的长度。

数据范围

• 对于 30 % 30\% 30% 的数据， n ≤ 200 n\leq 200 n≤200；
• 对于 60 % 60\% 60% 的数据， n ≤ 5000 n\leq 5000 n≤5000；
• 对于 100 % 100\% 100% 的数据， 1 ≤ n ≤ 200 , 000 1\leq n\leq 200,000 1≤n≤200,000。

样例数据

输入:

5
1 2 3 4

输出:

4 3 2 3 4

说明:

这棵树形如一条链

输入:

5
1 1 1 1

输出:

1 2 2 2 2

分析：

当时的想法：

当时觉得像树的重心那道题，一条向下的和一条向上的路，取一个最大值，但是当时犯傻觉得向上的路一定经过根，便有以下代码。

#include<bits/stdc++.h>//这是懂数组起名的
using namespace std;
#define MAXN 200010
int n,f[MAXN],dp[MAXN],fr[MAXN],dst[MAXN];
vector<int>s[MAXN];//存子节点
void rcss(int id,int rt){fr[id]=rt;//fr[i]表示节点i属于根节点的哪一棵子树for(int i=0;i<s[id].size();++i)rcss(s[id][i],rt);return;
}void rcs(int id,int dep){dp[id]=dep;//dp数组记录深度dst[fr[id]]=max(dst[fr[id]],dep);//dst数组记录根节点每一棵子树的最大深度for(int i=0;i<s[id].size();++i)rcs(s[id][i],dep+1);return;
}
int main(){cin>>n;f[1]=-1;//记录父节点for(int i=2;i<=n;++i)cin>>f[i],s[f[i]].push_back(i);for(int i=0;i<s[1].size();++i)rcss(s[1][i],i);rcs(1,1);int dpos=-1,dnum=-1;for(int i=0;i<s[1].size();++i)if(dnum<dst[i]){dpos=i;//记录深度最大的子树下标dnum=dst[i];//记录深度最大的子树深度}int dpos2=-1,dnum2=-1;//记录次大的子树下标和深度for(int i=0;i<s[1].size();++i)if(i!=dpos&&dnum2<dst[i]){dpos2=i;dnum2=dst[i];}if(dpos2==-1){//仅有一棵子树for(int i=1;i<=n;++i)cout<<max(i-1,n-i)<<" ";cout<<endl;}else{cout<<dnum-1<<" ";for(int i=2;i<=n;++i){if(fr[i]==dpos)cout<<max(dnum-dp[i],dp[i]+dnum2-2)<<" ";elsecout<<dp[i]+dnum-2<<" ";}cout<<endl;//进行运算}return 0;
}

树上动规：

看成三条路径：①向下走能到达的最远距离（通过 O ( n ) O(n) O(n) 搜索可以得到）；②向上达到父节点然后从父节点另一个子树下去能达到的最远距离（维护每个节点向下能达到的最远距离和次远距离）；③向上达到父节点然后继续向上达到父节点的父节点所能达到的最远距离（通过树上 d p dp dp 可以得到）

#include<bits/stdc++.h>
using namespace std;
#define MAXN 200010
int n,f[MAXN],dep[MAXN];
int dp1[MAXN],dp2[MAXN],dpu[MAXN],stmp[MAXN];
vector<int>s[MAXN];
int rcs(int id,int deep){dep[id]=deep;//深度dp1[id]=dp2[id]=deep;//最远和次远距离for(int i=0;i<s[id].size();++i){int dst=rcs(s[id][i],deep+1);//此处先维护出向下能达到的最大深度if(dst>dp1[id]){//打擂台得到dp1和dp2数组stmp[id]=i;//表示节点id最深子树存储时的下标dp2[id]=dp1[id];dp1[id]=dst;}else if(dst>dp2[id])dp2[id]=dst;}return dp1[id];
}
int main(){cin>>n;f[1]=-1;//父节点for(int i=2;i<=n;++i)cin>>f[i],s[f[i]].push_back(i);rcs(1,0);for(int i=1;i<=n;++i)dp1[i]-=dep[i],dp2[i]-=dep[i];//减去本身深度可得距离dpu[1]=0;//第一步向上能达到的最远距离for(int i=2;i<=n;++i)dpu[i]=max(dpu[f[i]]+1,s[f[i]][stmp[f[i]]]==i?dp2[f[i]]+1:dp1[f[i]]+1);//进行一个递的推for(int i=1;i<=n;++i)cout<<max(dp1[i],dpu[i])<<" ";//第一步向上和向下能达到的最长距离打擂台cout<<endl;return 0;
}

T4 最大频率

题目描述

给定一个长度为 n n n 的不下降序列 a 1 , a 2 , . . . , a n a_1,a_2,...,a_n a1​,a2​,...,an​，及 q q q 次询问，每次询问包含两个参数 L , R L , R L,R，请你计算出区间 [ L , R ] [L,R] [L,R]内，即 a L , . . . , a R a_L,...,a_R aL​,...,aR​中，所有出现过的数字中的最大频率。

所谓最大频率，指所有数字中，出现次数最多的数字出现的次数。

输入格式

输入第一行，两个正整数 n , q n,q n,q，表示给定序列长度和询问次数
输入第二行， n n n 个整数，分别表示序列的每一项 a 1 , a 2 , . . . , a n a_1,a_2,...,a_n a1​,a2​,...,an​
接下来 q q q行，每行两个正整数 L i , R i L_i,R_i Li​,Ri​，表示第 i i i次询问的两个参数。

输出格式

输出共 q q q行，第 i i i行输出对于第 i i i个问题的答案

数据范围

• 对于 30 % 30\% 30% 的数据， 1 ≤ n , q ≤ 100 1 \leq n ,q\leq 100 1≤n,q≤100
• 对于 60 % 60\% 60% 的数据， 1 ≤ n , q ≤ 1 0 4 1 \leq n ,q\leq 10^4 1≤n,q≤104
• 对于 100 % 100\% 100% 的数据， 1 ≤ n , q ≤ 1 0 5 1 \leq n,q \leq 10^5 1≤n,q≤105 , − 1 0 9 ≤ a 1 ≤ a 2 ≤ . . . ≤ a n ≤ 1 0 9 -10^9 \leq a_1 \leq a_2 \leq ...\leq a_n \leq 10^9 −109≤a1​≤a2​≤...≤an​≤109， 1 ≤ L ≤ R ≤ n 1 \leq L \leq R \leq n 1≤L≤R≤n

样例数据

输入:

10 4
-2 -2 -1 2 3 3 3 7 8 8
1 3
2 4
1 8
7 10

输出:

2
1
3
2

分析：

暴力：

#include<bits/stdc++.h>
using namespace std;
#define MAXN 100010
int n,q,a[MAXN];
int main(){cin>>n>>q;for(int i=1;i<=n;++i)cin>>a[i];int l,r;for(int i=1;i<=q;++i){cin>>l>>r;map<int,int>vh;int num=-1;for(int i=l;i<=r;++i){++vh[a[i]];if(num<vh[a[i]])num=vh[a[i]];}cout<<num<<endl;}return 0;
}

ST表（线段树就先不打了嚎）：

很明显的一个区间最值。

抽风打法：

将每一个平台长度拎出来。

#include<bits/stdc++.h>
using namespace std;
#define MAXN 100010
int n,q,a[MAXN];
vector<int>F[MAXN];
struct nod{int l,r,num;//区间端点和区间数值nod(int _l,int _r,int _n):l(_l),r(_r),num(_n){}
};
vector<nod>vh;
void ST_create(int len){//建表for(int i=0;i<len;++i)F[i].push_back(vh[i].r-vh[i].l+1);int k=log2(n);for(int j=1;j<=k;++j)for(int i=0;i<len-(1<<j)+1;++i)F[i].push_back(max(F[i][j-1],F[i+(1<<(j-1))][j-1]));return;
}int bs_l(int key,int len){//这两个二分就是为什么繁了if(vh[len-1].l<key)return len;if(key==vh[0].l)return 0;int left=0,right=len-1,mid=(left+right)>>1;while(right-left>1){if(vh[mid].l<key)left=mid;elseright=mid;mid=(left+right)>>1;}return right;
}int bs_r(int key,int len){if(key<vh[0].r)return -1;if(key==vh[len-1].r)return len-1;int left=0,right=len-1,mid=(left+right)>>1;while(right-left>1){if(vh[mid].r<=key)left=mid;elseright=mid;mid=(left+right)>>1;}return left;
}int ST_query(int l,int r){//查询int k=log2(r-l+1);return max(F[l][k],F[r-(1<<k)+1][k]);
}
int main(){cin>>n>>q;for(int i=1;i<=n;++i){cin>>a[i];if(vh.empty()||vh[vh.size()-1].num!=a[i])vh.push_back(nod(i,i,a[i]));else++vh[vh.size()-1].r;}ST_create(vh.size());int l,r;for(int i=1;i<=q;++i){cin>>l>>r;if(a[l]==a[r]){cout<<r-l+1<<endl;continue;}int left=bs_l(l,vh.size());int right=bs_r(r,vh.size());//将所给区间分成三部分，l和r处的不完整平台，以及中间的完整平台int ans=-1;if(l<vh[left].l)ans=max(ans,vh[left].l-l);if(vh[right].r<r)ans=max(ans,r-vh[right].r);if(left<=right)ans=max(ans,ST_query(left,right));//分类讨论不多做解释cout<<ans<<endl;}return 0;
}

优雅打法：

没必要拎出来，开辅助数组即可。

#include<bits/stdc++.h>
using namespace std;
#define MAXN 100010
int n,q,a[MAXN],num[MAXN],b[MAXN];
vector<int>F[MAXN];
void ST_create(int len){//建表for(int i=1;i<=len;++i)F[i].push_back(num[i]);//建的是num数组的ST表，意义见下int k=log2(len);for(int j=1;j<=k;++j)for(int i=1;i<=len-(1<<j)+1;++i)F[i].push_back(max(F[i][j-1],F[i+(1<<(j-1))][j-1]));return;
}int ST_query(int l,int r){//查表int k=log2(r-l+1);return max(F[l][k],F[r-(1<<k)+1][k]);
}
int main(){cin>>n>>q;for(int i=1;i<=n;++i){cin>>a[i];if(a[i]!=a[i-1])num[i]=1;//包括自己向前有多少相同的elsenum[i]=num[i-1]+1;}for(int i=n;i>=1;--i){if(a[i]!=a[i+1])b[i]=1;//包括自己向后有多少相同的elseb[i]=b[i+1]+1;}ST_create(n);int l,r;for(int i=1;i<=q;++i){cin>>l>>r;if(a[l]==a[r])cout<<r-l+1<<endl;elsecout<<max(b[l],ST_query(l+b[l],r))<<endl;//由此可以直接ST表查询}return 0;
}