7.20 节目效果拉满的牛客4
B-Basic Gcd Problem
题意
定义函数 f 在 x>1f_c(x)=max_{i=1…x-1}c*f_c(gcd(i,x))，在 x=1 时 f_c(x)=1，给定 c 和 x，求 f
思路
即求 c 的 x 因子个数次方
代码
代码语言：javascript复制#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("1n");
return pf("%lldn",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 去重一个道理。
代码
代码语言：javascript复制#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("%lldn",ans);
}
int main(){
/* int _; sc(_); while(_--) */ solve();
}D-Dividing Strings
题意
给定一个数字串，问怎么划分能使划分中的数字最大最小差值最小。划分的串不能包含前导零。
思路
模拟。每个串先拆为等长的数字串，枚举因数取 min 。再考虑进位情况：如果进位是三位即以上，找 10 开头的子串，到结尾/下一个 9 /下一个 10 为止，取为一个单位长度。如果进位是两位，一个 1 后面跟上一个数，剩下的全取个位数。注意当 1 为末尾的时候要判掉。
代码
代码语言：javascript复制#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("%dn",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("%dn",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 的倍数个数是最多的。
代码
代码语言：javascript复制#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("%dn",ans.size());
for(pii x:ans) pf("%d %dn",x.first,x.second);
rep(i,1,n 1) vis[i]=0,vv[i].clear();
}
int main(){
int _; sc(_); while(_--) solve();
}
