HHHOJ 2022.05.29「NOIP模拟赛贰」

yzxoi

发布于 2022-09-19 14:17:23

2950

发布于 2022-09-19 14:17:23

文章被收录于专栏：OI

HHHOJ 2022.05.29「NOIP模拟赛贰」

比赛概况

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) 的中位数。

，求

\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;
}

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2022-06-04 ，如有侵权请联系 cloudcommunity@tencent.com 删除

编程算法

游戏

本文分享自作者个人站点/博客前往查看

如有侵权，请联系 cloudcommunity@tencent.com 删除。

本文参与腾讯云自媒体同步曝光计划，欢迎热爱写作的你一起参与！

编程算法

游戏

登录后参与评论

0 条评论

热度

HHHOJ 2022.05.29「NOIP模拟赛贰」

HHHOJ 2022.05.29「NOIP模拟赛贰」

HHHOJ 2022.05.29「NOIP模拟赛贰」

比赛概况

A. Median

Tutorial

Solution

B. Game

Tutorial

Solution

C. Park

Tutorial

Solution

社区

活动

资源

关于

腾讯云开发者

热门产品

热门推荐

更多推荐

HHHOJ 2022.05.29「NOIP模拟赛 贰」

HHHOJ 2022.05.29「NOIP模拟赛 贰」

HHHOJ 2022.05.29「NOIP模拟赛 贰」

比赛概况

A. Median

Tutorial

Solution

B. Game

Tutorial

Solution

C. Park

Tutorial

Solution

社区

活动

资源

关于

腾讯云开发者

热门产品

热门推荐

更多推荐

HHHOJ 2022.05.29「NOIP模拟赛贰」

HHHOJ 2022.05.29「NOIP模拟赛贰」

HHHOJ 2022.05.29「NOIP模拟赛贰」