比赛链接：
https://ac.nowcoder.com/acm/contest/881#question
A. Equivalent Prefixes
题意：
给出两个序列，求出一个最大的$p$，使$RMQ(v,l,r)=RMQ(u,l,r),1leq lleq rleq p)$
$RMQ(v,l,r)$代表在$v$数组中，区间$[l,r]$的最小值下标
分析：
单调栈找到每个数向左延升第一个比它小的数，得到两个新的序列
找到最大相同前缀，就是题目所求的$p$
ac代码：
#include<bits/stdc++.h>
#define ll long long
#define PI acos(-1.0)
#define pa pair<int,int>
using namespace std;
const int maxn=1e5+10;
const ll mod=1e9+7;
int n;
int a[maxn],b[maxn];
int za[maxn],zb[maxn];
int top;
pa stac[maxn];
//找到第一个比它大的值
int main()
{
while(scanf("%d",&n)==1)
{
for(int i=1;i<=n;i++)scanf("%d",&a[i]);
for(int i=1;i<=n;i++)scanf("%d",&b[i]);
for(int i=n;i>=1;i--)
{
while(top>=1&&stac[top].first>a[i])za[stac[top].second]=i,top--;
stac[++top]=make_pair(a[i],i);
}
while(top)za[stac[top].second]=0,top--;
for(int i=n;i>=1;i--)
{
while(top>=1&&stac[top].first>b[i])zb[stac[top].second]=i,top--;
stac[++top]=make_pair(b[i],i);
}
while(top)zb[stac[top].second]=0,top--;
int ans=0;
for(int i=1;i<=n;i++)
{
// cout<<za[i]<<" "<<zb[i]<<endl;
if(za[i]==zb[i])
ans++;
else
break;
}
printf("%d
",ans);
}
return 0;
}
E. ABAB
题意：
求出能分解成$n$个$AB$子序列和$m$个$BA$子序列的字符串种类数
分析：
首先分析如何贪心判断一个字符串是否可以分解成$n$个$AB$和$m$个$BA$，如果遇到$A$并且总数少于$n$那么肯定合法，总数大于$n$，那么就让多余的$A$与前面的$B$结合
定义$dp[i][j]$长度位$i+j$并且有$i$个$A$和$j$个$B$的前缀方案数
例如 $dp[0][0]$方案数为$1$，只有空字符串一种
转移方程：看代码
ac代码：
#include<bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define pa pair<int,int>
using namespace std;
const int maxn=2e3+5;
const int maxm=1e7+10;
const ll mod=1e9+7;
int n,m;
int dp[maxn][maxn];
int main()
{
while(scanf("%d %d",&n,&m)==2)
{
for(int i=0;i<=n+m;i++)
for(int j=0;j<=n+m;j++)
dp[i][j]=0;
for(int i=0;i<=n;i++)dp[i][0]=1;
for(int i=0;i<=m;i++)dp[0][i]=1;
for(int i=1;i<=n+m;i++)
{
for(int j=1;j<=n+m;j++)
{
if(i<=n||j-i+1+n>0)
dp[i][j]=(dp[i][j]+dp[i-1][j])%mod;
if(j<=m||i-j+1+m>0)
dp[i][j]=(dp[i][j]+dp[i][j-1])%mod;
}
}
printf("%d
",dp[n+m][n+m]);
}
return 0;
}
F. Random Point in Triangle
题意：
求出在一个三角形中加一个点，三条边与这个点构成的三个三角形的最大三角形的期望面积*36
保证最后的结果是整数
分析：
既然保证是整数，那么结果应该不是很复杂，期望面积很可能与原三角形的面积有关
一种暴力的方法是，在给定的三角形中撒上$1e7$个点，求出的平均面积接近期望面积
网上也有大佬证明，看不懂
ac代码：
#include<bits/stdc++.h>
#define ll long long
#define PI acos(-1.0)
#define pa pair<int,int>
using namespace std;
const int maxn=1e5+10;
const ll mod=1e9+7;
struct Point
{
ll x,y;
}point[3];
int main()
{
while(scanf("%lld %lld",&point[0].x,&point[0].y)==2)
{
scanf("%lld %lld",&point[1].x,&point[1].y);
scanf("%lld %lld",&point[2].x,&point[2].y);
point[1].x-=point[0].x;
point[1].y-=point[0].y;
point[2].x-=point[0].x;
point[2].y-=point[0].y;
ll area=abs(point[1].x*point[2].y-point[1].y*point[2].x);
printf("%lld
",area*11);
}
return 0;
}
J.Fraction Comparision
题意：
给出$x,y,a,b$
求出$frac{x}{a}$与$frac{y}{b}$的大小关系
分析：
Java大数类可以直接过
ac代码：
import java.math.BigInteger;
import java.util.Scanner;
public class Main{
public static void main (String[] args)
{
int n;
Scanner cin=new Scanner(System.in);
while(cin.hasNext())
{
BigInteger x=cin.nextBigInteger();
BigInteger a=cin.nextBigInteger();
BigInteger y=cin.nextBigInteger();
BigInteger b=cin.nextBigInteger();
x=x.multiply(b);
y=y.multiply(a);
int key=x.compareTo(y);
if(key==0)System.out.println("=");
else if(key==-1)System.out.println("<");
else if(key==1)System.out.println(">");
}
}
}
B. Integration
题意：
求一个连乘表达式的积分
分析：
参考博客：https://www.cnblogs.com/Dillonh/p/11209476.html
大致思路，算出表达式的系数，化简
ac代码：
#include<bits/stdc++.h>
#define ll long long
#define PI acos(-1.0)
#define pa pair<int,int>
using namespace std;
const int maxn=1e3+10;
const ll mod=1e9+7;
ll a[maxn];
ll qpow(ll x,ll y)
{
ll res=1,k=x;
while(y){
if(y%2)res=res*k%mod;
k=k*k%mod;
y/=2;
}
return res;
}
int main()
{
int n;
while(scanf("%d",&n)==1){
ll ans=0;
for(int i=1;i<=n;i++)scanf("%lld",&a[i]);
for(int i=1;i<=n;i++){
ll res=1;
for(int j=1;j<=n;j++){
if(i==j)continue;
res=res*(a[j]*a[j]%mod-a[i]*a[i]%mod+mod)%mod;
}
res=qpow(res,mod-2)%mod;
res=res*qpow(a[i],mod-2)%mod;
ans=(ans+res)%mod;
}
ans=ans*qpow(2,mod-2)%mod;
printf("%lld
",ans);
}
return 0;
}
H. XOR
题意：
给出一个数组，求所有异或和为0的子集$size$累加和
分析
对于$a_i$，它对答案的贡献就是包含它的异或和为0的子集种类数
我们先对整体的数组求线性基，假设共$r$个元素作为基底
线性基外面的每个元素的贡献为$2^{n-r-1}$，因为基底外的元素可以被基底唯一表示
对于线性基里面的元素$a_i$，对$n-1$个数求一次线性基，如果$a_i$能插入，那么$a_i$没有贡献，否则同上计算
ac代码：
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int maxn = 1e5 + 5;
const ll mod = 1e9 + 7;
ll base1[70],base2[70],temp[70];
ll num[maxn],sk1[maxn],sk2[maxn];
int top1,top2,zz;
ll qpow(int x,ll y)
{
ll res=1,k=x;
while(y){
if(y&1)res=res*k%mod;
k=k*k%mod;
y/=2;
}
return res;
}
bool insert(ll base[],ll x)
{
for(int i=0;i<62;i++){
if(x&((ll)1<<i)){
if(base[i]==0){
base[i]=x;
return 1;
}
x^=base[i];
}
}
return 0;
}
int main()
{
int n;
// cout<<((ll)1<<62)<<endl;
while(scanf("%d",&n)==1){
for(int i=0;i<62;i++)base1[i]=base2[i]=0;
top1=top2=zz=0;
for(int i=1;i<=n;i++){
scanf("%lld",&num[i]);
if(insert(base1,num[i]))sk1[++top1]=num[i];
else sk2[++top2]=num[i];
}
ll ans=top2*qpow(2,top2-1)%mod;//基底外元素的贡献
// cout<<ans<<endl;
for(int i=1;i<=top2;i++)
if(insert(base2,sk2[i]))zz++;//先把基底外元素插入
for(int i=1;i<=top1;i++){
for(int j=0;j<62;j++)temp[j]=base2[j];
int cnt=0;
for(int j=1;j<=top1;j++)
if(j!=i)if(insert(temp,sk1[j]))cnt++;//插入基底内元素
if(insert(temp,sk1[i])==0)ans=(ans+qpow(2,n-cnt-1-zz))%mod;//此元素插不进时才可以计算贡献
// cout<<ans<<endl;
}
printf("%lld
",ans);
}
return 0;
}
C. Euclidean Distance
题意：
给出$a$数组，构造一个$p$数组，满足$p_{i}geq 0,sum p_i=1$
求$sum (a_{i}-p_{i})^{2}$的最小值
分析
贪心地将比较大的数变小，如果数相同，那么均摊给它们
ac代码：
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int maxn = 1e4 + 5;
const ll mod = 1e9 + 7;
ll a[maxn];
bool cmp(ll a,ll b)
{
return a>b;
}
int main()
{
int n,m;
while(scanf("%d %d",&n,&m)==2){
for(int i=1;i<=n;i++)scanf("%lld",&a[i]);
sort(a+1,a+1+n,cmp);
int cnt=0;
for(int i=1;i<=n;i++){
if(i<n&&(a[i]-a[i+1])*i+cnt<=m){
cnt+=(a[i]-a[i+1])*i;
}else{
ll ans=(m-cnt-i*a[i])*(m-cnt-i*a[i]);
for(int j=i+1;j<=n;j++)
ans=ans+i*a[j]*a[j];
ll d=(ll)i*m*m;
if(ans==0){
printf("0
");
break;
}
ll p=__gcd(d,ans);
ans/=p;
d/=p;
if(d==1)printf("%lld
",ans);
else printf("%lld/%lld
",ans,d);
break;
}
}
}
return 0;
}
I. Points Division
题意：
给出一些点，把它们划分成两个部分，第二部分点只有左上角可以出现第一部分的点
分析
$dp[i]$定义状态为以i点为划分折线上最后一个第二部分点
插入一个$x$极小，$y$极小的点，方便转移和计算全是第一部分的情况
这dp太难了，弱鸡理解了，但是很难正推到这样的dp
参考博客：https://blog.csdn.net/u013534123/article/details/96465704
ac代码：
#include<bits/stdc++.h>
#define ll long long
#define pa pair<int,int>
using namespace std;
const int maxn=1e5+10;
struct Node{
int x,y,a,b;
bool operator < (const Node &e)const{
if(x!=e.x)return x<e.x;
return y>e.y;
}
}ne[maxn];
ll tree[maxn*4],lazy[maxn*4];
int sk[maxn],n,ran[maxn];
void build(int st,int en,int rt)
{
if(st==en){
tree[rt]=-1e18;
lazy[rt]=0;
return ;
}
int md=(st+en)/2;
build(st,md,rt*2);
build(md+1,en,rt*2+1);
tree[rt]=max(tree[rt*2],tree[rt*2+1]);
}
void update1(int x,ll y,int st,int en,int rt)
{
if(st==en){
tree[rt]=max(y,tree[rt]);
return ;
}
if(lazy[rt]){
tree[rt*2+1]+=lazy[rt];
tree[rt*2]+=lazy[rt];
lazy[rt*2]+=lazy[rt];
lazy[rt*2+1]+=lazy[rt];
lazy[rt]=0;
}
int md=(st+en)/2;
if(x<=md)update1(x,y,st,md,rt*2);
else update1(x,y,md+1,en,rt*2+1);
tree[rt]=max(tree[rt*2],tree[rt*2+1]);
}
void update2(int l,int r,int y,int st,int en,int rt)
{
if(l>r)return ;
if(l>en||r<st){
return ;
}
if(l<=st&&r>=en){
tree[rt]+=y;
lazy[rt]+=y;
return;
}
if(lazy[rt]){
tree[rt*2+1]+=lazy[rt];
tree[rt*2]+=lazy[rt];
lazy[rt*2]+=lazy[rt];
lazy[rt*2+1]+=lazy[rt];
lazy[rt]=0;
}
int md=(st+en)/2;
update2(l,r,y,st,md,rt*2);
update2(l,r,y,md+1,en,rt*2+1);
tree[rt]=max(tree[rt*2],tree[rt*2+1]);
}
ll quer(int l,int r,int st,int en,int rt)
{
if(r<st||l>en)return -1e18;
if(l<=st&&r>=en)return tree[rt];
if(lazy[rt]){
tree[rt*2+1]+=lazy[rt];
tree[rt*2]+=lazy[rt];
lazy[rt*2]+=lazy[rt];
lazy[rt*2+1]+=lazy[rt];
lazy[rt]=0;
}
int md=(st+en)/2;
ll res=max(quer(l,r,st,md,rt*2),quer(l,r,md+1,en,rt*2+1));
tree[rt]=max(tree[rt*2],tree[rt*2+1]);
return res;
}
int main()
{
while(scanf("%d",&n)==1){
for(int i=1;i<=n;i++){
scanf("%d %d %d %d",&ne[i].x,&ne[i].y,&ne[i].a,&ne[i].b);
sk[i]=ne[i].y;
}
sort(ne+1,ne+1+n);
sort(sk+1,sk+1+n);
int cnt=unique(sk+1,sk+1+n)-sk-1;
for(int i=1;i<=n;i++)ran[i]=lower_bound(sk+1,sk+1+cnt,ne[i].y)-sk+1;
cnt++;
//cout<<cnt<<endl;
build(1,cnt,1);
update1(1,0,1,cnt,1);
for(int i=1;i<=n;i++){
update1(ran[i],quer(1,ran[i],1,cnt,1)+ne[i].b,1,cnt,1);
update2(1,ran[i]-1,ne[i].a,1,cnt,1);
update2(ran[i]+1,cnt,ne[i].b,1,cnt,1);
}
printf("%lld
",tree[1]);
}
return 0;
}