首页 > 其他分享 >HNOI2023

HNOI2023

时间:2024-03-09 22:44:05浏览次数:24  
标签:总分 测试点 int dfrac 然后 HNOI2023 性质

Day1

开把写了 A 的 \(k=0\),然后想 \(n=1\) 去了,想了大概一个半小时,就去开 BC 了。

看到 C 就把 C 弃了想 B,然后也是写了一点性质分。

事实证明没几个对的,爆搜还炸了。

写完之后继续想了一下 \(n=0\),然后写了个蜜汁二分,发现不对。

此时意识到了这个东西应该是一个单峰函数,然后并没有写三分,降智了。(好像有人三分过了?)

实际上需要解一个绝对值不等式的东西,考场上也并没有去推。

A

性质 B (\(k=0\)):

因为 \(k=0\),所以直接考虑前缀和。此时需要判一下整个序列和为 \(0\) 的情况,为 \(0\) 的话循环放多少次都可以。

对于不为 \(0\) 的,直接枚举循环若干次之后再放多少个,然后判断是否可行,取 \(\min\) 即可。

\(n=0\)

傻呗二分加一堆特判居然过了三个点,真神奇

总分:\(50\)

B

测试点 \(7,8\) (\(n \le 2\),\(m \le 1\),\(b_i \in \{1,2\}\),且只有一个 \(i\) 满足 \(b_i =1\))

\(n=1\) 直接贪就行。

先把小的放在 \(a_1\)。

(好像有个东西不是很好描述,贴个代码在这)

int f(int x){
	int num=0;
	for(int i=0;i<k;i++){
		int val=(1ll<<i);
		if((x&val)==0) num+=val;
	}
	return num;
}

然后若大的可加,答案就是 \(\min(a_1 \bigoplus f(a_1),a_2 + f(a_1))\)。这样可以使小的尽量大,大的也不会减小。

若小的可加,枚举每个二进制位,尝试进行操作。(即对小的加,大的异或)

然后如果小的变成更大的那个了,就当做大的可加的情况来做。

否则用现在的状态更新一下答案就是了。

如果两个都不可加,那就加上两个数都为 \(0\) 的二进制位就可以了。

(十分抽象)

爆搜挂了好像是因为把特判 if(n<=2) 写前面了。

总分:\(8\)

C

输出 \(n!\) 有 \(8\) 分,然后没看题没拿,傻呗了。

wsy 这题写了 \(16\) 分?

总分:\(0\)

Day1 总分:\(58\)

Day2

先扫了一遍三个题,首先判断 C 完全不可做,然后感觉 B 的性质分比较好写,就写了一个小时 B。

然后开了 A,先是写了性质 A,然后爆搜了一下。

想了一下 A,感觉是类似于分治的东西,推了一下发现在大样例就假了。

然后好像就写不出来了。

A

测试点 \(1 \sim 5\) (\(n<=4\))

直接 dfs 开哪些石像,然后贪心地走就好了。

特殊性质 A

首先需要尽可能地让 Bob 往左走,这样如果我能够开当前这个石像就肯定开,然后先递归处理左边;否则需要先递归处理右边。

然后也是跑一遍贪心算答案就可以了。

然后性质 B 应该是个树上背包,正解还真就是类似分治的东西,考场上应该是没有想到开启一个石像对于答案的影响。

总分:\(35\)

B

测试点 1

爆搜,但是太难写了,一直没写出来。

\(m=0\)

没有限制,直接输出 \(1\) 即可。

特殊性质 B

若 \(1\) 已经在第一个,就一定可以成功,概率为 \(\dfrac{1}{n}\);

若第一个不是 \(1\),则只要有一个分割点刚好在 \(1\) 左边的那个位置就可以成功。

大力算概率:首先,遇到这种情况的概率为 \(\dfrac{n-1}{n}\);前 \(i-1\) 个都不是 \(1\) 左边,且第 \(i\) 个是 \(1\) 左边的空位的概率为 \(\dfrac{n+i}{1} \times \prod\limits^{i-1}\limits_{j=1} \dfrac{n+i-1}{n+i}\)。全部加起来即可。

总分:\(20\)

C

不可做。

总分:\(0\)

Day2 总分:\(55\)

总分:\(50+8+0+35+20+0=113\)

中规中矩吧。

标签:总分,测试点,int,dfrac,然后,HNOI2023,性质
From: https://www.cnblogs.com/luqyou/p/18063526

相关文章

  • HNOI2023 游记
    Day???去中山集训回来了。Day0没啥心情做题,上午随便写了点板子,然后扫描线写了一个小时调不出来,感觉不是很好。下午听了下动员,听完之后心态确实好些了,虽然很久没做什么题,但是在考场上写满暴力不挂分似乎并不是很难达到的目标。晚上到考场旁边订了个酒店,稍微思考了一下明天的......