牛客 周赛101 20250726
https://ac.nowcoder.com/acm/contest/113313
A：
题目大意：
void solve(){int a;cin>>a;cout<<fixed<<setprecision(6)<<(double)150*log(a);
}
签到
B：
题目大意：
void solve(){int n;cin>>n;int a=0,b=0,c=0,d=0;for (int i=1;i<=n;i++){if (i>=5&&i%5==0) a+=2;if (i>=5&&(i-5)%10==0) b+=1;if (i>=20&&i%20==0) c+=3;else (d+=2); }cout<<a<<' '<<b<<' '<<c<<' '<<d;
}
模拟题
C：
题目大意：给定 \(n\) ，从 \([1,n]\) 的排列中选取任意个数进行异或操作，输出最大的异或值
void solve(){LL n;cin>>n;int d=log2(n)+1;cout<<(LL)pow(2,d)-1<<endl;
}
显然 \([1,n]\) 能构成的最大异或数是 \([1,n]\) 上能组成的每个二进制位上全 \(1\) 的数
D：
题目大意：
void solve(){int n,m;cin>>n>>m;if (!(m&1)){cout<<-1<<endl;return;}if (n==2&&m==1){cout<<"1 2"<<'\n'<<1<<'\n'<<1<<' '<<2;return;}set<int> res;for (int i=0;i<=20;i++)if (m&(1<<i)) res.insert((1<<i));if (*res.rbegin()>n){cout<<-1<<endl;return;}for (int i=1;i<=n;i++) if (res.count(i)) cout<<i<<' ';for (int i=1;i<=n;i++) if (!res.count(i)) cout<<i<<' ';if (res.size()==n){cout<<'\n'<<res.size()<<'\n';for (int i=1;i<=res.size();i++) cout<<i<<' '<<i<<'\n'; }else{cout<<'\n'<<res.size()+1<<'\n';for (int i=1;i<=res.size();i++) cout<<i<<' '<<i<<'\n';cout<<res.size()+1<<' '<<n<<'\n';}}
二进制拆位，将 \(m\) 拆分为多个 \(2\) 的整数次幂构成的数，将这些数单独拿出来构成一个部分
排列中剩余的数构成单独的一个部分，这些剩下的数的 \(\mathrm{gcd}\) 一定为 \(1\)
并且因为任意两个奇偶数的 \(\mathrm{gcd}\) 都为 \(1\) ，那么给定的 \(m\) 一定不能为偶数，因为 \(1\) 需要被或上
注意 \(n=2,m=1\) 时需要特判
E：
题目大意：
void solve(){int n;cin>>n;vector<pair<double,double>> p(n);for (int i=0;i<n;i++)cin>>p[i].first>>p[i].second;vector<double> d(n);for (int i=0;i<n-1;i++)d[i]=sqrt((p[i+1].first-p[i].first)*(p[i+1].first-p[i].first)+(p[i+1].second-p[i].second)*(p[i+1].second-p[i].second));const double ln2=log(2)/log(2.718281828);auto judge=[&](double mid,double dis){double f=2.0-2*dis*ln2/pow(2,mid);return f<0;};auto makef=[&](double k,double dis){double res=2*k+2*dis/pow(2,k);return res;};vector<double> vk;for (int i=0;i<n-1;i++){double l=0,r=10;while (r-l>0.000001){double mid=(l+r)/2;if (judge(mid,d[i])) l=mid;else r=mid;}vk.push_back(l);}double ans=0;for (int i=0;i<n-1;i++)ans+=makef(vk[i],d[i]);printf("%lf",ans);
}
\(t_i=2k^i+2e_i/2^{k_i}\) ，需要使得 \(t_i\) 最小化。不难看出这时一个单谷函数，所以利用三分或者求导后计算极值点
\[\frac{\mathrm{d} t_i}{\mathrm{d} k_i}=2-\frac{2\ln 2\cdot e_i}{2^{k_i}}
\]
对于每个地点之间的欧式距离 \(e_i\) ，都利用二分计算 \(0\) 点，这个点一定是原函数的极小值点，最后累加答案即可
F：
题目大意：
const int N=1e6+10;LL ksm(LL a,LL b,LL p){LL res=1;while (b){if (b&1) res=res*a%p;a=a*a%p;b>>=1;}return res;
}void solve(){vector<LL> c(N);LL base,mod;cin>>base>>c[0]>>mod;map<LL,int> mp;mp[c[0]]=0;int st,ed;for (int i=1;i<N;i++){c[i]=ksm(base%mod,c[i-1],mod);if (mp.count(c[i])){st=mp[c[i]];ed=i;break;}mp[c[i]]=i;}LL lamd=ed-st;vector<LL> loop;loop.push_back(0);for (int i=st;i<ed;i++)loop.push_back(c[i]);vector<LL> preloop(loop);for (int i=1;i<preloop.size();i++)preloop[i]=(preloop[i-1]+loop[i])%mod;vector<LL> prec(max(1,st));prec[0]=0;for (int i=1;i<st;i++)prec[i]=(prec[i-1]+c[i])%mod;int q;cin>>q;while (q--){LL k;cin>>k;LL ans=(st==0?-c[0]:0);if (k<st){ans=(ans+prec[k]+mod)%mod;cout<<ans<<endl;continue;}LL cslt=(k-st+1)/lamd%mod;LL rmde=(k-st+1)%lamd%mod;LL sum=cslt*preloop.back()%mod+preloop[rmde];ans=(ans+(prec.back()+sum%mod)%mod+mod)%mod;cout<<ans<<endl;}
}
因为 \(mod\in[1,10^6]\) ，说明在可以接受的范围内存在循环
找到循环后计算循环内和循环前两部分的前缀和（循环可能从某一位才开始），注意当循环从 \(0\) 就开始时答案需要多减去一个 \(c_0\)
因为需要计算的是 \(\sum_{i=1}^k c_i\) ，特别的，因为可能循环节的长度比较小而 \(k\) 很大，那么计算有多少个完整的循环时就需要取模