HHHOJ 2022.05.29「NOIP模拟赛贰」

yzxoi

2022-06-04 (Updated: 2022-06-25)

暴力, 树形dp, 贪心

比赛概况

100+50+100=250，2/16，t2 RE怒丢50pts

A. Median

定义两个数列，$S = {S(1), S(2), …, S(n)}$ 和 $S_2 = {S_2(1), S_2(2), …, S_2(n)}$

$$S(k) = (p_k\times k) \bmod w,\text{where } p_k \text{ is the kth prime number}$$

$$S_2(k) = S(k) + S(\lfloor\frac{k}{10}\rfloor + 1)$$

令 $M(i,j)$ 表示 $S_2(i)$ 到 $S_2(j)$ 的中位数。

现在给定 $n,k$，求 $$\sum_{i=1}^{n-k+1} M(i, i + k - 1)$$

$w\leq k\leq n \leq 10^7$

Tutorial

乍一看感觉比较神秘？仔细想一想应该是随机分布的，由于中位数每次移动只会移两位，所以暴力跳就好了。

Solution

#include<bits/stdc++.h>
#define Tp template<typename Ty>
#define Ts template<typename Ty,typename... Ar>
#define W while
#define I inline
#define RI register int
#define LL long long
#define Cn const
#define CI Cn int&
#define gc getchar
#define D isdigit(c=gc())
#define pc(c) putchar((c))
using namespace std;
namespace Debug{
Tp I void _debug(Cn char* f,Ty t){cerr<<f<<'='<<t<<endl;}
Ts I void _debug(Cn char* f,Ty x,Ar... y){W(*f!=',') cerr<<*f++;cerr<<'='<<x<<",";_debug(f+1,y...);}
Tp ostream& operator<<(ostream& os,Cn vector<Ty>& V){os<<"[";for(Cn auto& vv:V) os<<vv<<",";os<<"]";return os;}
#define gdb(...) _debug(#__VA_ARGS__,__VA_ARGS__)
}using namespace Debug;
namespace FastIO{
Tp I void read(Ty& x){char c;int f=1;x=0;W(!D) f=c^'-'?1:-1;W(x=(x<<3)+(x<<1)+(c&15),D);x*=f;}
Ts I void read(Ty& x,Ar&... y){read(x),read(y...);}
Tp I void write(Ty x){x<0&&(pc('-'),x=-x,0),x<10?(pc(x+'0'),0):(write(x/10),pc(x%10+'0'),0);}
Tp I void writeln(Cn Ty& x){write(x),pc('\n');}
}using namespace FastIO;
Cn int N=1e7+10,M=1.8e8;
int n,k,w,s2[N],p[N],cnt,t[N<<1],HL,DL,HR,DR;bool vis[M];
LL Ans;
I void GP(){RI i,j;for(i=2;cnt<=n;i++) for(!vis[i]&&(p[++cnt]=i),j=1;j<=cnt&&1LL*i*p[j]<M;j++) if(vis[i*p[j]]=1,!(i%p[j])) break ;}
signed main(){
#define s(i) (1LL*p[i]*(i)%w) 
RI i,l,r,mid,X;for(read(n,k,w),GP(),gdb(cnt,p[cnt]),i=1;i<=n;i++) s2[i]=s(i)+s(i/10+1);
for(i=1;i<k;i++) t[s2[i]]++;for(HL=HR=-1,i=k;i<=n;i++){
t[s2[i]]++,s2[i]<=HL&&++DL,s2[i]<=HR&&++DR;
W(DL<k/2) DL+=t[++HL];W(DL-t[HL]>=k/2) DL-=t[HL--];
W(DR<k/2+1) DR+=t[++HR];W(DR-t[HR]>=k/2+1) DR-=t[HR--];
Ans+=k&1?HR<<1:(HL+HR);
t[s2[i-k+1]]--,s2[i-k+1]<=HL&&--DL,s2[i-k+1]<=HR&&--DR;
}return printf("%.1lf\n",Ans/2.0),0;
}

B. Game

Alice和Bob又在玩游戏。

现在有一个长为 $n$ 的正整数序列 $a_i$ ，其中的数字小于等于 $n$，且相同的数字可能出现多次。

游戏最先，他们把序列的前 $p$ 个元素放入一个可重集 $S$，接下来两人轮流操作，一次操作包括：

当前操作者从集合中拿出一个数，计入自己的得分。
将序列中下一个数放入集合，也就是说，第一次操作后，$a_{p+1}$会被放入集合，以此类推。如果没有剩余的未放入的数，即不放入任何数。

Alice先手，她想知道，如果两人都采取最优策略让自己的得分最大，假设 Alice 最终分数为 $A$，Bob 最终分数为 $B$，则 $A-B$ 的值将会是多少。

他们进行了很多次游戏，每次游戏序列 $a_i$ 是相同的，只是给出不同的 $p$。

$n\leq 100000,k\leq 2000,1\leq a_i\leq n,1\leq p_i\leq n,k\leq n$

Tutorial

显然只需要每次取最大的，开个权值数组记录每个数出现的次数，一个指针指向这个数组中最大的出现过的数，这个指针是会不断的变小的，因为如果新加入的数更大，就会直接被拿走。

所以时间复杂度是 $O(kn)$。

Solution

#include<bits/stdc++.h>
#define Tp template<typename Ty>
#define Ts template<typename Ty,typename... Ar>
#define W while
#define I inline
#define RI register int
#define LL long long
#define Cn const
#define CI Cn int&
#define gc getchar
#define D isdigit(c=gc())
#define pc(c) putchar((c))
using namespace std;
namespace Debug{
Tp I void _debug(Cn char* f,Ty t){cerr<<f<<'='<<t<<endl;}
Ts I void _debug(Cn char* f,Ty x,Ar... y){W(*f!=',') cerr<<*f++;cerr<<'='<<x<<",";_debug(f+1,y...);}
Tp ostream& operator<<(ostream& os,Cn vector<Ty>& V){os<<"[";for(Cn auto& vv:V) os<<vv<<",";os<<"]";return os;}
#define gdb(...) _debug(#__VA_ARGS__,__VA_ARGS__)
}using namespace Debug;
namespace FastIO{
Tp I void read(Ty& x){char c;int f=1;x=0;W(!D) f=c^'-'?1:-1;W(x=(x<<3)+(x<<1)+(c&15),D);x*=f;}
Ts I void read(Ty& x,Ar&... y){read(x),read(y...);}
Tp I void write(Ty x){x<0&&(pc('-'),x=-x,0),x<10?(pc(x+'0'),0):(write(x/10),pc(x%10+'0'),0);}
Tp I void writeln(Cn Ty& x){write(x),pc('\n');}
}using namespace FastIO;
Cn int N=1e5+10,K=2e3+10;
int n,Qk,a[N],t[N];LL Ans;
int main(){
RI i,j,p,o,mx;for(read(n,Qk),i=1;i<=n;i++) read(a[i]);for(i=1;i<=Qk;i++){
for(read(p),mx=Ans=0,o=1,j=1;j<p;j++) t[a[j]]++,mx=max(mx,a[j]);for(j=1;j<=n;o^=1,j++){
W(!t[mx]) --mx;if(j+p-1<=n&&a[j+p-1]>mx) Ans+=(o&1?1:-1)*a[j+p-1];else Ans+=(o&1?1:-1)*mx,--t[mx],j+p-1<=n&&++t[a[j+p-1]];
}writeln(Ans);
}return 0;
}

C. Park

公园里有 $n$ 个雕像，有 $n-1$ 条道路分别连接其中两个雕像，使得任意两个雕像可以相连。

现在每个景点 $i$ 聚集着一群 $p_i$ 只鸽子，旅行家手里有 $v$ 数量的面包屑。

一旦旅行家在雕像 $i$ 撒下 $1$ 单位面包屑，那么相邻的雕像的鸽子就都会飞到雕像 $i$ 来觅食。

时间线是这样的：首先，旅行家到达雕像 $i$ 并与 $p_i$ 鸽子会面。然后，他放下 $1$ 单位面包屑。他离开雕像。在旅行家到达下一座雕像之前，来自相邻雕像的鸽子移动到雕像 $i$（所以这些鸽子 不计入 他遇到的鸽子数）。注意旅行家每到达雕像可以撒下面包屑，也可以不撒。

旅行家可以在任何一座雕像上进入公园，沿着一些道路走下去（但不要使用同一道路两次），然后离开公园。

在旅行家离开公园后，没有面包屑的小学生将进入并穿越完全相同的路线，并遇见许多群鸽子。

通过最多 $v$ 单位面包屑，旅行家希望最大化旅行家在路线上遇到的鸽子数量与小学生遇到的鸽子数量之间的差异。

$1\leq n\leq 10^5,0\leq v\leq 100,0\leq p_i\leq 10^9$

Tutorial

记录两个数组 $c_{i,j},d_{i,j}$ 分别表示从子树$i$ 中某个点走到 $i$ 或从$i$ 走到子树中某个点，撒了 $j$ 的最大收益

注意对一个子树遍历的相对顺序会影响贡献，所以得扫两次。

Solution

#include<bits/stdc++.h>
#define Tp template<typename Ty>
#define Ts template<typename Ty,typename... Ar>
#define W while
#define I inline
#define RI register int
#define LL long long
#define Cn const
#define CI Cn int&
#define gc getchar
#define D isdigit(c=gc())
#define pc(c) putchar((c))
using namespace std;
namespace Debug{
Tp I void _debug(Cn char* f,Ty t){cerr<<f<<'='<<t<<endl;}
Ts I void _debug(Cn char* f,Ty x,Ar... y){W(*f!=',') cerr<<*f++;cerr<<'='<<x<<",";_debug(f+1,y...);}
Tp ostream& operator<<(ostream& os,Cn vector<Ty>& V){os<<"[";for(Cn auto& vv:V) os<<vv<<",";os<<"]";return os;}
#define gdb(...) _debug(#__VA_ARGS__,__VA_ARGS__)
}using namespace Debug;
namespace FastIO{
Tp I void read(Ty& x){char c;int f=1;x=0;W(!D) f=c^'-'?1:-1;W(x=(x<<3)+(x<<1)+(c&15),D);x*=f;}
Ts I void read(Ty& x,Ar&... y){read(x),read(y...);}
Tp I void write(Ty x){x<0&&(pc('-'),x=-x,0),x<10?(pc(x+'0'),0):(write(x/10),pc(x%10+'0'),0);}
Tp I void writeln(Cn Ty& x){write(x),pc('\n');}
}using namespace FastIO;
Cn int N=1e5+10,M=110;
int n,a[N],v0,fir[N],nxt[N<<1],son[N<<1],tot;
LL c[N],Ans,up[N][M],dn[N][M];
I void Add(CI x,CI y){nxt[++tot]=fir[x],fir[x]=tot,son[tot]=y;}
#define to son[i]
vector<int> v;
#define pb push_back
I void DFS(CI x,CI fa){
#define G(x,y) ((x<(y))&&(x=(y)))
RI i,rd;for(i=fir[x];i;i=nxt[i]) to^fa&&(DFS(to,x),0);
for(v.clear(),i=fir[x];i;i=nxt[i]) to^fa&&(v.pb(to),0);
for(rd=1;rd<=2;rd++,reverse(v.begin(),v.end())){
for(i=1;i<=v0;i++) up[x][i]=c[x],dn[x][i]=c[x]-a[fa];
for(auto y:v){
for(i=1;i<=v0;i++) Ans=max(Ans,up[x][i]+dn[y][v0-i]);
for(i=1;i<=v0;i++) G(up[x][i],up[y][i-1]+c[x]-a[y]),G(up[x][i],up[y][i]),G(dn[x][i],dn[y][i-1]+c[x]-a[fa]),G(dn[x][i],dn[y][i]);
}
}
}
int main(){
RI i,j,x,y;for(read(n,v0),i=1;i<=n;i++) read(a[i]);
for(i=1;i<n;i++) read(x,y),Add(x,y),Add(y,x);
for(j=1;j<=n;j++) for(i=fir[j];i;i=nxt[i]) c[j]+=a[to];
return DFS(1,0),writeln(Ans),0;
}