首页 > 其他分享 >暑假集训CSP提高模拟27

暑假集训CSP提高模拟27

时间：2024-08-22 14:14:58浏览次数：14  
标签：cnt 27 int ll top 集训 500010 son CSP

暑假集训CSP提高模拟27

组题人： @KafuuChinocpp

\(T1\) P236.线性只因 \(100pts\)

  • 诈骗题。

  • 部分分

  • 正解

    • 记 \(opt\) 表示待选集合，统计 \(opt\) 中这一位为 \(1\) 的数并加入临时集合 \(tmp\) 。若 \(tmp\) 大小 \(\ge m\) 则加上这一位的贡献并将 \(opt\) 赋成 \(tmp\) 否则不管。
    点击查看代码 
    ll a[1000010];
vector<ll>opt,tmp;
int main()
{
	ll n,m,ans=0,i,s;
	cin>>n>>m;
	for(i=1;i<=n;i++)
	{
		cin>>a[i];
		opt.push_back(i);
	}
	for(s=32;s>=0;s--)
	{
		tmp.clear();
		for(i=0;i<opt.size();i++)
		{
			if((a[opt[i]]>>s)&1)
			{
				tmp.push_back(opt[i]);
			}
		}
		if(tmp.size()>=m)
		{
			opt=tmp;
			ans|=(1<<s);
		}
	}
	cout<<ans<<endl;
	return 0;
}

\(T2\) P234.金箱子 \(30pts\)

  • 若钓出来一个金箱子在模 \(99824435\) 意义下概率为 \(p_{i}\) ，则钓出来一个银箱子在模 \(99824435\) 意义下概率为 \(1-p_{i}+998244353\) 。

    • 设钓出来一个金箱子的概率为 \(\frac{x}{y}\) ，由题有 \(\gcd(y,998244353)=1\) ，那么 \(\frac{x}{y}\) 在模 \(99824435\) 意义等于 \(p_{i}=x \times y^{998244353-2} \bmod 998244353\) ，相应的 \(\frac{y-x}{y}\) 在模 \(99824435\) 意义下等于 \((y-x) \times y^{998244353-2} \bmod998244353=(y^{998244353-1}-p_{i}+998244353) \bmod 998244353=(1-p_{i}+998244353) \bmod 998244353\) 。

  • 部分分

    • \(20pts\) ：爆搜。
    • \(10pts\) ：观察到 \(k=1\) ，遂 \(\sum\limits_{i=1}^{n}p_{i}a_{i}+(1-p_{i})b_{i}\) 即为所求，
    点击查看代码 
    const ll p=998244353;
ll c[10010],a[10010],b[10010],ans=0;
ll qpow(ll a,ll b,ll p)
{
	ll ans=1;
	while(b)
	{
		if(b&1)
		{
			ans=ans*a%p;
		}
		b>>=1;
		a=a*a%p;
	}
	return ans;
}
void dfs(ll pos,ll mul,ll num,ll n,ll k)
{
	if(pos==n+1)
	{
		ans=(ans+mul*qpow(num,k,p))%p;
	}
	else
	{
		if(mul!=0)
		{
			dfs(pos+1,mul*c[pos]%p,(num+a[pos])%p,n,k);
			dfs(pos+1,mul*(1+p-c[pos])%p,(num+b[pos])%p,n,k);
		}
	}
}
int main()
{
	ll n,k,i;
	cin>>n>>k;
	for(i=1;i<=n;i++)
	{
		cin>>c[i]>>a[i]>>b[i];
	}
	if(k==1)
	{
		for(i=1;i<=n;i++)
		{
			ans=(ans+c[i]*a[i]%p+(1+p-c[i])*b[i]%p)%p;
		}
	}
	else
	{
		dfs(1,1,0,n,k);
	}
	cout<<ans<<endl;
	return 0;
}

  • 正解

\(T3\) P235.可持久化字符串 \(50pts\)

  • \(2\) 操作实际上是新建一个版本为 \(a\) 的前一个副本。
  • 部分分

    • \(50pts\) ：哈希判等。大样例没过遂不保证代码正确性。

      点击查看代码 
      const ll p=1000003579,base=13331;
ll a[100010],pre[100010],hsh[100010],len[100010],num[100010],sum[100010],jc[100010];
char s[100010];
void sx_hash(char s[],ll len,ll a[])
{
	for(ll i=0;i<=len;i++)
	{
		a[i]=(i==0)?0:(a[i-1]*base%p+s[i])%p;
	}
}
ll ask_hash(ll l,ll r)
{
	return (a[r]-a[l-1]*jc[r-l+1]%p+p)%p;
}
void solve(ll pos,ll n)
{
	for(ll i=1;i+len[pos]-1<=n;i++)
	{
		num[pos]+=(ask_hash(i,i+len[pos]-1)==hsh[pos]);
	}
}
int main()
{
	ll n,m,pd,x,l,r,c_cnt=0,i;
	char c;
	cin>>m>>n>>(s+1);
	sx_hash(s,n,a);
	for(i=0;i<=100000;i++)
	{
		jc[i]=(i==0)?1:jc[i-1]*base%p;
	}
	num[0]=sum[0]=1;
	for(i=1;i<=m;i++)
	{
		cin>>pd;
		if(pd==1)
		{
			cin>>x>>c;
			c_cnt++;
			pre[c_cnt]=x;
			hsh[c_cnt]=(hsh[x]*base+c)%p;
			len[c_cnt]=len[x]+1;
			solve(c_cnt,n);
			sum[c_cnt]=sum[c_cnt-1]+num[c_cnt];
		}
		if(pd==2)
		{
			cin>>x;
			c_cnt++;
			pre[c_cnt]=pre[pre[x]];
			hsh[c_cnt]=hsh[pre[x]];
			len[c_cnt]=len[pre[x]];
			num[c_cnt]=num[pre[x]];
			sum[c_cnt]=sum[c_cnt-1]+num[c_cnt];
		}
		if(pd==3)
		{
			cin>>l>>r;
			if(l-1>=0)
			{
				cout<<sum[r]-sum[l-1]<<endl;
			}
			else
			{
				cout<<sum[r]<<endl;
			}
		}
	}
	return 0;
}
  • 正解

\(T4\) T3236.圣诞树 \(0pts\)

  • 强化版： QOJ 7245. Frank Sinatra

  • 部分分

    • \(Subtask 1\) ：主席树代替原来的桶，询问时枚举值域判断。

      • 因 \(\operatorname{mex}\) 跑不满（数据没卡），不加 \(Subtask 3\) 的特判实测可以跑 \(70pts\) 。

        点击查看代码 
        struct node
{
	int nxt,to;
}e[1000010];
int head[500010],a[500010],top[500010],fa[500010],siz[500010],dep[500010],son[500010],vis[500010],cnt=0;
void add(int u,int v)
{
	cnt++;
	e[cnt].nxt=head[u];
	e[cnt].to=v;
	head[u]=cnt;
}
struct PDS_SMT
{
	int root[500010],rt_sum;
	struct SegmentTree
	{
		int ls,rs,sum,cnt;
	}tree[500010<<5];
	#define lson(rt) tree[rt].ls
	#define rson(rt) tree[rt].rs
	int build_rt()
	{
		rt_sum++;
		return rt_sum;
	}
	void build_tree(int &rt,int l,int r)
	{
		rt=build_rt();
		if(l==r)
		{
			return;
		}
		int mid=(l+r)/2;
		build_tree(lson(rt),l,mid);
		build_tree(rson(rt),mid+1,r);
	}
	void pushup(int rt)
	{
		tree[rt].cnt=tree[lson(rt)].cnt+tree[rson(rt)].cnt;
	}
	void update(int pre,int &rt,int l,int r,int pos)
	{
		rt=build_rt();
		tree[rt]=tree[pre];
		tree[rt].sum++;
		if(l==r)
		{
			tree[rt].cnt=1;
			return;
		}
		int mid=(l+r)/2;
		if(pos<=mid)
		{
			update(lson(pre),lson(rt),l,mid,pos);
		}
		else
		{
			update(rson(pre),rson(rt),mid+1,r,pos);
		}
		pushup(rt);
	}
	int query1(int rt1,int rt2,int rt3,int rt4,int l,int r,int pos)
	{
		if(l==r)
		{
			return tree[rt1].sum+tree[rt2].sum-tree[rt3].sum-tree[rt4].sum;
		}
		int mid=(l+r)/2;
		if(pos<=mid)
		{
			return query1(lson(rt1),lson(rt2),lson(rt3),lson(rt4),l,mid,pos);
		}
		else
		{
			return query1(rson(rt1),rson(rt2),rson(rt3),rson(rt4),mid+1,r,pos);
		}
	}
	int query3(int rt1,int rt2,int rt3,int rt4,int l,int r,int x,int y)
	{
		if(x<=l&&r<=y)
		{
			return tree[rt1].sum+tree[rt2].sum-tree[rt3].sum-tree[rt4].sum;
		}
		int mid=(l+r)/2,ans=0;
		if(x<=mid)
		{
			ans+=query3(lson(rt1),lson(rt2),lson(rt3),lson(rt4),l,mid,x,y);
		}
		if(y>mid)
		{
			ans+=query3(rson(rt1),rson(rt2),rson(rt3),rson(rt4),mid+1,r,x,y);
		}
		return ans;
	}
}T;
void dfs1(int x,int father,int n)
{
	siz[x]=1;
	fa[x]=father;
	dep[x]=dep[father]+1;
	T.update(T.root[father],T.root[x],1,n,a[x]);
	for(int i=head[x];i!=0;i=e[i].nxt)
	{
		if(e[i].to!=father)
		{
			dfs1(e[i].to,x,n);
			siz[x]+=siz[e[i].to];
			son[x]=(siz[e[i].to]>siz[son[x]])?e[i].to:son[x];
		}
	}
}
void dfs2(int x,int id)
{
	top[x]=id;
	if(son[x]!=0)
	{
		dfs2(son[x],id);
		for(int i=head[x];i!=0;i=e[i].nxt)
		{
			if(e[i].to!=fa[x]&&e[i].to!=son[x])
			{
				dfs2(e[i].to,e[i].to);
			}
		}
	}
}
int lca(int u,int v)
{
	while(top[u]!=top[v])
	{
		if(dep[top[u]]>dep[top[v]])
		{
			u=fa[top[u]];
		}
		else
		{
			v=fa[top[v]];
		}
	}
	return (dep[u]>dep[v])?v:u;
}
int query1(int u,int v,int n)
{
	int rt=lca(u,v);
	for(int i=1;i<=n;i++)
	{
		if(T.query1(T.root[u],T.root[v],T.root[rt],T.root[fa[rt]],1,n,i)==0)
		{
			return i;
		}
	}
	return n+1;
}
int main()
{
	int n,m,u,v,flag=1,i;
	scanf("%d%d",&n,&m);
	for(i=1;i<=n;i++)
	{
		scanf("%d",&a[i]);
		vis[a[i]]++;
		flag&=(vis[a[i]]==1);
	}
	for(i=1;i<=n-1;i++)
	{
		scanf("%d%d",&u,&v);
		add(u,v);
		add(v,u);
	}
	dfs1(1,0,n);
	dfs2(1,1);
	for(i=1;i<=m;i++)
	{
		scanf("%d%d",&u,&v);
		printf("%d\n",query1(u,v,n));
	}
	return 0;
}

    • \(Subtask 3\) ：因为每个数只出现一次，主席树维护一段值域内数的个数，询问时二分主席树或主席树上二分维护即可。

      点击查看代码 
      struct node
{
	int nxt,to;
}e[1000010];
int head[500010],a[500010],top[500010],fa[500010],siz[500010],dep[500010],son[500010],vis[500010],cnt=0;
void add(int u,int v)
{
	cnt++;
	e[cnt].nxt=head[u];
	e[cnt].to=v;
	head[u]=cnt;
}
struct PDS_SMT
{
	int root[500010],rt_sum;
	struct SegmentTree
	{
		int ls,rs,sum,cnt;
	}tree[500010<<5];
	#define lson(rt) tree[rt].ls
	#define rson(rt) tree[rt].rs
	int build_rt()
	{
		rt_sum++;
		return rt_sum;
	}
	void build_tree(int &rt,int l,int r)
	{
		rt=build_rt();
		if(l==r)
		{
			return;
		}
		int mid=(l+r)/2;
		build_tree(lson(rt),l,mid);
		build_tree(rson(rt),mid+1,r);
	}
	void pushup(int rt)
	{
		tree[rt].cnt=tree[lson(rt)].cnt+tree[rson(rt)].cnt;
	}
	void update(int pre,int &rt,int l,int r,int pos)
	{
		rt=build_rt();
		tree[rt]=tree[pre];
		tree[rt].sum++;
		if(l==r)
		{
			tree[rt].cnt=1;
			return;
		}
		int mid=(l+r)/2;
		if(pos<=mid)
		{
			update(lson(pre),lson(rt),l,mid,pos);
		}
		else
		{
			update(rson(pre),rson(rt),mid+1,r,pos);
		}
		pushup(rt);
	}
	int query1(int rt1,int rt2,int rt3,int rt4,int l,int r,int pos)
	{
		if(l==r)
		{
			return tree[rt1].sum+tree[rt2].sum-tree[rt3].sum-tree[rt4].sum;
		}
		int mid=(l+r)/2;
		if(pos<=mid)
		{
			return query1(lson(rt1),lson(rt2),lson(rt3),lson(rt4),l,mid,pos);
		}
		else
		{
			return query1(rson(rt1),rson(rt2),rson(rt3),rson(rt4),mid+1,r,pos);
		}
	}
	int query3(int rt1,int rt2,int rt3,int rt4,int l,int r,int x,int y)
	{
		if(x<=l&&r<=y)
		{
			return tree[rt1].sum+tree[rt2].sum-tree[rt3].sum-tree[rt4].sum;
		}
		int mid=(l+r)/2,ans=0;
		if(x<=mid)
		{
			ans+=query3(lson(rt1),lson(rt2),lson(rt3),lson(rt4),l,mid,x,y);
		}
		if(y>mid)
		{
			ans+=query3(rson(rt1),rson(rt2),rson(rt3),rson(rt4),mid+1,r,x,y);
		}
		return ans;
	}
}T;
void dfs1(int x,int father,int n)
{
	siz[x]=1;
	fa[x]=father;
	dep[x]=dep[father]+1;
	T.update(T.root[father],T.root[x],1,n,a[x]);
	for(int i=head[x];i!=0;i=e[i].nxt)
	{
		if(e[i].to!=father)
		{
			dfs1(e[i].to,x,n);
			siz[x]+=siz[e[i].to];
			son[x]=(siz[e[i].to]>siz[son[x]])?e[i].to:son[x];
		}
	}
}
void dfs2(int x,int id)
{
	top[x]=id;
	if(son[x]!=0)
	{
		dfs2(son[x],id);
		for(int i=head[x];i!=0;i=e[i].nxt)
		{
			if(e[i].to!=fa[x]&&e[i].to!=son[x])
			{
				dfs2(e[i].to,e[i].to);
			}
		}
	}
}
int lca(int u,int v)
{
	while(top[u]!=top[v])
	{
		if(dep[top[u]]>dep[top[v]])
		{
			u=fa[top[u]];
		}
		else
		{
			v=fa[top[v]];
		}
	}
	return (dep[u]>dep[v])?v:u;
}
int query1(int u,int v,int n)
{
	int rt=lca(u,v);
	for(int i=1;i<=n;i++)
	{
		if(T.query1(T.root[u],T.root[v],T.root[rt],T.root[fa[rt]],1,n,i)==0)
		{
			return i;
		}
	}
	return n+1;
}
int query3(int u,int v,int n)
{
	int rt=lca(u,v),l=1,r=n,mid,ans=n+1;
	while(l<=r)
	{
		mid=(l+r)/2;
		if(T.query3(T.root[u],T.root[v],T.root[rt],T.root[fa[rt]],1,n,1,mid)==mid)
		{
			l=mid+1;
		}
		else
		{
			r=mid-1;
			ans=mid;
		}
	}
	return ans;
}
int main()
{
	int n,m,u,v,flag=1,i;
	scanf("%d%d",&n,&m);
	for(i=1;i<=n;i++)
	{
		scanf("%d",&a[i]);
		vis[a[i]]++;
		flag&=(vis[a[i]]==1);
	}
	for(i=1;i<=n-1;i++)
	{
		scanf("%d%d",&u,&v);
		add(u,v);
		add(v,u);
	}
	dfs1(1,0,n);
	dfs2(1,1);
	if(flag==1)
	{
		for(i=1;i<=m;i++)
		{
			scanf("%d%d",&u,&v);
			printf("%d\n",query3(u,v,n));
		}
	}
	else
	{
		for(i=1;i<=m;i++)
		{
			scanf("%d%d",&u,&v);
			printf("%d\n",query1(u,v,n));
		}
	}
	return 0;
}

  • 正解

总结

  • 感觉看到题后立刻想到一个自己没学过的知识点能解决这个问题，然后自己思路就被限制住了，接着就开始着急、开始恼，对心态有不少影响。或许要学着做到初三原政治老师说的到考场后忘掉自己学过和没学过的一切，而是重新分析题意了。
  • \(T1\) 成功被题目名称和题目背景迷惑，以为线性基能处理按位与和的最大值，然后就没再管。最后打 \(m=2\) 部分分时发现 \(01Trie\) 维护不了，也就推翻了线性基的做法，然后就会维护从高到低维护待选集合的正解了，过了大样例后就交了。
  • \(T2\) 推式子时把 \(1\) 漏掉了，最后重新来看的时候才发现了这个问题。
  • \(T4\) 主席树向右子树递归把 update(rson(pre),rson(rt),mid+1,r,pos); 写成了 update(rson(pre),rson(rt),l,mid,pos); ，挂了 \(70pts\) 。

后记

  • 比赛一开始是 \(ACM/ICPC\) 赛制（但有部分分）然后又换成了 \(OI\) 赛制。
  • \(T3\) 中途上传数据和小样例，第一次下发的大样例还出锅了。
  • 不知道组题人怎么想的，会赛时改输入输出格式：标准输入输出->文件输入输出->标准输入输出。

标签：cnt,27,int,ll,top,集训,500010,son,CSP
From： https://www.cnblogs.com/The-Shadow-Dragon/p/18373575

相关文章

  • CSP防爆
    今日模拟赛T3把ac.inac.out愣是写成ac.txtac.txt自己在IDE里测大样例用的是.txt,提交没改过来100->0啊啊啊啊啊啊啊啊啊啊啊啊T6见祖宗0<=x<=1e9还要求和爆int但我没看见.....(100->90啊啊啊啊啊啊啊啊啊啊啊啊430->340经验考试绝不开多个页面,容易看错内存不紧......
  • 集训总结
    前言：写于2024年暑假中山集训期间，如果有误，望指出。20240729D1感觉今天整体还行，T1一眼题。T2胡了一个dp，死在没考虑到优化状态。T3裴蜀定理（忘了），T4建模Johnson。dp有点死板，可以考虑从不同的角度设计dp状态，比如交换dp的维度和其维护的值。数论还是需要巩固，竟然连裴蜀定理都......
  • 2024暑期第二次集训总结(202408)
    坐标cssyz08.12身体不适，请假在家，随便写写，把当天任务写了一下，结果你谷RMJ炸了，直接躺平。08.13上午原定9:00-12:00出去比赛，让我们8:00到，到了之后又没事做，直接与同学联机MC，后面开考，以为是csp-j难度，结果红+红+下位橙+红,14分钟秒了。(抽象)回到机房赶上思维训练，看了......
  • YC327A [ 20240821 CQYC NOIP 模拟赛 T1 ] 最值（minmax）
    题意对于一个序列\({b_n}\)，规定：\[f_min(b)=\prod_{i=1}^n(min_{j=1}^ib_j)\]\[f_max(b)=\prod_{i=1}^n(max_{j=1}^ib_j)\]给定一个序列\(a\)，求\(a\)所有的排列\(p\)的\(f_min(p)\)与\(f_max(p)\)之和。\(n\le5000\)Sol不难想到一个简......
  • 2024.8.21 总结（集训 考试）
    上午感觉不错，下午改不出题，晚上破防。简略思路：T1本质应该是DP维护一次函数。不会正解。晚上看了好久、好多篇题解还是不会。有点静不下心来看比较长的题解。放点别人的题解，有空再来研究：https://www.cnblogs.com/flywatre/p/17236732.htmlhttps://blog.51cto.com/u_1530083......
  • 『模拟赛』暑假集训CSP提高模拟26
    Rank打得一般，倒数第二场了。。A.博弈直接搬了牛客的一套题。一眼没思路，模了一会放弃直接去打T2了，后来把\(\mathcal{O(n^2)}\)暴力打了拿30pts。正解用到了异或哈希。首先确定合法的数量即为总对数\(\frac{n(n-1)}{2}\)减去不合法的数量，而比较显然的，不合法的判断......
  • [赛记] 暑假集训CSP提高模拟24
    与和100pts签到题但还是做了很久。。。考虑与的条件，可以发现，如果将$a$转化成二进制，那么二进制上为$1$的位置$x$和$y$都必须是$1$，所以首先将$s$减去$2\timesa$，然后再判断一下$(s-2\timesa)\operatorname{and}a$是否为$0$即可；赛时用......
  • 【题解】Solution Set - NOIP2024集训Day12 树上启发式合并
    【题解】SolutionSet-NOIP2024集训Day12树上启发式合并https://www.becoder.com.cn/contest/5472「CF600E」Lomsatgelral直接dsuontree。记录每一个颜色的出现次数。「IOI2011」Race之前是用点分治做的。考虑dsuontree。每个子树内维护到根节点的距离为\(x\)......
  • 2024暑假集训测试30
    前言比赛链接。T1普及了一下异或哈希，T2、T3赛时应该算乱搞题，还搞挂了，T4高级平衡树题，不太可做。原题全部出自：2022牛客OI赛前集训营-提高组（第四场）。T1博弈部分分\(30pts\)：\(O(n^2)\)暴力。正解：不难推出必胜策略就是\((x,y)\)路径上每个边权出现的次数不全为......
  • 2024年无人系统与自动化控制学术研讨会（ICUSAC 2024, 9月27-29）
    无人系统与自动化控制技术的创新和应用，对于提升国家科技竞争力和产业升级具有重要意义，已成为新时代驱动经济与社会变革的关键要素。为了顺应国家发展趋势，2024年无人系统与自动化控制学术研讨会（ICUSAC2024）将于2024年9月27日至29日在中国沈阳隆重举行。本次大会旨在顺应无......

赞助商

阅读排行

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

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

Copyright © 2020-2023 IPS99 版权所有 IPS99