首页 > 其他分享 >多校A层冲刺NOIP2024模拟赛02 & csp-s模拟9

多校A层冲刺NOIP2024模拟赛02 & csp-s模拟9

时间:2024-10-06 20:33:12浏览次数:8  
标签:02 cnt int ll 多校 100 sum 模拟

多校A层冲刺NOIP2024模拟赛02

四道题因为暑假被拉去当模拟赛 暑假集训CSP提高模拟22 了,遂直接把赛后代码交了上去,然后就被通知换题了。

原 \(100+100+100+20\) 被在 accoders NOI 上被卡成了 \(100+100+90+10\) ,更改 long longint 后达到了 \(100+100+100+30\) 。

\(T1\) P318. 法阵

\(T2\) P265. 连通块

\(T3\) P266. 军队

\(T4\) P267. 棋盘

csp-s模拟9

\(T1\) T1075. 邻面合并 \(0pts\)

  • 部分分
    • \(30 \%\) :打表加手摸。
      • 该代码 仅手摸了 \(n,m \le 3\) 的数据,且不保证正确性。
  • 正解
    • 观察到 \(\min \{ n,m \} \le 8\) ,考虑状压 \(DP\) 。

    • 具体地,以每一块的开头作为分割点,并记录作状态,总状态数为 \(2^{m}\) 。

      • 判断是否合法的一个重要标准是原矩阵中的 \(0\) 不可以是分割点,原矩阵的 \(1\) 若本身不是分割点则到前面最近的分割点直接不能有 \(0\) 。
    • 转移的时候枚举上一行的状态,计算达成这两行的分割方式需要新创建多少个块。较为简便的做法是拿本行块的总数减去与上一行分割方式相同的块数(可以直接合并的块),建议画图理解。

      • 图来自官方题解。

    • 时间复杂度为 \(O(nm2^{m})\) 。

      点击查看代码
      int a[120][10],f[110][1<<10],opt[110][10][1<<10];
      bool check(int hang,int s,int m)
      {
      	int last=0;
      	for(int i=0;i<=m-1;i++)
      	{
      		if(((s>>i)&1)&&a[hang][i+1]==0)
      		{
      			return false;
      		}
      	}
      	for(int i=0;i<=m-1;i++)
      	{
      		if((s>>i)&1)
      		{
      			last=1;
      		}
      		if(a[hang][i+1]==0)
      		{
      			last=0;
      		}
      		if(last==0&&a[hang][i+1]==1)
      		{
      			return false;
      		}
      	}
      	return true;
      }
      int work(int hang,int lie,int s)
      {
      	while(a[hang][lie+1]==1&&((s>>(lie-1+1))&1)==0)
      	{
      		lie++;
      	}
      	return lie;
      }
      int main()
      {
      	freopen("merging.in","r",stdin);
      	freopen("merging.out","w",stdout);
      	int n,m,ans=0x7f7f7f7f,sum,i,j,k,h;
      	cin>>n>>m;
      	for(i=1;i<=n;i++)
      	{
      		for(j=1;j<=m;j++)
      		{
      			cin>>a[i][j];
      		}
      	}
      	memset(f,0x3f,sizeof(f));
      	f[0][0]=0;
      	for(i=0;i<=(1<<m)-1;i++)
      	{
      		f[0][i]=0;
      	}
      	for(k=1;k<=n;k++)
      	{
      		for(i=0;i<=(1<<m)-1;i++)
      		{
      			if(check(k,i,m)==true)
      			{
      				for(j=1;j<=m;j++)
      				{
      					opt[k][j][i]=work(k,j,i);
      				}
      			}
      		}
      	}
      	for(k=1;k<=n;k++)
      	{
      		for(i=0;i<=(1<<m)-1;i++)
      		{
      			if(check(k,i,m)==true)
      			{
      				for(j=0;j<=(1<<m)-1;j++)
      				{
      					if(check(k-1,j,m)==true) 
      					{
      						sum=__builtin_popcount(i);
      						for(h=0;h<=m-1;h++)
      						{
      							if(((i>>h)&1)&&((j>>h)&1))
      							{
      								sum-=(opt[k][h+1][i]==opt[k-1][h+1][j]);
      							}
      						}
      						f[k][i]=min(f[k][i],f[k-1][j]+sum);
      					}
      				}
      			}
      		}
      	}
      	for(i=0;i<=(1<<m)-1;i++)
      	{
      		ans=min(ans,f[n][i]);
      	}
      	cout<<ans<<endl;
      	fclose(stdin);
      	fclose(stdout);
      	return 0;
      }
      

\(T2\) T1076. 光线追踪 \(0pts\)

  • 正解

\(T3\) T2186. 百鸽笼 \(0pts\)

  • 原题: UOJ 390. 【UNR #3】百鸽笼
  • 部分分
    • \(0pts\) :爆搜。

      点击查看代码
      const ll p=998244353;
      ll a[50],aa[50],pos[50],inv[50],f[50];
      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 len,ll n,ll sum,ll mul,ll cnt)
      {
      	if(len==sum)
      	{
      		for(ll i=1;i<=n;i++)
      		{
      			if(a[i]==1)
      			{
      				f[i]=(f[i]+mul)%p;
      				return;
      			}
      		}
      	}
      	else
      	{
      		for(ll i=1;i<=n;i++)
      		{
      			if(a[i]>=1)
      			{
      				a[i]--;
      				dfs(len+1,n,sum,mul*inv[cnt]%p,cnt-(a[i]==0));
      				a[i]++;
      			}
      		}
      	}
      }
      int main()
      {
      	freopen("c.in","r",stdin);
      	freopen("c.out","w",stdout);
      	ll n,sum=-1,i;
      	cin>>n;
      	for(i=1;i<=n;i++)
      	{
      		cin>>a[i];
      		sum+=a[i];
      		inv[i]=qpow(i,p-2,p);
      	}
      	dfs(0,n,sum,1,n);
      	for(i=1;i<=n;i++)
      	{
      		cout<<f[i]<<" ";
      	}
      	fclose(stdin);
      	fclose(stdout);
      	return 0;
      }
      
    • 详见 UOJ NOI Round #3 Day2 题解 百鸽笼

  • 详见 UOJ NOI Round #3 Day2 题解 百鸽笼

\(T4\) T2188. 滑稽树下你和我 \(0pts\)

  • 原题: UOJ 371. 【UR #17】滑稽树下你和我
  • 部分分
    • \(5 \%\) :输出 \(stx,sty\) 在图上的距离。

      点击查看代码
      struct node
      {
      	int nxt,to;
      }e[2010];
      int head[2010],du[2010],cnt=0;
      double x[2010],y[2010];
      void add(int u,int v)
      {
      	cnt++;
      	e[cnt].nxt=head[u];
      	e[cnt].to=v;
      	head[u]=cnt;
      }
      double work(double x1,double y1,double x2,double y2)
      { 
      	return sqrt((x2-x1)*(x2-x1)+(y2-y1)*(y2-y1));
      }
      int main()
      {
      	freopen("tree.in","r",stdin);
      	freopen("tree.out","w",stdout);
      	int n,u,v,stx,sty,i;
      	double ans=0x7f7f7f7f;
      	cin>>n>>stx>>sty;
      	for(i=1;i<=n;i++)
      	{
      		cin>>x[i]>>y[i];
      	}
      	for(i=1;i<=n-1;i++)
      	{
      		cin>>u>>v;
      		add(u,v);
      		add(v,u);
      		du[u]++;
      		du[v]++;
      	}
      	printf("%.8lf\n",work(x[stx],y[stx],x[sty],y[sty]));
      	fclose(stdin);
      	fclose(stdout);
      	return 0;
      }
      
    • 详见 UOJ Round #17 题解 滑稽树下你和我

  • 详见 UOJ Round #17 题解 滑稽树下你和我

总结

  • \(T1\) 不会写爆搜,打表程序出的结果都是手动判断的。
  • \(T2\) 做法假了,把矩形覆盖当成了点的覆盖,询问直接死掉,从一开始的暴力到 map 套动态开点线段树、珂朵莉树都 \(RE,MLE,TLE,WA\) 了。
  • \(T4\) 两点间距离公式炸 int 了,挂了 \(20pts\) 。

标签:02,cnt,int,ll,多校,100,sum,模拟
From: https://www.cnblogs.com/The-Shadow-Dragon/p/18449371

相关文章

  • [JOI 2024 Final] 建设工程 2
    [JOI2024Final]建设工程2题意给出一张图和\(S\),\(T\)。可在任意两点\(u,v(u<v)\)之间添加一条长度为\(L\)的边(只可添加一次)。求有多少种添加方案使得\(S\)到\(T\)的最短路长度\(\leK\)。思路首先,若\(S\)到\(T\)的最短路已经\(\leK\),答案为\(\frac{n\t......
  • E61 树形DP P8744 [蓝桥杯 2021 省 A] 左孩子右兄弟
    视频链接:  P8744[蓝桥杯2021省A]左孩子右兄弟-洛谷|计算机科学教育新生态(luogu.com.cn)//树形DPO(n)#include<bits/stdc++.h>usingnamespacestd;constintN=100005;intn,f[N],son[N];inthead[N],idx;structE{intv,ne;}e[N<<1];voidadd(intu......
  • 2024-2025-1 20241327 《计算机基础与程序设计》第2周学习总结
    作业信息|2024-2025-1-计算机基础与程序设计)||--|-|2024-2025-1计算机基础与程序设计第二周作业)||快速浏览一遍教材计算机科学概论(第七版),课本每章提出至少一个自己不懂的或最想解决的问题并在期末回答这些问题|作业正文|https://www.cnblogs.com/shr060414/p/18440575|教......
  • SMC 2024 游记
    (评分规则:25道五选一,满分125分,选对得5分,不选得1分,选错得0分)题目都没有什么难度啊,但是T3可以看一下:(回忆)两个标准骰子叠放在桌子上。已知:(1)两个骰子接触面上的点数相等,均为\(A\)。(2)\(9\)个可见的面(骰子之间接触面有两个,骰子与桌面的接触面有一个,这三个面不可见)的点数......
  • # 2024-2025-1 学号(2024130) 《计算机基础与程序设计》第二周学习总结
    作业信息|这个作业属于哪个课程|<[2024-2025-1-计算机基础与程序设计]>(https://edu.cnblogs.com/campus/besti/2024-2025-1-CFAP))||-- |-- ||这个作业要求在哪里|<[2024-2025-1计算机基础与程序设计第一周作业]>(https://edu.cnblogs.com/campus/besti/2024-2025-1-CFAP/home......
  • 20222412 2024-2025-1 《网络与系统攻防技术》实验一实验报告
    1.实验内容本周学习内容1.熟悉基本的汇编语言指令及其功能。2.掌握了栈与堆的概念及其在进程内存管理中的应用以及用户态与内核态的区别。3.熟练运用了Linux系统下的基本操作命令。实验任务1.手工修改可执行文件,改变程序执行流程,直接跳转到getShell函数。2.利用foo函数的Bo......
  • 『模拟赛』CSP-S模拟9
    Rank烂,知耻而后勇A.邻面合并签。注意到列数\(m\le8\),我们可以直接先搜出每一行可能的“分块”情况,然后转移时枚举上一行的所有状态和这一行的所有状态,根据拼接情况来更新答案,最终答案即为\(n\)行所有情况的最小值。赛时开始打的错解,错解如果第一行总数计算错了就能过......
  • 2024-2025-1 20241322《计算机基础与程序设计》第二周学习总结
    作业信息这个作业属于哪个课程https://edu.cnblogs.com/campus/besti/2024-2025-1-CFAP这个作业要求在哪里https://www.cnblogs.com/rocedu/p/9577842.html#WEEK02这个作业的目标<数字化信息安全自学教材计算机科学概论(第七版)第1章并完成云班课测试《C语言程序......
  • 2024-2025-1 20241407《计算机基础与程序设计》第二周学习总结
    这个作业属于哪个课程2024-2025-1-计算机基础与程序设计这个作业要求在哪里[2024-2025-1计算机基础与程序设计第二周作业](https://edu.cnblogs.com/campus/besti/2024-2025-1-CFAP/homework/13266)这个作业的目标数字化信息安全*自学教材:计算机科学概论(第七版)第1......
  • 复盘工作2024-10
    复盘工作-2024-10-061.关于对通过Arrays.asList()获得的list执行.removeAll会报错:需先创建支持修改的集合(例如ArrayList再removeAll)/***练习:关于对通过Arrays.asList()获得的list执行.removeAll会报错:需先创建支持修改的集合(例如ArrayList再removeAll)*/......