ABC478

ABC478

没有 AK /ll

A. Grapes

nn 个人 mm 个糖。

对于 i=1∼mi=1\sim m，执行：

  • 人类 (i−1) mod n+1(i-1)\bmod{n}+1 的糖的数量 +1+1 。

求每个人最终的糖果数量。

n≤1000,m≤10000n\le 1000,m\le 10000。

数学或者模拟，随便你怎么写。

数学的话就是 ⌊mn⌋+[i≤m mod n]\lfloor\frac{m}{n}\rfloor+[i\le m\bmod{n}]。

::::success[代码]

1
2
3
4
5
6
7
8
9
#include <bits/stdc++.h>
using namespace std;
const int N=1001;
int main(){
    int n,m;
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)printf("%d\n",m/n+(i<=m%n));
    return 0;
}

::::

B. Topping

有 nn 个数，第 ii 个数为 aia_i。

求 max⁡i≠j≠k,i+j+k≤V{ai+aj+ak}\max\limits_{i\ne j\ne k,i+j+k\le V}\{a_i+a_j+a_k\}。

n≤100n\le100。

如果说 nn 大一些我可能会写一个 DP 之类的东西。

但是 n≤100n\le 100，我枚举就行啊。

::::success[代码]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include <bits/stdc++.h>
using namespace std;
const int N=1100;
int n,v,w[N];
int main(){
    scanf("%d%d",&n,&v);
    for(int i=1;i<=n;i++)scanf("%d",w+i);
    int ans=0;
    for(int i=1;i<=n;i++){
        for(int j=i+1;j<=n;j++){
            for(int k=j+1;k<=n;k++){
                if(i+j+k<=v){
                    ans=max(ans,w[i]+w[j]+w[k]);
                }
            }
        }
    }
    printf("%d",ans);
    return 0;
}

::::

C. Sort Subarray

有一个长度 nn 数组 aa。你可以将其中一个长度为 KK 的子数组排序。求是否有可能在这一次操作内使得整个数组有序。

n≤2×105n\le 2\times10^5。

直接将 AA 排序，设排序后的数组为 BB。

找出 AA 和 BB 的 LCP 和 LCS。若数组 AA 去除 LCP,LCS 后的长度 ≤k\le k，则可行。

正确性显然。

::::success[代码]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include <bits/stdc++.h>
using namespace std;
const int N=200010;
int n,a[N],k,b[N];
int main(){
    scanf("%d%d",&n,&k);
    for(int i=1;i<=n;i++)scanf("%d",a+i),b[i]=a[i];
    int t1=0,t2=n+1;
    sort(b+1,b+1+n);
    for(int i=1;i<=n;i++){
        if(a[i]==b[i])t1++;
        else break;
    }
    for(int i=n;i;i--){
        if(a[i]==b[i])t2--;
        else break;
    }
    if(t2-t1-1<=k)puts("Yes");
    else puts("No");
    return 0;
}

::::

D. Range Set Insertion Query

我竟然第一眼没有开始写代码，愤怒 /fn

有 nn 个集合（初始为空），QQ 次操作。第 ii 次操作将编号在 [Li,Ri][L_i,R_i] 内的所有集合加入 XiX_i。求所有操作完后每一个集合内部的元素个数。

n,Q≤2×105n,Q\le 2\times10^5，1≤Xi≤Q1\le X_i\le Q。

第一眼秒不掉。

第二眼看出要对于每一个 XiX_i 拆开算贡献。

第三眼发现就是一个扫描线。对于同一个 XiX_i 的所有区间，我们顺序扫描线过来。中途遇到的区间进行差分算贡献。最后还原即可。

没了。

::::success[代码]

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
#include <bits/stdc++.h>
using namespace std;
const int N=200010;
int n,m,c[N];
struct node{int l,opt;};
vector<node>v[N];
int main(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;i++){
        int l,r,x;
        scanf("%d%d%d",&l,&r,&x);
        v[x].push_back({l,1});
        v[x].push_back({r+1,-1});
    }
    for(int i=1;i<=m;i++){
        sort(v[i].begin(),v[i].end(),[](node x,node y){
            return x.l<y.l;
        });
        int len=v[i].size(),cnt=0,lst=0;
        for(int j=0;j<len;j++){
            int t=v[i][j].l;            
            if(cnt){
                c[lst]++;
                c[t]--;
            }
            cnt+=v[i][j].opt;
            while(j+1<len&&v[i][j+1].l==t){
                cnt+=v[i][j+1].opt;
                j++;
            }
            lst=t;
        }
        if(cnt)c[lst]++;
    }
    for(int i=1;i<=n;i++)c[i]+=c[i-1];
    for(int i=1;i<=n;i++)printf("%d ",c[i]);
    return 0;
}

::::

E. lt and le

有 nn 个数，mm 个限制。第 ii 个限制要求 aui≤avia_{u_i}\le a_{v_i} 或者 aui<avia_{u_i}<a_{v_i}。同时要求 1≤ai≤n1\le a_i\le n。问是否存在合法的 aa，若存在则构造出方案。

n,m≤2×105n,m\le 2\times 10^5。

一眼差分约束。不过由于只有 ≤\le 和 << 两种限制，于是改为 tarjan，模仿糖果那题就行。

::::success[代码]

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
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
#include <bits/stdc++.h>
using namespace std;
const int N=200010;
int n,m,dfn[N],low[N],idx,s[N],top,in[N],cnt,scc[N];
vector<int>v[N],q[N];
void dfs(int x){
	s[++top]=x;
	in[x]=1;
	dfn[x]=low[x]=++idx;
	for(int u:v[x]){
		if(!dfn[u]){
			dfs(u);
			low[x]=min(low[x],low[u]);
		}
		else if(in[u])
			low[x]=min(low[x],dfn[u]);
	}
	if(low[x]==dfn[x]){
		++cnt;
		int t;
		do{
			t=s[top--];
			in[t]=0;
			scc[t]=cnt;
		}while(t!=x);
	}
}
int X[N],Y[N],tot,rd[N],Dfn[N],id;
queue<int>Q;
int main(){
	scanf("%d%d",&n,&m);
	for(int i=1,x,y;i<=m;i++){
        int t;
        scanf("%d",&t);
		scanf("%d%d",&x,&y);
		if(t==0)v[x].push_back(y);
        else{
            ++tot;
            X[tot]=x,Y[tot]=y;
        }
	}
    for(int i=1;i<=n;i++)if(!dfn[i])dfs(i);
    for(int i=1;i<=n;i++){
        for(int j:v[i]){
            int x=scc[i],y=scc[j];
            if(x!=y)
                q[x].push_back(y),rd[y]++;
        }
    }
    for(int i=1;i<=tot;i++){
        q[scc[X[i]]].push_back(scc[Y[i]]);
        rd[scc[Y[i]]]++;
    }
    for(int i=1;i<=cnt;i++)if(!rd[i])Q.push(i);
    while(!Q.empty()){
        int x=Q.front();
        Dfn[x]=++id;
        Q.pop();
        for(int u:q[x]){
            rd[u]--;
            if(!rd[u])
                Q.push(u);
        }
    }
    int flag=0;
    for(int i=1;i<=cnt;i++){
        if(rd[i]){
            puts("No");
            return 0;
        }
    }
    puts("Yes");
    for(int i=1;i<=n;i++)printf("%d ",Dfn[scc[i]]);
	return 0;
}

::::

定义一个以 11 为根的树 TT 的“最小优先搜索” f(T)f(T) 为：

  • 定义有序集合 P=∅,S={1}P=\varnothing,S=\{1\}。
  • 重复执行直到 S=∅S=\varnothing：
    • 取 x=min⁡i∈S{i}x=\min_{i\in S}\{i\}。
    • 将 xx 加入 PP 末尾。
    • 将 xx 的所有子节点加入 SS。
  • f(T)=Pf(T)=P。

给定排列 QQ，求有多少个树 TT 满足 f(T)=Qf(T)=Q。对 998244353998244353 取模。

n≤2×105n\le2\times 10^5。

保证 Q1=1Q_1=1。

令 p=Qp=Q，pospos 为 pp 的逆。

注意到一棵树的本质实际上是一个 ff 父亲数组。

考虑刻画条件，发现所谓“最小优先搜索”实际上是要求对于每一个 xx，有：

{posfx<posx∀posu>posx, posfu>posx∨u>x\begin{cases}pos_{f_x}<pos_x\\ \forall pos_u>pos_x,\ pos_{f_u}>pos_x\lor u>x \end{cases}

也就是说 fxf_x 的选择理论上有 posx−1pos_x-1 种选择，实际上会有一些 pospos 作出限制。

于是我们倒着枚举 i=n∼2i=n\sim 2，那么对于 ii，fif_i 必须满足对于所有 >i>i 的 jj，若 posj<posipos_j<pos_i，则 posfi≥posjpos_{f_i}\ge pos_j。

因此一个树状数组就能确定 posfipos_{f_i} 的最小值 tit_i，那么答案为：

∏i(posi−ti)\prod_i (pos_i-t_i)

注意特判没有任何一个 jj 满足 j>i,posj<posij>i,pos_j<pos_i 的情况。

::::success[代码]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include <bits/stdc++.h>
using namespace std;
const int N=200010,P=998244353;
int n,p[N],c[N],pos[N];
void add(int x,int y){for(int i=x;i<=n;i+=(i&-i))c[i]=max(c[i],y);}
int query(int x,int cnt=0){for(int i=x;i>=1;i-=(i&-i))cnt=max(cnt,c[i]);return cnt;}
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++)scanf("%d",p+i),pos[p[i]]=i;
    int ans=1;
    for(int i=n;i>=2;i--){
        int t=query(pos[i]);
        if(t==0)t=1;
        ans=1ll*ans*(pos[i]-t)%P;
        add(pos[i],pos[i]);
    }
    printf("%d",ans);
    return 0;
}

::::

G. Division Point Hull

/ll

差一点写出来。

有 nn 个点 PiP_i，称 Qi,jQ_{i,j} 为 PiPjP_iP_j 的 p:qp:q 内分点。

求所有 1≤i<j≤n1\le i<j\le n 的 Qi,jQ_{i,j} 构成的凸包的面积。输出一个分数。

首先如果没有 i<ji<j 的限制，则这是一个模板的闵可夫斯基和。

然而有，于是我们考虑分治。

分数过于麻烦，不妨放缩 p+qp+q 倍，答案最后 1(p+q)2\frac{1}{(p+q)^2} 即可。

具体的，对于区间 [l,r][l,r]，我们需要求出 TT 和 QQ，分别表示凸包和答案。

那么我们就有：

  • 分治递归区间 LL 和 RR。
  • T=merge⁡(TL,TR)T=\operatorname{merge}(T_L,T_R)。
  • Q=merge⁡(QL,QR,MinkelfuSelki⁡(qTL,pTR))Q=\operatorname{merge}(Q_L,Q_R,\operatorname{MinkelfuSelki}(qT_L,pT_R))。

正确性显然。

代码有一点难写（好像是计算几何通用的难写）。

::::success[代码]

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
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N=200100;
struct point{
    int x,y;
    point(){}
    point(int x,int y):x(x),y(y){}
    bool operator<(point a){
        return x-a.x==0?y<a.y:x<a.x;
    }
    bool operator==(point a){
        return x-a.x==0&&y==a.y;
    }
    point operator-(point a){
        return point(x-a.x,y-a.y);
    }
    point operator+(point a){
        return point(x+a.x,y+a.y);
    }
    point operator*(int a){
        return point(x*a,y*a);
    }
};
int n,px,py;
vector<point>p;
int cross(point a,point b){
    return a.x*b.y-a.y*b.x;
}
vector<point>andrew(vector<point>&l){
    sort(l.begin(),l.end());
    int n=unique(l.begin(),l.end())-l.begin();
    vector<point>res;
    int m=0;
    for(int i=0;i<n;i++){
        while(m>1&&cross(res[m-1]-res[m-2],l[i]-res[m-2])<=0)m--,res.pop_back();
        res.push_back(l[i]);m++;
    }
    int k=m;
    for(int i=n-2;i>=0;i--){
        while(m>k&&cross(res[m-1]-res[m-2],l[i]-res[m-2])<=0)m--,res.pop_back();
        res.push_back(l[i]);m++;
    }
    if(res.size()>1)res.pop_back();
    return res;
}
vector<point>Andrew(vector<point>x1,vector<point>x2){
    if(x1.empty())return x2;
    if(x2.empty())return x1;
    for(point u:x2)x1.push_back(u);
    return andrew(x1);
}
vector<point>MinkefuSelki(vector<point>&l,vector<point>&r){
    vector<point>a(l.size()),b(r.size()),ans,res;
    for(int i=0;i<a.size();i++){
        int j=(i+1)%a.size();
        a[i]=l[j]-l[i];
    }
    for(int i=0;i<r.size();i++){
        int j=(i+1)%r.size();
        b[i]=r[j]-r[i];
    }
    int x=0,y=0;
    while(x<a.size()&&y<b.size()){
        if(cross(a[x],b[y])>=0){
            ans.push_back(a[x]);
            x++;
        }
        else{
            ans.push_back(b[y]);
            y++;
        }
    }
    while(x<a.size())ans.push_back(a[x]),x++;
    while(y<b.size())ans.push_back(b[y]),y++;
    res.push_back(l[0]+r[0]);
    for(int i=0;i<ans.size();i++){
        point k=res[i];
        res.push_back(k+ans[i]);
    }
    return andrew(res);
}
pair<vector<point>,vector<point>>merge(int l,int r){
    if(l==r)return {{p[l]},{}};
    int mid=(l+r)>>1;
    pair<vector<point>,vector<point>>L=merge(l,mid),R=merge(mid+1,r);
    vector<point>t1=L.first,t2=R.first;
    for(point &u:t1)u=u*py;
    for(point &u:t2)u=u*px;
    return {Andrew(L.first,R.first),Andrew(
        Andrew(L.second,R.second),
        MinkefuSelki(t1,t2)
    )};
}
signed main(){
    scanf("%lld%lld%lld",&n,&px,&py);
    p.resize(n);
    for(int i=0;i<n;i++){
        scanf("%lld%lld",&p[i].x,&p[i].y);
    }
    vector<point>t=merge(0,n-1).second;
    int len=t.size(),ans=0;
    for(int i=0;i<len;i++){
        ans+=cross(t[i],t[(i+1)%len]);
    }
    int dn=2*(px+py)*(px+py);
    int g=__gcd(ans,dn);
    ans/=g,dn/=g;
    printf("%lld %lld",ans,dn);
    return 0;
}

::::

::::warning[考场代码]

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
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N=100010;
int n;
int gcd(int a,int b){return b==0?a:gcd(b,a%b);}
struct Q{
    int a,b;
    Q():a(0),b(1){}
    Q(int x):a(x),b(1){}
    Q(int a,int b):a(a),b(b){}
    Q operator+(const Q &x)const{return Q(a*x.b+b*x.a,b*x.b);}
    Q operator-(const Q &x)const{return Q(a*x.b-b*x.a,b*x.b);}
    Q operator*(const Q &x)const{return Q(a*x.a,b*x.b);}
    Q operator/(const Q &x)const{return Q(a*x.b,b*x.a);}
    bool operator<(const Q &x)const{return a*x.b<b*x.a;}
    void easy(){
        int t=gcd(a,b);
        a/=t,b/=t;
    }
};
int sign(Q a){
    if(a.a==0)return 0;
    return a.a*a.b>0?1:-1;
}
struct point{
    Q x,y;
    point(){}
    point(Q x,Q y):x(x),y(y){}
    point operator-(point a){return point(x-a.x,y-a.y);}
    point operator+(point a){return point(x+a.x,y+a.y);}
    point operator*(int a){return point(x*a,y*a);}
    bool operator==(point a)const{
        return sign(a.x-x)==0&&sign(a.y-y)==0;
    }
    bool operator<(point a)const{
        return sign(x-a.x)==0?y<a.y:x<a.x;
    }
};
vector<point>p;
int M=0;
Q dot(point a,point b){
    return a.x*b.x+a.y*b.y;
}
Q cross(point a,point b){
    return a.x*b.y-a.y*b.x;
}
int px,py;
vector<point> andrew(vector<point>&l){
    sort(l.begin(),l.end());
    unique(l.begin(),l.end());
    vector<point>res;
    int m=0,n=l.size();
    for(int i=0;i<n;i++){
        while(m>1&&sign(cross(res[m-1]-res[m-2],l[i]-res[m-2]))<=0)m--,res.pop_back();
        res.push_back(l[i]);m++;
    }
    int k=m;
    for(int i=n-2;i>=0;i--){
        while(m>k&&sign(cross(res[m-1]-res[m-2],l[i]-res[m-2]))<=0)m--,res.pop_back();
        res.push_back(l[i]);m++;
    }
    res.pop_back();
    return res;
}
vector<point>Andrew(vector<point>x1,vector<point>x2){
    for(point u:x2)x1.push_back(u);
    return andrew(x1);
}
vector<point> MinkefuSelki(vector<point>&l,vector<point>&r){
    vector<point>a(l.size()),b(r.size()),ans,res;
    for(int i=0;i<a.size();i++){
        int j=(i+1)%a.size();
        a[i]=l[j]-l[i];
    }
    for(int i=0;i<r.size();i++){
        int j=(i+1)%r.size();
        b[i]=r[j]-r[i];
    }
    int x=0,y=0;
    while(x<a.size()&&y<b.size()){
        if(sign(cross(a[x],b[y]))>=0){
            ans.push_back(a[x]);
            x++;
        }
        else{
            ans.push_back(b[y]);
            y++;
        }
    }
    while(x<a.size())ans.push_back(a[x]),x++;
    while(y<b.size())ans.push_back(b[y]),y++;
    res.push_back(l[0]+r[0]);
    for(int i=0;i<ans.size();i++){
        point k=res[i];
        res.push_back(k+ans[i]);
    }
    return andrew(res);
}
pair<vector<point>,vector<point>>Merge(int l,int r){
    if(l==r)return ;
    int mid=(l+r)>>1;
    pair<vector<point>,vector<point>>L=Merge(l,mid),R=Merge(mid+1,r);
    vector<point>t1=L.first,t2=R.first;
    for(point &u:t1)u=u*py;
    for(point &u:t2)u=u*px;
    return {Andrew(L.first,R.first),Andrew(
        Andrew(L.second,R.second),
        MinkefuSelki(t1,t2)
    )};
}
signed main(){
    cin>>n>>px>>py;
    p.resize(n);
    int nn=n;
    for(int i=0;i<n;i++){
        int x,y;
        cin>>x>>y;
        p[i].x=Q(x),p[i].y=Q(y);
    }
    pair<vector<point>,vector<point>>t=Merge(0,n-1);

    return 0;
}

别问我为什么我写了分数结构体。

::::