首页 > 其他分享 >CSP2024 前集训：多校A层冲刺NOIP2024模拟赛08

CSP2024 前集训：多校A层冲刺NOIP2024模拟赛08

时间：2024-10-17 19:09:53浏览次数：1  
标签：unlocked int 08 多校 Tp CSP2024 read inline void

前言

image

光顾着想 T2 了，但是不知道哪儿假了，只有 \(\dfrac{n}{k}\le 5\) 的点是对的，然后居然只有二十分，发现数据放错了，找喵喵改了成五十了。

然后 T1 因为重边挂没了。

T3 没调出来，确切的说是省的时间不多了打不完，就写了个部分分。

T4 咕了。

机房凳子没靠椅，一直坐着腰快折了肿么办。

T1 传送

按照横坐标（纵坐标）排序，\(i\to i+1\) 连边，再连上 \(m\) 调隧道，跑 dijkstra 就行了。

点击查看代码 
#include<bits/stdc++.h>
#define ll long long
#define endl '\n'
#define sort stable_sort
using namespace std;
const int N=2e5+10,M=1.2e6+10;
template<typename Tp> inline void read(Tp&x)
{
	x=0;register bool z=true;
	register char c=getchar_unlocked();
	for(;!isdigit(c);c=getchar_unlocked()) if(c=='-') z=0;
	for(;isdigit(c);c=getchar_unlocked()) 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_unlocked((x%10)+'0');}
template<typename Tp> inline void write(Tp x){if(x<0)putchar_unlocked('-'),x=~x+1;wt(x);}
template<typename T,typename ...Tp> inline void write(T x,Tp ...y){write(x);putchar_unlocked(' ');write(y...);}
int n,m,tot,head[N],nxt[M],to[M],w[M]; ll dis[N]; bitset<N>vis;
void _(int x,int y,int z)
{nxt[++tot]=head[x],to[tot]=y,w[tot]=z,head[x]=tot;}
void add(int x,int y,int z) {_(x,y,z),_(y,x,z);}
struct aa {int x,y,id;}e[N];
void dijkstra()
{
	memset(dis,0x3f,sizeof(dis)),dis[1]=0;
	priority_queue<pair<ll,int> >q; q.push(make_pair(0,1));
	while(!q.empty())
	{
		int x=q.top().second; q.pop();
		if(vis[x]) continue; vis[x]=1;
		for(int i=head[x],y;y=to[i];i=nxt[i]) if(dis[y]>dis[x]+w[i]) 
			dis[y]=dis[x]+w[i],q.push(make_pair(-dis[y],y));
	}
}
signed main()
{
	freopen("teleport.in","r",stdin),freopen("teleport.out","w",stdout);
	read(n,m); for(int i=1,x,y;i<=n;i++) read(x,y),e[i]={x,y,i};
	sort(e+1,e+1+n,[&](aa a,aa b){return a.x<b.x;});
	for(int i=1;i<n;i++) add(e[i].id,e[i+1].id,e[i+1].x-e[i].x);
	sort(e+1,e+1+n,[&](aa a,aa b){return a.y<b.y;});
	for(int i=1;i<n;i++) add(e[i].id,e[i+1].id,e[i+1].y-e[i].y);
	for(int i=1,x,y,z;i<=m;i++) read(x,y,z),add(x,y,z);
	dijkstra(); for(int i=2;i<=n;i++) write(dis[i]),putchar_unlocked(' ');
}

T2 排列

  • 部分分 \(50pts\)：考虑 \(\dfrac{n}{k}\le 5\) 时不会有算重的情况，遂组合一下就好了。

  • 正解：

    因为 \(\dfrac{n}{k}\le 10\)，考虑状压。

    \(f_{i,j,k}\) 表示处理到第 \(i\) 位，这 \(\dfrac{n}{k}\) 数的出现情况为 \(j\)，结尾是 \(k\) 的方案数，\(k=0\) 表示不是以这 \(\dfrac{n}{k}\) 中的一个结尾，直接转移即可。

    acsoders 跑得太快了，所以需要卡卡常，预处理 \(\gcd\) 或每个状态的合法结尾数，复杂度 \(O(n2^{\frac{n}{k}}k)\)，可以滚一下优化空间。

    点击查看代码 
    #include<bits/stdc++.h>
#define ll long long
#define endl '\n'
#define sort stable_sort
using namespace std;
const int N=3010,M=1024,P=998244353;
template<typename Tp> inline void read(Tp&x)
{
	x=0;register bool z=true;
	register char c=getchar_unlocked();
	for(;!isdigit(c);c=getchar_unlocked()) if(c=='-') z=0;
	for(;isdigit(c);c=getchar_unlocked()) 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_unlocked((x%10)+'0');}
template<typename Tp> inline void write(Tp x){if(x<0)putchar_unlocked('-'),x=~x+1;wt(x);}
template<typename T,typename ...Tp> inline void write(T x,Tp ...y){write(x);putchar_unlocked(' ');write(y...);}
int n,m,k,ans,cnt[M],f[2][M][11]; vector<int>e[M];
inline int mod(int x,int y) {return (x+=y)>=P?x-P:x;}
inline int gcd(int x,int y) {return !y?x:gcd(y,x%y);}
signed main()
{
	freopen("permutation.in","r",stdin),freopen("permutation.out","w",stdout);
	read(n,k),m=n/k; f[0][0][0]=1;
	for(int i=0;i<(1<<m);cnt[i]=e[i].size(),e[i++].push_back(0))
		for(int j=__lg(i);j>=0;j--) if((i>>j)&1) e[i].push_back(j+1);
	for(int i=1,x=1,y=0;i<=n;i++,x^=1,y^=1)
	{
		memset(f[x],0,sizeof(f[x]));
		for(int j=0;j<(1<<m);j++) if(cnt[j]<=i)
		{
			for(int k:e[j]) f[x][j][0]=mod(f[x][j][0],f[y][j][k]);
			f[x][j][0]=1ll*f[x][j][0]*(n-m-(i-cnt[j])+1)%P;
			for(int k:e[j]) if(k)
			{
				f[x][j][k]=mod(f[x][j][k],f[y][j^(1<<(k-1))][0]);
				for(int h:e[j]) if(h&&k!=h&&gcd(k,h)!=1)
					f[x][j][k]=mod(f[x][j][k],f[y][j^(1<<(k-1))][h]);
			}
		}
	}
	for(int i=0;i<=m;i++) ans=mod(ans,f[n&1][(1<<m)-1][i]);
	write(ans);
}

  • 还有个 \(O(2^{\frac{n}{k}}\dfrac{n}{k})\) 的做法，没有写。

T3 战场模拟器

  • 第一档部分分：\(l=r\)，暴力。

  • 第二档部分分：没有死亡的也没有套盾的，线段树维护最小值及其个数即可。

  • 第三档部分分：最多套 \(n\) 个盾，线段树标记一下往下递归即可。

  • 正解：和第三档类似，死亡的也只会死一次，若最小值不够扣往下递归到叶子即可，若这个区间已经死光了结束递归就行了，注意实现的细节。

    点击查看代码 
    #include<bits/stdc++.h>
#define ll long long
#define endl '\n'
#define sort stable_sort
#define mid (l+r>>1)
#define ls (mid<<1)
#define rs (mid<<1|1)
using namespace std;
const int N=2e5+10; const ll inf=2e14;
template<typename Tp> inline void read(Tp&x)
{
	x=0;register bool z=true;
	register char c=getchar_unlocked();
	for(;!isdigit(c);c=getchar_unlocked()) if(c=='-') z=0;
	for(;isdigit(c);c=getchar_unlocked()) 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_unlocked((x%10)+'0');}
template<typename Tp> inline void write(Tp x){if(x<0)putchar_unlocked('-'),x=~x+1;wt(x);}
template<typename T,typename ...Tp> inline void write(T x,Tp ...y){write(x);putchar_unlocked(' ');write(y...);}
int n,m,a[N],h[N<<1],sum[N<<1],cnt[N<<1]; ll val[N<<1],add[N<<1];
void pushup(int p,int l,int r)
{
	val[p]=min(val[ls],val[rs]),cnt[p]=cnt[ls]+cnt[rs],h[p]=h[ls]+h[rs];
	sum[p]=val[ls]==val[rs]?sum[ls]+sum[rs]:(val[ls]<val[rs]?sum[ls]:sum[rs]);
}
void spread(int p,int l,int r)
{
	if(val[ls]!=inf) val[ls]+=add[p],add[ls]+=add[p];
	if(val[rs]!=inf) val[rs]+=add[p],add[rs]+=add[p];
	add[p]=0;
}
void build(int p,int l,int r)
{
	if(l==r) return val[p]=a[l],sum[p]=1,void();
	build(ls,l,mid),build(rs,mid+1,r),pushup(p,l,r);
}
void change(int p,int l,int r,int vl,int vr,int d)
{
	if(val[p]==inf) return ;
	if(vl<=l&&vr>=r&&(d>0||!h[p])) 
	{val[p]+=d; if(val[p]>=0) return add[p]+=d,void();}
	if(l==r&&h[p]&&d<0) return h[p]--,void();
	if(l==r&&val[p]+d<0) return val[p]=inf,cnt[p]=1,void();
	if(add[p]) spread(p,l,r);
	if(vl<=mid) change(ls,l,mid,vl,vr,d);
	if(vr>mid) change(rs,mid+1,r,vl,vr,d);
	pushup(p,l,r);
}
void protect(int p,int l,int r,int x)
{
	if(val[p]==inf) return ; if(l==r) return h[p]++,void();
	if(add[p]) spread(p,l,r);
	x<=mid?protect(ls,l,mid,x):protect(rs,mid+1,r,x),pushup(p,l,r);
}
int dead(int p,int l,int r,int vl,int vr)
{
	if(val[p]==inf) return min(vr,r)-max(l,vl)+1;
	if(vl<=l&&vr>=r) return cnt[p];
	if(add[p]) spread(p,l,r); int res=0;
	if(vl<=mid) res+=dead(ls,l,mid,vl,vr);
	if(vr>mid) res+=dead(rs,mid+1,r,vl,vr);
	return res;
}
int dying(int p,int l,int r,int vl,int vr)
{
	if(val[p]!=0) return 0; if(vl<=l&&vr>=r) return (!val[p])*sum[p];
	if(add[p]) spread(p,l,r); int res=0;
	if(vl<=mid) res+=dying(ls,l,mid,vl,vr);
	if(vr>mid) res+=dying(rs,mid+1,r,vl,vr);
	return res;
}
signed main()
{
	freopen("simulator.in","r",stdin),freopen("simulator.out","w",stdout);
	read(n); for(int i=1;i<=n;i++) read(a[i]);
	build(1,1,n),read(m); for(int i=1,op,l,r,x;i<=m;i++)
	{
		read(op); switch(op)
		{
			case 1: read(l,r,x),change(1,1,n,l,r,-x); break;
			case 2: read(l,r,x),change(1,1,n,l,r,x); break;
			case 3: read(x),protect(1,1,n,x); break;
			case 4: read(l,r),write(dead(1,1,n,l,r)),puts(""); break;
			case 5: read(l,r),write(dying(1,1,n,l,r)),puts(""); break;
		}
	}
}

T4 点亮

咕了咕了。

标签：unlocked,int,08,多校,Tp,CSP2024,read,inline,void
From： https://www.cnblogs.com/Charlieljk/p/18472910

相关文章

  • 08_实现 reactive
    目录编写reactive的函数签名处理对象的其他行为拦截in操作符拦截for...in循环delete操作符处理边界新旧值发生变化时才触发依赖的情况处理从原型上继承属性的情况处理一个对象已经是代理对象的情况处理一个原始对象已经被代理过一次之后的情况浅响应与深响应代......
  • 『模拟赛』多校A层冲刺NOIP2024模拟赛08
    Rank还行A.传送(teleport)签。单元最短路，先想Dijkstra。发现这道题还有个不同寻常的移动方式，可以以\(min\left(|x_i-x_j|,|y_i-y_j|\right)\)的代价从\(i\)移动到\(j\)。暴力连边是\(\mathcal{O(n^2)}\)的，时间空间都过不去。被叫去整内务在楼梯上想到，一个点不应......
  • 多校A层冲刺NOIP2024模拟赛08
    多校A层冲刺NOIP2024模拟赛08\(T1\)A.传送(teleport)\(0pts\)弱化版：[ABC065D]Built?|luoguP8074[COCI2009-2010#7]SVEMIR|“迎新春，过大年”多校程序设计竞赛H二次元世界之寻找珂朵莉先不管后面加入的\(m\)条边。对于两点间的路径\(i\toj\)，经过中......
  • Oracle 19c OCP 认证考试 083 题库(第3题)- 2024年修正版
    【优技教育】Oracle19cOCP083题库(Q3题)-2024年修正版考试科目：1Z0-083考试题量：85道（线下）通过分数：57%以上考试时间：150min（线下）本文为(CUUG原创)整理并解析，转发请注明出处，禁止抄袭及未经注明出处的转载。原文地址：http://www.cuug.com.cn/ocp/083kaoshitiku/38540354314.ht......
  • 「模拟赛」多校 A 层联训 8
    \(22pts\)，本来可以切掉前两个题的？！A.传送(teleport)签到12pts，错的很唐！我把Dij用的dis数组直接赋值成了点到1号点之间的x距离和y距离的最小值，没再赋成极大值，这样会改变Dij过程中点遍历到的顺序，然后就跑不出最短路了。好像不能算挂分？但其实赛时有点感觉是这的问......
  • 2024.10.08星期二
    今天配置了vue环境，学习了基础的vue语法，在这个过程中遇到了如下问题1.安装完node.js和vuecli后，创建项目的时候出现了问题我无法通过yarnserve启动项目，但由于默认下载设置的是yarn，导致也无法使用npmrunserve启动在这里卡了很久，解决办法是在C盘的user目录下有一个文件，其实后面......
  • 洛谷题单指南-字符串-P2922 [USACO08DEC] Secret Message G
    原题链接：https://www.luogu.com.cn/problem/P2922题意解读：已知M个01串，给出N个01串，对于N个串的每一个，求在M个串中有多少与其有公共前缀，且前缀长度是两个串中较小者。解题思路：用Trie树存储M个01串，用cnt1[]记录某个节点结束的01串个数，cnt2[]记录经过某个节点的01串的数量对于N个0......
  • 《安富莱嵌入式周报》第344期：开源手表一年的误差不到1秒，开源32路IMU传感器矩阵，STM32L4
    周报汇总地址：http://www.armbbs.cn/forum.php?mod=forumdisplay&fid=12&filter=typeid&typeid=104 本周更新视频DSP视频教程第13期：汇编浮点库qfplib性能媲美TI的IQmath和硬件FPU，强于C库的math和ARMDSP库，适用于M0和M3(2024-10-12)https://www.armbbs.cn/forum.php?mod=view......
  • CSP2024 前做题情况
    10.12开始写，每天做的题都在这里了。AT_arc058_b考虑组合数。对于从\((1,1)\)走到\((n,m)\)的方案数，显然是\(C_{(n-1+1)+(m-1+1)-2}^{(n-1+1)-1/(m-1+1)-1}\)。那么考虑枚举一个行\(i(1\lei\len-a)\)，我们需要从\((1,1)\)走到\((i,b)\)。这样能够使得我们的每一步都......
  • 2023杭电多校4
    2023杭电多校4C-SimpleSetProblem题目描述：一共T组输入，每组输入有K个集合，从K个集合中选取K个数，也就是每个集合选取一个数，问这些数字中的最大值减去这些数字中的最小值的最小的值。解题思路：利用双指针，对于每一个右端点，存一段至少包含所有集合的点各一个的区间，然后就......

赞助商

阅读排行

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

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

Copyright © 2020-2023 IPS99 版权所有 IPS99