看题目戳这里
总结
时间分配：早自习20min。听歌60min，游走60min。100min考试。
t1看了40min没看出来转t2，t2打了一半发现负数没想出来，最后二三十分钟打t3暴力，结果神奇般地0pts，因为根节点深度设为1。当然t4没看一眼。唉。
下次打模拟赛的时候把耳机摘了。
结果：30+0+0+0
总结：wssb
解析
A. 最终测试
难度：绿
我觉得很不错的概率期望题。
第 \(i\) 名的同学的期望排名 \(E_i=1+\sum_{1\leq j\leq n,j\neq i}P(s_j>s_i)\)。
而 \(P(s_j>s_i)=\frac{1}{16}\sum\limits_{0\leq f_1,f_2\leq1}\sum\limits_{0\leq g_1,g_2\leq1,i\neq j}[f_1a_{i,1}+f_2a_{i,2}<g_1a_{j,1}+g_2a_{j,2}]\)。
为什么要乘 \(\frac{1}{16}\)？因为这里每个人的不同成绩被重复算进去了。有点难想，不过可以猜结论。
我们排序再二分一下就行，复杂度 \(O(n\log n)\)。
当时看的时候想到了排序，但不知道处理排名。有时候还是要大胆一点猜结论。
#include<bits/stdc++.h>
#define mxn 100010
#define ll long long
using namespace std;
ll n,a[mxn][4];
ll sc[mxn*4],cnt,ans[mxn];
int main(){
freopen("test.in","r",stdin);
freopen("test.out","w",stdout);
ios::sync_with_stdio(0);
cin.tie(0),cout.tie(0);
cin>>n;
for(int i=1;i<=n;i++){
cin>>a[i][1]>>a[i][2];
a[i][0]=20000;
a[i][1]=20000-a[i][1],a[i][2]=20000-a[i][2];
a[i][3]=a[i][1]+a[i][2]-20000;
sc[cnt++]=a[i][0],sc[cnt++]=a[i][1];
sc[cnt++]=a[i][2],sc[cnt++]=a[i][3];
}
sort(sc,sc+cnt);
for(int i=1;i<=n;i++){
for(int j=0;j<4;j++){
int rak=lower_bound(sc,sc+cnt,a[i][j])-sc;
for(int k=0;k<4;k++)
if(a[i][k]>a[i][j])rak--;
ans[i]+=rak;
}
}
for(int i=1;i<=n;i++)
cout<<fixed<<setprecision(8)<<ans[i]/16.0+1<<'\n';
return 0;
}
B. 空间跳跃
难度：绿
容易发现 \(n>0\) 的时候就是角谷猜想，然后 \(n<0\) 的时候不知道怎么搞被迫换题。。。
实际上 \(n<0\) 的时候必会跳到 \(-1,-5,-17\) 中的一个（这是怎么看出来的？？？）
剩下的看代码。
#include<bits/stdc++.h>
#define ll long long
#define pb push_back
#define mxn 1510
using namespace std;
ll q,d,l,nega[mxn],ncnt=1501;
vector<int> ans;
void solve(int n){
ans.clear();
ans.pb(n);
while(n!=0&&n!=1&&n!=-1&&n!=-5&&n!=-17){
if(n%2)n=n*3+1;
else n/=2;
ans.pb(n);
}
while(n<=0){
n+=d;
ans.pb(n);
}
while(n!=1){
if(n%2)n=n*3+1;
else n/=2;
ans.pb(n);
}
cout<<ans.size()-1<<' ';
for(int i=ans.size()-1;i>=0;i--)
cout<<ans[i]<<' ';
cout<<'\n';
}
int main(){
freopen("jump.in","r",stdin);
freopen("jump.out","w",stdout);
ios::sync_with_stdio(0);
cin.tie(0),cout.tie(0);
cin>>q>>d>>l;
for(int i=1;i<=q;i++){
int n;
cin>>n;
solve(n);
}
return 0;
}
C. 快速访问
难度：蓝
我们知道，\(dis_{i,j}=dep_i+dep_j-2*dep_{lca(i,j)}\)。
维护一个点集 \(S\) 为对于点 \(i\)，满足题意的点。则有：
\(\sum\limits_{j\in S}dis_{i,j}=|S|dep_i+\sum\limits_{j\in S}dep_j-2*\sum\limits_{j\in S}dep_{lca(i,j)}\)
加上一个平方即为：
\(dis_{i,j}^2=dep^2_i+dep^2_j+4*dep_{lca(i,j)}^2-4*dep_idep_{lca(i,j)}-4*dep_jdep_{lca(i,j)}+2*dep_idep_j\)
三项就变成了六项，用树链剖分维护即可。
树剖+线段树复杂度 \(O(n\log^2n)\)。
#include<bits/stdc++.h>
#define mxn 200010
#define pb push_back
#define ll long long
using namespace std;
int n,q;
ll fa[mxn],sze[mxn],top[mxn],son[mxn],dep[mxn];
ll dfn[mxn],id[mxn],cnt;
vector<int> t[mxn];
void dfs1(int u,int f){
fa[u]=f,sze[u]=1;
for(int i=0;i<t[u].size();i++){
int v=t[u][i];
if(v==f)continue;
dep[v]=dep[u]+1;
dfs1(v,u);
sze[u]+=sze[v];
if(sze[son[u]]<sze[v])son[u]=v;
}
return;
}
void dfs2(int u,int f,int tp){
id[u]=++cnt;
dfn[cnt]=u,top[u]=tp;
if(son[u]!=n+1)dfs2(son[u],u,tp);
for(int i=0;i<t[u].size();i++){
int v=t[u][i];
if(v==f||v==son[u])continue;
dfs2(v,u,v);
}
return;
}
struct seg_tree1{
ll sum[mxn<<2]={0},lazy[mxn<<2]={0};
void push_up(int rot){
sum[rot]=sum[rot<<1]+sum[rot<<1|1];
}
void push_down(int rot,int l,int r){
if(!lazy[rot])return;
int mid=(l+r)>>1;
sum[rot<<1]+=lazy[rot]*(mid-l+1);
sum[rot<<1|1]+=lazy[rot]*(r-mid);
lazy[rot<<1]+=lazy[rot];
lazy[rot<<1|1]+=lazy[rot];
lazy[rot]=0;
}
void add(int rot,int l,int r,int x,int y,ll k){
if(l>=x&&r<=y){
sum[rot]+=k*(r-l+1);
lazy[rot]+=k;
return;
}
push_down(rot,l,r);
int mid=(l+r)>>1;
if(mid>=x)add(rot<<1,l,mid,x,y,k);
if(mid<y)add(rot<<1|1,mid+1,r,x,y,k);
push_up(rot);
}
ll query(int rot,int l,int r,int x,int y){
if(l>=x&&r<=y)return sum[rot];
push_down(rot,l,r);
ll ans=0;
int mid=(l+r)>>1;
if(mid>=x)ans+=query(rot<<1,l,mid,x,y);
if(mid<y)ans+=query(rot<<1|1,mid+1,r,x,y);
return ans;
}
}tre1,tre2;
struct seg_tree2{
ll sum[mxn<<2]={0},lazy[mxn<<2]={0},val[mxn<<2]={0};
void push_up(int rot){
sum[rot]=sum[rot<<1]+sum[rot<<1|1];
}
void push_down(int rot,int l,int r){
if(!lazy[rot])return;
int mid=(l+r)>>1;
sum[rot<<1]+=lazy[rot]*val[rot<<1];
sum[rot<<1|1]+=lazy[rot]*val[rot<<1|1];
lazy[rot<<1]+=lazy[rot];
lazy[rot<<1|1]+=lazy[rot];
lazy[rot]=0;
}
void build(int rot,int l,int r){
if(l==r){
val[rot]=dep[dfn[l]]*2-1;
return;
}
int mid=(l+r)>>1;
build(rot<<1,l,mid);
build(rot<<1|1,mid+1,r);
val[rot]=val[rot<<1]+val[rot<<1|1];
}
void add(int rot,int l,int r,int x,int y,int k){
if(l>=x&&r<=y){
sum[rot]+=k*val[rot];
lazy[rot]+=k;
return;
}
push_down(rot,l,r);
int mid=(l+r)>>1;
if(mid>=x)add(rot<<1,l,mid,x,y,k);
if(mid<y)add(rot<<1|1,mid+1,r,x,y,k);
push_up(rot);
}
ll query(int rot,int l,int r,int x,int y){
if(l>=x&&r<=y)return sum[rot];
push_down(rot,l,r);
ll ans=0;
int mid=(l+r)>>1;
if(mid>=x)ans+=query(rot<<1,l,mid,x,y);
if(mid<y)ans+=query(rot<<1|1,mid+1,r,x,y);
return ans;
}
}tre3;
namespace sol{
ll num,sum1,sum2;
void add(int x,int val){
num+=val,sum1+=val*dep[x],sum2+=val*dep[x]*dep[x];
int tmp=x;
while(x!=-1){
tre1.add(1,1,n,id[top[x]],id[x],val);
tre2.add(1,1,n,id[top[x]],id[x],val*dep[tmp]);
tre3.add(1,1,n,id[top[x]],id[x],val);
x=fa[top[x]];
}
}
ll query(int x){
ll ans=0,tmp=x;
ans+=num*dep[x]*dep[x];
ans+=sum2;
ans+=2ll*dep[x]*sum1;
ll ret1=0,ret2=0,ret3=0;
while(x!=-1){
ret1+=tre1.query(1,1,n,id[top[x]],id[x]);
ret2+=tre2.query(1,1,n,id[top[x]],id[x]);
ret3+=tre3.query(1,1,n,id[top[x]],id[x]);
x=fa[top[x]];
}
ans-=4ll*dep[tmp]*ret1;
ans-=4ll*ret2;
ans+=4ll*ret3;
return ans;
}
}
int main(){
freopen("visit.in","r",stdin);
freopen("visit.out","w",stdout);
ios::sync_with_stdio(0);
cin.tie(0),cout.tie(0);
cin>>n>>q;
son[0]=n+1,dep[0]=1;
for(int i=1;i<=n;i++){
son[i]=n+1;
int u,v;cin>>u>>v;
t[u].pb(v),t[v].pb(u);
}
dfs1(0,-1);
dfs2(0,-1,0);
tre3.build(1,1,n);
sol::add(0,1);
for(int i=1;i<=n;i++){
if(i-q-1>=1)sol::add(i-q-1,-1);
cout<<sol::query(i)<<'\n';
sol::add(i,1);
}
return 0;
}
D. 门童
难度：紫
首先，题目中有 \(x_{1,0}+x_{0,1}\geq 2*x_{0,0}\)。所以走一半再返回大门是不明智的。离开大门后一定要在沙发上休息一段时间后再回来。
所以可以设 \(dp(i)\) 为时刻 \(i\) 在门口，且接待完所有 \(t_j\leq i\) 选手的最大开心度。考虑上次转移时时刻为 \(k\)，则有两种情况，一种是到沙发上打摆，一种是一直站门口。
然后我们会发现关键时刻只有 \(0,t_i,t_i+p_i\)。所以可以离散化一下，复杂度 \(O(n^2)\)。
我最多想到这里。solution说用李超树，我也不会，把题目搬上来吧。
#include<bits/stdc++.h>
#define ll long long
#define inf 0x3f3f3f3f3f3f3f3fll
#define maxn 202020
using namespace std;
ll t[maxn],a[maxn],b[maxn],c[maxn],L[maxn];
ll N[maxn],K[maxn],B[maxn],dp[maxn];
ll left_i[maxn],right_i[maxn];
struct lichao_tree{
struct line{
ll k,b;
}tr[maxn*4];
void init(int n){
for(int i=0;i<=4*n;i++)
tr[i].k=0,tr[i].b=-inf;
}
void add(int L,int R,ll k,ll b,int l,int r,int rt){
if(L<=l&&r<=R){
int mid=(l+r)/2;
bool bl=((k*t[l]+b)<=(tr[rt].k*t[l]+tr[rt].b));
bool br=((k*t[r]+b)<=(tr[rt].k*t[r]+tr[rt].b));
if(bl&&br)return;
else if(!bl&&!br){
tr[rt]=(line){k,b};
return;
}
else{
bool bm=(k*t[mid]+b)<=(tr[rt].k*t[mid]+tr[rt].b);
line li=(line){k,b};
if(!bm)li=tr[rt],tr[rt]=(line){k,b};
if((!bm&&bl)||(bm&&!bl))
add(L,R,li.k,li.b,l,mid,rt<<1);
else add(L,R,li.k,li.b,mid+1,r,rt<<1|1);
}
return;
}
int mid=(l+r)/2;
if(L<=mid)add(L,R,k,b,l,mid,rt<<1);
if(mid<R)add(L,R,k,b,mid+1,r,rt<<1|1);
}
ll ask(int p,int l,int r,int rt){
if(l==r)return tr[rt].k*t[p]+tr[rt].b;
int mid=(l+r)/2;
ll ans=tr[rt].k*t[p]+tr[rt].b;
if(p<=mid)ans=max(ans,ask(p,l,mid,rt<<1));
else ans=max(ans,ask(p,mid+1,r,rt<<1|1));
return ans;
}
}S1,S2;
int main(){
// freopen("doorman.in","r",stdin);
// freopen("doorman.out","w",stdout);
ios::sync_with_stdio(0);
cin.tie(0),cout.tie(0);
int tot=0,n,l;
cin>>n>>l;
int x[4];
for(int i=0;i<4;i++)
cin>>x[i];
t[tot++]=0;
for(int i=1;i<=n;i++){
cin>>a[i]>>b[i]>>c[i];
t[tot++]=a[i];
t[tot++]=a[i]+b[i];
}
sort(t,t+tot);
tot=unique(t,t+tot)-t;//排序加去重
for(int i=1;i<=n;i++){
int l=lower_bound(t,t+tot,a[i])-t;
int r=lower_bound(t,t+tot,a[i]+b[i])-t;
L[r]=max(L[r],l*1ll);
N[l]++;
K[l]+=c[i];
B[l]+=c[i]*(a[i]+b[i]);
}
for(int i=1;i<tot;i++){
L[i]=max(L[i],L[i-1]);
N[i]+=N[i-1];
K[i]+=K[i-1];
B[i]+=B[i-1];
}
ll O=((x[1]+x[2]+2*x[3])*l)/(x[0]+x[3]);
int las=tot-1;
for(;N[las]==n;las--);
ll ans=-inf;
int left_t=0,right_t=-1;
memset(left_i,0x3f,sizeof(left_i));
for(int i=1;i<tot;i++){
while(right_t+1<i&&right_t+1<=las){
right_t++;
left_i[right_t]=i;
}
while(left_t<L[i-1]){
right_i[left_t]=i-1;
left_t++;
}
}
while(left_t<=right_t)
right_i[left_t]=tot-1,left_t++;
S1.init(tot);
if(left_i[0]<=right_i[0])
S1.add(left_i[0],right_i[0],K[0],dp[0]-B[0]-x[3]*t[0],0,tot-1,1);
for(int i=1;i<tot;i++){
dp[i]=max(S1.ask(i,0,tot-1,1)+B[i]-K[i]*t[i]+x[3]*t[i]-(x[1]+x[2]+2*x[3])*l,
dp[i-1]+B[i]-B[i-1]-(K[i]-K[i-1])*t[i]-x[0]*(t[i]-t[i-1]));
if(left_i[i]<=right_i[i])
S1.add(left_i[i],right_i[i],K[i],dp[i]-B[i]-x[3]*t[i],0,tot-1,1);
if(N[i]==n)ans=max(ans,dp[i]);
}
cout<<ans;
return 0;
}