Country Meow & Pyramid & Prime Game ICPC 2018 Nanjing R

[ICPC 2018 Nanjing R] Country Meow

题目链接： Country Meow 。

题目描述：

给 n≤100n\le 100 个三维点，求最小球覆盖的半径（精度 33 位即可）。

因为精度不高，于是三份套三分套三分。

代码：

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
#include <bits/stdc++.h>
using namespace std;
const int N=110;
const double eps=1e-8;
int n;
double x[N],y[N],z[N];
double dis(double x,double y,double z,double X,double Y,double Z){
    return sqrt((x-X)*(x-X)+(y-Y)*(y-Y)+(z-Z)*(z-Z));
}
double h(double X,double Y,double Z){
    double ans=0;
    for(int i=1;i<=n;i++)
        ans=max(ans,dis(X,Y,Z,x[i],y[i],z[i]));
    return ans;
}
double g(double x,double y){
    double l=-1.2e5,r=1.2e5;
    while(r-l>eps){
        double mid=(l*2+r)/3,mid2=(l+r*2)/3;
        if(h(x,y,mid)>h(x,y,mid2))l=mid;
        else r=mid2;
    }
    return h(x,y,l);
}
double f(double x){
    double l=-1.2e5,r=1.2e5;
    while(r-l>eps){
        double mid=(l*2+r)/3,mid2=(l+r*2)/3;
        if(g(x,mid)>g(x,mid2))l=mid;
        else r=mid2;
    }
    return g(x,l);
}
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
        scanf("%lf%lf%lf",x+i,y+i,z+i);
    double l=-1.2e5,r=1.2e5;
    while(r-l>eps){
        double mid=(l*2+r)/3,mid2=(l+r*2)/3;
        if(f(mid)>f(mid2))l=mid;
        else r=mid2;
    }
    printf("%.9lf",f(l));
    return 0;
}

[ICPC 2018 Nanjing R] Pyramid

/bangbangt

题目链接： [ICPC 2018 Nanjing R] Pyramid 。

题目描述：

nn 边长的正三角形中的格点正三角形计数。

T≤106,n≤109T\le 10^6,n\le 10^9 ，对 109+710^9+7 取模。

经典结论， (n+34)\binom{n+3}{4} 。

代码：

1
2
3
4
5
6
7
8
9
10
11
12
#include <bits/stdc++.h>
using namespace std;
int main(){
    long long T,n;
    scanf("%lld",&T);
    while(T--){
        scanf("%lld",&n);
        long long t=n*(n+1)%1000000007*(n+2)%1000000007*(n+3)%1000000007*41666667%1000000007;
        printf("%lld\n",t);
    }
    return 0;
}

[ICPC 2018 Nanjing R] Prime Game

题目链接： [ICPC 2018 Nanjing R] Prime Game 。

题目描述：

给定一个由 nn 个整数构成的序列 aia_i。

令 mul(l,r)=∏i=lrai\text{mul}(l, r) = \prod_{i = l}^{r} a_i，并令 fac(l,r)\text{fac}(l, r) 表示 mul(l,r)\text{mul}(l, r) 的不同质因子的个数。

请计算 ∑i=1n∑j=infac(i,j)\sum_{i = 1}^{n}\sum_{j = i}^{n}\text{fac}(i, j)。

n≤106n\le 10^6 。

一个子区间计算，考虑历史和。

根据历史和结论，我们只需要扫描线 i=1∼ni=1\sim n ，然后维护 aj=fac(i,j)a_j=\text{fac}(i,j) 就行。

这个可以看作是一个类似于“数颜色”的问题。将每一个质因子视为一个颜色。那么对每一个颜色统计最后一次出现的位置即可。

代码：

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
#include <bits/stdc++.h>
using namespace std;
const int N=1000010;
int n,a[N],book[N],p[N],cnt,cl[N];
vector<int>v[N];
void get_prime(int x){
    for(int i=2;i<=x;i++){
        if(!book[i]){
            p[++cnt]=i;
            for(int j=i;j<=x;j+=i)
                book[j]=1,v[j].push_back(cnt);
        }
    }
}
using ll=long long;
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++)scanf("%d",a+i);
    get_prime(1000000);
    ll ans=0,lst=0;
    for(int i=1;i<=n;i++){
        for(int j:v[a[i]])
            lst+=(i-cl[j]),cl[j]=i;
        ans+=lst;
    }
    printf("%lld",ans);
    return 0;
}