2021牛客多校第二场题解
K题
题目大意：给出n,k，表示一共n个数，生成单调栈序列b，接下来k行每行输入p和v表示b[p] = v，请写出一个满足要求的序列。n<1e6。
思路：k可能小于n，那么将b数组都填满，按如下的规则：若当前b有值，则从此位置到前一个有值的b之间填充b[i]-1,b[i]-2......，最后一个有值的b右边都用最后一个b的值填充。比如已知b[2]=2,b[5]=4,则完整的填充序列为1,2,2,3,4。
接下来按从小到大，从右到左的原则排序并赋值。
ac代码：
#include <bits/stdc++.h>
using namespace std;
const int N = 5e6+6;
int b[N],a[N];
bitset<N> vis;
struct node{
int id,v,ans;
bool operator<(const node&t)const{
if(v == t.v)return id > t.id;
return v < t.v;
}
}c[N];
bool cmp(node t1,node t2){
return t1.id<t2.id;
}
int main(){
int n,k;
scanf("%d%d",&n,&k);
for(int i = 1;i <= k;i++){
int p,v;
scanf("%d%d",&p,&v);
b[p] = v,vis[p] = true;
}
for(int i = 1;i <= n;i++)
if(vis[i])
for(int j = i - 1;j >= 1&&!vis[j];j--)
b[j] = max(1,b[j + 1] - 1);
for(int i = 1;i <= n;i++)
if(!b[i])b[i] = b[i - 1];
int f = 0;
for(int i = 2;i <= n;i++)
if(b[i] >1 + b[i - 1]){
f = 1;
break;
}
if(b[1]>1)f = 1;
if(f){
cout << "-1" << endl;
}
else{
for(int i = 1;i <= n;i++)
c[i].id = i,c[i].v = b[i];
sort(c+1,c+n+1);
int idx = 1;
for(int i = 1;i <= n;i++)c[i].ans = idx++;
sort(c+1,c+1+n,cmp);
for(int i = 1;i <= n;i++)printf("%d ",c[i].ans);
printf("\n");
}
return 0;
}p.s. 当时没有想到填满b数组，其实如果不填满b数组，b[2]=2和b[2]=3得到的序列可能一样，这并不是我们想要的答案。
J题
题目大意：t组输入，每组给出s,k,p,有s个数，求所有大小为k的子集中，每个子集的所有元素的最大公约数，输出它们的乘积。t<=60,s<=4e4,k<=30,1e6<=p<=1e14.
思路：用容斥原理求出每个数作为最大公约数可以出现在几个集合中。如i作为最大公约数出现在ki个集合中，则本题要求的是∏(i=1,i=maxn)(i ^ ki)，其中maxn为s个数中的最大值。由于p较大且不一定为质数，考虑用欧拉降幂(a ^ b(mod m)=a ^ (b mod phi + phi) mod m)，其中phi为b的欧拉函数值。
ac代码（玄学，同样的代码有可能1001ms也有可能800ms，看评测机发挥了）
#include <bits/stdc++.h>
using namespace std;
const int N = 8e4+4;
typedef long long LL;
LL cnt[N];
LL c[N][35],dp[N];
LL S,k,res,phi;
int T;
LL P;
LL total = 0,factor[100];
//LL euler_phi(LL n) {
// LL ans = n;
// for (LL i = 2; i * i <= n; i++)
// if (n % i == 0) {
// ans = ans / i * (i - 1);
// while (n % i == 0) n /= i;
// }
// if (n > 1) ans = ans / n * (n - 1);
// return ans;
//}
LL ksc(LL a, LL b, LL mod) {
return ((a * b - (long long)((long long)((long double)a / mod * b + 1e-3) * mod)) % mod + mod) % mod;
}
LL gcd(LL a,LL b){
return b==0?a:gcd(b,a%b);
}
//LL ksc(LL a,LL b,LL c){
// LL res = 0;
// while(b){
// if(b&1)res = (res + a)%c;
// a = (a + a)%c;
// b>>=1;
// }
// return res%c;
//}
LL ksm(LL a,LL b,LL c){
LL res = 1;
while(b){
if(b&1)res =ksc(res,a,c);
b >>= 1;
a = ksc(a,a,c);
}
return res%c;
}
//LL ksm(LL a,LL b,LL c){
// LL res = 1;
// while(b){
// if(b&1)res = ksc(res,a,c);
// b >>= 1;
// a = ksc(a,a,c);
// }
// return res%c;
//}
int a[] = { 2, 3, 5, 7, 11 };
bool miller_rabin(LL n) {
if (n == 1) return 0;
for (int i = 0; i < 5; ++i) {
if (n == a[i]) return 1;
if (!(n % a[i])) return 0;
}
LL d = n - 1;
while (!(d & 1)) d >>= 1;
for (int i = 1; i <= 5; ++i) {
LL a = rand() % (n - 2) + 2;
bool tmp_k = false;
LL tmp_d = d;
LL tmp = ksm(a, tmp_d, n);
if (tmp == 1) tmp_k = true;
// 先把所有的2给提出来，然后在一个一个乘上去，这样比直接做快
while (tmp != 1 && tmp != n - 1 && tmp_d != n - 1) {
tmp = ksc(tmp, tmp, n);
tmp_d <<= 1;
}// 二次探测
if (tmp == n - 1) tmp_k = true;
if (!tmp_k)
return 0;
}
return 1;
}
// 找出n的一个因数
const int M = (1 << 7) - 1;// 一个玄学值
LL pollard_rho(LL n) {
for (int i = 0; i < 5; ++i) if (n % a[i] == 0) return a[i];
LL x = rand(), y = x, t = 1, a = rand() % (n - 2) + 2;
for (int k = 2; ; k <<= 1, y = x) {
LL q = 1;
// k用于倍增
for (int i = 1; i <= k; ++i) {
x = (ksc(x, x, n) + a) % n;// f(x) = x^2+a
q = ksc(q, abs(x - y), n);// 每一次的|x-y|累加
// 如果次数超过M
if (!(i & M)) {
t = gcd(q, n);
if (t > 1) break;
}
}
if (t > 1 || (t = gcd(q, n)) > 1) break;
}
return t;
}
// 找出x的所有因数
void find(LL x) {
if (x == 1 || x <= 0) return;
if (miller_rabin(x)) {
factor[++total] = x;
return;
}
LL p = x;
while (p == x) p = pollard_rho(x);
while (x % p == 0) x /= p;
find(p);// 递归遍历所有的因数
find(x);
}
LL C(LL n,LL k){
if (n < k)return 0;
return c[n][k];
}
inline LL read() {
LL s = 0;
char ch = getchar();
while (ch < 48 || ch>57)ch = getchar();
while (ch > 47 && ch < 58)s = (s << 1) + (s << 3) + (ch ^ 48), ch = getchar();
return s;
}
int main(){
// scanf("%d",&T);
T = read();
while(T--){
memset(cnt,0,sizeof cnt);
// scanf("%lld%lld%lld",&S,&k,&P);
S = read(),k = read(),P = read();
int maxn = 0;
for(int i = 1;i <= S;i++){
int tm;
// scanf("%d",&tm);
tm = read();
cnt[tm]++;
maxn = max(maxn,tm);
}
res = 1;
total = 0;
find(P);// 寻找p的约数
phi = P;// 计算phi(p)
for (int i = 1; i <= total; i++) {
phi = phi / factor[i] * (factor[i] - 1);
}
c[0][0] = 1;
for (int i = 1; i <= S; i++) {
c[i][0] = 1;
if (i <= 31) c[i][i] = 1;
// k的值不会超过30，不需要计算更多位
for (int j = 1; j < i && j <= 31; j++) {
c[i][j] = (c[i - 1][j] + c[i - 1][j - 1]);// 组合数的递推公式
while (c[i][j] - phi >= phi) c[i][j] -= phi;
}
}
// for (int i = 0; i <= S; i ++ )
// for (int j = 0; j <= 30&&j<=i; j ++ )
// if (!j) c[i][j] = 1;
// else c[i][j] = (c[i - 1][j] + c[i - 1][j - 1])%phi;
for(int i = maxn;i >= 1;i--){
int tp = 0;
for(int j = i;j <= maxn;j+=i){
tp+=cnt[j];
}
dp[i] = C(tp,k)%phi;
for(int j = i + i;j <= maxn;j+=i){
dp[i]-=dp[j];
}
if(dp[i]<0)dp[i] = (dp[i]%phi + phi)%phi;
if(dp[i]>phi)res = ksc(res,(ksm(i,dp[i]%phi+phi,P)),P);
else res = ksc(res,(ksm(i,dp[i],P)),P);
}
printf("%lld\n",res);
}
return 0;
}p.s. 真的是一言难尽，从写完第一份到debug完，前前后后四个小时。factor数组记得开long long；快速乘的玄学写法，很快；米勒罗宾素数筛当板子用了，求某个大数的欧拉函数；大体思路都没问题了就慢慢调整细节，尝试各种写法，说不定就快个几十ms就卡过了。
F题
题目大意：给出三维的四个点ABCD的坐标和k1,k2，要求求出同时满足|AP|>=k1|BP|,|CP|>=k2|DP|的点P的可取的区域的体积。
思路：推式子，设A(x1,y1,z1),B(x2,y2,z2),p(x,y,z),则有(x-x1)²+(y-y1)²+(z-z1)²>=k1²[(x-x2)²+(y-y2)²+(z-z2)²],整理可得(k1² - 1)(x² + y² + z²)-(2k1²x2 - 2x1)x - (2k1²y2 - 2y1)y - (2k1²z2 - 2z1)z <= 0，我们发现这是形如x²+y²+z²+Ax+By+Cz+D<=0的球面方程，而该方程的几何意义是P为该球体内部(含边界)的点。该球体半径为sqrt((A² + B² + C² - 4*D)/4)，球心为(-A/2,-B/2,-C/2)。接下来分情况讨论：两球相切、包含、相交。
ac代码：
#include <bits/stdc++.h>
using namespace std;
const int N = 1010;
const double pi = acos(-1);
int t;
double x[4],y[4],z[4],k1,k2;
int main(){
scanf("%d",&t);
while(t--){
for(int i = 0;i < 4;i++)scanf("%lf%lf%lf",&x[i],&y[i],&z[i]);
scanf("%lf%lf",&k1,&k2);
double k11 = k1*k1-1,c1x,c1y,c1z,r1;
c1x = (k1*k1*x[1]-x[0])/k11,c1y = (k1*k1*y[1]-y[0])/k11,c1z = (k1*k1*z[1]-z[0])/k11;
r1 = sqrt(c1x*c1x+c1y*c1y+c1z*c1z-(k1*k1*((x[1]*x[1])+(y[1]*y[1])+(z[1]*z[1]))-x[0]*x[0]-y[0]*y[0]-z[0]*z[0])/k11);
double k22 = k2*k2-1,c2x,c2y,c2z,r2;
c2x = (k2*k2*x[3]-x[2])/k22,c2y = (k2*k2*y[3]-y[2])/k22,c2z = (k2*k2*z[3]-z[2])/k22;
r2 = sqrt(c2x*c2x+c2y*c2y+c2z*c2z-(k2*k2*((x[3]*x[3])+(y[3]*y[3])+(z[3]*z[3]))-x[2]*x[2]-y[2]*y[2]-z[2]*z[2])/k22);
double dis = sqrt((c1x-c2x)*(c1x-c2x)+(c1y-c2y)*(c1y-c2y)+(c1z-c2z)*(c1z-c2z));
double ans = 0.000;
if(dis>=r1+r2)ans = 0;
else if(dis + r1 <= r2)ans = (4.000/3.000)*pi*r1*r1*r1;
else if(dis + r2 <= r1)ans = (4.000/3.000)*pi*r2*r2*r2;
else{
double h1 = r1*(1-(r1*r1+dis*dis-r2*r2)/(2.000*dis*r1));//余弦定理求角度，再算h
double h2 = r2*(1-(r2*r2+dis*dis-r1*r1)/(2.000*dis*r2));
ans+=(1.000/3.000)*pi*((3.000*r1-h1)*h1*h1+(3.000*r2-h2)*h2*h2);
}
printf("%.3f\n",ans);
}
return 0;
}p.s. 赛场上没来得及看这个题...补题的时候感觉挺可做的。学习了球缺的计算公式：V=pih²(3R-h)/3，其中h为球缺（那个小片）的高，R为球的半径。注意求h的时候要用余弦定理间接求一下，不能草率的直接用(r1+r2-dis)/2，因为球的半径是不一定一样大，不一定能均分滴~
投递淘天集团等公司10个岗位 >
