2020牛客暑期多校训练营（第四场）BCFH B. Basic God Problem C. Count New String F. Finding the Order H. Haeder Gcd Problem
BCFH
题意
给出c和n，求fc（n）。
题解
递归到最后 fc 函数肯定等于1，那么就变成了求c被乘了几次，只要找到 x 最多能被分解成多少个数相乘就好了。预处理用线性筛求出每个数最多能被分解成多少个数相乘，快速幂求出解。
代码
1 #include<bits/stdc++.h> 2 #define ll long long 3 #define pb push_back 4 #define ft first 5 #define sd second 6 #define pii pair<int,int> 7 #define pll pair<ll,ll> 8 using namespace std; 9 10 ll st[1001000]; 11 ll prime[1001000]; 12 ll d[1001000]; 13 ll cnt; 14 const ll mod=1e9+7; 15 void Prime(ll n) 16 { 17 cnt=0; 18 for(ll i=2;i<=n;i++){ 19 if(!st[i]) prime[cnt++]=i,d[i]=1; 20 for(int j=0;prime[j]*i<=n;j++){ 21 st[prime[j]*i]=1; 22 d[prime[j]*i]=d[i]+1; 23 if(i%prime[j]==0) break; 24 } 25 } 26 } 27 ll quick(ll a,ll b) 28 { 29 ll res=1; 30 a=a%mod; 31 while(b){ 32 if(b&1) res=(res*a)%mod; 33 a=(a*a)%mod; 34 b>>=1; 35 } 36 return res%mod; 37 } 38 int main() 39 { 40 ios::sync_with_stdio(false); 41 cin.tie(0); 42 cout.tie(0); 43 Prime(1000000); 44 for(ll i=1;i<=10;i++) cout<<d[i]<<endl; 45 int t; 46 cin>>t; 47 while(t--){ 48 ll n,c; 49 cin>>n>>c; 50 cout<<quick(c,d[n])<<endl; 51 } 52 return 0; 53 }
C. Count New String
题意
f(S,x,y)(1≤x≤y≤n)表示一个长度为y-x+1的字符串，字符串的第 i 位为maxi=x...x+k−1Si。 A={ f( f(S,x1,y1), x2−x1+1 , y2−x1+1 ) | 1≤x1≤x2≤y2≤y1≤n}，求有多少不同的集合A。
题解
出题人的题解：
• 核心点 1
• 这题等价于 f(S,i,n) 这 n 个串的不同子串的个数
• 核心点 2
• 假设当前字符的位置是 i，最近的大于等于它的字符的位置
是 j，那么新增的代价是 j-i。
• f(S,i,n) 翻转后构成的字典树的大小不超过 10N
• 所以我们要考虑这个字典树本质不同的子串
• 最暴力的方法：在构成的字典树上建广义后缀自动机即可，
设 k 为字符集大小，复杂度O(Nk2)
• 也可以用一些哈希或序列自动机的方法求一求。
我的想法：
比赛的时候第一点我就没看出来，好菜.....
A集合中区间范围可以看出[x2,y2]完全包含在[x1,y1]里边，所以[x2,y2]这个是不起任何作用的。故问题就转换成了求f(S,x,y)(1≤x≤y≤n)有多少本质不同的子串。这个问题不就是广义后缀自动机的经典题型了吗。但是如果对于所有的[x1,y1]都建立sam的话，肯定是不行的，于是就要用到别的办法。观察可以发现f(S,x,y)调用过程中任意一个位置的字符最多会被替换9次（因为子集字符串长度最大为10）。看巨巨们的博客有两种方法，一种用单调队列完成，一种是序列自动机。找到第一个大于等于s[i]的字符的位置记录为pos，那么只要每次往sam中插入s[i]~s[pos-1]即可。
关于序列自动机的做法：（来自@Frozen_Guardian ）nt[ i ][ j ] 表示为记录位置 i 开始的首次大于等于字母 j 的位置，这样对于第 i 个位置的字母 j 来说，只需要暴力更新一下 [ i , nt[ i ][ j ] - 1 ] 就好了，nt[ i ][ j ] 往后的位置都可以直接从前面维护的 trie 树中拉下来继续用。
代码
序列自动机+SAM
1 #include<bits/stdc++.h> 2 #define ll long long 3 using namespace std; 4 5 const int maxn=1e6+10; 6 7 struct state 8 { 9 int mxlen,link; 10 int cnt; 11 int nt[26]; 12 }st[maxn<<1]; 13 14 int sz,last,len; 15 char s[maxn]; 16 17 inline void sam_init() 18 { 19 st[0].mxlen=0; 20 st[0].link=-1; 21 sz=1; 22 last=0; 23 } 24 25 inline void sam_extend(int c) 26 { 27 int cur=sz++; 28 st[cur].mxlen=st[last].mxlen+1; 29 st[cur].cnt=1; 30 int p=last; 31 while(p!=-1&&!st[p].nt[c]){ 32 st[p].nt[c]=cur; 33 p=st[p].link; 34 } 35 if(p==-1) st[cur].link=0; 36 else{ 37 int q=st[p].nt[c]; 38 if(st[p].mxlen+1==st[q].mxlen) st[cur].link=q; 39 else{ 40 int clone=sz++; 41 st[clone].mxlen=st[p].mxlen+1; 42 memcpy(st[clone].nt,st[q].nt,sizeof(st[q].nt)); 43 st[clone].link=st[q].link; 44 while(p!=-1&&st[p].nt[c]==q){ 45 st[p].nt[c]=clone; 46 p=st[p].link; 47 } 48 st[q].link=st[cur].link=clone; 49 } 50 } 51 last=cur; 52 } 53 54 int nt[maxn][10],id[maxn]; 55 //nx[i][j]第i个位置(包括)后首次出现大于等于j的位置 56 57 int main() 58 { 59 cin>>s+1; 60 sam_init(); 61 int n=strlen(s+1); 62 for(int i=0;i<10;i++) nt[n+1][i]=n+1; 63 for(int i=n;i>=1;i--){ 64 for(int j=0;j<10;j++) nt[i][j]=nt[i+1][j]; 65 nt[i][s[i]-'a']=i; 66 for(int j=8;j>=0;j--) nt[i][j]=min(nt[i][j],nt[i][j+1]); 67 } 68 id[n+1]=last; 69 for(int i=n;i>=1;i--){ 70 int pos=nt[i+1][s[i]-'a']; 71 last=id[pos]; 72 for(int j=i;j<pos;j++) sam_extend(s[i]-'a'); 73 id[i]=last; 74 } 75 ll ans=0; 76 for(int i=1;i<=sz;i++){ 77 ans+=st[i].mxlen-st[st[i].link].mxlen; 78 } 79 cout<<ans<<endl; 80 return 0; 81 }
单调队列+SAM
1 #include<bits/stdc++.h> 2 #define ll long long 3 using namespace std; 4 5 const int maxn=1e6+10; 6 7 struct state 8 { 9 int mxlen,link; 10 int cnt; 11 int nt[26]; 12 }st[maxn<<1]; 13 14 int sz,last,len; 15 char s[maxn]; 16 17 inline void sam_init() 18 { 19 st[0].mxlen=0; 20 st[0].link=-1; 21 sz=1; 22 last=0; 23 } 24 25 inline void sam_extend(int c) 26 { 27 int cur=sz++; 28 st[cur].mxlen=st[last].mxlen+1; 29 st[cur].cnt=1; 30 int p=last; 31 while(p!=-1&&!st[p].nt[c]){ 32 st[p].nt[c]=cur; 33 p=st[p].link; 34 } 35 if(p==-1) st[cur].link=0; 36 else{ 37 int q=st[p].nt[c]; 38 if(st[p].mxlen+1==st[q].mxlen) st[cur].link=q; 39 else{ 40 int clone=sz++; 41 st[clone].mxlen=st[p].mxlen+1; 42 memcpy(st[clone].nt,st[q].nt,sizeof(st[q].nt)); 43 st[clone].link=st[q].link; 44 while(p!=-1&&st[p].nt[c]==q){ 45 st[p].nt[c]=clone; 46 p=st[p].link; 47 } 48 st[q].link=st[cur].link=clone; 49 } 50 } 51 last=cur; 52 } 53 54 int id[maxn]; 55 56 int main() 57 { 58 cin>>s+1; 59 sam_init(); 60 int n=strlen(s+1); 61 stack<int>ss; 62 ss.push(n+1); 63 id[n+1]=last; 64 for(int i=n;i>=1;i--){ 65 while(ss.size()!=1&&s[ss.top()]<s[i]) ss.pop(); 66 int pos=ss.top(); 67 last=id[pos]; 68 for(int j=i;j<pos;j++) sam_extend(s[i]-'a'); 69 id[i]=last; 70 ss.push(i); 71 } 72 ll ans=0; 73 for(int i=1;i<=sz;i++){ 74 ans+=st[i].mxlen-st[st[i].link].mxlen; 75 } 76 cout<<ans<<endl; 77 return 0; 78 }
F. Finding the Order
题意
有两条平行的线AB和CD，给出AC, AD, BC, BD 的长度，分别为a, b, c, d。问是AB//CD，还是AB//DC。
题解
- 这是一个神奇的题目，我是把所有情况画出来记录，毕竟暴力出奇迹嘛^_^
-
发现自己是憨憨，看了其他巨巨的题解发现自己的方法好蠢，我连小学数学的水平都没有┭┮﹏┭┮ ，这个解法来自@Harris-H。根据两边之和大于第三边，直接比较AC+BD和AB+BC的长度就好了，长的是四边形的交线，就可以判断是CD还是DC了。
代码
菜鸡本人的代码
1 #include<bits/stdc++.h> 2 #define ll long long 3 #define pb push_back 4 #define ft first 5 #define sd second 6 #define pii pair<int,int> 7 #define pll pair<ll,ll> 8 using namespace std; 9 10 int main() 11 { 12 ios::sync_with_stdio(false); 13 cin.tie(0); 14 cout.tie(0); 15 int t; 16 cin>>t; 17 while(t--){ 18 int a,b,c,d; 19 cin>>a>>b>>c>>d; 20 if(b>a&&c>d&&b>d||a>b&&c>d&&c>a||b>a&&d>c&&b>d||a==b&&c>d&&c>a||c==d&&b>a&&b>d) cout<<"AB//CD"<<endl; 21 else cout<<"AB//DC"<<endl; 22 } 23 return 0; 24 }
巨巨的代码
1 #include<bits/stdc++.h> 2 using namespace std; 3 typedef long long ll; 4 const int N=1e3+5,M=2e4+5,inf=0x3f3f3f3f,mod=1e9+7; 5 #define mst(a) memset(a,0,sizeof a) 6 #define lx x<<1 7 #define rx x<<1|1 8 #define reg register 9 #define PII pair 10 #define fi first 11 #define se second 12 #define pb push_back 13 int main(){ 14 int t; 15 cin>>t; 16 while(t--){ 17 int a,b,c,d; 18 cin>>a>>b>>c>>d; 19 puts(b+c>a+d?"AB//CD":"AB//DC"); 20 } 21 return 0; 22 }
H. Haeder Gcd Problem
题意
集合A和B都是{1,2,.....,n}的子集，A∩B≠∅。问A和B最多有多少对数GCD(Ap，Bq)>1。
题解
所有gcd>1的两个数肯定是倍数关系，最小肯定是本身和2倍。越大的数能和他匹配的就会越少，为了简单，从大的数往小的数匹配。先用线性筛O(n)预处理出1-n之间的质数，然后找到小于n的质数最大，并且要有至少一个数可以和他配对。从这个质数开始往下计算，如果有偶数个可以和该质数配对的，那就直接记录下来；如果是奇数个，最简单的方法是将这个数的二倍放弃，剩下的记录下来。因为是2的倍数，肯定存在，并且方便计算。
代码
1 #include<bits/stdc++.h> 2 #define ll long long 3 #define pb push_back 4 #define ft first 5 #define sd second 6 #define pii pair<int,int> 7 #define pll pair<ll,ll> 8 using namespace std; 9 10 ll st[200100]; 11 ll prime[200100]; 12 ll cnt; 13 14 void Prime(ll n) 15 { 16 cnt=0; 17 for(ll i=2;i<=n;i++){ 18 if(!st[i]) prime[cnt++]=i; 19 for(int j=0;prime[j]*i<=n;j++){ 20 st[prime[j]*i]=1; 21 if(i%prime[j]==0) break; 22 } 23 } 24 } 25 26 ll quick(int a,int b) 27 { 28 int res=1; 29 while(b){ 30 if(b&1) res=(res*a); 31 a=(a*a); 32 b>>=1; 33 } 34 return res; 35 } 36 37 bool vis[200100]; 38 vector<int>v[200100]; 39 40 int main() 41 { 42 ios::sync_with_stdio(false); 43 cin.tie(0); 44 cout.tie(0); 45 int t; 46 cin>>t; 47 Prime(200000); 48 while(t--){ 49 memset(vis,0,sizeof(vis)); 50 int n; 51 cin>>n; 52 for(int i=0;i<=n;i++) v[i].clear(); 53 int k=cnt-1; 54 for(int i=0;i<cnt;i++){ 55 if(prime[i]>n) {k=i-1;break;} 56 } 57 int ans=0; 58 for(int i=k;i>=0;i--){ 59 int p=n/prime[i],x=0; 60 for(int j=1;j<=n/prime[i];j++) 61 if(!vis[prime[i]*j]) x++; 62 if(x&1){ 63 int flag=0; 64 if(n/prime[i]<2) continue; 65 for(int j=1;j<=n/prime[i];j++){ 66 if(!flag&&!vis[prime[i]*j]&&(prime[i]*j)%2==0) flag=1; //删掉一个2的倍数 67 else if(!vis[prime[i]*j]) { 68 vis[prime[i]*j]=1; 69 v[i].push_back(prime[i]*j); 70 } 71 } 72 } 73 else{ 74 for(int j=1;j<=n/prime[i];j++) 75 if(!vis[prime[i]*j]) { 76 vis[prime[i]*j]=1; 77 v[i].push_back(prime[i]*j); 78 } 79 } 80 } 81 for(int i=0;i<=k;i++){ 82 ans+=v[i].size()/2; 83 } 84 cout<<ans<<endl; 85 for(int i=0;i<=k;i++){ 86 for(int j=1;j<v[i].size();j+=2){ 87 cout<<v[i][j-1]<<' '<<v[i][j]<<endl; 88 } 89 } 90 } 91 return 0; 92 }