首页 > 其他分享 >2024.11.15 NOIP 模拟 - 模拟赛记录

2024.11.15 NOIP 模拟 - 模拟赛记录

时间:2024-11-15 17:08:49浏览次数:1  
标签:偏序 2024.11 15 第一个 int 后面 样例 三元组 模拟

image


返乡(home

不给大样例是怕我找规律出答案吗?但是我还是找到规律了。

题解说是结论题,但是这个结论即使观察小样例也很好猜(如果我是出题人就把样例打乱一下顺序)。

首先考虑只有二维偏序时的最优放置方法

首先第一个数是不能重复的,因为一旦重复,第二个数无论怎么选,都会构成偏序;第二个数同理,也不能重复。所以最多有 \((n+1)\) 个二元组。

那么我们将 \(0 \sim n\) 全部放上去,并且将第一个数排序,试试看能不能抵满上限。

因为不能构成偏序,所以对于第二个数,后面的不能比前面的更大(这样的话,因为后面的第一个数本来就比前面的第一个数更大,两个都更大就构成偏序了),所以后面的需要是从大到小的顺序排列。

当 \(N=4\) 时,一种最优放法如下:

(如果最左侧多了一列数字,请忽略,那是代码块行号,下同)

0 4
1 3
2 2
3 1
4 0

再来考虑三维偏序的情况:

如果第一个数相同,第二三个数可以转化成上面的二维偏序形式,放法与上面所述相同。

观察样例,第一个数为 \(0\) 有两个,\(1\) 有三个,\(2\) 有两个,所以我们先放 \(1\) 试试看:

1 0 2
1 1 1
1 2 0

放了 \(1\) 以后,对于第一个数小于 \(1\) 的,后面两个数的值域需要更大才能够不被 \(1\) 开头的三元组偏序,所以我们从 \(1\) 开始放(这个观察样例也很好发现吧)。

0 1 2
0 2 1
1 0 2
1 1 1
1 2 0

而第一个数大于 \(1\) 的三元组,后面数的值域应当更小才不会偏序 \(1\) 开头的三元组,我们只能放到 \(1\):

0 1 2
0 2 1
1 0 2
1 1 1
1 2 0
2 0 1
2 1 0

所以规律即为:从中间开始放数,前面的三元组后两个数的最小值逐渐增加,后面的三元组后两个数的最大值逐渐减小。

正确性严格证明不会,但是可以感性理解一下:第一个数递增或递减的时候,所可以构成的三元组数量每次都一定要减一的,把最开始三元组最多的那一个放在正中间可以让所减的值最小。

int n;
struct Triple{
	int x,y,z;
}ans[300000];
int tot=0;

int main()
{
	freopen("home.in","r",stdin);
	freopen("home.out","w",stdout);
	
	read(n);
	for(int i=0;i<=n>>1;i++)
	{
		int s=(n>>1)-i; //start point
		for(int j=s;j<=n;j++)
			ans[++tot]={i,j,s+n-j};
	}
	for(int i=(n>>1)+1;i<=n;i++)
	{
		int t=n-(i-(n>>1)); //end point
		for(int j=0;j<=t;j++)
			ans[++tot]={i,j,0+t-j};
	}
	write(tot,'\n');
	for(int i=1;i<=tot;i++)
		write(ans[i].x,' '),write(ans[i].y,' '),write(ans[i].z,'\n');
	return 0;
}

连接(connect

标签:偏序,2024.11,15,第一个,int,后面,样例,三元组,模拟
From: https://www.cnblogs.com/jerrycyx/p/18548252

相关文章

  • 学习日记-2024.11.12
    想使用xarm搭建一个通过视觉(yolo)进行抓取的系统.(仅供参考,自己复盘用,初学者)1,先使用xarm_ros(github)搭建自己想要的环境.准备使用xarm_gazebo中的xarm6_beside_table.launch文件(但是world选择xarm_camera_scene.aorld).我希望在xarm末端处有一个D435i摄像机.同时,在桌......
  • NOIP2024模拟赛#21 总结
    坐牢3h+。赛时开T1,发现好唐啊,10min切了。过了全部大样例。开T2,现在是8:10。?现在是8:27,我怎么把T2大样例全过了。是不是太水了。我只是胡了一个贪心啊。开T3,现在是8:30。草,T1加样例了,做法假了。先不管T1了,先去看T3。感觉保证每次操作后都会满足对于\(i......
  • 241115 noip 模拟赛
    省流:\(90+100+25+10\)。T1题意:给定一个长为\(n\)的排列,定义一次操作为选出排列中至多\(4\)个不同的数,将它们任意重排,求最少操作次数让这个排列单调递增。\(n\leq10^6\)。找出排列的所有置换环,设环长为\(t_1,t_2,t_3,\cdots,t_m\),则答案为:\[\sum_{i=1}^m\lflo......
  • NOIP模拟赛 #11
    A一个\(R\timesC\)的矩阵\(A\),有\(N\)个位置已知,第\(i\)个为\(A_{r_i,c_i}=a_i\)。求是否存在一种填写剩下数字的方案,满足每个数字都非负且对于任意\(i,j(1\lei\leR-1,1\lej\leC-1)\)都有\(A_{i,j}+A_{i+1,j+1}=A_{i,j+1}+A_{i+1,j}......
  • [2024.11.15]NOIP 模拟赛
    赛后的思路永远比赛时清晰。赛时T1玩了一会发现\(a_3\sima_7\)一定是相邻的,所以只需要考虑两个数字即可。答案显然有单调性,所以考虑先二分\(a_2\),再二分\(a_1\)。两个二分的思路都很简单,第二个二分用lower_bound即可。第一个的话其实就是模拟lower_bound内置,赛时调......
  • cmu15545笔记-Join算法(Join Algorithms)
    目录OverviewNestedLoopJoinNaïveBlockIndexSort-MergeJoinHashJoinSimpleHashJoinPartitionHashJoin总结Overview输出形式:早物化与晚物化(OLAP一般都是晚物化)代价分析:一般用IO次数计算(最终结果可能落盘,也可能不落盘,所以我们只计算输出结果之前的IO次数)。Join左边称为......
  • 1159. 市场分析 II
    目录题目链接(无VIP请直接看下面的需求)题目和题目代码1.读题(建议使用这种表结构和数据对比看阅读)2.答案代码以及图表解释题目链接(无VIP请直接看下面的需求)链接:15分钟没思路建议直接看答案题目和题目代码表:Users+----------------+---------+|Colu......
  • 11.15
    实验二:逻辑回归算法实现与测试 一、实验目的深入理解对数几率回归(即逻辑回归的)的算法原理,能够使用Python语言实现对数几率回归的训练与测试,并且使用五折交叉验证算法进行模型训练与评估。 二、实验内容(1)从scikit-learn库中加载iris数据集,使用留出法留出1/3的样......
  • Linux系统编译QT5.15.0及串口问题
    编译流程:1>下载QT源码源码的下载可以到qt的官网http://www.qt.io/download/ 2>解压tarxvfqt-everywhere-src-x.x.x.tar.gz注意后缀和解压方式3>配置 ./configure进行环境配制。4>编译执行make编译,时间长,大概在三四个小时左右。5>安装sudomakeinstall需要5分钟......
  • 11/15
    #include<stdio.h>intmain(){ intN,i,j,M,count; unsignedintarr[1000],times[10]={0},maxvalue[10]; scanf("%d",&N); for(i=0;i<N;i++){ scanf("%d",&arr[i]); }// times[10]={0}; for(i=0;i<N;i++){ ......