| Solved | A | B | C | D | E | F | G | H | I | J |
|---|---|---|---|---|---|---|---|---|---|---|
| 8/10 | 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 Equivalent Prefixes
题目描述
定义两个数组$u,v$等价当且仅当任意$l,r$，有$RMQ(u,l,r)=RMQ(v,l,r)$，其中$RMQ(u,l,r)$表示数组$u$中下标为$[l,r]$中最小元素的位置。
给两个只包含不同元素的数组，求出两数组最长等价前缀长度。
解题思路
之前做过一个类似的笛卡尔树的题（HDU 6305，这里的B题），感觉还是比较容易的。
首先二分区间进行$check$，每次$check$的时候，找出$[l,r]$区间中最小值位置$pos$，因为这个最小值不影响$[l,pos-1]$和$[pos+1,r]$的检查，故可以分治解决。预处理出$ST$表，总复杂度$O(n\log n)$。
（代码里为了找$pos$好写就离散化了一下，其实可以直接在构造$ST$表的时候存储最小位置，懒得改了）
AC代码
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
typedef long long ll;
using namespace std;
int a[N],b[N],n;
int aa[N],bb[N];
int lg[N],p[17][N],q[17][N];
int pa[N],pb[N];
void init(){
int i,j;
for(i=0;i<n;i++)p[0][i]=a[i],q[0][i]=b[i];
for(i=1;(1<<i)<=n;i++){
for(j=0;j+(1<<(i-1))<n;j++){
p[i][j]=min(p[i-1][j],p[i-1][j+(1<<(i-1))]);
q[i][j]=min(q[i-1][j],q[i-1][j+(1<<(i-1))]);
}
for(;j<n;j++)p[i][j]=q[i][j]=2e9;
}
}
int solve(int l,int r){
if(l>=r)return 1;
int len=r-l+1,x=lg[len],pos;
if(p[x][l]>p[x][r-(1<<x)+1]){
pos=pa[p[x][r-(1<<x)+1]];
if(pos!=pb[q[x][r-(1<<x)+1]]||q[x][l]<q[x][r-(1<<x)+1])return 0;
if(solve(l,pos-1)==0)return 0;
return solve(pos+1,r);
}else{
pos=pa[p[x][l]];
if(pos!=pb[q[x][l]]||q[x][l]>q[x][r-(1<<x)+1])return 0;
if(solve(l,pos-1)==0)return 0;
return solve(pos+1,r);
}
}
int check(int x){return solve(0,x-1);}
int main(){
int i;
for(i=2;i<=100000;i++)lg[i]=lg[i-1]+(1<<(lg[i-1]+1)==i);
while(~scanf("%d",&n)){
for(i=0;i<n;i++)scanf("%d",&a[i]),aa[i]=a[i];
for(i=0;i<n;i++)scanf("%d",&b[i]),bb[i]=b[i];
sort(aa,aa+n);sort(bb,bb+n);
map<int,int>mpa,mpb;
mpa.clear();mpb.clear();
for(i=0;i<n;i++){
mpa[aa[i]]=i;
mpb[bb[i]]=i;
}
for(i=0;i<n;i++)a[i]=mpa[a[i]],b[i]=mpb[b[i]];
for(i=0;i<n;i++)pa[a[i]]=i,pb[b[i]]=i;
init();
int l=0,r=n,ans=0;
while(l<=r){
int mid=(l+r)/2;
if(check(mid))l=mid+1,ans=mid;
else r=mid-1;
}
printf("%d\n",ans);
}
return 0;
}
B Integration
题目描述
给定数组$a_i$，计算$\frac1{\pi}\int_{0}^{\inf}\frac{1}{\prod_{i=1}^{n}(a_i^2+x^2)}\text{d}x$。
解题思路
被积函数是一堆很好积分的东西的乘积，我们发现每一项$\frac{1}{a_i^2+x^2}$的$x$系数都为$1$，容易想到将乘积转化成和的形式逐项积分。
$\frac{1}{\prod_{i=1}^{n}(a_i^2+x^2)}$$=\frac{c_1}{(a_1^2+x^2)}+\frac{c_2}{(a_2^2+x^2)}+…+\frac{c_n}{(a_n^2+x^2)}$
两边同乘$\prod_{i=1}^{n}(a_i^2+x^2)$，得$1=c_i\prod_{j\neq i}(a_j^2+x^2)+\sum_{j\neq i}\frac{c_j\prod(a_k^2+x^2)}{a_j^2+x^2}$
为了求出$c_i$，我们不妨令$x=a_i\cdot i$，则$x^2=-a_i^2$。于是$1=c_i\prod_{j\neq i}(a_j^2-a_i^2)$，$c_i=\frac1{\prod_{j\neq i}(a_j^2-a_i^2)}$。
逐项求积分即可。
AC代码
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
typedef long long ll;
using namespace std;
int n;
ll a[1010];
ll mod=1000000007;
ll qp(ll x,int p){
ll ans=1;
for(;p;p>>=1,x=x*x%mod)if(p&1)ans=ans*x%mod;
return ans;
}
int main(){
int i,j;
while(~scanf("%d",&n)){
for(i=0;i<n;i++)scanf("%lld",&a[i]);
ll ans=0;
for(i=0;i<n;i++){
ll now=a[i];
for(j=0;j<n;j++){
if(i==j)continue;
now=(a[j]*a[j]-a[i]*a[i])%mod*now%mod;
}
if(now<0)now+=mod;
(ans+=qp(now,mod-2))%=mod;
}
ans=ans*qp(2,mod-2)%mod;
printf("%lld\n",(ans+mod)%mod);
}
return 0;
}
C Euclidean Distance
题目描述
给定一个$n$维的点$A$，求一个$n$维点$P(p_1,p_2,…,p_n)$满足$\sum p_i=1,p_i\geq 0(1\leq i\leq n)$，使得$|AP|$最短。
解题思路
考虑$A$点在平面$x+y+z+…=1$的超平面上的投影$B$，设$b_i=a_i-dis$，则$\sum a_i-n\cdot dis=1$，$dis=\frac{\sum a_i-1}{n}$，$b_i=a_i-\frac{\sum a_i-1}n$。
若$\forall i, b_i\geq 0$，则$B$即为$P$点。否则设$b_k<0$，则要使得距离最短，必然有$p_k=0$，即该维的坐标为$0$，故问题转化为少一维度的情况（注意$b_i$计算的时候$n$会发生变化），重复运算一直到$\forall i,b_i\geq 0$。
于是我们可以对$a_i$排序，找到首个$b_i\geq 0$的点，则往后的所有维度都满足这个条件，所以前面的$p_k=0$，后面的$p_k=b_k$，分别求和即可。
AC代码
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
typedef long long ll;
using namespace std;
int n,m;
ll a[N],s2[N];
int main(){
int i,j;
while(~scanf("%d%d",&n,&m)){
ll s=0;
for(i=1;i<=n;i++)scanf("%lld",&a[i]),s+=a[i];
sort(a+1,a+1+n);
for(i=1;i<=n;i++)s2[i]=s2[i-1]+a[i]*a[i];
for(i=1;i<=n;i++){
if(a[i]*(n-i+1)-s+m>=0)break;
s-=a[i];
}
ll fz=s2[i-1]*(n-i+1)+(s-m)*(s-m),fm=1LL*m*m*(n-i+1);
ll g=__gcd(fz,fm);
fz/=g;fm/=g;
if(fm==1)printf("%lld\n",fz);
else printf("%lld/%lld\n",fz,fm);
}
return 0;
}
D Parity of Tuples
题目描述
解题思路
AC代码
2
E ABBA
题目描述
构造一个长度为$2(n+m)$的$AB$字符串，其中能够拆分出$n$个$AB$，$m$个$BA$，问有多少种构造方法。
解题思路
考虑从第一位开始填字符，类似$catalan$数的求法，建立一个坐标轴，$x$轴表示$A$的数量，$y$轴表示$B$的数量。从原点走起，每一次填写$A$则$x++$，否则$y++$，最后走到$(n+m,n+m)$点。
任意前缀的$B-A$最大值即为这个串中$AB$个数的最小值，所以如果有某个前缀$B-A>n$，那么$B$要组成大于$n$个$AB$，$BA$的个数就不会到达$m$，所以任意前缀有$B\leq A+n$。同理可得：$A\leq B+m$。
黑体字部分证明如下：设$A-B$在某个前缀$[1,l]$取得最大值$p$，则$[l+1,2(n+m)]$区间中$B-A=p$。尽量使得后面区间中的$B$组成$BA$而非$AB$，则可以$BABABA….BA,BBB..B$进行排列，最终有$p$个$B$必须同前面的$A$进行匹配，故$AB$的最小可能值为$p$。
通过类似$catalan$数对称处理的方法可以得出答案。
AC代码
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
typedef long long ll;
using namespace std;
ll fac[N],inv[N],mod=1000000007;
ll qp(ll x,int p){
ll ans=1;
for(;p;p>>=1,x=x*x%mod)if(p&1)ans=ans*x%mod;
return ans;
}
ll c(int n,int m){
if(n<m||m<0)return 0;
return fac[n]*inv[m]%mod*inv[n-m]%mod;
}
int main(){
int i,n,m;
inv[0]=fac[0]=1;
for(i=1;i<N;i++)
fac[i]=fac[i-1]*i%mod,
inv[i]=qp(fac[i],mod-2);
while(~scanf("%d%d",&n,&m))
printf("%lld\n",((c((n+m)<<1,n+m)-c((n+m)<<1,n-1)-c((n+m)<<1,m-1))%mod+mod)%mod);
return 0;
}
F Random Point in Triangle
题目描述
给定三角形，求任意三角形内一点与顶点分别形成的三个三角形面积最大值的期望。
解题思路
先猜结论是常数倍的三角形面积，然后用等边三角形特例求出常数。
AC代码
2
3
4
5
6
7
8
9
10
11
12
typedef long long ll;
int x1,y1,x2,x3,y2,y3;
int main(){
while(~scanf("%d%d%d%d%d%d",&x1,&y1,&x2,&y2,&x3,&y3)){
ll S=(1LL*x1*y2+1LL*x2*y3+1LL*x3*y1-1LL*x1*y3-1LL*x2*y1-1LL*x3*y2);
ll t=S*11;
if(t<0)t=-t;
printf("%lld\n",t);
}
}
G Substrings 2
题目描述
解题思路
AC代码
2
H XOR
题目描述
求一个数列中，所有异或和为$0$的子集大小之和。
解题思路
等价于求每一个元素在多少个子集中再求一下和。
对于每一个元素$i$，可以考虑对其他所有元素建一个线性基，假设线性基中包含了$k$个元素。如果这个元素不能插入这个线性基，就表示这个元素可以被线性基中的$k$个元素线性表示，也就是另外的$n-k-1$个元素中任意选择都能找到对应的线性基中元素使得异或和为$0$，对答案的贡献为$2^{n-k-1}$。
但这样复杂度太高，是$O(n^2\log n)$的，显然会$T$掉。
考虑对所有数先建立一个线性基$lb$。假设$lb$的大小为$k$，则同理对于剩下的$n-k$个元素中的每一个元素$i$，任意再取$lb$外的元素，都能找到$lb$中的元素对应使得异或和为$0$，故每个$lb$外元素都在$2^{n-k-1}$个子集中。
再对$lb$外的元素建立一个线性基$res$，对于所有$lb$中的元素建立的包含其他$n-1$个元素的线性基，可以从$res$中插入不多于$\log n$次建立，于是总时间复杂度变为$O(n\log n+\log ^3 n)$。
AC代码
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
typedef long long ll;
using namespace std;
struct LinearBase{
ll bas[P];int cnt=0;
int insert(ll x){
int i;
for(i=P-1;i>=0;i--){
if((x>>i)&1){
if(bas[i])x^=bas[i];
else{
bas[i]=x;
cnt++;
return 1;
}
}
}
return 0;
}
void clear(){
cnt=0;
memset(bas,0,sizeof(bas));
}
}lb,res,tmp;
ll a[N],pw[N],mod=1000000007;
ll b[N],tot,c[N],tot2;
int main(){
int i,j,n;
pw[0]=1;
for(i=1;i<N;i++)pw[i]=pw[i-1]*2%mod;
while(~scanf("%d",&n)){
lb.clear();res.clear();tot=tot2=0;
for(i=1;i<=n;i++){
scanf("%lld",&a[i]);
if(!lb.insert(a[i]))b[tot++]=a[i];
else c[tot2++]=a[i];
}
ll ans=pw[n-lb.cnt-1]*(n-lb.cnt)%mod;
for(i=0;i<tot;i++)res.insert(b[i]);
for(i=0;i<tot2;i++){
tmp=res;
for(j=0;j<tot2;j++){
if(i==j)continue;
tmp.insert(c[j]);
}
if(!tmp.insert(c[i]))(ans+=pw[n-tmp.cnt-1])%=mod;
}
printf("%lld\n",ans);
}
return 0;
}
I Points Division
题目描述
有$n$个点，每个点有一个坐标$(x_i,y_i)$，有两个属性$a_i,b_i$。把这$n$个点分成两个集合$A,B$，保证不存在$A$中的点位于$B$中的点的右下方，最大化$\sum_{i\in A}a_i+\sum_{j\in B}b_j$。
解题思路
可以转化为，有一条折线把$A,B$两个集合分开。规定位于折线上的点归属于$B$，设$f[i]$表示$i$位于折线上时原式的最大值，每次加入一个新点$i$的时候，有$f[j]=f[j]+ai;$$f[j]=f[j]+bi;$ $f[i]=b[i]+max(f[j]),j<i$。
所以每次需要支持的操作为：单点修改，区间查询最大值，区间修改。
对于$y$坐标离散化，建一棵线段树维护一下在每一个$y$上的最大值即可。
注意初始状态有$f[0]=0$，即考虑$y=0$的情况，也即所有点都进入$A$集合。
还需要注意的是，对点进行排序的时候，$x$坐标升序，而为了防止多加，$y$坐标应当为降序。
AC代码
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
typedef long long ll;
using namespace std;
ll lazy[N<<2],mx[N<<2];
int L[N<<2],R[N<<2];
struct Poi{
int a,b;
int x,y;
bool operator<(const Poi&p)const{return x==p.x?y>p.y:x<p.x;}
}a[N];
int b[N];
void pushup(int p){
mx[p]=max(mx[p<<1],mx[p<<1|1]);
}
void pushdown(int p){
ll t=lazy[p];
if(!t)return;
if(L[p<<1])lazy[p<<1]+=t,mx[p<<1]+=t;
if(L[p<<1|1])lazy[p<<1|1]+=t,mx[p<<1|1]+=t;
lazy[p]=0;
}
void build(int p,int l,int r){
L[p]=l,R[p]=r;
int mid=(l+r)>>1;
lazy[p]=0;mx[p]=-1e18;
if(l==r)return;
build(p<<1,l,mid);
build(p<<1|1,mid+1,r);
}
void upd(int p,int pos,ll x){
pushdown(p);
if(L[p]>pos||R[p]<pos)return;
if(L[p]==pos&&pos==R[p]){mx[p]=max(mx[p],x);return;}
upd(p<<1,pos,x);
upd(p<<1|1,pos,x);
pushup(p);
}
void modify(int p,int l,int r,ll x){
if(l<=L[p]&&r>=R[p]){
lazy[p]+=x;
mx[p]+=x;
return;
}
if(l>R[p]||r<L[p])return;
modify(p<<1,l,r,x);
modify(p<<1|1,l,r,x);
pushup(p);
}
ll querymax(int p,int l,int r){
pushdown(p);
if(l<=L[p]&&r>=R[p])return mx[p];
if(l>R[p]||r<L[p])return -1e18;
return max(querymax(p<<1,l,r),querymax(p<<1|1,l,r));
}
int main(){
int i,n;
while(~scanf("%d",&n)){
for(i=0;i<=(n<<2);i++)lazy[i]=0,mx[i]=0,L[i]=R[i]=0;
for(i=1;i<=n;i++)scanf("%d%d%d%d",&a[i].x,&a[i].y,&a[i].a,&a[i].b),b[i]=a[i].y;
sort(b+1,b+1+n);
int cnt=unique(b+1,b+1+n)-b;
for(i=1;i<=n;i++)a[i].y=lower_bound(b+1,b+cnt,a[i].y)-b+1;
sort(a+1,a+1+n);
build(1,1,cnt);
upd(1,1,0);
for(i=1;i<=n;i++){
upd(1,a[i].y,querymax(1,1,a[i].y)+a[i].b);
modify(1,1,a[i].y-1,a[i].a);
modify(1,a[i].y+1,cnt,a[i].b);
}
printf("%lld\n",mx[1]);
}
return 0;
}
J Fraction Comparision
题目描述
给两个分数$\frac xa, \frac yb$，比较大小。（$0\leq x,y\leq 10^{18},1\leq a,b\leq 10^9$）
解题思路
可以化成假分数比较，可以用$JAVA$，可以写高精度，也可以$__int128$。
AC代码
2
3
4
5
6
7
8
9
10
11
12
13
typedef long long ll;
using namespace std;
int main(){
ll a,b,c,d;
while(~scanf("%lld%lld%lld%lld",&a,&b,&c,&d)){
__int128 A=a,B=b,C=c,D=d;
if(A*D==B*C)puts("=");
else if(A*D<B*C)puts("<");
else puts(">");
}
return 0;
}