2020 CCPC Wannafly camp day5 题解

Solved	A	B	C	D	E	F	G	H	I	J
9/10	O	O	Ø	Ø	O	.	O	O	O	O

O for passing during the contest
Ø for passing after the contest
! for attempted but failed
· for having not attempted yet

比赛链接

A

题目描述
有$k\in [1,3]$场比赛，$n\in [1,10^5]$个账号，给定每场比赛中出现的账号。一个人可以有多个号，但在一场比赛中只能最多使用一个号。问这$n$个账号里最少有多少人。

解题思路
因为$k$很小，对$k$分类讨论。设参加的比赛集合为$S$的账号个数为$num[S]$。

$k=1$：所有参赛账号都是单独的人，答案为$num[1]$。

$k=2$：只参加第一场的和只参加第二场的合并，答案为$num[3]+max(num[2],num[1])$。

$k=3$：先把只参加一场的和只参加两场的合并，再把多出来的只参加一场的合并，实现时可以先把参加两场的全计入答案，然后把参加一场的对应减少，最后取$max$即可。

AC代码
点击
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
#include<cstdio>
#include<algorithm>
#include<queue>
#include<map>
#include<cstring>
#include<cmath>
#include<cstdlib>
#include<set>
#include<unordered_map>
#include<vector>
typedef long long ll;
using namespace std;
int n,k,m,state[100010];
int num[10];
int main(){
    int i;
    scanf("%d%d",&n,&k);
    for(i=0;i<k;i++){
        scanf("%d",&m);
        while(m--){
            int x;
            scanf("%d",&x);
            state[x]+=1<<i;
        }
    }
    for(i=1;i<=n;i++)num[state[i]]++;
    if(k==1)printf("%d\n",num[1]);
    else if(k==2)printf("%d\n",num[3]+max(num[1],num[2]));
    else{
        int ans=0;
        for(i=0;i<3;i++){
            int now=1<<i,op=(1<<3)-1-(1<<i);
            ans+=num[op];
            if(num[op]<=num[now])num[now]-=num[op];
            else num[now]=0;
        }
        printf("%d\n",ans+num[7]+max(max(num[1],num[2]),num[4]));
    }
    return 0;
}

B

题目描述
有一个$n\leq 5\times 10^5$个点的树，点标号为$1,2,…,n$，每个点初始有一个集合$S_p=${$p$}，边为$p_1,p_2,…,p_{n-1}$，分别连接$u_i,v_i$。

进行$m$次操作，每次操作选一个$p_k$，使得$S_{u_i},S_{v_i}$改变为他们的并集。问最后对于每个$i$，出现在多少个集合中。

解题思路
维护一个节点能够到达的集合大小$ans[p]$，从后向前递推并维护边对应历史大小即可。

AC代码
点击
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<cstdio>
#include<algorithm>
#include<queue>
#include<map>
#include<cstring>
#include<cmath>
#include<cstdlib>
#include<set>
#include<unordered_map>
#include<vector>
typedef long long ll;
using namespace std;
#define N 500010
int ans[N],u[N],v[N],ind[N];
int s[N];
int main(){
    int i,n,m;
    scanf("%d%d",&n,&m);
    for(i=1;i<=n;i++)ans[i]=1;
    for(i=1;i<n;i++)scanf("%d%d",&u[i],&v[i]);
    for(i=1;i<=m;i++)scanf("%d",&ind[i]);
    for(i=m;i;i--){
        int temp=ans[u[ind[i]]]+ans[v[ind[i]]]-s[ind[i]];
        s[ind[i]]=ans[u[ind[i]]]=ans[v[ind[i]]]=temp;
    }
    for(i=1;i<=n;i++)printf("%d ",ans[i]);
    return 0;
}

C

题目描述
一棵可以随便搞孩子位置的线段树，$q$次区间查询，问最小的查询的线段树区间个数。

解题思路
我们先假设，对于一个区间$[l,r]$内，每一个点$i\in [l,r]$对应的线段树区间（即节点长度为$1$的点）都会被查询到一次，记$w[l,r]$表示选择了线段树这个区间后对答案的贡献，有$w[i,i]++(i\in [l,r])$。

从$2$开始枚举线段树中的节点长度$len$，沿着线段树从底向上找，如果有区间$[L,R](L\neq R)\in[l,r]$，那么如果选择了这个区间，将可以少枚举一个子区间，对答案贡献$-1$；如果有区间$[L,R](L\neq R)\notin[l,r]$且$[L,R]$与$[l,r]$相交，那么需要访问该区间一次，而下面访问的次数并没有减少，于是对答案贡献$+1$。

算出贡献$w$之后，区间$dp$就可以了。

AC代码
点击
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
#include<cstdio>
#include<algorithm>
#include<queue>
#include<map>
#include<cstring>
#include<cmath>
#include<cstdlib>
#include<set>
#include<unordered_map>
#include<vector>
typedef long long ll;
using namespace std;
#define N 520
int w[N][N],f[N][N],d[N];
int main(){
    int i,j,k,n,m,l,r;
    scanf("%d%d",&n,&m);
    for(i=0;i<m;i++){
        scanf("%d%d",&l,&r);
        d[l]++;d[r+1]--;
        w[1][l]++;w[l][l]--;
        w[1][n+1]--;w[l][n+1]++;
         
        w[l][r+1]++;w[l][n+1]--;
        w[r+1][r+1]--;w[r+1][n+1]++;
         
        w[l][l]--;w[l][r+1]++;
        w[r+1][l]++;w[r+1][r+1]--;
    }
    for(i=1;i<=n;i++)d[i]+=d[i-1];
    for(i=1;i<=n;i++)
        for(j=1;j<=n;j++)
            w[i][j]+=w[i-1][j]+w[i][j-1]-w[i-1][j-1];
    memset(f,0x3f,sizeof(f));
    for(i=1;i<=n;i++)w[i][i]=d[i],f[i][i]=d[i];
    for(l=1;l<n;l++){
        for(i=1;i+l<=n;i++){
            int j=i+l,ans=1e8;
            for(k=i;k<j;k++)ans=min(ans,f[i][k]+f[k+1][j]+w[i][j]);
            f[i][j]=ans;
        }
    }
    printf("%d",f[1][n]);
    return 0;
}

D

题目描述

有$n\leq 1000$个圆，每个圆有一定几率出现。问覆盖面积的期望。

解题思路1

upsolved by qxforever

枚举每个圆$i$，对于和圆$i$相交的圆，记录下相交位置$p_j$，做一下前缀积就是这片圆弧出现在边界的概率。一个曲面的面积是绕着闭合曲线一周积分得到的，将每段弧的积分贡献加入即可求出。

比如当前积分区域$D$，圆弧集合为$C$：

$S$

$=\iint_D1\text dx\text dy$

$=\frac 12\oint_Cx\text dy-y\text dx$

$=\sum_{c\in C}\frac 12\int_{\theta_1}^{\theta_{2}}(x_0+r_c\cos\theta)\text d(y_0+r_c\sin\theta)-(y_0+r_c\sin\theta)\text d(x_0+r_c\cos\theta)$

$=\sum_{c\in C}\frac 12\int_{\theta_1}^{\theta_{2}}((x_0+r_c\cos\theta)\cos\theta+(y_0+r_c\sin\theta)\sin\theta)\text d\theta$

$=\sum_{c\in C}\frac 12\int_{\theta_1}^{\theta_{2}}(x_0\cos\theta+y_0\sin\theta+r_c)\text d\theta$

AC代码 - by qxforever

点击

#include <bits/stdc++.h>
using namespace std;
typedef pair<double,double> pdd;
const double eps = 1e-10;
const double pi = acos(-1.0);
const double pi2 = 2*pi;
const int maxn = 1e3+23;
struct Point{
    double x,y;
    Point(double x=0,double y=0):x(x),y(y) {}
    bool operator < (const Point &b) const
    {
        return x<b.x||(x==b.x&&y<b.y);
    }
};
typedef Point Vector;
Point operator + (Point A,Point B){return Point(A.x+B.x,A.y+B.y);}
Point operator - (Point A,Point B) {return Point(A.x-B.x,A.y-B.y);}
Point operator * (Point A,double B) {return Point(A.x*B,A.y*B);}
Point operator / (Point A,double B) {return Point(A.x/B,A.y/B);}
int dcmp(double x)
{
    if(fabs(x)<eps) return 0;
    return x<0 ? -1 : 1;
}
bool operator == (const Point &a,const Point &b)
{
    return dcmp(a.x-b.x)==0&&dcmp(a.y-b.y)==0;
}
 
double dot(Vector a,Vector b)
{
    return a.x*b.x+a.y*b.y;
}
double length(Vector a)
{
    return sqrt(dot(a,a));
}
double angle(Vector v)
{
    return atan2(v.y,v.x);
}
double cross(Vector a,Vector b)
{
    return a.x*b.y-a.y*b.x;
}
struct Circle
{
    Point c;double r,p;double lg;
    Point point(double a)
    {
        return Point(c.x+cos(a)*r,c.y+sin(a)*r);
    }
    void read()
    {
        //scanf("%lf%lf%lf",&c.x,&c.y,&r);p=1000;
        scanf("%lf%lf%lf%lf",&c.x,&c.y,&r,&p);
        p=1-p/1000;
    }
    double oint(double t1,double t2)
    {
        return r*(r*(t2-t1)+c.x*(sin(t2)-sin(t1))-c.y*(cos(t2)-cos(t1)));
    }
    bool operator < (const Circle rhs) const
    {
        return c<rhs.c||(c==rhs.c&&r<rhs.r);
    }
    bool operator == (const Circle rhs) const
    {
        return c==rhs.c&&(dcmp(r-rhs.r)==0);
    }
}a[maxn];
pdd p[maxn<<2];int cnt;double pb,base;
void getCircleIntersection(const Circle &C1,const Circle &C2)
{
    double d=length(C1.c-C2.c);
    if((C1.r+C2.r-d)<=0||C1.r-C2.r-d>=0){
        return ;
    }
    if(((C2.r-C1.r)-d)>=0) {base*=C2.p;return ;}
    double a=angle(C2.c-C1.c);
    double da=acos((C1.r*C1.r+d*d-C2.r*C2.r)/(2*C1.r*d));
    double l=a-da,r=a+da;
    if(l<-pi) l+=pi2;
    if(r>=pi) r-=pi2;
    if(l>r) pb+=C2.lg;
    p[cnt++]={l,C2.lg};
    p[cnt++]={r,-C2.lg};
}
int n;
 
double cal(int x)
{
    double ans=0;cnt=1;pb=0,base=1;
    p[0].first=-pi;
    for(int i=1;i<=n;i++){
        if(i==x) continue;
        getCircleIntersection(a[x],a[i]);
    }
    p[cnt++].first=pi;
    sort(p+1,p+cnt-1);
    for(int i=1;i<cnt;i++){
        ans+=(long double)exp(pb)*a[x].oint(p[i-1].first,p[i].first);
        pb+=p[i].second;
    }
    return base*ans*(1-a[x].p);
}
 
int main()
{
    cin>>n;
    for(int i=1;i<=n;i++) a[i].read();
    sort(a+1,a+1+n);
    for(int i=1;i<=n;i++){
        if(a[i]==a[i+1]) a[i+1].p*=a[i].p;
    }
    int m=0;
    for(int i=1;i<=n;i++) if(!(a[i]==a[i+1])) a[++m]=a[i]; n=m;
    for(int i=1;i<=n;i++){
        a[i].lg=log(a[i].p<eps?eps:a[i].p);
    }
    double ans=0;
    for(int i=1;i<=n;i++) ans+=cal(i);
    printf("%.10f",ans/2);
}

解题思路2 - by nikkukun

定义$f(x)$为在$x$处的线段长度，对任意$x$，$f(x)$是可以线性求出的，对$f(x)$自适应辛普森积分即可。

AC代码 - 没补

点击

1
2

E

题目描述

给定一个长度为$n$的序列$a$，以及长度为$4$的序列$b$，问$a$有多少子序列$(x_1,x_2,x_3,x_4)$满足：$\forall i,j\in [1,n]$，$x_i=x_j$当且仅当$b_i=b_j$。

解题思路

solved by qxforever

暴力枚举前三个元素，第四个元素用前缀和处理一下即可。

AC代码 - by qxforever

点击

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const int maxn = 323;
int a[maxn],b[5];
int pre[maxn][maxn];
int n;
 
 
 
int main()
{
    cin>>n;
    for(int i=1;i<=n;i++) scanf("%d",a+i);
    for(int i=1;i<=4;i++) scanf("%d",b+i);
    for(int i=1;i<=n;i++){
        pre[i][a[i]]++;
        for(int j=1;j<=n;j++) pre[i][j]+=pre[i-1][j];
    }
    ll ans=0;
    for(int i=1;i<=n;i++){
        for(int j=i+1;j<=n;j++){
            if((a[i]==a[j])!=(b[1]==b[2])) continue;
            for(int k=j+1;k<=n;k++){
                if((a[i]==a[k])!=(b[1]==b[3])) continue;
                if((a[j]==a[k])!=(b[2]==b[3])) continue;
                //printf("%d %d %d ",a[i],a[j],a[k]);
                if(b[1]==b[4]) ans+=pre[n][a[i]]-pre[k][a[i]];
                else if(b[2]==b[4]) ans+=pre[n][a[j]]-pre[k][a[j]];
                else if(b[3]==b[4]) ans+=pre[n][a[k]]-pre[k][a[k]];
                else{
                    int t=n-k-(pre[n][a[i]]-pre[k][a[i]])-(pre[n][a[j]]-pre[k][a[j]])-(pre[n][a[k]]-pre[k][a[k]]);
                    if(b[1]==b[2]) t+=(pre[n][a[i]]-pre[k][a[i]]);
                    if(b[3]==b[1]||b[3]==b[2]) t+=(pre[n][a[k]]-pre[k][a[k]]);
                    ans+=t;
                }
                //printf("%lld\n",ans);
            }
        }
    }
    cout<<ans;
}

F

题目描述
解题思路
AC代码
点击
1
2

G

题目描述

定义$f(x)$为$x$在模$p$意义下的逆元。

给定$p$，求出所有满足$2\leq x\leq p,f(x)=min_{k=2}^{x}f(k)$的$x$。

解题思路

从底向上枚举$i$，有$f(f(i))=i$，同时维护左、右端点即可。

AC代码

点击

#include<cstdio>
#include<algorithm>
#include<queue>
#include<map>
#include<cstring>
#include<cmath>
#include<cstdlib>
#include<set>
#include<unordered_map>
#include<vector>
typedef long long ll;
using namespace std;
ll mod;
int iv[1000000];
int main(){
    int i,t;
    iv[0]=iv[1]=1;
    scanf("%d",&t);
    while(t--){
        scanf("%lld",&mod);
        vector<pair<int,int>>ans;
        vector<pair<int,int>>rans;
        ll mnnum=1e10;
        for(i=2;i<mod;i++){
            int inv=(mod-mod/i)*iv[mod%i]%mod;
            iv[i]=inv;
            if(i>inv)break;
            if(inv<mnnum){
                ans.push_back(make_pair(inv,i));
                if(i!=inv)rans.push_back(make_pair(i,inv));
                mnnum=inv;
            }
        }
        printf("%d\n",ans.size()+rans.size());
        for(auto i=rans.begin();i!=rans.end();i++){
            printf("%d %d\n",(*i).first,(*i).second);
        }
        for(auto i=ans.rbegin();i!=ans.rend();i++){
            printf("%d %d\n",(*i).first,(*i).second);
        }
    }
    return 0;
}

H

题目描述
构造三个在一个球上的整数点，满足坐标绝对值不超过$1e6$、原点距离该平面不超过$1e-18$、把球化作单位球后三点间距离均大于$1.7$。

解题思路
solved by nikkukun

均摊一下然后随机抖动搜索出结果即可。

AC代码 - by nikkukun
点击
1
2
3
4
5
6
7
8
9
10
#include<bits/stdc++.h>
using namespace std;
 
int main(){
    cout << "333337 -666670 333333\n";
    cout << "333330 333338 -666668\n";
    cout << "-666663 333332 333331\n";
     
    return 0;
}

I

题目描述

给一个$n\times n$矩阵，先来$m_1$次操作，每次操作把一个矩形内加上$w$，再来$m_2$次操作，每次询问区间最值。

解题思路

先构造好矩阵后二维线段树查询即可。

AC代码

点击

#include<cstdio>
#include<algorithm>
#include<queue>
#include<map>
#include<cstring>
#include<cmath>
#include<cstdlib>
#include<set>
#include<unordered_map>
#include<vector>
typedef long long ll;
using namespace std;
int n,m1,m2;
#define N 8010
ll v[N][N];
ll mx[N][N];
int L[N],R[N];
void pushupx(int p,int x){
    mx[x][p]=max(mx[x<<1][p],mx[x<<1|1][p]);
    if(L[p]==R[p])return;
    pushupx(p<<1,x);
    pushupx(p<<1|1,x);
}
void buildy(int p,int x,int l,int r){
    if(l==r){
        mx[x][p]=v[L[x]][l];
        return;
    }
    buildy(p<<1,x,l,(l+r)>>1);
    buildy(p<<1|1,x,((l+r)>>1)+1,r);
    mx[x][p]=max(mx[x][p<<1],mx[x][p<<1|1]);
}
void buildx(int p,int l,int r){
    if(l==r){
        buildy(1,p,1,n);
        return;
    }
    buildx(p<<1,l,(l+r)>>1);
    buildx(p<<1|1,((l+r)>>1)+1,r);
    pushupx(1,p);
}
ll queryy(int p,int x,int l,int r){
    if(L[p]>r||R[p]<l)return 0;
    if(l<=L[p]&&R[p]<=r)return mx[x][p];
    return max(queryy(p<<1,x,l,r),queryy(p<<1|1,x,l,r));
}
ll queryx(int p,int l,int r,int y1,int y2){
    if(L[p]>r||R[p]<l)return 0;
    if(l<=L[p]&&R[p]<=r)return queryy(1,p,y1,y2);
    return max(queryx(p<<1,l,r,y1,y2),queryx(p<<1|1,l,r,y1,y2));
}
void init(int p,int l,int r){
    L[p]=l;R[p]=r;
    if(l==r)return;
    init(p<<1,l,(l+r)>>1);
    init(p<<1|1,((l+r)>>1)+1,r);
}
int main(){
    int i,j,x1,x2,y1,y2,w;
    scanf("%d%d%d",&n,&m1,&m2);
    init(1,1,n);
    while(m1--){
        scanf("%d%d%d%d%d",&x1,&y1,&x2,&y2,&w);
        v[x1][y1]+=w;v[x1][y2+1]-=w;
        v[x2+1][y1]-=w;v[x2+1][y2+1]+=w;
    }
    for(i=1;i<=n;i++)for(j=1;j<=n;j++)v[i][j]+=v[i-1][j]+v[i][j-1]-v[i-1][j-1];
    buildx(1,1,n);
    while(m2--){
        scanf("%d%d%d%d",&x1,&y1,&x2,&y2);
        printf("%lld\n",queryx(1,x1,x2,y1,y2));
    }
    return 0;
}

J

题目描述

给定一个$n\times n$的印章，印章上的一些位置有凸起，当把印章往平面上按的时候，凸起部分的平面状态从$0$变为$1$或者反之。

印章扩展到无限大，平面也扩展到无限大。可以无限制按印章，对于$n\times n$的范围，问一共可以有多少种状态？

解题思路

solved by nikkukun

枚举印章左下角位置，其能够改变状态的点集为$s_{ij}$。由于所有状态都是由$s_{i_1j_1}\oplus s_{i_2j_2}\oplus…\oplus s_{i_kj_k}$产生的，即为一个异或和，故$s$的集合$S$的线性基个数即为答案。

用$bitset$可以维护这个线性基。

AC代码 - by nikkukun

点击

// 14:16 - 14:25
#include<bits/stdc++.h>
using namespace std;
 
typedef long long ll;
 
const int N = 32 + 5;
const int S = 1024 + 5;
const int MOD = 1e9 + 7;
typedef bitset<S> bs;
 
struct LBase{
    bs b[S];
    void Insert(bs x){
        for(int i=S-1; i>=0; i--)
            if(x[i]){
                if(b[i].none()){
                    b[i] = x;
                    return;
                }else x ^= b[i];
            }
    }
    int Size(){
        int cnt = 0;
        for(int i=S-1; i>=0; i--)
            if(b[i].any()) cnt++;
        return cnt;
    }
};
 
LBase lb;
char g[N][N];
 
int main(){
    ios::sync_with_stdio(0);
 
    int k; cin >> k;
    int n = 1 << k;
    for(int i=0; i<n; i++)
        for(int j=0; j<n; j++)
            cin >> g[i][j];
 
    for(int i=0; i<n; i++)
        for(int j=0; j<n; j++){
            bs b;
            for(int x=0; x<n; x++)
                for(int y=0; y<n; y++){
                    int nx = (x + i) % n;
                    int ny = (y + j) % n;
                    int idx = nx * n + ny;
                    b[idx] = g[x][y] - '0';
                }
            lb.Insert(b);
        }
 
    int siz = lb.Size();
    ll ans = 1;
    while(siz--)
        ans = ans * 2 % MOD;
    cout << ans << endl;
 
    return 0;
}