2020牛客暑期多校训练营（第四场）
BCFH
B. Basic God Problem
题意
给出c和n，求fc（n）。
题解
递归到最后 fc 函数肯定等于1，那么就变成了求c被乘了几次，只要找到 x 最多能被分解成多少个数相乘就好了。预处理用线性筛求出每个数最多能被分解成多少个数相乘，快速幂求出解。
代码
#include<bits/stdc++.h>
#define ll long long
#define pb push_back
#define ft first
#define sd second
#define pii pair<int,int>
#define pll pair<ll,ll>
using namespace std;
ll st[1001000];
ll prime[1001000];
ll d[1001000];
ll cnt;
const ll mod=1e9+7;
void Prime(ll n)
{
cnt=0;
for(ll i=2;i<=n;i++){
if(!st[i]) prime[cnt++]=i,d[i]=1;
for(int j=0;prime[j]*i<=n;j++){
st[prime[j]*i]=1;
d[prime[j]*i]=d[i]+1;
if(i%prime[j]==0) break;
}
}
}
ll quick(ll a,ll b)
{
ll res=1;
a=a%mod;
while(b){
if(b&1) res=(res*a)%mod;
a=(a*a)%mod;
b>>=1;
}
return res%mod;
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
Prime(1000000);
for(ll i=1;i<=10;i++) cout<<d[i]<<endl;
int t;
cin>>t;
while(t--){
ll n,c;
cin>>n>>c;
cout<<quick(c,d[n])<<endl;
}
return 0;
}
C. Count New String
题意
题解
出题人的题解：
• 核心点 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]这个是不起任何作用的。故问题就转换成了求%20(1%5Cleq%20x%5Cleq%20y%5Cleq%20n))
有多少本质不同的子串。这个问题不就是广义后缀自动机的经典题型了吗。但是如果对于所有的[x1,y1]都建立sam的话，肯定是不行的，于是就要用到别的办法。观察可以发现)
调用过程中任意一个位置的字符最多会被替换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
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int maxn=1e6+10;
struct state
{
int mxlen,link;
int cnt;
int nt[26];
}st[maxn<<1];
int sz,last,len;
char s[maxn];
inline void sam_init()
{
st[0].mxlen=0;
st[0].link=-1;
sz=1;
last=0;
}
inline void sam_extend(int c)
{
int cur=sz++;
st[cur].mxlen=st[last].mxlen+1;
st[cur].cnt=1;
int p=last;
while(p!=-1&&!st[p].nt[c]){
st[p].nt[c]=cur;
p=st[p].link;
}
if(p==-1) st[cur].link=0;
else{
int q=st[p].nt[c];
if(st[p].mxlen+1==st[q].mxlen) st[cur].link=q;
else{
int clone=sz++;
st[clone].mxlen=st[p].mxlen+1;
memcpy(st[clone].nt,st[q].nt,sizeof(st[q].nt));
st[clone].link=st[q].link;
while(p!=-1&&st[p].nt[c]==q){
st[p].nt[c]=clone;
p=st[p].link;
}
st[q].link=st[cur].link=clone;
}
}
last=cur;
}
int nt[maxn][10],id[maxn];
//nx[i][j]第i个位置(包括)后首次出现大于等于j的位置
int main()
{
cin>>s+1;
sam_init();
int n=strlen(s+1);
for(int i=0;i<10;i++) nt[n+1][i]=n+1;
for(int i=n;i>=1;i--){
for(int j=0;j<10;j++) nt[i][j]=nt[i+1][j];
nt[i][s[i]-'a']=i;
for(int j=8;j>=0;j--) nt[i][j]=min(nt[i][j],nt[i][j+1]);
}
id[n+1]=last;
for(int i=n;i>=1;i--){
int pos=nt[i+1][s[i]-'a'];
last=id[pos];
for(int j=i;j<pos;j++) sam_extend(s[i]-'a');
id[i]=last;
}
ll ans=0;
for(int i=1;i<=sz;i++){
ans+=st[i].mxlen-st[st[i].link].mxlen;
}
cout<<ans<<endl;
return 0;
}
单调队列+SAM
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int maxn=1e6+10;
struct state
{
int mxlen,link;
int cnt;
int nt[26];
}st[maxn<<1];
int sz,last,len;
char s[maxn];
inline void sam_init()
{
st[0].mxlen=0;
st[0].link=-1;
sz=1;
last=0;
}
inline void sam_extend(int c)
{
int cur=sz++;
st[cur].mxlen=st[last].mxlen+1;
st[cur].cnt=1;
int p=last;
while(p!=-1&&!st[p].nt[c]){
st[p].nt[c]=cur;
p=st[p].link;
}
if(p==-1) st[cur].link=0;
else{
int q=st[p].nt[c];
if(st[p].mxlen+1==st[q].mxlen) st[cur].link=q;
else{
int clone=sz++;
st[clone].mxlen=st[p].mxlen+1;
memcpy(st[clone].nt,st[q].nt,sizeof(st[q].nt));
st[clone].link=st[q].link;
while(p!=-1&&st[p].nt[c]==q){
st[p].nt[c]=clone;
p=st[p].link;
}
st[q].link=st[cur].link=clone;
}
}
last=cur;
}
int id[maxn];
int main()
{
cin>>s+1;
sam_init();
int n=strlen(s+1);
stack<int>ss;
ss.push(n+1);
id[n+1]=last;
for(int i=n;i>=1;i--){
while(ss.size()!=1&&s[ss.top()]<s[i]) ss.pop();
int pos=ss.top();
last=id[pos];
for(int j=i;j<pos;j++) sam_extend(s[i]-'a');
id[i]=last;
ss.push(i);
}
ll ans=0;
for(int i=1;i<=sz;i++){
ans+=st[i].mxlen-st[st[i].link].mxlen;
}
cout<<ans<<endl;
return 0;
}
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了。
代码
菜鸡本人的代码
#include<bits/stdc++.h>
#define ll long long
#define pb push_back
#define ft first
#define sd second
#define pii pair<int,int>
#define pll pair<ll,ll>
using namespace std;
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int t;
cin>>t;
while(t--){
int a,b,c,d;
cin>>a>>b>>c>>d;
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;
else cout<<"AB//DC"<<endl;
}
return 0;
} 巨巨的代码
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e3+5,M=2e4+5,inf=0x3f3f3f3f,mod=1e9+7;
#define mst(a) memset(a,0,sizeof a)
#define lx x<<1
#define rx x<<1|1
#define reg register
#define PII pair
#define fi first
#define se second
#define pb push_back
int main(){
int t;
cin>>t;
while(t--){
int a,b,c,d;
cin>>a>>b>>c>>d;
puts(b+c>a+d?"AB//CD":"AB//DC");
}
return 0;
}
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的倍数，肯定存在，并且方便计算。
代码
#include<bits/stdc++.h>
#define ll long long
#define pb push_back
#define ft first
#define sd second
#define pii pair<int,int>
#define pll pair<ll,ll>
using namespace std;
ll st[200100];
ll prime[200100];
ll cnt;
void Prime(ll n)
{
cnt=0;
for(ll i=2;i<=n;i++){
if(!st[i]) prime[cnt++]=i;
for(int j=0;prime[j]*i<=n;j++){
st[prime[j]*i]=1;
if(i%prime[j]==0) break;
}
}
}
ll quick(int a,int b)
{
int res=1;
while(b){
if(b&1) res=(res*a);
a=(a*a);
b>>=1;
}
return res;
}
bool vis[200100];
vector<int>v[200100];
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int t;
cin>>t;
Prime(200000);
while(t--){
memset(vis,0,sizeof(vis));
int n;
cin>>n;
for(int i=0;i<=n;i++) v[i].clear();
int k=cnt-1;
for(int i=0;i<cnt;i++){
if(prime[i]>n) {k=i-1;break;}
}
int ans=0;
for(int i=k;i>=0;i--){
int p=n/prime[i],x=0;
for(int j=1;j<=n/prime[i];j++)
if(!vis[prime[i]*j]) x++;
if(x&1){
int flag=0;
if(n/prime[i]<2) continue;
for(int j=1;j<=n/prime[i];j++){
if(!flag&&!vis[prime[i]*j]&&(prime[i]*j)%2==0) flag=1; //删掉一个2的倍数
else if(!vis[prime[i]*j]) {
vis[prime[i]*j]=1;
v[i].push_back(prime[i]*j);
}
}
}
else{
for(int j=1;j<=n/prime[i];j++)
if(!vis[prime[i]*j]) {
vis[prime[i]*j]=1;
v[i].push_back(prime[i]*j);
}
}
}
for(int i=0;i<=k;i++){
ans+=v[i].size()/2;
}
cout<<ans<<endl;
for(int i=0;i<=k;i++){
for(int j=1;j<v[i].size();j+=2){
cout<<v[i][j-1]<<' '<<v[i][j]<<endl;
}
}
}
return 0;
} 
