Solutions
A：Equivalent Prefixes
题意：
若$\text{RMQ(u,l,r)=RMQ(v,l,r)}$ for all $1{\leq}l{\leq}r{\leq}m$，则为$equivalent$
其中$\text{RMQ(w,l,r)}$的定义是${[l,r]}$区间内最小数的下标
给两个数组，每组元素各不相同，求最大的$p{\leq}n\ where\ \{a_1,a_2,{\ldots}a_p\} are\ equivalent$
单调栈思路：
处理出每一位左边第一个比它小的下标，然后相同的话可取，不同不可取。
假如当前处理$a_i$，(也就是$\{a_1,a_2,{\ldots}a_{i-1}\}$满足条件)，假设比它第一个小的是$last[i]$，那么$last[i]$右边的$RMQ$一定是$a_i$，这样的话，$last[i]$左边的$RMQ$一定与新数无关，因为仅仅$last[i]$处就已经比$a_i$小了。
可以利用单调栈求每一位左边第一个比它小的下标
1 1 #include<bits/stdc++.h> 2 2 using namespace std; 3 3 const int maxn=1e5+10; 4 4 5 5 int n,a[maxn],b[maxn],ida[maxn],idb[maxn]; 6 6 7 7 stack<pair<int,int> > s; 8 8 9 9 int main() { 1010 while(~scanf("%d",&n)) { 1111 s.push(make_pair(-1,-1)); 1212 for(int i=0;i<n;i++) { 1313 scanf("%d",&a[i]); 1414 while(!s.empty()&&s.top().first>a[i]) s.pop(); 1515 ida[i]=s.top().second; 1616 s.push(make_pair(a[i],i)); 1717 } 1818 while(!s.empty()) s.pop(); 1919 s.push(make_pair(-1,-1)); 2020 for(int i=0;i<n;i++) { 2121 scanf("%d",&b[i]); 2222 while(!s.empty()&&s.top().first>b[i]) s.pop(); 2323 idb[i]=s.top().second; 2424 s.push(make_pair(b[i],i)); 2525 } 2626 int cur=0; 2727 while(cur<n) { 2828 if(ida[cur]==idb[cur]) cur++; 2929 else break; 3030 } 3131 printf("%d\n",cur); 3232 } 3333 return 0; 3434 }
二分+分治+ST思路：
通过$ST$表预处理出$RMQ$，$p$具有单调性，可以二分判断是否满足条件，然后询问$1{\sim}mid$最小值，再分治
1 1 #include<bits/stdc++.h> 2 2 using namespace std; 3 3 const int maxn=100010; 4 4 5 5 int dpa[maxn][20],dpb[maxn][20],a[maxn],b[maxn]; 6 6 int mm[maxn],n,ida[maxn],idb[maxn]; 7 7 8 8 void init() { 9 9 mm[0]=-1; 1010 for(int i=1;i<=n;i++) { 1111 mm[i]=((i&(i-1))==0)?mm[i-1]+1:mm[i-1]; 1212 dpa[i][0]=a[i]; 1313 dpb[i][0]=b[i]; 1414 } 1515 for(int j=1;j<=mm[n];j++) { 1616 for(int i=1;i+(1<<j)-1<=n;i++) { 1717 dpa[i][j]=min(dpa[i][j-1],dpa[i+(1<<(j-1))][j-1]); 1818 dpb[i][j]=min(dpb[i][j-1],dpb[i+(1<<(j-1))][j-1]); 1919 } 2020 } 2121 } 2222 2323 int rmqa(int x,int y) { 2424 int k=mm[y-x+1]; 2525 return ida[min(dpa[x][k],dpa[y-(1<<k)+1][k])]; 2626 } 2727 2828 int rmqb(int x,int y) { 2929 int k=mm[y-x+1]; 3030 return idb[min(dpb[x][k],dpb[y-(1<<k)+1][k])]; 3131 } 3232 3333 bool dfs(int l,int r) { 3434 if(l>=r) return true; 3535 int x=rmqa(l,r); 3636 int y=rmqb(l,r); 3737 if(x!=y) return false; 3838 else return dfs(1,x-1)&&dfs(y+1,r); 3939 } 4040 4141 bool check(int mid) { 4242 return dfs(1,mid); 4343 } 4444 4545 int main() { 4646 while(~scanf("%d",&n)) { 4747 for(int i=1;i<=n;i++) { 4848 scanf("%d",&a[i]); 4949 ida[a[i]]=i; 5050 } 5151 for(int i=1;i<=n;i++) { 5252 scanf("%d",&b[i]); 5353 idb[b[i]]=i; 5454 } 5555 init(); 5656 int l=1,r=n,ans=1; 5757 while(l<=r) { 5858 int mid=(l+r)>>1; 5959 if(check(mid)) { 6060 ans=mid; 6161 l=mid+1; 6262 } else { 6363 r=mid-1; 6464 } 6565 } 6666 printf("%d\n",ans); 6767 } 6868 }
B: Integration
题意：
给出$n$个数，$a_1,a_2,\ldots,a_n$，求$\frac1\pi\int_0^{\infty}\frac1{\prod_{i=0}^n(a_i^2+x^2)}dx$
因为分母是连乘积，所以可以列项拆分。推几项可以得出规律
1 1 #include<bits/stdc++.h> 2 2 using namespace std; 3 3 const int maxn=1010; 4 4 typedef long long ll; 5 5 const int mod=1e9+7; 6 6 7 7 ll a[maxn]; 8 8 int n; 9 9 1010 ll q_power(ll a,ll b) { 1111 ll ans=1,tmp=a%mod; 1212 while(b) { 1313 if(b&1) ans=ans*tmp%mod; 1414 tmp=tmp*tmp%mod; 1515 b>>=1; 1616 } 1717 return ans; 1818 } 1919 2020 int main() { 2121 while(~scanf("%d",&n)) { 2222 for(int i=1;i<=n;i++) scanf("%lld",&a[i]); 2323 ll ans=0; 2424 for(int i=1;i<=n;i++) { 2525 ll tmp=1; 2626 for(int j=1;j<=n;j++) { 2727 if(i==j) continue; 2828 tmp=tmp*(((a[j]*a[j]%mod)-(a[i]*a[i]%mod)+mod)%mod)%mod; 2929 } 3030 tmp=tmp*2*a[i]%mod; 3131 ans=(ans+q_power(tmp,mod-2))%mod; 3232 } 3333 printf("%lld\n",ans); 3434 } 3535 }
C：Euclidean Distance
题意：
给出$A$点的$n$维坐标$A=(a_1/m,a_2/m,\ldots,a_n/m)$，请找一点$P=(p_1,p_2,\ldots,p_n)$，满足一下条件
- $p_1,p_2,\ldots,p_n\ \in{\mathbb{R}}$
- $p_1,p_2,\ldots,p_n{\geq}0$
- $p_1+p_2+\ldots+p_n=1$
使得$\sum_{i=1}^n(a_i/m-p_i)^2$最小。
思路：
首先，我们可以将$p$的坐标放大m倍,那么答案可以转化为：
$\sum_{i=1}^n(a_i/m-p_i)^2\ =\ \sum_{i=1}^n[m(a_i/m-p_i)]^2\ \Rightarrow\ \frac1{m^2}\sum_{i=1}^n(a_i-mpi)^2$
考虑$a_i$为每个矩形的高，减去的$m$相当于削减矩形的高度，首先将$a_1,a_2,\ldots,a_n$降序排列。证：
削减高度较大的收益会比削减高度较小的收益更大，（比如负数，减去数反而变大了）。
如图中的绿线，把矩形一点一点往下推，然后下一步一起推，道理同上。
若不能进一步往下推，就把整体减一点点。可以预处理出前缀和。然后判断够不够把$a_i$前面的全部推平。
具体细节可以见上面大佬的博客。
1 1 #include<bits/stdc++.h> 2 2 using namespace std; 3 3 #define ll long long 4 4 int n,m,a[10010],sum[10010]; 5 5 6 6 bool cmp(int a,int b) { 7 7 return a>b; 8 8 } 9 9 1010 int main() { 1111 while(~scanf("%d%d",&n,&m)) { 1212 for(int i=1;i<=n;i++) scanf("%d",&a[i]); 1313 sort(a+1,a+n+1,cmp); 1414 sum[0]=-m; 1515 for(int i=1;i<=n;i++) { 1616 sum[i]=sum[i-1]+a[i]; 1717 } 1818 ll frac1,frac2; 1919 int now=n; 2020 for(int i=1;i<n;i++) { 2121 if(sum[i]>a[i+1]*i) { 2222 now=i; 2323 break; 2424 } 2525 } 2626 frac1=1ll*sum[now]*sum[now]*now; 2727 frac2=now*now; 2828 for(int i=now+1;i<=n;i++) { 2929 frac1+=1ll*a[i]*a[i]*frac2; 3030 } 3131 frac2=frac2*1ll*m*m; 3232 ll tmp=__gcd(frac1,frac2); 3333 if(frac2/tmp==1) printf("%lld\n",frac1/tmp); 3434 else if(!(frac1/tmp)) printf("0\n"); 3535 else printf("%lld/%lld\n",frac1/tmp,frac2/tmp); 3636 } 3737 }
E：ABBA
题意：
给出$2(n+m)$个$A,B$构成序列，求可以划分为$n$个$AB$，$m$个$BA$的序列的个数。
思路：
首先贪心的想，前$n$个$A$是$AB$的$A$，前$m$个$B$是$BA$的$B$。
然后$dp[i][j]$表示放了$i$个$A$，$j$个$B$的方案数。
若$i{\leq}n$，$A$可以直接放
若$j{\leq}m$，$B$可以直接放
若$i-n{\leq}j$，即现在用于组合$BA$的$A$的数量小于$B$的数量，$A$可以放
若$j-m{\leq}i$，即现在用于组合$AB$的$B$的数量小于$A$的数量，$B$可以放
1 1 #include<bits/stdc++.h> 2 2 using namespace std; 3 3 const int mod=1e9+7; 4 4 5 5 int dp[2010][2010]; 6 6 int n,m; 7 7 8 8 int main() { 9 9 while(~scanf("%d%d",&n,&m)) { 1010 for(int i=0;i<=n+m;i++) { 1111 for(int j=0;j<=n+m;j++) 1212 dp[i][j]=0; 1313 } 1414 dp[0][0]=1; 1515 for(int i=0;i<=n+m;i++) { 1616 for(int j=0;j<=n+m;j++) { 1717 if(i-n<j) dp[i+1][j]=(dp[i+1][j]+dp[i][j])%mod; 1818 if(j-m<i) dp[i][j+1]=(dp[i][j+1]+dp[i][j])%mod; 1919 } 2020 } 2121 printf("%d\n",dp[n+m][n+m]); 2222 } 2323 }
F：Random Point in Triangle
题意：
给出三角形三点坐标$A,B,C$，求
$$E=max\{S_{PAB},S_{PBC},S_{PCA}\}$$
输出$36{\times}E$
思路：
暂时只知道$ans=22{\times}S_{ABC}$，证明不会，记一下叉积求面积。$S_{ABC}=\frac12\vec{AB}{\times}\vec{AC}$
1 1 #include<iostream> 2 2 #include<cstdio> 3 3 #define lowbit(x) (x&(-x)) 4 4 #include<cstring> 5 5 using namespace std; 6 6 typedef long long ll; 7 7 8 8 int main() { 9 9 ll x1,y1,x2,y2,x3,y3; 1010 while(~scanf("%lld%lld%lld%lld%lld%lld",&x1,&y1,&x2,&y2,&x3,&y3)) { 1111 ll ans=abs(x2*y3-x2*y1-x1*y3-y2*x3+x1*y2+y1*x3); 1212 printf("%lld\n",22/2*ans); 1313 } 1414 }
I：Points Division
题意：
给出$n$个点，每个点有两个权值$a_i,b_i$，然后把这些点划分为两个集合，若点$i$在$A$中，则贡献为$a_i$，若若点$i$在$B$中，则贡献为$b_i$，
要求集合$A$在集合$B$的左上方。求划分后的最大权值和。
思路：
显然可以用一条递增的折线划分为两个区域。然后就开始玄学了。
$dp[i]$表示第$i$个点在折线上时的最大权值和。
当加入$i$时，如果$y_i$大于之前的$y_j$，则$i$的贡献为$a_i$，如果$y_i$小于之前的$y_j$，则$i$的贡献为$b_i$
那么$dp[j]=
\begin{cases}
dp[j]+b_i & j<i,y_j>y_i\\
dp[j]+a_i & j<i,y_j<y_i
\end{cases}$
$dp[i]=b_i+max_{1{\leq}<i,y_j<y_i}dp[j]$
式子可以用线段树维护区间最值（但是我比较迷，看不太懂）
还需要多加一个点。因为dp初始化为0。
（仅复习下线段树区间修改时的最大值，注意可能L>R，所以判一下）
1 1 #include<bits/stdc++.h> 2 2 using namespace std; 3 3 const int maxn=1e5+10; 4 4 typedef long long ll; 5 5 const int inf=0x3f3f3f3f; 6 6 7 7 struct node{ 8 8 ll x,y,a,b; 9 9 }p[maxn]; 10 10 ll t[maxn]; 11 11 int tot,cnt,n; 12 12 13 13 bool cmp(node a,node b) { 14 14 if(a.x==b.x) return a.y>b.y; 15 15 else return a.x<b.x; 16 16 } 17 17 18 18 ll maxx[maxn<<2],lazy[maxn<<2]; 19 19 20 20 void pushup(int rt) { 21 21 maxx[rt]=max(maxx[rt<<1],maxx[rt<<1|1]); 22 22 } 23 23 24 24 void build(int l,int r,int rt) { 25 25 lazy[rt]=maxx[rt]=0; 26 26 if(l==r) return ; 27 27 int mid=(l+r)>>1; 28 28 build(l,mid,rt<<1); 29 29 build(mid+1,r,rt<<1|1); 30 30 pushup(rt); 31 31 } 32 32 33 33 void pushdown(int rt) { 34 34 if(lazy[rt]) { 35 35 lazy[rt<<1]+=lazy[rt]; 36 36 lazy[rt<<1|1]+=lazy[rt]; 37 37 maxx[rt<<1]+=lazy[rt]; 38 38 maxx[rt<<1|1]+=lazy[rt]; 39 39 lazy[rt]=0; 40 40 } 41 41 } 42 42 43 43 void updata1(int pos,ll val,int l,int r,int rt) { 44 44 if(l==r) { 45 45 maxx[rt]=max(maxx[rt],val); 46 46 return ; 47 47 } 48 48 int mid=(l+r)>>1; 49 49 pushdown(rt); 50 50 if(pos<=mid) updata1(pos,val,l,mid,rt<<1); 51 51 else updata1(pos,val,mid+1,r,rt<<1|1); 52 52 pushup(rt); 53 53 } 54 54 55 55 void updata2(int L,int R,int val,int l,int r,int rt) { 56 56 if(L<=l&&R>=r) { 57 57 maxx[rt]+=val; 58 58 lazy[rt]+=val; 59 59 return ; 60 60 } 61 61 int mid=(l+r)>>1; 62 62 pushdown(rt); 63 63 if(L<=mid) updata2(L,R,val,l,mid,rt<<1); 64 64 if(R>mid) updata2(L,R,val,mid+1,r,rt<<1|1); 65 65 pushup(rt); 66 66 } 67 67 68 68 ll query(int L,int R,int l,int r,int rt) { 69 69 if(L<=l&&R>=r) { 70 70 return maxx[rt]; 71 71 } 72 72 ll ans=0; 73 73 int mid=(l+r)>>1; 74 74 pushdown(rt); 75 75 if(L<=mid) ans=max(ans,query(L,R,l,mid,rt<<1)); 76 76 if(R>mid) ans=max(ans,query(L,R,mid+1,r,rt<<1|1)); 77 77 return ans; 78 78 } 79 79 80 80 int main() { 81 81 while(~scanf("%d",&n)) { 82 82 cnt=0; 83 83 for(int i=1;i<=n;i++) { 84 84 scanf("%lld%lld%lld%lld",&p[i].x,&p[i].y,&p[i].a,&p[i].b); 85 85 t[++cnt]=p[i].y; 86 86 } 87 87 sort(p+1,p+n+1,cmp); 88 88 sort(t+1,t+cnt+1); 89 89 tot=unique(t+1,t+cnt+1)-t-1; 90 90 for(int i=1;i<=n;i++) { 91 91 p[i].y=lower_bound(t+1,t+tot+1,p[i].y)-t+1; 92 92 } 93 93 tot++; 94 94 build(1,tot,1); 95 95 for(int i=1;i<=n;i++) { 96 96 ll ans=query(1,p[i].y,1,tot,1); 97 97 updata1(p[i].y,ans+p[i].b,1,tot,1); 98 98 updata2(1,p[i].y-1,p[i].a,1,tot,1); 99 99 if(p[i].y+1<=tot) updata2(p[i].y+1,tot,p[i].b,1,tot,1); 100100 } 101101 printf("%lld\n",maxx[1]); 102102 } 103103 }
J：Fraction Comparision
题意：
判断$\frac{x}a$与$\frac{y}b$的大小关系
- $0{\leq}x,y{\leq}10^{18}$
- $1{\leq}a,b{\leq}10^9$
思路：
-
不能用浮点数判断(精度不够？)
-
把$\frac{x}a$写成${\lfloor}{\frac{x}a}{\rfloor}+{x\%a}$ 先比较整数部分，再交叉相乘比较分数
1 #include<bits/stdc++.h> 2 using namespace std; 3 typedef long long ll; 4 5 void out(ll x,ll y) { 6 if(x==y) puts("="); 7 else if(x>y) puts(">"); 8 else puts("<"); 9 } 10 11 12 int main() { 13 ll x,a,y,b; 14 while(~scanf("%lld%lld%lld%lld",&x,&a,&y,&b)) { 15 ll A=x/a; 16 ll B=y/b; 17 x%=a; 18 y%=b; 19 if(A!=B) out(A,B); 20 else out(xb,ya); 21 } 22 return 0; 23 }