2020牛客暑期多校训练营(第四场)

7.20 节目效果拉满的牛客4

B-Basic Gcd Problem

题意

定义函数 $f$ 在 $x>1$ 有 $f_c(x)=\max_{i=1…x-1}c*f_c(gcd(i,x))$,在 $x=1$ 时 $f_c(x)=1$,给定 $c$ 和 $x$,求 $f$

思路

即求 $c$ 的 $x$ 因子个数次方

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
#include<bits/stdc++.h>
#define pf printf
#define sc(x) scanf("%d", &x)
#define mst(a,x) memset(a, x, sizeof(a))
#define rep(i,s,e) for(int i=s; i<e; ++i)
#define dep(i,e,s) for(int i=e; i>=s; --i)
using namespace std;
typedef long long ll;
const int maxn = 1e6 + 5;
const int mod = 1e9 + 7;
int p[maxn],vis[maxn],pn;
void init(){
rep(i,2,maxn){
if(!vis[i]) p[pn++]=i;
for(int j=0;j<pn&&i*p[j]<maxn;j++) vis[i*p[j]]=1;
} mst(vis,0);
}
ll qpow(ll a,ll b){
ll ans=1; while(b>0){
if(b&1) ans=ans*a%mod;
b>>=1; a=a*a%mod;
} return ans;
}
ll cnt[maxn];
void dfs(int x){
if(x==1){ cnt[x]=0,vis[x]=1; return;}
rep(i,0,pn){
if(p[i]*p[i]>x) break;
if(x%p[i]==0){
if(!vis[x/p[i]]) dfs(x/p[i]);
cnt[x]=cnt[x/p[i]]+1,vis[x]=1;
return;
}
} cnt[x]=1,vis[x]=1;
}
int solve(){
int n,c; sc(n); sc(c);
if(n==1) return pf("1\n");
return pf("%lld\n",qpow(c,cnt[n]));
}
int main(){
init(); dep(i,1e6,1) if(!vis[i]) dfs(i);
int _; sc(_); while(_--) solve();
}

C-Count New String

题意

给定一个字符串,求此字符串的前缀最大值的前缀最大值的本质不同子串个数。

思路

参考 出来看神仙.jpg 代码。太牛了!!!永远滴神!!!

《叛逆小转偏偏要乱搞过板子题》

倒着处理。每次和后一位对比,如果比后一位小或者和后一位一样,那后面已经不会有变化了,所以只用加上包含当前位的所有方案数;如果比后一位大,那就需要更新,更新到和此位一样或者更大的位置。$t$ 记录的是这个位数差。每次更新答案就是 $1+d$ 到 $t+d$ 的等差为 $1$ 的数列求和,其中 $d=len-i-t+1$。

同时每次记录当前状态。其实和 $sa$ 的最后相邻 $lcp$ 去重一个道理。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
#include<bits/stdc++.h>
#define pf printf
#define scs(x) scanf("%s", x)
#define rep(i,s,e) for(int i=(s); i<(e); ++i)
#define dep(i,e,s) for(int i=(e); i>=(s); --i)
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const int maxn = 1e5 + 5;
char s[maxn];
vector<vector<int>>vv;
int solve(){
scs(s+1); int len=strlen(s+1);
vector<int>tmp(10); s[len+1]='z'+1;
ll ans(0); dep(i,len,1){
int val=s[i]-'a',t(0);
rep(j,0,val) t+=tmp[j]; t++;
if(s[i]<=s[i+1]){
ans+=len-i+1;
tmp[val]++;
vv.push_back(tmp);
}
else if(s[i]>s[i+1]){
rep(j,0,val) tmp[j]=0;
rep(j,0,t){
tmp[val]++;
vv.push_back(tmp);
} ans+=1ll*t*(t+(len-i-t+1)*2+1)/2;
}
// 如果前一位是大的 说明后面要更新
// 更新到不用更新的地方的串数量
// 如果是小的 只用加上包含此位的所有串数量
} // 去重 相邻的lcp
sort(vv.begin(),vv.end());
rep(i,1,vv.size()) rep(j,0,10){
ans-=min(vv[i-1][j],vv[i][j]);
if(vv[i-1][j]!=vv[i][j]) break;
} return pf("%lld\n",ans);
}
int main(){
/* int _; sc(_); while(_--) */ solve();
}

D-Dividing Strings

题意

给定一个数字串,问怎么划分能使划分中的数字最大最小差值最小。划分的串不能包含前导零。

思路

模拟。每个串先拆为等长的数字串,枚举因数取 $min$ 。再考虑进位情况:如果进位是三位即以上,找 $10$ 开头的子串,到结尾/下一个 $9$ /下一个 $10$ 为止,取为一个单位长度。如果进位是两位,一个 $1$ 后面跟上一个数,剩下的全取个位数。注意当 $1$ 为末尾的时候要判掉。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
#include<bits/stdc++.h>
#define pf printf
#define sc(x) scanf("%d", &x)
#define scs(x) scanf("%s", x)
#define rep(i,s,e) for(int i=(s); i<(e); ++i)
using namespace std;
const int maxn = 1e5 + 5;
int n; char s[maxn];
int qaq(){
int len(0); rep(i,1,n-1) if(s[i]=='1'&&s[i+1]=='0'){
rep(j,i+2,n+2) if(j==n+1||s[j]=='9'||(s[j]=='1'&&s[j+1]=='0')){
len=j-i; break;
} break;
} if(len<=2||len==n) return 9;
int mn(0),mx(0),t(0),ff(0);
rep(i,1,n+1) if(ff){
if(ff>0) t=t*10+s[i]-'0',ff++;
else t=t*10-s[i]+'0',ff--;
if(t>=9) return 9;
if(abs(ff)==len){
if(ff<0) mn=max(mn,t);
else mx=max(mx,t);
t=0; ff=0;
}
} else{
if(s[i]=='1') ff=1,t=0;
else if(s[i]=='9') ff=-2,t=1;
else return 9;
} if(ff) return 9;
return mn+mx;
}
int qwq(){
int mn=1e9,mx(0),t(0);
rep(i,1,n+1){
if(t) mx=max(mx,t*10+s[i]-'0'),t=0;
else if(s[i]=='1'&&i!=n) t=1;
else mn=min(mn,(int)s[i]-'0');
} if(mn==1e9||!mx) return 9;
return mx-mn;
}
int slove(int x){
int mn(0),mx(0),t(0),c=1;
rep(i,x+1,n+1){
if(i%x==1&&s[i]=='0') return 9;
t=t*10+s[i]-s[i-c*x];
if(abs(t)>=9) return 9;
if(i%x==0){
if(t<0) mn=max(mn,-t);
else mx=max(mx,t);
c++; t=0;
}
} return mn+mx;
}
int solve(){
sc(n); scs(s+1);
char a='9'+1,b='0'-1;
rep(i,1,n+1) a=min(a,s[i]),b=max(b,s[i]);
int mn=b-a; if(s[1]=='0') return pf("%d\n",mn);
for(int i=2;i*i<=n;++i) if(n%i==0){
mn=min(mn,slove(i));
if(i*i!=n) mn=min(mn,slove(n/i));
} mn=min(mn,qaq()); mn=min(mn,qwq());
return pf("%d\n",mn);
}
int main(){
int _; sc(_); while(_--) solve();
}

H-Harder Gcd Problem

题意

将 $1-n$ 不重复地放入两个无交集的集合 $A$ 、$B$且满足所有 $gcd(A[i],B[i])>1$ ,问最大对数

思路

$1$ 到 $n$ 分解质因数。将所有有同一个质因数的放进同一个 $vector$ ,倒着两两匹配。使用过的数打上标记,没使用过的数存进临时使用的 $vector$ 。如果有奇数个,考虑剩一个偶数出来。因为 $2$ 是最小的质数,$2$ 的倍数个数是最多的。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
#include<bits/stdc++.h>
#define pf printf
#define sc(x) scanf("%d", &x)
#define mst(a,x) memset(a, x, sizeof(a))
#define rep(i,s,e) for(int i=s; i<e; ++i)
#define dep(i,e,s) for(int i=e; i>=s; --i)
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const int maxn = 2e5 + 5;
vector<int>vv[maxn];
void init(int x){
int x1=x;
vv[x].push_back(x);
rep(i,2,x+1){
if(i*i>x) break;
if(x%i==0){
vv[i].push_back(x1);
while(x%i==0) x/=i;
}
} if(x>1&&x!=x1) vv[x].push_back(x1);
}
int vis[maxn];
vector<pii>ans;
void solve(){
int n; sc(n); rep(i,1,n+1) init(i);
ans.clear(); dep(i,n,2){
if(vv[i].size()<=1) continue;
int cnt(0),tt(0); vector<int>tmp;
rep(j,0,vv[i].size()){
int x=vv[i][j];
if(!vis[x]){
tmp.push_back(x);
if(x%2==0) tt=x;
}
} int sz=tmp.size();
if(sz%2&&tt){
vector<int>::iterator it;
for(it=tmp.begin();it!=tmp.end();++it){
if(*it==tt) tmp.erase(it),--it;
} sz--;
} if(sz<=1) continue;
rep(j,0,sz){
int x=tmp[j],y=tmp[j+1];
vis[x]=vis[y]=1,j++;
ans.push_back(pii(x,y));
}
} pf("%d\n",ans.size());
for(pii x:ans) pf("%d %d\n",x.first,x.second);
rep(i,1,n+1) vis[i]=0,vv[i].clear();
}
int main(){
int _; sc(_); while(_--) solve();
}