首页 > 其他分享 >NOIP2024 前集训：NOIP2024加赛 3（欢乐赛）

NOIP2024 前集训：NOIP2024加赛 3（欢乐赛）

时间：2024-11-13 15:57:38浏览次数：1  
标签：int void Tp write read inline 加赛 集训 NOIP2024

前言

再次考古，现在才写。

这场叫欢乐赛，搬的 CF，不知道 OJ 哪儿来的 RMJ。

就记得 T3 一直往数据结构上想浪费好多时间，结果发现是结论题 \(O(n)\) 可做。

T1 Sakurako and Water

虽然我之前不知道主对角线是什么东西，但是看完题目自动把他过滤成左上角到右下角了（不知道当时怎么想的，好像根本没想），然后发现一条对角线每次选都选了不全选是唐氏，就做完了。

T2 Binomial Coefficients, Kind Of

题目是给了一串（错误的）杨辉三角求组合数代码，人均读假一遍题，发现他写的是错的，实际是 \(2^k\)。

T3 QED's Favorite Permutation

不知道 QED 和这题啥关系。

发现 LR 会成为分割点使左右不再互通，因为他每次都是单点修改，所以根本不用维护这说直接判就可以了，判断这个 LR 是否有区间需要越过他，前缀和一下即可。

点击查看代码 
#include<bits/stdc++.h>
#define ll long long
#define endl '\n'
#define sort stable_sort
using namespace std;
const int N=2e5+10;
int T,n,m,cant,a[N],suml[N],sumr[N]; string s;
signed main()
{
	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	for(cin>>T;T;T--,cant=0)
	{
		cin>>n>>m,memset(suml,0,4*(n+1)),memset(sumr,0,4*(n+1));
		for(int i=1,x;i<=n;i++)
			cin>>x,(x!=i)&&(++suml[min(x,i)+1])&&(++sumr[max(x,i)]);
		for(int i=1;i<=n;i++) suml[i]+=suml[i-1],sumr[i]+=sumr[i-1];
		cin>>s,s=" "+s; for(int i=2,tmp;i<=n;i++)
			cant+=(s[i]=='R'&&s[i-1]=='L'&&suml[i]-sumr[i-1]);
		for(int i=1,x;i<=m;i++)
		{
			cin>>x;
			cant-=(s[x]=='L'&&s[x+1]=='R'&&suml[x+1]-sumr[x]);
			cant-=(s[x]=='R'&&s[x-1]=='L'&&suml[x]-sumr[x-1]);
			cant+=(s[x]=='L'&&s[x-1]=='L'&&suml[x]-sumr[x-1]);
			cant+=(s[x]=='R'&&s[x+1]=='R'&&suml[x+1]-sumr[x]);
			puts(cant?"NO":"YES"),s[x]=s[x]=='R'?'L':'R';
		}
	}
}

T4 Card Game

是道不需要一点优化的朴素 DP，但赛时一直唐 T3 没有写出来。

发现对于 \(1\) 花色的牌只有 Alice 可以多拿，同理剩下的牌只有 Bob 可以多拿，且 Alice 多拿的数量等于 Bob 多拿的数量。

\(f_{i,j}\) 表示在花色为 \(1\) 的排中，目前为第 \(i\) 大的牌，Alice 多拿了 \(j\) 张的方案数，显然有转移：

\[f_{i,j}=f_{i-1,j-1}+f_{i-1,j+1} \]

\(g_{i,j}\) 表示在不包括 \(1\) 的前 \(i\) 种花色中 Bob 多拿了 \(j\) 张牌的贡献，发现对于每一种花色的转移和上面是一样的，所以有：

\[g_{i,j}=\sum_{k=0}^jg_{i-1,k}f_{m,j-k} \]

根据上面的结论，最后答案就是 \(\sum\limits_{i=0}^mf_{m,i}g_{n-1,i}\)。

点击查看代码 
#include<bits/stdc++.h>
#define ll long long
#define endl '\n'
#define sort stable_sort
using namespace std;
const int N=510,P=998244353;
template<typename Tp> inline void read(Tp&x)
{
	x=0;register bool z=true;
	register char c=getchar();
	for(;!isdigit(c);c=getchar()) if(c=='-') z=0;
	for(;isdigit(c);c=getchar()) x=(x<<1)+(x<<3)+(c^48);
	x=(z?x:~x+1);
}
template<typename T,typename ...Tp> inline void read(T &x,Tp &...y){read(x);read(y...);}
template<typename Tp> inline void wt(Tp x){if(x>9)wt(x/10);putchar((x%10)+'0');}
template<typename Tp> inline void write(Tp x){if(x<0)putchar('-'),x=~x+1;wt(x);}
template<typename T,typename ...Tp> inline void write(T x,Tp ...y){write(x);putchar(' ');write(y...);}
int n,m,ans,f[N][N],g[N][N];
inline int mod(int x,int y) {return (x+=y)>=P?x-P:x;}
signed main()
{
	read(n,m),n--,f[0][0]=1;
	for(int i=1;i<=m;f[i][0]=f[i-1][1],i++) for(int j=1;j<=m;j++)
		f[i][j]=mod(f[i-1][j-1],f[i-1][j+1]);
	g[0][0]=1; for(int i=1;i<=n;i++) for(int j=0;j<=m;j++)
		for(int k=0;k<=j;k++) g[i][j]=mod(g[i][j],1ll*f[m][k]*g[i-1][j-k]%P);
	for(int i=0;i<=m;i++) ans=mod(ans,1ll*f[m][i]*g[n][i]%P);
	write(ans);
}

T5 Long Way to be Non-decreasing

每次选一个集合就是说直接对每个点计算步数，最后取最大值就是答案，所以发现可以二分答案，表示是否能在 \(mid\) 步内走完，check 可以双指针跑。

考虑怎么计算距离，\(i\to b_i\) 连边，发现这是一棵基环树森林，所以不在一棵树上的距离为 \(\inf\)，否则计算断边前后的距离取最小值即可。

点击查看代码 
#include<bits/stdc++.h>
#define ll long long
#define endl '\n'
#define sort stable_sort
using namespace std;
const int N=1e6+10;
template<typename Tp> inline void read(Tp&x)
{
	x=0;register bool z=true;
	register char c=getchar();
	for(;!isdigit(c);c=getchar()) if(c=='-') z=0;
	for(;isdigit(c);c=getchar()) x=(x<<1)+(x<<3)+(c^48);
	x=(z?x:~x+1);
}
template<typename T,typename ...Tp> inline void read(T &x,Tp &...y){read(x);read(y...);}
template<typename Tp> inline void wt(Tp x){if(x>9)wt(x/10);putchar((x%10)+'0');}
template<typename Tp> inline void write(Tp x){if(x<0)putchar('-'),x=~x+1;wt(x);}
template<typename T,typename ...Tp> inline void write(T x,Tp ...y){write(x);putchar(' ');write(y...);}
int T,n,m,tot,ans=-1,a[N],b[N],f[N],in[N],out[N],del[N],dep[N]; vector<int>e[N];
inline int find(int x) {return x==f[x]?x:f[x]=find(f[x]);}
inline void dfs(int x)
{in[x]=++tot; for(int y:e[x]) dep[y]=dep[x]+1,dfs(y); out[x]=tot;}
inline bool insub(int x,int y) {return in[x]<=in[y]&&out[x]>=out[y];}
inline int getdis(int x,int y)
{
	if(find(x)!=find(y)) return 1e9;
	if(insub(y,x)) return dep[x]-dep[y];
	if(insub(y,b[del[find(x)]])) return dep[x]+dep[b[del[find(x)]]]-dep[y]+1;
	return 1e9;
}
inline bool check(int x)
{
	for(int i=1,j=1;i<=n;i++)
	{while(j<=m&&getdis(a[i],j)>x) j++; if(j>m) return 0;}
	return 1;
}
signed main()
{
	for(read(T);T;T--,tot=0,ans=-1)
	{
		read(n,m),memset(del,0,4*(m+1)),memset(dep,0,4*(n+1));
		for(int i=1;i<=n;i++) read(a[i]);
		for(int i=1;i<=m;i++) read(b[i]),f[i]=i,vector<int>().swap(e[i]);
		for(int i=1,x,y;i<=m;i++)
		{
			if((x=find(i))==(y=find(b[i]))) del[x]=i;
			else f[x]=y,e[b[i]].push_back(i);
		}
		for(int i=1;i<=m;i++) if(f[i]==i) dfs(del[i]);
		for(int l=0,r=m,mid;l<=r;)
		{if(check(mid=l+r>>1)) ans=mid,r=mid-1; else l=mid+1;}
		write(ans),puts("");
	}
}

T6 Many Games

考虑如何 DP，这是简单的，设 \(f_{j}\) 表示和为 \(j\) 的概率，01 背包直接做，但是发现复杂度是错误的，现在需要考虑怎么证明其复杂度是正确的。

首先对于 \(p=100\) 的一定都选上，否则对于所有 \(p\) 相等的，设其选 \(k\) 个最优，则当然是选 \(w\) 最大的 \(k\) 个，设 \(s=\sum\limits_{i=1}^k w_i,mn=\min\limits_{i=1}^kw_i\)，则有：

\[(p\%)^ks\ge (p\%)^{k-1}(s-mn)\ge (p\%)^{k-1}\dfrac{k-1}{k}s \]

从而得到 \(k\le \lfloor\frac{1}{1-p\%}\rfloor=\lfloor\frac{100}{100-p}\rfloor\)，从而选出的总数 \(\le \sum\limits_{i=1}^{99}\lfloor\frac{100}{100-p}\rfloor=481\)。

现在还有一维 \(\sum w\) 还是很大，设 \(s=\sum w,t=\prod p\)，根据最优性，去掉一个 \((p,w)\) 一定不优，有：

\[t\times s\ge \frac{t}{p\%}(s-w) \]

\[s\le \frac{w}{1-p\%} \]

又因为 \(w\times p\le 2\times 10^5\)，所以有：

\[s\le \frac{\frac{2\times 10^5}{p}}{1-p\%}=\frac{2\times 10^7}{p(100-p)} \]

当 \(p=1\) 或 \(99\) 时取到最大，即 \(s\le 202020\)，从而最初那个 DP 的复杂度便变成了正确的。

点击查看代码 
#include<bits/stdc++.h>
#define ll long long
#define endl '\n'
#define sort stable_sort
using namespace std;
const int mx=202020;
template<typename Tp> inline void read(Tp&x)
{
	x=0;register bool z=true;
	register char c=getchar();
	for(;!isdigit(c);c=getchar()) if(c=='-') z=0;
	for(;isdigit(c);c=getchar()) x=(x<<1)+(x<<3)+(c^48);
	x=(z?x:~x+1);
}
template<typename T,typename ...Tp> inline void read(T &x,Tp &...y){read(x);read(y...);}
template<typename Tp> inline void wt(Tp x){if(x>9)wt(x/10);putchar((x%10)+'0');}
template<typename Tp> inline void write(Tp x){if(x<0)putchar('-'),x=~x+1;wt(x);}
template<typename T,typename ...Tp> inline void write(T x,Tp ...y){write(x);putchar(' ');write(y...);}
int n,sum; double ans,f[mx+5]; priority_queue<int>q[100];
signed main()
{
	read(n),f[0]=1; for(int i=1,x,y;i<=n;i++)
	{read(x,y); if(x==100) sum+=y; else q[x].push(y);}
	for(int i=1;i<=99;i++) for(int j=100/(100-i),x;j&&q[i].size();j--)
	{
		x=q[i].top(),q[i].pop();
		for(int k=mx;k>=x;k--) f[k]=max(f[k],f[k-x]*i/100.0);
	}
	for(int i=0;i<=mx;i++) ans=max(ans,(i+sum)*f[i]);
	printf("%.8lf",ans);
}

标签：int,void,Tp,write,read,inline,加赛,集训,NOIP2024
From： https://www.cnblogs.com/Charlieljk/p/18544166

相关文章

  • NOIP2024 前集训：多校A层冲刺NOIP2024模拟赛20
    前言考古了，现在才写。已经忘了赛时历程了，就记得T1打了个错误率高达\(\dfrac{1}{100000}\)的乱搞做法（前后各连\(\log\)个\(k\)大值）然后被卡常了，后三道都没交不记得为啥了。T1星际联邦std是\(O(m\logm)\)的菠萝算法，但是被众人疯狂爆标。正解是\(O(n)\)的，不考虑......
  • 多校A层冲刺NOIP2024模拟赛21
    以为150要垫底了，没想到还有高手。送信卒签，没一会就写完但因为交的太晚被猫娘抢了首A。恼火。简要题意给一个\(n\timesm(n,m\le100)\)的网格图，左右走的代价为\(1\)，上下走的代价为\(k\)，求最小的\(k\)，使得\((sx,sy)\)到\((tx,ty)\)的代价恰好为\(s(s\le10^5)\)。数据保证有解......
  • 『模拟赛』多校A层冲刺NOIP2024模拟赛21
    Rank别样的，不好评价，烂完了A.送信卒签，我是唐氏。为什么呢题目没给最短路的定义，我赛时觉得最短路就是最短路径，于是直接bfs一遍随便加个check就做完了。当然过得那遍按我的思路来说是错的，然后我也发现了这一点，然后就改了，然后就WA了。总结：错误思路的错解是正确思路......
  • 多校A层冲刺NOIP2024模拟赛21
    多校A层冲刺NOIP2024模拟赛21\(T1\)A.送信卒\(90pts/100pts\)部分分\(90pts\)设最后的可能的最短路中左右共移动了\(d\)次，上下共移动了\(x\)次。则等价于求\(\min\{x_{i}k+d_{i}\}=s\)的解，观察到\(d\in[0,\min(\left\lceil\frac{nm}{2}\right\rce......
  • 好题记录 [集训队互测 2023] 优惠购物 题解
    首先发现这个过程的限制比较多，那么考虑重新描述这个过程。令\(x_i\)表示在第\(i\)个物品上使用了\(x_i\)张券，那么一组\(x_{1\simn}\)就描述了一个方案。方便起见，令\(s_i\)为前i个物品买完后剩了几张券，那么有：\(s_0=m\)\(s_i=s_{i-1}+\lfloor\frac{a_i-......
  • 题解：「2017 山东一轮集训 Day7」逆序对
    LibreOJ6077前置知识：生成函数、组合数先考虑平方怎么做。\(f_{i,j}\)表示处理了前\(i\)个值，逆序对有\(j\)个。显然可以转移到\(f_{i+1,j},f_{i+1,j+1},f_{i+1,j+2},...,f_{i+1,j+i}\)。然后发现这个东西是个很简单的递推，而且长得很生成函数，于是可以很自然的写成\[1\t......
  • IOI2025集训队互测 W5
    Day13(20241112)获得成就：在集训队员中登顶。T1线段树与区间加感觉题解做法很牛，所以我来写一下我的\(O(n\logn+q\sqrt{n})\)做法。我们先考虑单独维护\(laz\)数组。如果先不考虑pushdown。发现我们对区间\([l,r]\)进行加法操作，就是找到所有\([L_i,R_i]\subseteq[l,r......
  • NOIP2024模拟赛#18 总结
    头要炸了。T1题面很好懂，手玩了一下发现答案最小是\((m-1)\timesn\)。可能会多出来一个长度为\(k\)的部分，会发现如果多出来一个长度为\(k\)的部分且合法，那么单个串\(1\simk\)位与\(n-k+1\simn\)位一定相同，\(k+1\simn\)位与\(1\simn-k\)一定相同。Hash判一下即......
  • 『模拟赛』NOIP2024加赛4
    Rank给我唐完了，又名，【MX-S5】梦熊NOIP2024模拟赛1。A.王国边缘好像简单倍增就做完了。由于昨天T5在我脑海中留下了挥之不去的印象，今天一上来看到这题就发现是一个内向基环树森林。然后被硬控硬控硬控，最后一个小点加一点优化就能过没调出来，挂30pts，菜菜菜菜菜。注......
  • NOIP2024加赛4
    简评：搬的梦熊的，一签一难两不可做。王国边缘倍增板子（但我不会打倍增所以场上调了半天）。记\(f_{i,j}\)表示从\(i\)开始走\(2^j\)次时走的距离，\(g_{i,j}\)表示从\(i\)开始走\(2^j\)次时走到的点，这个用倍增。处理\(f_{i,0}\)和\(g_{i,0}\)时分讨即可，卡不卡常无所谓。时空复杂度\(O......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99